Abstract
Even and Mansour [EM97] proposed a block cipher construction that takes a publicly computable random permutation oracle P and XORs different keys prior to and after applying P : C =k 2 ⊕ P(M ⊕ k 1). They did not, however, describe how one could instantiate such a permutation securely. It is a fundamental open problem whether their construction could be proved secure outside the random permutation oracle model. We resolve this question in the affirmative by showing that the construction can be proved secure in the random function oracle model. In particular, we show that the random permutation oracle in their scheme can be replaced by a construction that utilizes a four-round Feistel network (where each round function is a random function oracle publicly computable by all parties including the adversary). Further, we prove that the resulting cipher is super pseudorandom – the adversary’s distinguishing advantage is at most 2q 2/2n if he makes q total queries to the cipher, its inverse, as well as any random oracles. Even and Mansour, on the other hand, only showed security against inversion and forgery. One noteworthy aspect of this result is that the cipher remains secure even though the adversary is permitted separate oracle access to all of the round functions. One can achieve a two-fold and four-fold reduction respectively in the amount of key material by a closer inspection of the proof and by instantiating the scheme using group operations other than exclusive-OR. On the negative side, a straightforward adaption of an advanced slide attack recovers the 4n-bit key with approximately \(\sqrt{2} \cdot 2^{n}\) work using roughly \(\sqrt{2} \cdot 2^{n}\) known plaintexts. Finally, if only three Feistel rounds are used, the resulting cipher is pseudorandom, but not super pseudorandom.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Bellare, M., Boldyreva, A., Palacio, A.: An uninstantiable random-oracle-model scheme for a hybrid-encryption problem. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 171–188. Springer, Heidelberg (2004)
Bellare, M., Canetti, R., Krawczyk, H.: Pseudorandom functions revisited: The cascade construction and its concrete security. In: 37th Annual Symposium on Foundations of Computer Science, pp. 514–523. IEEE, Los Alamitos (1996)
Bellare, M., Kilian, J., Rogaway, P.: The security of cipher block chaining. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 341–358. Springer, Heidelberg (1994)
Bellare, M., Rogaway, P.: Random oracles are practical: A paradigm for designing efficient protocols. In: First ACM Conference on Computer and Communications Security, Fairfax, pp. 62–73 (1993)
Biryukov, A., Wagner, D.: Advanced slide attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, p. 589. Springer, Heidelberg (2000)
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. In: Proc. 30th ACM Symp. on Theory of Computing (1998)
Daemen, J.: Limitations of the Even-Mansour construction. In: ASIACRYPT 1991, vol. 739, pp. 495–498. Springer, Heidelberg (1992); Initially Presented at the Rump Session
Even, S., Mansour, Y.: A construction of a cipher from a single pseudorandom permutation. Journal of Cryptology 10(3), 151–162 (summer 1997); Earlier version in Proc. ASIACRYPT 1991. LNCS, vol. 739, pp. 210–224. Springer, Heidelberg (1992)
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. Journal of the ACM 33(4), 792–807 (1984)
Goldwasser, S., Tauman Kalai, Y.: On the (in)security of the Fiat-Shamir Paradigm. In: Proceedings of FOCS 2003 (2003)
Gentry, C., Ramzan, Z.: Eliminating random permutation oracles in the Even-Mansour cipher. Cryptology ePrint archive (2004)
Kilian, J., Rogaway, P.: How to protect against exhaustive search. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 252–267. Springer, Heidelberg (1996)
Luby, M., Rackoff, C.: How to construct pseudorandom permutations and pseudorandom functions. SIAM J. Computing 17(2), 373–386 (1988)
National Bureau of Standards. FIPS publication 46: Data encryption standard (1977); Federal Information Processing Standards Publication 46
Naor, M., Reingold, O.: On the construction of pseudo-random permutations: Luby-Rackoff revisited. J. of Cryptology 12, 29–66 (1999); Preliminary version in Proc. STOC 1997
Patel, S., Ramzan, Z., Sundaram, G.: Luby-Rackoff ciphers: Why XOR is not exclusive. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 271–290. Springer, Heidelberg (2003)
Ramzan, Z., Reyzin, L.: On the Round Security of Symmetric-Key Cryptographic Primitives. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, p. 376. Springer, Heidelberg (2000)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gentry, C., Ramzan, Z. (2004). Eliminating Random Permutation Oracles in the Even-Mansour Cipher. In: Lee, P.J. (eds) Advances in Cryptology - ASIACRYPT 2004. ASIACRYPT 2004. Lecture Notes in Computer Science, vol 3329. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30539-2_3
Download citation
DOI: https://doi.org/10.1007/978-3-540-30539-2_3
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-23975-8
Online ISBN: 978-3-540-30539-2
eBook Packages: Springer Book Archive