Welcome to the resource topic for 2013/222
Title:
Tight security bounds for key-alternating ciphers
Authors: Shan Chen, John Steinberger
Abstract:A t-round \emph{key-alternating cipher} (also called \emph{iterated Even-Mansour cipher}) can be viewed as an abstraction of AES. It defines a cipher E from t fixed public permutations P_1, \ldots, P_t : \bits^n \ra \bits^n and a key k = k_0\Vert \cdots \Vert k_t \in \bits^{n(t+1)} by setting E_{k}(x) = k_t \oplus P_t(k_{t-1} \oplus P_{t-1}(\cdots k_1 \oplus P_1(k_0 \oplus x) \cdots)). The indistinguishability of E_k from a truly random permutation by an adversary who also has oracle access to the (public) random permutations P_1, \ldots, P_t was investigated in 1997 by Even and Mansour for t = 1 and for higher values of t in a series of recent papers. For t = 1, Even and Mansour proved indistinguishability security up to 2^{n/2} queries, which is tight. Much later Bogdanov et al$.$ (2011) conjectured that security should be 2^{\frac{t}{t+1}n} queries for general t, which matches an easy distinguishing attack (so security cannot be more) . A number of partial results have been obtained supporting this conjecture, besides Even and Mansour’s original result for t = 1: Bogdanov et al$.$ proved security of 2^{\frac{2}{3}n} for t \geq 2, Steinberger (2012) proved security of 2^{\frac{3}{4}n} for t \geq 3, and Lampe, Patarin and Seurin (2012) proved security of 2^{\frac{t}{t+2}n} for all even values of t, thus “barely” falling short of the desired 2^{\frac{t}{t+1}n}. Our contribution in this work is to prove the long-sought-for security bound of 2^{\frac{t}{t+1}n}, up to a constant multiplicative factor depending on t. Our method is essentially an application of Patarin’s H-coefficient technique. The proof contains some coupling-like and inclusion-exclusion ideas, but the main trick that pushes the computations through is to stick with the combinatorics and to refrain from rounding any quantities too early. For the reader’s interest, we include a self-contained tutorial on the H-coefficient technique.
ePrint: https://eprint.iacr.org/2013/222
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 .