Paper 2014/443
Minimizing the TwoRound EvenMansour Cipher
Shan Chen, Rodolphe Lampe, Jooyoung Lee, Yannick Seurin, and John P. Steinberger
Abstract
The $r$round (iterated) \emph{EvenMansour cipher} (also known as \emph{keyalternating 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 blackbox 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 EvenMansour 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 tworound EvenMansour 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 AESlike ciphers that does not assume independent round keys.
Note: An abridged version appears in the proceedings of CRYPTO 2014. This is the full version. The revised version of Dec. 18, 2014 contains some additional results and a more extensive discussion of the security bounds.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 A major revision of an IACR publication in CRYPTO 2014
 Keywords
 generalized EvenMansour cipherkeyalternating cipherindistinguishabilitypseudorandom permutationrandom permutation modelsumcapture problem
 Contact author(s)
 yannick seurin @ m4x org
 History
 20141218: revised
 20140613: received
 See all versions
 Short URL
 https://ia.cr/2014/443
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/443, author = {Shan Chen and Rodolphe Lampe and Jooyoung Lee and Yannick Seurin and John P. Steinberger}, title = {Minimizing the TwoRound EvenMansour Cipher}, howpublished = {Cryptology ePrint Archive, Paper 2014/443}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/443}}, url = {https://eprint.iacr.org/2014/443} }