Cryptology ePrint Archive: Report 2013/418

On Tight Security Proofs for Schnorr Signatures

Nils Fleischhacker and Tibor Jager and Dominique Schröder

Abstract: The Schnorr signature scheme is the most efficient signature scheme based on the discrete logarithm 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 (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 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 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.

Category / Keywords: Schnorr signatures, black-box reductions, generic reductions, algebraic reductions, tightness.

Date: received 25 Jun 2013, last revised 7 Apr 2014

Contact author: tibor jager at rub de

Available format(s): PDF | BibTeX Citation

Note: Preliminary version.

Version: 20140407:075410 (All versions of this report)

Short URL: ia.cr/2013/418

Discussion forum: Show discussion | Start new discussion