Paper 2015/525

Short Randomizable Signatures

David Pointcheval and Olivier Sanders


Digital signature is a fundamental primitive with numerous applications. Following the development of pairing-based cryptography, several taking advantage of this setting have been proposed. Among them, the Camenisch-Lysyanskaya (CL) signature scheme is one of the most flexible and has been used as a building block for many other protocols. Unfortunately, this scheme suffers from a linear size in the number of messages to be signed which limits its use in many situations. In this paper, we propose a new signature scheme with the same features as CL-signatures but without the linear-size drawback: our signature consists of only two elements, whatever the message length, and our algorithms are more efficient. This construction takes advantage of using type 3 pairings, that are already widely used for security and efficiency reasons. We prove the security of our scheme without random oracles but in the generic group model. Finally, we show that protocols using CL-signatures can easily be instantiated with ours, leading to much more efficient constructions.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. CT-RSA 2016
Digital SignatureRandomizableBilinear Groups
Contact author(s)
oliviersanders @ live fr
2016-10-08: last of 2 revisions
2015-06-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {David Pointcheval and Olivier Sanders},
      title = {Short Randomizable Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2015/525},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.