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,\dots ,P_t:\{0,1{\}}^n\text{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,\dots ,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\ge 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\ge 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 $$ (by Even and Mansour) and for $$ (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.