Paper 2018/1224
Further Lower Bounds for StructurePreserving Signatures in Asymmetric Bilinear Groups
Essam Ghadafi
Abstract
StructurePreserving 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 DiffieHellman (DH) pairs, it is possible to circumvent the known lower bounds in the Type3 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 attributebased signatures and direct anonymous attestation. Only the cases of signing a single DH pair or a DH pair and a vector from $\Z_p$ 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. An open question is whether such an improved lower bound also applies to signing a vector of $\ell > 1$ messages. We answer this question negatively for schemes existentially unforgeable under an adaptive chosenmessage attack (EUFCMA) whereas we answer it positively for schemes existentially unforgeable under a randommessage attack (EUFRMA) and those which are existentially unforgeable under a combined chosenrandommessage attack (EUFCMARMA). 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 chosenmessage attack (sEUFCMA) schemes with 2element signatures exist. We answer this question negatively, proving it is impossible to construct sEUFCMA schemes with 2element signatures even if the signature consists of elements from both source groups. On the other hand, we prove that sEUFRMA and sEUFCMARMA schemes with 2element (unilateral) signatures are possible by giving constructions for those notions. Among other things, our findings show a gap between randommessage/combined chosenrandommessage security and chosenmessage security in this setting.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. AFRICACRYPT 2019
 Contact author(s)
 essam ghadafi @ gmail com
 History
 20190510: revised
 20181230: received
 See all versions
 Short URL
 https://ia.cr/2018/1224
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/1224, author = {Essam Ghadafi}, title = {Further Lower Bounds for StructurePreserving Signatures in Asymmetric Bilinear Groups}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/1224}, year = {2018}, url = {https://eprint.iacr.org/2018/1224} }