In this paper, we propose a new signature scheme that also has a tight security reduction to CDH but whose resulting signatures are smaller than EDL signatures. Further, similarly to the Schnorr signature scheme (but contrary to EDL), our signature is naturally efficient on-line: no additional trick is needed for the off-line phase and the verification process is unchanged.
For example, in elliptic curve groups, our scheme results in a 25% improvement on the state-of-the-art discrete-log based schemes, with the same security level. This represents to date the most efficient scheme of any signature scheme with a tight security reduction in the discrete-log setting.
Category / Keywords: signature schemes, discrete logarithm problem, Diffie-Hellman problem, EDL Publication Info: Full version of Crypto'05 paper Date: received 10 Feb 2005, last revised 23 Jan 2006 Contact author: benoit chevallier-mames at gemplus com Available formats: Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation Note: (Monday, January 23, 2006): Appendix C is added, to use shorter hash outputs and then save some bits in the signature length Version: 20060123:173212 (All versions of this report) Discussion forum: Show discussion | Start new discussion