Paper 2012/481

Improved Security Bounds for Key-Alternating 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_{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.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
blockcipher indistinguishability
Contact author(s)
jpsteinb @ gmail com
History
2012-12-07: last of 2 revisions
2012-08-21: received
See all versions
Short URL
https://ia.cr/2012/481
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/481,
      author = {John Steinberger},
      title = {Improved Security Bounds for Key-Alternating 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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.