Improved Security Bounds for Key-Alternating Ciphers via Hellinger Distance.
John P. Steinberger · 2012
At-roundkey alternating cipher canbeviewedasanabstractionofAES.ItdefinesacipherE from t fixed public permutations P1,...,Pt: {0,1} n → {0,1} n and a key k = k0‖···‖kt ∈ {0,1} n(t+1) by setting Ek(x) = kt ⊕ Pt(kt−1 ⊕ Pt−1(···k1 ⊕ P1(k0 ⊕ x)···)). The indistinguishability of Ek from a random truly random permutation by an adversary who also has oracle access to the (public) random permutations P1,...,Pt was investigated for t = 2 by Even and Mansour [5] and, much later, by Bogdanov et al. [1]. The former proved indistinguishability up to 2n/2 queries for t = 1 while the latter proved indistinguishability up to 22n/3 queries for t ≥ 2 (ignoring low-order terms). Our contribution is to improve the analysis of Bogdanov et al. by showing security up to 23n/4 queries for t ≥ 3. Given that security cannot exceed 2 t t+1n 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 sample distinguishability game introduced by Bogdanov et al. [1]. 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.