Abstract
We analyze the security of the iterated Even-Mansour cipher (a.k.a. key-alternating cipher), a very simple and natural construction of a blockcipher in the random permutation model. This construction, first considered by Even and Mansour (J. Cryptology, 1997) with a single permutation, was recently generalized to use t permutations in the work of Bogdanov et al. (EUROCRYPT 2012). They proved that the construction is secure up to \( \mathcal{O} (N^{2/3})\) queries (where N is the domain size of the permutations), as soon as the number t of rounds is 2 or more. This is tight for t = 2, however in the general case the best known attack requires Ω(N t/(t + 1)) queries. In this paper, we give asymptotically tight security proofs for two types of adversaries:
-
1
for non-adaptive chosen-plaintext adversaries, we prove that the construction achieves an optimal security bound of \( \mathcal{O} (N^{t/(t+1)})\) queries;
-
2
for adaptive chosen-plaintext and ciphertext adversaries, we prove that the construction achieves security up to \( \mathcal{O} (N^{t/(t+2)})\) queries (for t even). This improves previous results for t ≥ 6.
Our proof crucially relies on the use of a coupling to upper-bound the statistical distance of the outputs of the iterated Even-Mansour cipher to the uniform distribution.
Chapter PDF
Similar content being viewed by others
Keywords
References
Aldous, D.J.: Random walks on finite groups and rapidly mixing Markov chains. In: Séminaire de Probabilités XVII. Lecture Notes in Mathematics, vol. 986, pp. 243–297. Springer (1983)
Bellare, M., Rogaway, P.: Random Oracles are Practical: A Paradigm for Designing Efficient Protocols. In: ACM Conference on Computer and Communications Security, pp. 62–73 (1993)
Biryukov, A., Wagner, D.: Advanced Slide Attacks. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 589–606. Springer, Heidelberg (2000)
Bogdanov, A., Knudsen, L.R., Leander, G., Standaert, F.-X., Steinberger, J., Tischhauser, E.: Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations (Extended Abstract). In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 45–62. Springer, Heidelberg (2012)
Canetti, R., Goldreich, O., Halevi, S.: The Random Oracle Methodology, Revisited (Preliminary Version). In: Symposium on Theory of Computing, STOC 1998, pp. 209–218. ACM (1998); Full version available at http://arxiv.org/abs/cs.CR/0010019 .
Daemen, J.: Limitations of the Even-Mansour Construction. In: Imai, H., Rivest, R.L., Matsumoto, T. (eds.) ASIACRYPT 1991. LNCS, vol. 739, pp. 495–498. Springer, Heidelberg (1993)
Daemen, J., Rijmen, V.: Probability Distributions of Correlations and Differentials in Block Ciphers. ePrint Archive Report 2005/212 (2005), http://eprint.iacr.org/2005/212.pdf
Dunkelman, O., Keller, N., Shamir, A.: Minimalism in Cryptography: The Even-Mansour Scheme Revisited. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 336–354. Springer, Heidelberg (2012)
Even, S., Mansour, Y.: A Construction of a Cipher from a Single Pseudorandom Permutation. Journal of Cryptology 10(3), 151–162 (1997)
Gentry, C., Ramzan, Z.: Eliminating Random Permutation Oracles in the Even-Mansour Cipher. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 32–47. Springer, Heidelberg (2004)
Guo, J., Peyrin, T., Poschmann, A., Robshaw, M.: The LED Block Cipher. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 326–341. Springer, Heidelberg (2011)
Hoang, V.T., Rogaway, P.: On Generalized Feistel Networks. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 613–630. Springer, Heidelberg (2010)
Kilian, J., Rogaway, P.: How to Protect DES Against Exhaustive Key Search (an Analysis of DESX). Journal of Cryptology 14(1), 17–35 (2001)
Maurer, U.M., Pietrzak, K.: Composition of Random Systems: When Two Weak Make One Strong. In: Naor, M. (ed.) TCC 2004. LNCS, vol. 2951, pp. 410–427. Springer, Heidelberg (2004)
Maurer, U.M., Pietrzak, K., Renner, R.: Indistinguishability Amplification. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 130–149. Springer, Heidelberg (2007)
Mironov, I.: (Not So) Random Shuffles of RC4. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 304–319. Springer, Heidelberg (2002)
Morris, B., Rogaway, P., Stegers, T.: How to Encipher Messages on a Small Domain. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 286–302. Springer, Heidelberg (2009)
Patarin, J.: New Results on Pseudorandom Permutation Generators Based on the DES Scheme. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 301–312. Springer, Heidelberg (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 International Association for Cryptologic Research
About this paper
Cite this paper
Lampe, R., Patarin, J., Seurin, Y. (2012). An Asymptotically Tight Security Analysis of the Iterated Even-Mansour Cipher. In: Wang, X., Sako, K. (eds) Advances in Cryptology – ASIACRYPT 2012. ASIACRYPT 2012. Lecture Notes in Computer Science, vol 7658. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34961-4_18
Download citation
DOI: https://doi.org/10.1007/978-3-642-34961-4_18
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34960-7
Online ISBN: 978-3-642-34961-4
eBook Packages: Computer ScienceComputer Science (R0)