Balanced permutations Even-Mansour ciphers
This work addresses security vulnerabilities in block ciphers for cryptography applications, offering a provably secure construction that is incremental but improves on prior attacks.
The paper tackles the problem of constructing secure Even-Mansour ciphers by introducing balanced permutations, where the distribution of P(x) ⊕ x is uniform, to address vulnerabilities in typical permutations. It shows that using balanced permutations from the Luby-Rackoff construction in a 2-round Even-Mansour scheme yields a 2n-bit block cipher provably indistinguishable from a random permutation with security up to o(2^{n/2}) queries, and provides a practical 256-bit example using AES.
The $r$-rounds Even-Mansour block cipher is a generalization of the well known Even-Mansour block cipher to $r$ iterations. Attacks on this construction were described by Nikolić et al. and Dinur et al., for $r = 2, 3$. These attacks are only marginally better than brute force, but are based on an interesting observation (due to Nikolić et al.): for a "typical" permutation $P$, the distribution of $P(x) \oplus x$ is not uniform. This naturally raises the following question. Call permutations for which the distribution of $P(x) \oplus x$ is uniform "balanced." Is there a sufficiently large family of balanced permutations, and what is the security of the resulting Even-Mansour block cipher? We show how to generate families of balanced permutations from the Luby-Rackoff construction, and use them to define a $2n$-bit block cipher from the $2$-rounds Even-Mansour scheme. We prove that this cipher is indistinguishable from a random permutation of $\{0, 1\}^{2n}$, for any adversary who has oracle access to the public permutations and to an encryption/decryption oracle, as long as the number of queries is $o (2^{n/2})$. As a practical example, we discuss the properties and the performance of a $256$-bit block cipher that is based on our construction, and uses AES as the public permutation.