Skip to main content

Research Repository

Advanced Search

Further lower bounds for structure-preserving signatures in asymmetric bilinear groups

Ghadafi, Essam

Authors

Essam Ghadafi Essam.Ghadafi@uwe.ac.uk
Senior Lecturer in Computer Science



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.

Citation

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

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
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

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



Downloadable Citations