Short Signatures Without Random Oracles

By Dan Boneh and Xavier Boyen.

In Advances in Cryptology (EUROCRYPT 2004), volume 3027 of Lecture Notes in Computer Science, pages 56-73. Springer, 2004.


We describe a short signature scheme which is existentially unforgeable under a chosen message attack without using random oracles. The security of our scheme depends on a new complexity assumption we call the Strong Diffie-Hellman assumption. This assumption has similar properties to the Strong RSA assumption, hence the name. Strong RSA was previously used to construct signature schemes without random oracles. However, signatures generated by our scheme are much shorter and simpler than signatures from schemes based on Strong RSA. Furthermore, our scheme provides a limited form of message recovery.


- published paper (accessible from the publisher) © IACR
- old expanded version (PS) (PDF) (see below for an updated full journal version)
- presentation slides (HTML)


Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups


  author = {Dan Boneh and Xavier Boyen},
  title = {Short Signatures Without Random Oracles},
  booktitle = {Advances in Cryptology---EUROCRYPT 2004},
  series = {Lecture Notes in Computer Science},
  volume = {3027},
  pages = {56--73},
  publisher = {Berlin: Springer-Verlag},
  year = {2004},
  note = {Available at \url{}}

Unless indicated otherwise, these documents are Copyright © Xavier Boyen; all rights reserved in all countries.
Back to Xavier's homepage