On Tight Security Proofs for Schnorr Signatures
Nils Fleischhacker, Tibor Jager, Dominique Schröder · 2014
The Schnorr signature scheme is the most efficient signature scheme based on the discrete loga-rithm problem and a long line of research investigates the existence of a tight security reduction for this scheme. Almost all recent works present lower tightness bounds and most recently Seurin (Euro-crypt 2012) showed that under certain assumptions the non-tight security proof for Schnorr signatures by Pointcheval and Stern (Eurocrypt 1996) is essentially optimal. All previous works in this direction rule out tight reductions from the (one-more) discrete logarithm problem. In this paper we introduce a new meta-reduction technique, which shows lower bounds for the large and very natural class of generic reductions. A generic reduction is independent of a particular representation of group elements and most reductions in state-of-the-art security proofs have this desirable property. Our approach shows uncondi-tionally that there is no tight generic reduction from any natural computational problem Π defined over algebraic groups (including even interactive problems) to breaking Schnorr signatures, unless solving Π is easy.