How low can you go? short structure-preserving signatures for Diffie-Hellman vectors.

*(English)*Zbl 1397.94065
O’Neill, Máire (ed.), Cryptography and coding. 16th IMA international conference, IMACC 2017, Oxford, UK, December 12–14, 2017. Proceedings. Cham: Springer (ISBN 978-3-319-71044-0/pbk; 978-3-319-71045-7/ebook). Lecture Notes in Computer Science 10655, 185-204 (2017).

Summary: Structure-preserving signatures (SPSs) are an important tool for the design of modular cryptographic protocols. It has been proven that such schemes in the most efficient Type-3 bilinear group setting 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). Very recently, the author [More efficient structure-preserving signatures – or: bypassing the Type-III lower bounds. In: ESORICS 2017, Lect. Notes Comput. Sci. 10493, 43–61 (2017; doi:10.1007/978-3-319-66399-9_3] showed that by restricting the message space to the set of Diffie-Hellman pairs (which does not hinder applicability of the schemes), some of the existing lower bounds for the single message case can be circumvented. However, the case of signing multiple messages, which is required for many applications, was left as an open problem since the techniques used for signing single messages do not seem to lend themselves to the multi-message setting. In this work we investigate this setting and answer the question in the affirmative. We construct schemes that sign vectors of messages and which yield shorter signatures than optimal schemes for vectors of unilateral messages. More precisely, we construct 2 fully randomizable schemes that sign vectors of Diffie-Hellman pairs yielding signatures consisting of only 2 elements regardless of the size of the vector signed. We also construct a unilateral scheme that signs a pair of messages yielding signatures consisting of 3 elements from the shorter base group. All of our schemes require a single PPE for verification (not counting the cost of verifying the well-formedness of the messages). Thus, all of our schemes compare favourably to all existing schemes with respect to signature size and verification overhead. Even when considering single messages, our first 2 schemes compare favourably to the best existing schemes in many aspects including the verification overhead and the key size.

For the entire collection see [Zbl 1380.94005].

For the entire collection see [Zbl 1380.94005].

##### MSC:

94A60 | Cryptography |