[Resource Topic] 2005/035: An Efficient CDH-based Signature Scheme With a Tight Security Reduction

Welcome to the resource topic for 2005/035

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

Authors: 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.

ePrint: https://eprint.iacr.org/2005/035

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .