Paper 2016/255
More Efficient StructurePreserving Signatures  Or: Bypassing the TypeIII Lower Bounds
Essam Ghadafi
Abstract
Structurepreserving signatures are an important cryptographic primitive that is useful for the design of modular cryptographic protocols. It has been proven that structurepreserving signatures (in the most efficient TypeIII bilinear group setting) have a lower bound of 3 group elements in the signature (which must include elements from both source groups) and require at least 2 pairingproduct equations for verification. In this paper, we show that such lower bounds can be circumvented. In particular, we define the notion of Unilateral StructurePreserving Signatures on DiffieHellman pairs (USPSDH) which are structurepreserving signatures in the efficient TypeIII bilinear group setting with the message space being the set of DiffieHellman pairs, in the terminology of Abe et al. (Crypto 2010). The signatures in these schemes are elements of one of the source groups, i.e. unilateral, whereas the verification key elements' are from the other source group. We construct a number of new structurepreserving signature schemes which bypass the TypeIII lower bounds and hence they are much more efficient than all existing structurepreserving signature schemes. We also prove optimality of our constructions by proving lower bounds and giving some impossibility results. Our contribution can be summarized as follows: \begin{itemize} \item We construct two optimal randomizable CMAsecure schemes with signatures consisting of only 2 group elements from the first short source group and therefore our signatures are at least half the size of the best existing structurepreserving scheme for unilateral messages in the (most efficient) TypeIII setting. Verifying signatures in our schemes requires, besides checking the wellformedness of the message, the evaluation of a single PairingProduct Equation (PPE) and requires a fewer pairing evaluations than all existing structurepreserving signature schemes in the TypeIII setting. Our first scheme has a feature that permits controlled randomizability (combined unforgeability) where the signer can restrict some messages such that signatures on those cannot be rerandomized which might be useful for some applications. \item We construct optimal strongly unforgeable CMAsecure onetime schemes with signatures consisting of 1 group element, and which can also sign a vector of messages while maintaining the same signature size. \item We give a onetime strongly unforgeable CMAsecure structurepreserving scheme that signs unilateral messages, i.e. messages in one of the source groups, whose efficiency matches the best existing optimal onetime scheme in every respect. \item We investigate some lower bounds and prove some impossibility results regarding this variant of structurepreserving signatures. \item We give an optimal (with signatures consisting of 2 group elements and verification requiring 1 pairingproduct equation) fully randomizable CMAsecure partially structurepreserving scheme that simultaneously signs a DiffieHellman pair and a vector in $\Z^k_p$. \item As an example application of one of our schemes, we obtain efficient instantiations of randomizable weakly blind signatures which do not rely on random oracles. The latter is a building block that is used, for instance, in constructing Direct Anonymous Attestation (DAA) protocols, which are protocols deployed in practice. \end{itemize} Our results offer value along two fronts: On the practical side, our constructions are more efficient than existing ones and thus could lead to more efficient instantiations of many cryptographic protocols. On the theoretical side, our results serve as a proof that many of the lower bounds for the TypeIII setting can be circumvented.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. Major revision. ESORICS 2017
 Keywords
 StructurePreservingDigital SignaturesTypeIII Bilinear GroupsLower Bounds
 Contact author(s)
 essam_gha @ yahoo com
 History
 20170801: revised
 20160308: received
 See all versions
 Short URL
 https://ia.cr/2016/255
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/255, author = {Essam Ghadafi}, title = {More Efficient StructurePreserving Signatures  Or: Bypassing the Type{III} Lower Bounds}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/255}, year = {2016}, url = {https://eprint.iacr.org/2016/255} }