Paper 2013/418

Unconditional Tightness Bounds for Generic Reductions: The Exact Security of Schnorr Signatures, Revisited

Nils Fleischhacker and Tibor Jager and Dominique Schröder

Abstract

A long line of research investigates the existence of tight security reductions for the Schnorr signature scheme. Most of these works presented lower tightness bounds, most recently Seurin (Eurocrypt 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 share the same restrictions: The results hold only under the interactive one-more discrete logarithm assumption, they only consider algebraic reductions, and they only rule out tight reductions from the (one-more) discrete logarithm problem. The existence of a tight reduction from weaker computational problems, like CDH or DDH, remained open. In this paper we introduce a new meta-reduction technique, which allows to prove lower bounds for the large and very natural class of generic reductions. A generic reduction is independent of a particular representation of group elements. Most reductions in state-of-the-art security proofs have this desirable property. This new approach allows to show unconditionally that there is no tight generic reduction from any natural computational problem \Pi defined over algebraic groups (including even interactive problems) to breaking Schnorr signatures, unless solving \Pi is easy.

Note: Preliminary version.