Paper 2026/2304

Gram Moments and Pairwise Mixing of AES

Abstract

Almost pairwise independence asks how closely a block cipher reproduces the joint output distribution of a random permutation on two distinct plaintexts. Existing analyses of AES with independent round keys combine bounds on the distribution after the first few rounds with contraction over later rounds. Diffusion makes local output differences dependent, and estimating local responses or successive transitions separately can lose useful information. We preserve these dependencies in two ways. First, Gram-moment estimates sum the squared overlaps between local responses whose inputs are linked by diffusion. Second, we estimate two consecutive transitions together. The compatible intermediate differences form affine fibers; summing over these fibers inside the composed operator retains the constraints shared by the two diffusion layers. We prove $\varepsilon_{8+2k}<2^{-92.19-41k}$ for every integer $k\ge0$, where $\varepsilon_r$ is the largest total variation distance, over distinct plaintext pairs, between the ciphertext-pair law and the corresponding random-permutation law. The round keys are independent and uniform, sampled once and reused across evaluations. Consequently, 10, 14, and 16 rounds suffice for statistical accuracy $2^{-128}$, $2^{-192}$, and $2^{-256}$. The same bound controls the complete view of an algorithm making at most two adaptive classical forward queries with an independent finite private seed. The resulting family gives 41 additional bits of pairwise accuracy for every two additional rounds, starting at eight rounds.