Improved Bounds on Security Reductions for Discrete Log Based Signatures
Discrete Log (DL) based signatures, such as those proposed by Schnorr, are among the simplest and the most efficient signature schemes. Despite considerable research efforts, no efficient reduction from the discrete log problem to forging a discrete log based signature (e.g. Schnorr) is currently known. In fact, negative results are known. Paillier and Vergnaud show that the forgeability of several discrete log based signatures cannot be equivalent to solving the discrete log problem in the standard model, assuming the so-called one-more discrete log assumption and algebraic reductions.