  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\'c 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\'c 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.
