Cryptology ePrint Archive: Report 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.

Category / Keywords: public-key cryptography / digital signatures, provable security

Publication Info: An extended abstract appears in EUROCRYPT 2004.

Date: received 20 Jul 2004, last revised 21 Jul 2004

Contact author: eprint at boyen org

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20040721:183744 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]