Welcome to the resource topic for 2012/481
Title:
Improved Security Bounds for Key-Alternating Ciphers via Hellinger Distance
Authors: John Steinberger
Abstract:A t-round key alternating cipher can be viewed as an abstraction of AES. It defines a cipher E from t fixed public permutations P_1, \ldots, P_t : \{0,1\}^n \ra \{0,1\}^n and a key k = k_0\Vert \cdots \Vert k_t \in \{0,1\}^{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 random truly random permutation by an adversary who also has oracle access to the (public) random permutations P_1, \ldots, P_t was investigated for t = 2 by Even and Mansour and, much later, by Bogdanov et al. The former proved indistinguishability up to 2^{n/2} queries for t = 1 while the latter proved indistinguishability up to 2^{2n/3} queries for t \geq 2 (ignoring low-order terms). Our contribution is to improve the analysis of Bogdanov et al$.$ by showing security up to 2^{3n/4} queries for t \geq 3. Given that security cannot exceed 2^{\frac{t}{t+1}n} queries, this is in particular achieves a tight bound for the case t = 3, whereas, previously, tight bounds had only been achieved for t = 1 (by Even and Mansour) and for t = 2 (by Bogdanov et al$.$). Our main technique is an improved analysis of the elegant \emph{sample distinguishability} game introduced by Bogdanov et al. More specifically, we succeed in eliminating adaptivity by considering the Hellinger advantage of an adversary, a notion that we introduce here. To our knowledge, our result constitutes the first time Hellinger distance (a standard measure of ``distance’’ between random variables, and a cousin of statistical distance) is used in a cryptographic indistinguishability proof.
ePrint: https://eprint.iacr.org/2012/481
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 .