An Efficient CDH-based Signature Scheme With a Tight Security Reduction.
Benoît Chevallier-Mames · 2005
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 e±cient 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 % im-provement on the state-of-the-art discrete-log based schemes, with the same security level. This represents to date the most e±cient scheme of any signature scheme with a tight security reduction in the discrete-log setting.