[Resource Topic] 2024/1795: How Fast Does the Inverse Walk Approximate a Random Permutation?

Welcome to the resource topic for 2024/1795

Title:
How Fast Does the Inverse Walk Approximate a Random Permutation?

Authors: Tianren Liu, Angelos Pelecanos, Stefano Tessaro, Vinod Vaikuntanathan

Abstract:

For a finite field \mathbb{F} of size n, the (patched) inverse permutation \operatorname{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 \operatorname{ARK}_K (for AddRoundKey) permutation adds a fixed constant K to its input, i.e.,
$$\operatorname{INV}(x) = x^{n-2} \hspace{.1in} \mbox{and} \hspace{.1in} \operatorname{ARK}_K(x) = x + K ;.$$
We study the process of alternately applying the \operatorname{INV} permutation followed by a random linear permutation \operatorname{ARK}_K, which is a random walk over the alternating (or symmetric) group that we call the inverse walk.

We show both lower and upper 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^2 n + n\log n\log \frac{1}{\epsilon}\right)$$ rounds generates a permutation that is \epsilon-close (in variation distance) to a uniformly random even permutation (i.e. a permutation from the alternating group A_{n}). This is tight, up to logarithmic factors.

Our result answers an open question from the work of Liu, Pelecanos, Tessaro and Vaikuntanathan (CRYPTO 2023) by providing a missing piece in their proof of t-wise independence of (a variant of) AES. 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 \operatorname{INV} and \operatorname{ARK}. We show a tight convergence result, namely a tight quantitative bound on the number of rounds to reach a random (even) permutation.

ePrint: https://eprint.iacr.org/2024/1795

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .