nach oben

Erschienen in:

2016 | OriginalPaper | Buchkapitel

Indifferentiability of 8-Round Feistel Networks

verfasst von : Yuanxi Dai, John Steinberger

Erschienen in: Advances in Cryptology – CRYPTO 2016

Verlag: Springer Berlin Heidelberg

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We prove that a balanced 8-round Feistel network is indifferentiable from a random permutation, improving on previous 10-round results by Dachman-Soled et al. and Dai et al. Our simulator achieves security $O(q^8/2^n)$, similarly to the security of Dai et al. For further comparison, Dachman-Soled et al. achieve security $O(q^{12}/2^n)$, while the original 14-round simulator of Holenstein et al. achieves security $O(q^{10}/2^n)$.

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

Vorheriges Kapitel XPX: Generalized Tweakable Even-Mansour with Improved Security Guarantees

Nächstes Kapitel EWCDM: An Efficient, Beyond-Birthday Secure, Nonce-Misuse Resistant MAC

This introduces a small amount of non-uniformity into the simulator, but which seems not to matter in practice. While in our case the dependence of S on q is made mainly for the sake of simplicity and could as well be avoided (with a more convoluted proof and a simulator that runs efficiently only with high probability), we note, interestingly, that there is one indifferentiabiliy result that we are aware of—namely that of [16]—for which the simulator crucially needs to know the number of distinguisher queries in advance.

FIFO: First-In-First-Out. LIFO: Last-In-First-Out.

In this context we use the verb “sampled” as a euphemism for “have their endpoints sampled”.

Recall that the endpoints of a path with adapt zone 3, 4 are $x_2$ and $x_5$, and that the endpoints of a path with adapt zone 7, 8 are $x_6$ and $x_9$.

The simulator is not multi-threaded, but this metaphor is still helpful.

This might sound a bit ad-hoc right now, but it actually corresponds to the most natural way of programming the simulator, as will become clearer in the technical simulator overview.

In more detail, when a tree becomes stable the simulator lazy samples

$$\begin{aligned} F_i(x_i) \end{aligned}$$

for every endpoint (a.k.a., pending query) in the tree. Then if the tree is, say, a (2, 5)-tree, the simulator can compute the values

$$\begin{aligned}&x_3 := x_1 \oplus F_2(x_2)\\&x_4 := F_5(x_5) \oplus x_6 \end{aligned}$$

and set

$$\begin{aligned}&F_3(x_3) := x_2 \oplus x_4\\&F_4(x_4) := x_3 \oplus x_5 \end{aligned}$$

for each path in the tree. If two paths “collide” by having the same value of $x_3$ or $x_4$ the simulator aborts. Likewise the simulator aborts if either $F_3(x_3) \ne \bot $ or $F_4(x_4) \ne \bot $ for some path, before adapting those values. We call this two-step process “sampling and adapting” the (2, 5)-tree. The process of sampling and adapting a (6, 9)-tree is analogous.

Henceforth, “the” 10-round simulator refers to the simulator of [11].

To solidify things with some examples, a “trigger” for a pending query $(5, x_5)$ is a pair values of $x_3$, $x_4$ such that $F_3(x_3) \ne \bot $, $F_4(x_4) \ne \bot $ and such that $x_3 \oplus F_4(x_4) = x_5$, corresponding to the rightmost, bottommost diagram of Fig. 2; a “trigger” for a pending query $(1, x_1)$ is pair of values $x_7$, $x_8$ such that $F_7(x_7) \ne \bot $, $F_8(x_8) \ne \bot $, and such that P$^{-1}(x_8, x_9) = (*, x_1)$ where $x_9 := x_7 \oplus F_8(x_8)$, corresponding to the leftmost, topmost diagram of Fig. 2. Etc.

This operation cannot be included in $\mathrm {G_{1}}$ as the original simulator is not allowed to see the distinguisher’s permutation queries.

Or a call “CheckP$^-$ ($x_1, x_7, x_8$)” subject to symmetric conditions.

The fact that CheckP$^+$ ($x_1, x_2, x_8$) is called in the first place implies that $F_1(x_1) \ne \bot $ in either game.

Andreeva, E., Bogdanov, A., Dodis, Y., Mennink, B., Steinberger, J.P.: On the indifferentiability of key-alternating ciphers. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 531–550. Springer, Heidelberg (2013)CrossRef

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

Bertoni, G., Daemen, J., Peeters, M., Van Assche, G.: On the indifferentiability of the sponge construction. In: Smart, N.P. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 181–197. Springer, Heidelberg (2008)CrossRef

Canetti, R.: Security and composition of multi-party cryptographic protocols. J. Cryptol. 13(1), 143–202 (2000)MathSciNetCrossRefMATH

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

Chen, S., Steinberger, J.: Tight security bounds for key-alternating ciphers. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 327–350. Springer, Heidelberg (2014)CrossRef

Coron, J.-S., Dodis, Y., Malinaud, C., Puniya, P.: Merkle-Damgård revisited: how to construct a hash function. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 430–448. Springer, Heidelberg (2005)CrossRef

Coron, J.-S., Dodis, Y., Mandal, A., Seurin, Y.: A domain extender for the ideal cipher. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 273–289. Springer, Heidelberg (2010)CrossRef

Coron, J.-S., Patarin, J., Seurin, Y.: The random oracle model and the ideal cipher model are equivalent. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 1–20. Springer, Heidelberg (2008)CrossRef

10.

Dachman-Soled, D., Katz, J., Thiruvengadam, A.: 10-round feistel is indifferentiable from an ideal cipher. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 649–678. Springer, Heidelberg (2016). doi:10.1007/978-3-662-49896-5_23 CrossRef

11.

Dai, Y., Steinberger, J.: Indifferentiability of 10-round Feistel networks. IACR ePrint Archive, Technical Report 2015/874 (2015)

12.

Dai, Y., Steinberger, J.: Indifferentiability of 8-round Feistel networks. IACR ePrint Archive, Technical Report 2015/1069 (2015)

13.

Dodis, Y., Puniya, P.: On the relation between the ideal cipher and the random oracle models. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 184–206. Springer, Heidelberg (2006)CrossRef

14.

Dodis, Y., Liu, T., Stam, M., Steinberger, J.: On the indifferentiability of confusion-diffusion networks. IACR ePrint Archive, Technical Report 2015/680 (2015)

15.

Dodis, Y., Reyzin, L., Rivest, R.L., Shen, E.: Indifferentiability of permutation-based compression functions and tree-based modes of operation, with applications to MD6. In: Dunkelman, O. (ed.) FSE 2009. LNCS, vol. 5665, pp. 104–121. Springer, Heidelberg (2009)CrossRef

16.

Dodis, Y., Ristenpart, T., Steinberger, J., Tessaro, S.: To hash or not to hash again? (In)Differentiability results for H $^\text{2 }$ and HMAC. In: Canetti, R., Safavi-Naini, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 348–366. Springer, Heidelberg (2012)CrossRef

17.

Feistel, H.: Cryptographic coding for data-bank privacy. IBM Technical report RC-2827, 18 March 1970

18.

Feistel, H., Notz, W.A., Lynn Smith, J.: Some cryptographic techniques for machine-to-machine data communications. IEEE Proc. 63(11), 1545–1554 (1975)CrossRef

19.

Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987)CrossRef

20.

Holenstein, T., Künzler, R., Tessaro, S.: The equivalence of the random oracle model and the ideal cipher model, revisited. In: Fortnow, L., Vadhan, S.P. (eds.) Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, pp. 89–98. ACM, 6–8 June 2011

21.

Lampe, R., Seurin, Y.: How to construct an ideal cipher from a small set of public permutations. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, Part I. LNCS, vol. 8269, pp. 444–463. Springer, Heidelberg (2013)CrossRef

22.

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

23.

Maurer, U.M., Renner, R.S., Holenstein, C.: Indifferentiability, impossibility results on reductions, and applications to the random oracle methodology. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 21–39. Springer, Heidelberg (2004)CrossRef

24.

Naor, M., Reingold, O.: On the construction of pseudorandom permutations: Luby-Rackoff revisited. J. Cryptol. 12(1), 29–66 (1999). Preliminary Version: STOC 1997MathSciNetCrossRefMATH

25.

Patarin, J.: Security of balanced and unbalanced Feistel schemes with linear non equalities. IACR ePrint Arxiv, Technical Report 2010/293 (2010)

26.

Pfitzmann, B., Waidner, M.: Composition and integrity preservation of secure reactive systems. In: 7th ACM Conference on Computer and Communications Security, pp. 245–254. ACM Press (2000)

27.

Pfitzmann, B., Waidner, M.: A model for asynchronous reactive systems and its application to secure message transmission. Technical report 93350, IBM Research Division, Zürich (2000)

28.

Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 387–398. Springer, Heidelberg (1996)CrossRef

29.

Ristenpart, T., Shacham, H., Shrimpton, T.: Careful with composition: limitations of the indifferentiability framework. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 487–506. Springer, Heidelberg (2011)CrossRef

30.

Hoang, V.T., Rogaway, P.: On generalized Feistel networks. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 613–630. Springer, Heidelberg (2010)CrossRef

31.

Seurin, Y.: Primitives et protocoles cryptographiques à sécurité prouvée. Ph.D. thesis, Université de Versailles Saint-Quentin-en-Yvelines, France (2009)

32.

Seurin, Y.: A note on the indifferentiability of the 10-round Feistel construction. http://yannickseurin.free.fr/pubs/Seurin_note_ten_rounds.pdf

33.

Winternitz, R.: A secure one-way hash function built from DES. In: Proceedings of the IEEE Symposium on Information Security and Privacy, pp. 88–90. IEEE Press (1984)

Titel: Indifferentiability of 8-Round Feistel Networks
verfasst von: Yuanxi Dai
John Steinberger
Verlag: Springer Berlin Heidelberg
Buch: Advances in Cryptology – CRYPTO 2016
Print ISBN: 978-3-662-53017-7

Electronic ISBN: 978-3-662-53018-4

Copyright-Jahr: 2016
DOI: https://doi.org/10.1007/978-3-662-53018-4_4

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"