International Association
for Cryptologic Research

The $r$-rounds Even-Mansour block cipher uses $r$ public permutations of $\\{0, 1\\}^n$ and $r+1$ secret keys. An attack on this construction was described in \\cite{DDKS}, for $r = 2, 3$. Although this attack is only marginally better than brute force, it is based on an interesting observation (due to \\cite{NWW}): for a \"typical\" permutation $P$, the distribution of $P(x) \\oplus x$ is not uniform.

To address this, and other potential threats that might stem from this observation in this (or other) context, we introduce the notion of a ``balanced permutation\'\' for which the distribution of $P(x) \\oplus x$ is uniform, and show how to generate families of balanced permutations from the Feistel construction.

This allows us to define a $2n$-bit block cipher from the $2$-rounds Even-Mansour scheme. The cipher uses public balanced permutations of $\\{0, 1\\}^{2n}$, which are based on two public permutations of $\\{0, 1\\}^{n}$.

By construction, this cipher is immune against attacks that rely on the non-uniform behavior of $P(x) \\oplus x$. 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 AES.