On Tight Security Proofs for Schnorr Signatures

Journal article

Publication Details

Author(s): Fleischhacker N, Jager T, Schröder D
Journal: Journal of Cryptology
Publication year: 2019
Volume: 32
Journal issue: 2
Pages range: 566-599
ISSN: 0933-2790


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 in the random oracle model. 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 in the random oracle by Pointcheval and Stern EUROCRYPT'96 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. Most reductions in state-of-the-art security proofs have this property. It is desirable, because then the reduction applies generically to any concrete instantiation of the group. Our approach shows unconditionally that there is no tight generic reduction from any natural non-interactive computational problem defined over algebraic groups to breaking Schnorr signatures, unless solving is easy. In an additional application of the new meta-reduction technique, we also unconditionally rule out any (even non-tight) generic reduction from natural non-interactive computational problems defined over algebraic groups to breaking Schnorr signatures in the non-programmable random oracle model.

FAU Authors / FAU Editors

Schröder, Dominique Prof. Dr.
Lehrstuhl für Informatik 13 (Angewandte Kryptographie)

External institutions with authors

Ruhr-Universität Bochum (RUB)
Universität Paderborn

How to cite

Fleischhacker, N., Jager, T., & Schröder, D. (2019). On Tight Security Proofs for Schnorr Signatures. Journal of Cryptology, 32(2), 566-599. https://dx.doi.org/10.1007/s00145-019-09311-5

Fleischhacker, Nils, Tibor Jager, and Dominique Schröder. "On Tight Security Proofs for Schnorr Signatures." Journal of Cryptology 32.2 (2019): 566-599.


Last updated on 2019-11-04 at 13:23