Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log
Damien Vergnaud ( Laboratoire LMNO - Université de Caen (France) )
Thursday 02 February 2006, 14.00 sharp (s.t.), b-it 2.1 (Seminar room)
Contents
We provide evidence that the unforgeability of several discrete-log based signatures like Schnorr signatures cannot be equivalent to the discrete log problem in the standard model. This contradicts in nature well-known proofs standing in weakened proof methodologies, in particular proofs employing various formulations of the Forking Lemma in the random oracle Model. Our impossibility proofs apply to many discrete-log-based signatures like ElGamal signatures and their extensions, DSA, ECDSA and KCDSA as well as standard generalizations of these, and even RSA-based signatures like GQ.
All known reductions attesting the unforgeability of Fiat-Shamir transformed signatures in the random oracle model lead to a loss factor close to q_h in terms of execution time or success probability (q_h denotes the number of oracle queries). There exists no proof that this loss factor is necessary. We prove, however, that any random-oracle-based reduction from computing the discrete logarithm to forging Schnorr signatures must lose at least a factor close to the square root of q_h. We further conjecture that the 1/q_h loss is optimal. In any case, our results show that a proof of equivalence in the ROM (if algebraic) will *never be tight*. We believe our work sheds a new perspective as to why no efficient proof of equivalence to the discrete log problem has ever been found for Schnorr signatures despite considerable research efforts.
We stress that our work sheds more light on the provable (in)security of popular signature schemes but does not explicitly lead to actual attacks on these.
(Joint work with Pascal Paillier from Advanced Cryptographic Services, Gemplus Card International.)