Welcome to the resource topic for 2014/642
Title:
Balanced permutations Even-Mansour ciphers
Authors: Shoni Gilboa, 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.
ePrint: https://eprint.iacr.org/2014/642
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .