nach oben

Journal of Cryptology

Erschienen in:

06.02.2019

On Tight Security Proofs for Schnorr Signatures

verfasst von: Nils Fleischhacker, Tibor Jager, Dominique Schröder

Erschienen in: Journal of Cryptology | Ausgabe 2/2019

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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 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 \(\Pi \) defined over algebraic groups to breaking Schnorr signatures, unless solving \(\Pi \) 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.

Vorheriger Artikel Cryptanalysis of the CLT13 Multilinear Map

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Usually even a polynomially bounded increase/loss is considered as significant, if the polynomial may be large. An increase/loss by a small constant factor is not considered as significant.

Such a group \({{\hat{{\mathbb {G}}}}}\) can trivially be obtained for any group \({\mathbb {G}}\), for instance by modifying the encoding by prepending a suitable fixed string to each group element, and changing the group law accordingly.

Recall that the same encoding may occur multiple times in \({\mathcal {L}}^E\).

Note that GetIdxmay receive only encodings \(e_1,\ldots ,e_w\) which are already contained in \({\mathcal {L}}^E\), as otherwise the behavior of \(\textsc {GetIdx}\) is undefined. We will make sure that this is always the case.

M. Abdalla, M. Bellare, P. Rogaway, The oracle Diffie–Hellman assumptions and an analysis of DHIES, in David Naccache, editor, Topics in Cryptology—CT-RSA 2001, Volume 2020 of Lecture Notes in Computer Science, San Francisco, CA, USA (Springer, Heidelberg, 2001), pp. 143–158

M. Bellare, C. Namprempre, D. Pointcheval, M. Semanko. The one-more-RSA-inversion problems and the security of Chaum’s blind signature scheme. J. Cryptol. 16(3), 185–215 (2003)MathSciNetCrossRefMATH

M. Bellare, P. Rogaway. Random oracles are practical: a paradigm for designing efficient protocols, in V. Ashby, editor, ACM CCS 93: 1st Conference on Computer and Communications Security, Fairfax, Virginia, USA (ACM Press, London, 1993), pp 62–73

M. Bellare, P. Rogaway. The exact security of digital signatures: how to sign with RSA and Rabin, in Ueli M. Maurer, editor, Advances in Cryptology—EUROCRYPT’96, Volume 1070 of Lecture Notes in Computer Science, Saragossa, Spain (Springer, Heidelberg, 1996), pp. 399–416

D.J. Bernstein. Proving tight security for Rabin–Williams signatures, in Nigel P. Smart, editor, Advances in Cryptology—EUROCRYPT 2008, Volume 4965 of Lecture Notes in Computer Science, Istanbul, Turkey (Springer, Heidelberg, 2008), pp. 70–87

D.J. Bernstein. Multi-user schnorr security, revisited. Cryptology ePrint Archive, Report 2015/996. https://eprint.iacr.org/2015/996 (2015)

D. Boneh, X. Boyen, Secure identity based encryption without random oracles, in Matthew Franklin, editor, Advances in Cryptology—CRYPTO 2004, Volume 3152 of Lecture Notes in Computer Science, Santa Barbara, CA, USA (Springer, Heidelberg, 2004), pp. 443–459

J.-S. Coron, On the exact security of full domain hash, in Mihir Bellare, editor, Advances in Cryptology—CRYPTO 2000, Volume 1880 of Lecture Notes in Computer Science, Santa Barbara, CA, USA (Springer, Heidelberg, 2000), pp. 229–235

J.-S. Coron, Optimal security proofs for PSS and other signature schemes, in Lars R. Knudsen, editor, Advances in Cryptology—EUROCRYPT 2002, Volume 2332 of Lecture Notes in Computer Science, Amsterdam, The Netherlands (Springer, Heidelberg, 2002), pp.272–287

10.

Y. Dodis, I. Haitner, A. Tentes, On the instantiability of hash-and-sign RSA signatures, in Ronald Cramer, editor, TCC 2012: 9th Theory of Cryptography Conference, Volume 7194 of Lecture Notes in Computer Science, Taormina, Sicily, Italy (Springer, Heidelberg, 2012), pp. 112–132

11.

Y. Dodis, R. Oliveira, K. Pietrzak, On the generic insecurity of the full domain hash, in Victor Shoup, editor, Advances in Cryptology—CRYPTO 2005, Volume 3621 of Lecture Notes in Computer Science, Santa Barbara, CA, USA (Springer, Heidelberg, 2005), pp. 449–466

12.

Y. Dodis, L. Reyzin, On the power of claw-free permutations, in Stelvio Cimato, Clemente Galdi, and Giuseppe Persiano, editors, SCN 02: 3rd International Conference on Security in Communication Networks, Volume 2576 of Lecture Notes in Computer Science, Amalfi, Italy (Springer, Heidelberg, 2003), pp. 55–73

13.

A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems, in Andrew M. Odlyzko, editor, Advances in Cryptology–CRYPTO’86, Volume 263 of Lecture Notes in Computer Science, Santa Barbara, CA, USA (Springer, Heidelberg, 1987), pp. 186–194

14.

M. Fischlin, N. Fleischhacker, Limitations of the meta-reduction technique: the case of Schnorr signatures, in Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology—EUROCRYPT 2013, Volume 7881 of Lecture Notes in Computer Science, Athens, Greece (Springer, Heidelberg, 2013), pp. 444–460

15.

M. Fischlin, A. Lehmann, T. Ristenpart, T. Shrimpton, M. Stam, S. Tessaro, Random oracles with(out) programmability, in Masayuki Abe, editor, Advances in Cryptology—ASIACRYPT 2010, Volume 6477 of Lecture Notes in Computer Science, Singapore (Springer, Heidelberg, 2010), pp. 303–320

16.

N. Fleischhacker, T. Jager, D. Schröder, On tight security proofs for Schnorr signatures, in Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology—ASIACRYPT 2014, Part I, Volume 8873 of Lecture Notes in Computer Science, Kaoshiung, Taiwan, R.O.C (Springer, Heidelberg, 2014), pp. 512–531

17.

S.D. Galbraith, J. Malone-Lee, N.P. Smart. Public key signatures in the multi-user setting. Inf. Process. Lett., 83(5), 263–266 (2002)MathSciNetCrossRefMATH

18.

S. Garg, R. Bhaskar, S.V. Lokam, Improved bounds on security reductions for discrete log based signatures, in David Wagner, editor, Advances in Cryptology—CRYPTO 2008, Volume 5157 of Lecture Notes in Computer Science, Santa Barbara, CA, USA (Springer, Heidelberg, 2008), pp. 93–107

19.

S. Goldwasser, S. Micali, and R. L. Rivest. A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput., 17(2), 281–308 (1988)MathSciNetCrossRefMATH

20.

S. A. Kakvi, E. Kiltz, Optimal security proofs for full domain hash, revisited, in David Pointcheval and Thomas Johansson, editors, Advances in Cryptology—EUROCRYPT 2012, Volume 7237 of Lecture Notes in Computer Science, Cambridge, UK (Springer, Heidelberg, 2012), pp. 537–553

21.

E. Kiltz, D. Masny, J. Pan, Optimal security proofs for signatures from identification schemes, in Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology—CRYPTO 2016, Part II, Volume 9815 of Lecture Notes in Computer Science, Santa Barbara, CA, USA (Springer, Heidelberg, 2016), pp. 33–61

22.

U.M. Maurer, Abstract models of computation in cryptography (invited paper), in Nigel P. Smart, editor, 10th IMA International Conference on Cryptography and Coding, Volume 3796 of Lecture Notes in Computer Science, Cirencester, UK (Springer, Heidelberg, 2005), pp. 1–12

23.

G. Neven, N. Smart, B. Warinschi. Hash function requirements for Schnorr signatures. J. Math. Cryptol., 3(1), 69–87 (2009)MathSciNetCrossRefMATH

24.

P. Paillier, D. Vergnaud, Discrete-log-based signatures may not be equivalent to discrete log, in Bimal K. Roy, editor, Advances in Cryptology—ASIACRYPT 2005, Volume 3788 of Lecture Notes in Computer Science, Chennai, India (Springer, Heidelberg, 2005), pp. 1–20.

25.

D. Pointcheval, J. Stern, Security proofs for signature schemes, in Ueli M. Maurer, editor, Advances in Cryptology—EUROCRYPT’96, Volume 1070 of Lecture Notes in Computer Science, Saragossa, Spain (Springer, Heidelberg, 1996), pp. 387–398

26.

O. Reingold, L. Trevisan, S. P. Vadhan, Notions of reducibility between cryptographic primitives, in Moni Naor, editor, TCC 2004: 1st Theory of Cryptography Conference, Volume 2951 of Lecture Notes in Computer Science, Cambridge, MA, USA (Springer, Heidelberg, 2004), pp. 1–20

27.

A. Rupp, G. Leander, E. Bangerter, A.W. Dent, A.-R. Sadeghi, Sufficient conditions for intractability over black-box groups: generic lower bounds for generalized DL and DH problems, in Josef Pieprzyk, editor, Advances in Cryptology—ASIACRYPT 2008, Volume 5350 of Lecture Notes in Computer Science, Melbourne, Australia (Springer, Heidelberg, 2008), pp. 489–505

28.

S. Schäge, Tight proofs for signature schemes without random oracles, in Kenneth G. Paterson, editor, Advances in Cryptology—EUROCRYPT 2011, Volume 6632 of Lecture Notes in Computer Science, Tallinn, Estonia (Springer, Heidelberg, 2011), pp. 189–206

29.

C.-P. Schnorr, Efficient identification and signatures for smart cards, in Gilles Brassard, editor, Advances in Cryptology—CRYPTO’89, Volume 435 of Lecture Notes in Computer Science, Santa Barbara, CA, USA (Springer, Heidelberg, 1990), pp. 239–252

30.

C.-P. Schnorr. Efficient signature generation by smart cards. J. Cryptol., 4(3), 161–174 (1991)CrossRefMATH

31.

Y. Seurin, On the exact security of Schnorr-type signatures in the random oracle model, in David Pointcheval and Thomas Johansson, editors, Advances in Cryptology—EUROCRYPT 2012, Volume 7237 of Lecture Notes in Computer Science, Cambridge, UK (Springer, Heidelberg, 2012), pp. 554–571

32.

V. Shoup, Lower bounds for discrete logarithms and related problems, in Walter Fumy, editor, Advances in Cryptology—EUROCRYPT’97, Volume 1233 of Lecture Notes in Computer Science, Konstanz, Germany (Springer, Heidelberg, 1997), pp. 256–266

33.

B.R. Waters, Efficient identity-based encryption without random oracles, in Ronald Cramer, editor, Advances in Cryptology—EUROCRYPT 2005, Volume 3494 of Lecture Notes in Computer Science, Aarhus, Denmark (Springer, Heidelberg, 2005), pp. 114–127

Titel: On Tight Security Proofs for Schnorr Signatures
verfasst von: Nils Fleischhacker
Tibor Jager
Dominique Schröder
Publikationsdatum: 06.02.2019
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 2/2019
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-019-09311-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 2/2019

(Efficient) Universally Composable Oblivious Transfer Using a Minimal Number of Stateless Tokens

Automated Analysis of Cryptographic Assumptions in Generic Group Models

From Physical to Stochastic Modeling of a TERO-Based TRNG

Non-black-box Simulation in the Fully Concurrent Setting, Revisited

Hardness-Preserving Reductions via Cuckoo Hashing

Efficient RSA Key Generation and Threshold Paillier in the Two-Party Setting