Paper 2014/642

Balanced permutations Even-Mansour ciphers

Shoni Gilboa and Shay Gueron

Abstract

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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Even-Mansour cipherblock ciphersrandom permutations
Contact author(s)
shay @ math haifa ac il
History
2014-08-27: received
Short URL
https://ia.cr/2014/642
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/642,
      author = {Shoni Gilboa and Shay Gueron},
      title = {Balanced permutations Even-Mansour ciphers},
      howpublished = {Cryptology ePrint Archive, Paper 2014/642},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/642}},
      url = {https://eprint.iacr.org/2014/642}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.