Paper 2012/481
Improved Security Bounds for KeyAlternating Ciphers via Hellinger Distance
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_{t1} \oplus P_{t1}(\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 loworder 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.
Metadata
 Available format(s)
 Category
 Secretkey cryptography
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 blockcipher indistinguishability
 Contact author(s)
 jpsteinb @ gmail com
 History
 20121207: last of 2 revisions
 20120821: received
 See all versions
 Short URL
 https://ia.cr/2012/481
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/481, author = {John Steinberger}, title = {Improved Security Bounds for KeyAlternating Ciphers via Hellinger Distance}, howpublished = {Cryptology ePrint Archive, Paper 2012/481}, year = {2012}, note = {\url{https://eprint.iacr.org/2012/481}}, url = {https://eprint.iacr.org/2012/481} }