Paper 2005/035

An Efficient CDH-based Signature Scheme With a Tight Security Reduction

Benoit Chevallier-Mames


At Eurocrypt'03, Goh and Jarecki showed that, contrary to other signature schemes in the discrete-log setting, the EDL signature scheme has a tight security reduction, namely to the Computational Diffie-Hellman (CDH) problem, in the Random Oracle (RO) model. They also remarked that EDL can be turned into an off-line/on-line signature scheme using the technique of Shamir and Tauman, based on chameleon hash functions. 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.

Note: (Monday, January 23, 2006): Appendix C is added, to use shorter hash outputs and then save some bits in the signature length

Available format(s)
Publication info
Published elsewhere. Full version of Crypto'05 paper
signature schemesdiscrete logarithm problemDiffie-Hellman problemEDL
Contact author(s)
benoit chevallier-mames @ gemplus com
2006-01-23: last of 4 revisions
2005-02-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benoit Chevallier-Mames},
      title = {An Efficient CDH-based Signature Scheme With a Tight Security Reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2005/035},
      year = {2005},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.