More efficient structure-preserving signatures - or: Bypassing the type-III lower bounds

Ghadafi, Essam

Abstract

© 2017, Springer International Publishing AG. Structure-Preserving Signatures (SPSs) are an important cryptographic primitive that is useful for the design of modular cryptographic protocols. It has be shown that in the most efficient Type-III bilinear group setting such schemes have a lower bound of 3-element signatures, which must include elements from both base groups, and a verification overhead of at least 2 Pairing-Product Equations (PPEs). In this work we show how to circumvent these lower bounds by constructing more efficient schemes than existing optimal schemes. Towards this end, we first formally define the notion of Unilateral Structure-Preserving Signatures on Diffie-Hellman pairs (USPSDH) as Type-III SPS schemes with messages being Diffie-Hellman pairs and signatures being elements of one of the base groups, i.e. unilateral. We construct a number of new fully randomizable SPS schemes that are existentially unforgeable against adaptive chosen-message attacks, and which yield signatures consisting of only 2 elements from the shorter base group, and which require only a single PPE for verification (not counting the cost of verifying the well-formedness of the message). Thus, our signatures are at least half the size of the best existing scheme for unilateral messages. Our first scheme has a feature that permits controlled randomizability which might be of independent interest. We also give various optimal strongly unforgeable one-time schemes with 1-element signatures, including a new scheme for unilateral messages that matches the best existing scheme in every respect. We prove optimality of our constructions by proving different lower bounds and giving some impossibility results. We also show how to extend our schemes to sign a vector of messages. Finally, we highlight how our schemes yield more efficient instantiations of various cryptographic protocols, including variants of attribute-based signatures and direct anonymous attestation, which is a protocol deployed in practice. Our results offer value along two fronts: On the theoretical side, our results serve as a workaround to bypass existing lower bounds. On the practical side, our constructions could lead to more efficient instantiations of various cryptographic protocols.

• Presentation Conference Type: Conference Paper (published)
• Conference Name: 22nd European Symposium on Research in Computer Security
• Start Date: Sep 11, 2017
• End Date: Sep 15, 2017
• Acceptance Date: Jul 4, 2017
• Online Publication Date: Aug 12, 2017
• Publication Date: Nov 1, 2017
• Publicly Available Date: Jun 7, 2019
• Pages: 43-61
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• ISBN: 9783319663982
• DOI: https://doi.org/10.1007/978-3-319-66399-9_3
• Keywords: digital signatures, structure-preserving signatures, controlled randomizability, lower bounds
• Public URL: https://uwe-repository.worktribe.com/output/879177
• Publisher URL: https://doi.org/10.1007/978-3-319-66399-9_3