Issuing CL-Signatures on Speed: Signing with a Constant Number of Exponentiations
Thomas Groß · School of Computing Science Technical Report Series · 2014
In SCN 2002, Jan Camenisch and Anna Lysyanskaya have proposed the Strong RSA version of their Camenisch-Lysyanskaya (CL) signature scheme [8], a fundamental cryptographic building block to compute a digital signature on hidden committed messages and allow zero-knowledge proofs of knowledge on them. Ever since, the CL signature scheme has been adopted for different applications, such as anonymous credential systems, Direct Anonymous Attestation, and different prototypes for smart cards. Unfortunately, CL signatures place a significant workload on the issuer, as the signature generation requires a number of modular exponentiations linear in the number of message blocks signed, which, in turn, constitutes a significant obstacle for the broad adoption of the scheme. In this work, we propose a variant of the Strong RSA CL-signature scheme, which computes the signature with a constant number of modular exponentiations, that is, independent of the number of message blocks involved. In fact, we show that issuer can compute a commitment on an arbitrary number of message blocks with one modular exponentiation and complete the signature generation with five modular exponentiations. All the issuer needs to do is store n group elements readily available from the standard key generation with its private key and use this knowledge in the signature generation. The output of the optimized CL-issuing is fully wire-format compatible to the standard CL-issuing. We provide a comprehensive performance analysis of the optimized issuing approach, which shows that signatures with strong security parameters and even with tens of thousands of message blocks can be computed in the order of one hundred milliseconds. © 2015 Newcastle University Printed and published by Newcastle University, Computing Science, Claremont Tower, Claremont Road, Newcastle upon Tyne, NE1 7RU, England. Bibliographical details Issuing CL-Signatures on Speed: Signing with a Constant Number of Exponentiations Thomas Gros School of Computing Science, Newcastle University, UK