Welcome to the resource topic for 2014/443
Title:
Minimizing the Two-Round Even-Mansour Cipher
Authors: Shan Chen, Rodolphe Lampe, Jooyoung Lee, Yannick Seurin, John P. Steinberger
Abstract:The r-round (iterated) \emph{Even-Mansour cipher} (also known as \emph{key-alternating cipher}) defines a block cipher from r fixed public n-bit permutations P_1,\ldots,P_r as follows: given a sequence of n-bit round keys k_0,\ldots,k_r, an n-bit plaintext x is encrypted by xoring round key k_0, applying permutation P_1, xoring round key k_1, etc. The (strong) pseudorandomness of this construction in the random permutation model (i.e., when the permutations P_1,\ldots,P_r are public random permutation oracles that the adversary can query in a black-box way) was studied in a number of recent papers, culminating with the work of Chen and Steinberger (EUROCRYPT~2014), who proved that the r-round Even-Mansour cipher is indistinguishable from a truly random permutation up to O(2^{\frac{rn}{r+1}}) queries of any adaptive adversary (which is an optimal security bound since it matches a simple distinguishing attack). All results in this entire line of work share the common restriction that they only hold under the assumption that \emph{the round keys k_0,\ldots,k_r and the permutations P_1,\ldots,P_r are independent}. In particular, for two rounds, the current state of knowledge is that the block cipher E(x)=k_2\oplus P_2(k_1\oplus P_1(k_0\oplus x)) is provably secure up to O(2^{2n/3}) queries of the adversary, when k_0, k_1, and k_2 are three independent n-bit keys, and P_1 and P_2 are two independent random n-bit permutations. In this paper, we ask whether one can obtain a similar bound for the two-round Even-Mansour cipher \emph{from just one n-bit key and one n-bit permutation}. Our answer is positive: when the three n-bit round keys k_0, k_1, and k_2 are adequately derived from an n-bit master key k, and the same permutation P is used in place of P_1 and P_2, we prove a qualitatively similar \tilde{O}(2^{2n/3}) security bound (in the random permutation model). To the best of our knowledge, this is the first ``beyond the birthday bound’’ security result for AES-like ciphers that does not assume independent round keys.
ePrint: https://eprint.iacr.org/2014/443
Talk: https://www.youtube.com/watch?v=jBe4PPwNunE
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 .