Paper 2024/1795

How Fast Does the Inverse Walk Approximate a Random Permutation?

Abstract

For a finite field $\mathbb{F}$ of size $n$, the (patched) inverse permutation $\mathrm{INV}: \mathbb{F} \to \mathbb{F}$ computes the inverse of $x$ over $\mathbb{F}$ when $x\neq 0$ and outputs $0$ when $x=0$, and the $\mathrm{ARK}_K$ (AddRoundKey) permutation adds a fixed constant $K$ to its input, i.e., $$\mathrm{INV}(x) = x^{n-2} \hspace{.1in} \mbox{and} \hspace{.1in} \mathrm{ARK}_K(x) = x + K \;.$$ We study the process of alternately applying the $\mathrm{INV}$ permutation followed by a random linear permutation $\mathrm{ARK}_K$, which is a random walk over the alternating (or symmetric) group that we call the inverse walk. We show matching upper and lower bounds on the number of rounds it takes for this process to approximate a random permutation over $\mathbb{F}$. We show that $r$ rounds of the inverse walk over the field of size $n$ with $$r = \Theta\left(n\log n + n\log \frac{1}{\epsilon}\right)$$rounds generate a permutation that is $\epsilon$-close (in total variation distance) to a uniformly random permutation of the appropriate sign. Our bound on $r$ is optimal, up to a constant. In fact, we prove stronger lower bounds showing that the inverse walk needs at least $t = \Omega(n \log(1/\epsilon))$ rounds to become $\epsilon$-approximately $4$-wise independent and at least $s = \Omega(n\log n)$ rounds to get to within $(1-o_n(1))$ in total variation distance of a given $4$-wise independent permutation. Our result answers an open question from the work of Liu, Pelecanos, Tessaro, and Vaikuntanathan (CRYPTO 2023) by proving the $t$-wise independence of (a variant of) AES for $t$ up to the square root of the field size, compared to the original result that only held for $t=2$. It also constitutes a significant improvement on a result of Carlitz (Proc. American Mathematical Society, 1953) who showed a reachability result: namely, that every even permutation can be generated eventually by composing $\mathrm{INV}$ and $\mathrm{ARK}$. We show a tight convergence result, namely a tight quantitative bound on the number of rounds to reach a random (even) permutation. Our work brings to the forefront the view of block ciphers as random walks and uses novel combinatorial and analytic tools to study their pseudorandomness, both of which we hope will prove useful in the study of block ciphers.

Note: 31 pages. This version corrects an error inherited from a reference and contains matching upper and lower bounds.