nach oben

Journal of Cryptology

Erschienen in:

01.01.2016

How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction

verfasst von: Jean-Sébastien Coron, Thomas Holenstein, Robin Künzler, Jacques Patarin, Yannick Seurin, Stefano Tessaro

Erschienen in: Journal of Cryptology | Ausgabe 1/2016

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper provides the first provably secure construction of an invertible random permutation (and of an ideal cipher) from a public random function that can be evaluated by all parties in the system, including the adversary. The associated security goal was formalized via the notion of indifferentiability by Maurer et al. (TCC 2004). The problem is the natural extension of that of building (invertible) random permutations from (private) random functions, first solved by Luby and Rackoff (SIAM J Comput 17(2):373–386, 1988) via the four-round Feistel construction. As our main result, we prove that the Feistel construction with fourteen rounds is indifferentiable from an invertible random permutation. We also provide a new lower bound showing that five rounds are not sufficient to achieve indifferentiability. A major corollary of our result is the equivalence (in a well-defined sense) of the random oracle model and the ideal cipher model.

Vorheriger Artikel Fast Cryptography in Genus 2

Nächster Artikel Efficient Set Intersection with Simulation-Based Security

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

Nur mit Berechtigung zugänglich

Usually required to be efficient, i.e., with running time polynomial in the number of queries it processes.

Note that in contrast to the case of indistinguishability considered by Luby and Rackoff, we cannot construct a non-invertible random permutation from a random oracle, regardless of the number of rounds. This follows from a well-known result by Rudich [43] and Kahn et al. [31].

Of course, much more is needed, as this is only one specific distinguisher. But it will be convenient right now to restrict ourselves to thwarting this type of distinguishing attacks.

Such a tuple can also be seen as a random primitive.

Recall that a queue is a first in first out data structure.

We may assume that \(\mathbf {D}\) is deterministic, since we are only interested in the advantage of the optimal distinguisher, and for any probabilistic distinguisher, the advantage can be at most the advantage of the optimal deterministic distinguisher.

It is actually not hard to see that the simulator always gives an answer in \(\mathsf {S}_3\) after a finite number of steps, but we don’t need to show this as \(\mathsf {S}_2\) and \(\mathsf {S}_3\) behave almost the same anyway.

It would actually be sufficient to consider the scenario \(\mathsf {E}_3\) here, but we can save a little bit of work by considering both \(\mathsf {E}_3\) and \(\mathsf {E}_4\).

The symmetry can be violated if in the two-sided random function \( \mathbf{R }\) an entry of the table \(P\) is overwritten.

Of course, to avoid running an exponential number of simulator instances, we use lazy evaluation, running only \( \mathbf S _k\) for keys \(k\) that are actually queried.

E. Andreeva, A. Bogdanov, Y. Dodis, B. Mennink, J.P. Steinberger, On the indifferentiability of key-alternating ciphers, in R. Canetti, J.A. Garay, editors, Advances in Cryptology—CRYPTO 2013 (Proceedings, Part I), Lecture Notes in Computer Science, vol. 8042 (Springer, Berlin, 2013), pp. 531–550. Full version available at http://eprint.iacr.org/2013/061

G. Bertoni, J. Daemen, M. Peeters, G. Van Assche, On the indifferentiability of the sponge construction, in N.P. Smart, editor, Advances in Cryptology—EUROCRYPT 2008, Lecture Notes in Computer Science, vol. 4965 (Springer, Berlin, 2008), pp. 181–197

D. Boneh, M.K. Franklin, Identity-based encryption from the weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)

M. Bellare, T. Kohno, A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications, in Advances in Cryptology—EUROCRYPT 2003, Lecture Notes in Computer Science, vol. 2656, pp. 491–506 (2003)

A. Bogdanov, L.R. Knudsen, G. Leander, F.-X. Standaert, J.P. Steinberger, E. Tischhauser, Key-alternating ciphers in a provable setting: encryption using a small number of public permutations—(Extended Abstract), in D. Pointcheval, T. Johansson, editors, Advances in Cryptology—EUROCRYPT 2012, Lecture Notes in Computer Science, vol. 7237 (Springer, Berlin, 2012), pp. 45–62

J. Black, The ideal-cipher model, revisited: an uninstantiable blockcipher-based hash function, in FSE 2006, Lecture Notes in Computer Science, vol. 4047, pp. 328–340 (2006)

D. Boneh, B. Lynn, H. Shacham, Short signatures from the weil pairing. J. Cryptol. 17(4), 297–319 (2004)

M. Bellare, D. Pointcheval, P. Rogaway, Authenticated key exchange secure against dictionary attacks, in EUROCRYPT00, Lecture Notes in Computer Science, vol. 1807, pp. 139–155 (2000)

M. Bellare, P. Rogaway, Random oracles are practical: a paradigm for designing efficient protocols, in CCS ’93: Proceedings of the 1st ACM Conference on Computer and Communications Security (ACM, New York, NY, USA, 1993), pp. 62–73

10.

M. Bellare, P. Rogaway. Optimal asymmetric encryption, in Advances in Cryptology—EUROCRYPT ’94, Lecture Notes in Computer Science, pp. 92–111 (1994)

11.

M. Bellare, P. Rogaway, The exact security of digital signatures—how to sign with RSA and Rabin, in Advances in Cryptology—EUROCRYPT ’96, Lecture Notes in Computer Science, pp. 399–416 (1996)

12.

J. Black, P. Rogaway, Ciphers with arbitrary finite domains, in CT-RSA 2002, Lecture Notes in Computer Science, pp. 114–130 (2002)

13.

M. Bellare, P. Rogaway, The security of triple encryption and a framework for code-based game-playing proofs, in Advances in Cryptology—EUROCRYPT 2006, Lecture Notes in Computer Science, vol. 4004, pp. 409–426 (2006)

14.

J. Black, P. Rogaway, T. Shrimpton, Black-box analysis of the block-cipher-based hash-function constructions from PGV, in Advances in Cryptology—CRYPTO 2002, Lecture Notes in Computer Science, vol. 2442, pp. 320–335 (2002)

15.

R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, in FOCS ’01: Proceedings of the 42nd IEEE Annual Symposium on Foundations of Computer Science, pp. 136–145 (2001)

16.

J.-S. Coron, Y. Dodis, C. Malinaud, P. Puniya, Merkle-Damgård revisited: how to construct a hash function, in V. Shoup, editor, Advances in Cryptology—CRYPTO 2005, Lecture Notes in Computer Science, vol. 3621 (Springer, Berlin, 2005), pp. 430–448

17.

R. Canetti, O. Goldreich, S. Halevi, The random oracle methodology, revisited. J. ACM 51(4), 557–594 (2004)

18.

S. Chen, R. Lampe, J. Lee, Y. Seurin, J.P. Steinberger, Minimizing the two-round even-mansour cipher, in J.A. Garay, R. Gennaro, editors, Advances in Cryptology—CRYPTO 2014 (Proceedings, Part I), Lecture Notes in Computer Science, vol. 8616 (Springer, Berlin, 2014), pp. 39–56. Full version available at http://eprint.iacr.org/2014/443

19.

J.-S. Coron, J. Patarin, Y. Seurin, The random oracle model and the ideal cipher model are equivalent, in D. Wagner, editor, CRYPTO, Lecture Notes in Computer Science, vol. 5157 (Springer, Berlin, 2008), pp. 1–20

20.

J.-S. Coron, J. Patarin, Y. Seurin, The random oracle model and the ideal cipher model are equivalent. Cryptology ePrint Archive, Report 2008/246, August 2008. Version: 20080816:121712, http://eprint.iacr.org/, Extended Abstract at CRYPTO 2008

21.

S. Chen, J. Steinberger, Tight security bounds for key-alternating ciphers, in P.Q. Nguyen, E. Oswald, editors, Advances in Cryptology—EUROCRYPT 2014, Lecture Notes in Computer Science, vol. 8441, pp. 327–350 (Springer, Berlin, 2014). Full version available at http://eprint.iacr.org/2013/222

22.

I.B. Damgård, A design principle for hash functions, in Advances in Cryptology—CRYPTO ’89, Lecture Notes in Computer Science, vol. 435, pp. 416–427 (1989)

23.

G. Demay, P. Gazi, M. Hirt, U. Maurer, Resource-restricted indifferentiability, in EUROCRYPT13, Lecture Notes in Computer Science, vol. 7881, pp. 664–683 (2013)

24.

Y. Dodis, P. Puniya, On the relation between the ideal cipher and the random oracle models, in Theory of Cryptography—TCC 2006, Lecture Notes in Computer Science, vol. 3876, pp. 184–206 (2006)

25.

S. Dziembowski, K. Pietrzak, D. Wichs, Non-malleable codes, in Innovations in Computer Science—ICS 2010, pp. 434–452 (2010)

26.

Y. Dodis, L. Reyzin, R.L. Rivest, E. Shen, Indifferentiability of permutation-based compression functions and tree-based modes of operation, with applications to MD6, in O. Dunkelman, editor, Fast Software Encryption—FSE 2009, Lecture Notes in Computer Science, vol. 5665 (Springer, Berlin, 2009), pp. 104–121

27.

S. Even, Y. Mansour, A construction of a cipher from a single pseudorandom permutation. J. Cryptol. 10(3), 151–162 (1997)

28.

A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems, in Advances in Cryptology—CRYPTO ’86, Lecture Notes in Computer Science, vol. 263, pp. 186–194 (1986)

29.

T. Holenstein, R. Künzler, S. Tessaro, The equivalence of the random oracle model and the ideal cipher model, revisited, in L. Fortnow, S.P. Vadhan, editors, STOC (ACM, New York, 2011), pp. 89–98

30.

J. Kilian, P. Rogaway, How to protect DES against exhaustive key search (an analysis of DESX). J. Cryptol. 14(1), 17–35 (2001)

31.

J. Kahn, M.E. Saks, C.D. Smyth, A dual version of Reimer’s inequality and a proof of Rudich’s conjecture, in IEEE Conference on Computational Complexity, pp. 98–103 (2000)

32.

M. Luby, C. Rackoff, How to construct pseudorandom permutations from pseudorandom functions. SIAM J. Comput. 17(2), 373–386 (1988)

33.

R. Lampe, Y. Seurin, How to construct an ideal cipher from a small set of public permutations, in K. Sako, P. Sarkar, editors, Advances in Cryptology—ASIACRYPT 2013 (Proceedings, Part I), Lecture Notes in Computer Science, vol. 8269 (Springer, Berlin, 2013), pp. 444–463. Full version available at http://eprint.iacr.org/2013/255

34.

Y. Lindell, H. Zarosim, Adaptive zero-knowledge proofs and adaptively secure oblivious transfer, in Theory of Cryptography Conference—TCC 2009, Lecture Notes in Computer Science, vol. 5444, pp. 183–201 (2009)

35.

U. Maurer, Indistinguishability of random systems, in Advances in Cryptology—EUROCRYPT 2002, Lecture Notes in Computer Science, vol. 2332, pp. 110–132 (2002)

36.

R.C. Merkle, A certified digital signature, in Advances in Cryptology—CRYPTO ’89, Lecture Notes in Computer Science, vol. 435, pp. 218–238 (1989)

37.

A. Mandal, J. Patarin, Y. Seurin, On the public indifferentiability and correlation intractability of the 6-round Feistel construction, in TCC (2012). Full version available at http://eprint.iacr.org/2011/496.pdf

38.

U. Maurer, R. Renner. Abstract cryptography, in Innovations in Computer Science—ICS 2011, pp. 1–21 (2011)

39.

U. Maurer, R. Renner, C. Holenstein, Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology, in Theory of Cryptography Conference—TCC 2004, Lecture Notes in Computer Science, vol. 2951, pp. 21–39, February 2004

40.

P. Rogaway, J.P. Steinberger, Constructing cryptographic hash functions from fixed-key blockciphers, in D. Wagner, editor, Advances in Cryptology—CRYPTO 2008, Lecture Notes in Computer Science, vol. 5157 (Springer, Berlin, 2008), pp. 433–450

41.

P. Rogaway, J.P. Steinberger, Security/efficiency tradeoffs for permutation-based hashing, in N.P. Smart, editor, Advances in Cryptology—EUROCRYPT 2008, Lecture Notes in Computer Science, vol. 4965 (Springer, Berlin, 2008), pp. 220–236

42.

T. Ristenpart, H. Shacham, T. Shrimpton, Careful with composition: limitations of the indifferentiability framework, in K.G. Paterson, editor, EUROCRYPT, Lecture Notes in Computer Science, vol. 6632 (Springer, Berlin, 2011), pp. 487–506

43.

S. Rudich, Limits on the Provable Consequences of One-way Functions. PhD thesis (1989)

44.

Y. Seurin, Primitives et protocoles cryptographiques à sécurité prouvée. PhD thesis, Université de Versailles Saint-Quentin-en-Yvelines, UFR de Sciences - École doctorale SoFt - Laboratoire PRiSM (2009)

45.

Y. Seurin, A note on the indifferentiability of the 10-round feistel construction, March 2011. Unpublished note available from the author

46.

C.E. Shannon, Communication theory of secrecy systems. Bell Syst. Tech. J. 28, 656–715 (1949)

47.

V. Shoup, Sequences of games: a tool for taming complexity in security proofs (2004)

Titel: How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction
verfasst von: Jean-Sébastien Coron
Thomas Holenstein
Robin Künzler
Jacques Patarin
Yannick Seurin
Stefano Tessaro
Publikationsdatum: 01.01.2016
Verlag: Springer US
Erschienen in: Journal of Cryptology / Ausgabe 1/2016
Print ISSN: 0933-2790
Elektronische ISSN: 1432-1378
DOI: https://doi.org/10.1007/s00145-014-9189-6

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 1/2016

Enhanced Public Key Security for the McEliece Cryptosystem

Breaking RSA May Be As Difficult As Factoring

Efficient Set Intersection with Simulation-Based Security

Fast Cryptography in Genus 2

Concurrent Knowledge Extraction in Public-Key Models

Premium Partner