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.
Original Publication (with major differences): IACR-ASIACRYPT-2014
Date: received 25 Jun 2013, last revised 3 Jun 2016
Contact author: tibor jager at rub de
Available format(s): PDF | BibTeX Citation
Note: An error was pointed out in the original publication.
Version: 20160603:144432 (All versions of this report)
Short URL: ia.cr/2013/418
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]