Paper 2004/171

Short Signatures Without Random Oracles

Dan Boneh and Xavier Boyen

Abstract

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 {\em 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.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. An extended abstract appears in EUROCRYPT 2004.
Keywords
digital signaturesprovable security
Contact author(s)
eprint @ boyen org
History
2004-07-21: revised
2004-07-21: received
See all versions
Short URL
https://ia.cr/2004/171
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2004/171,
      author = {Dan Boneh and Xavier Boyen},
      title = {Short Signatures Without Random Oracles},
      howpublished = {Cryptology ePrint Archive, Paper 2004/171},
      year = {2004},
      note = {\url{https://eprint.iacr.org/2004/171}},
      url = {https://eprint.iacr.org/2004/171}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.