Essam Ghadafi Essam.Ghadafi@uwe.ac.uk
Senior Lecturer in Computer Science
Further lower bounds for structure-preserving signatures in asymmetric bilinear groups
Ghadafi, Essam
Authors
Contributors
Johannes Buchmann
Editor
Nitaj Abderrahmane
Editor
Rachidi Tajjeeddine
Editor
Abstract
Structure-Preserving Signatures (SPSs) are a useful tool for the design of modular cryptographic protocols. Recent series of works have shown that by limiting the message space of those schemes to the set of Diffie-Hellman (DH) pairs, it is possible to circumvent the known lower bounds in the Type-3 bilinear group setting thus obtaining the shortest signatures consisting of only 2 elements from the shorter source group. It has been shown that such a variant yields efficiency gains for some cryptographic constructions, including attribute-based signatures and direct anonymous attestation. Only the cases of signing a single DH pair or a DH pair and a vector from \Zp have been considered. Signing a vector of group elements is required for various applications of SPSs, especially if the aim is to forgo relying on heuristic assumptions. Example applications where it is required to sign a vector of group elements include group, attribute-based and proxy signatures, and k-times anonymous authentication.
An open question is whether such an improved lower bound also applies to signing a vector of ℓ>1 messages. We answer this question negatively for schemes existentially unforgeable under an adaptive chosen-message attack (EUF-CMA) whereas we answer it positively for schemes existentially unforgeable under a random-message attack (EUF-RMA) and those which are existentially unforgeable under a combined chosen-random-message attack (EUF-CMA-RMA). The latter notion is a leeway between the two former notions where it allows the adversary to adaptively choose part of the message to be signed whereas the remaining part of the message is chosen uniformly at random by the signer.
Another open question is whether strongly existentially unforgeable under an adaptive chosen-message attack (sEUF-CMA) schemes with 2-element signatures exist. We answer this question negatively, proving it is impossible to construct sEUF-CMA schemes with 2-element signatures even if the signature consists of elements from both source groups. On the other hand, we prove that sEUF-RMA and sEUF-CMA-RMA schemes with 2-element (unilateral) signatures are possible by giving constructions for those notions.
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 11th International Conference on Cryptology in Africa |
Start Date | Jul 9, 2019 |
End Date | Jul 11, 2019 |
Acceptance Date | Jul 28, 2019 |
Publication Date | Sep 1, 2019 |
Deposit Date | May 13, 2019 |
Publicly Available Date | Sep 2, 2020 |
Journal | N/A |
Peer Reviewed | Peer Reviewed |
Book Title | 11th International Conference on Cryptology, AFRICACRYPT 2019 |
ISBN | 978-3-030-23695-3 |
DOI | https://doi.org/10.1007/978-3-030-23696-0 |
Public URL | https://uwe-repository.worktribe.com/output/845909 |
Contract Date | May 13, 2019 |
Files
Main.pdf
(387 Kb)
PDF
Licence
http://www.rioxx.net/licenses/all-rights-reserved
Copyright Statement
Copyright Springer 2019. This is the authors accepted manuscript of a conference item appearing in Ghadafi, E. (2019). Further lower bounds for structure-preserving signatures in asymmetric bilinear groups. In R. Tajjeeddine, N. Abderrahmane, & J. Buchmann (Eds.), 11th International Conference on Cryptology, AFRICACRYPT 2019https://doi.org/10.1007/978-3-030-23696-0
You might also like
Attribute-based signatures with user-controlled linkability
(2014)
Presentation / Conference Contribution
Decentralized traceable attribute-based signatures
(2014)
Presentation / Conference Contribution
Stronger security notions for decentralized traceable attribute-based signatures and more efficient constructions
(2015)
Presentation / Conference Contribution
Efficient Distributed tag-based encryption and its application to group signatures with efficient distributed traceability
(2015)
Presentation / Conference Contribution
How low can you go? Short structure-preserving signatures for Diffie-Hellman vectors
(-0001)
Book Chapter
Downloadable Citations
About UWE Bristol Research Repository
Administrator e-mail: repository@uwe.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search