Paper 2024/1795

How Fast Does the Inverse Walk Approximate a Random Permutation?

Tianren Liu, Peking University
Angelos Pelecanos, University of California, Berkeley
Stefano Tessaro, University of Washington
Vinod Vaikuntanathan, Massachusetts Institute of Technology
Abstract

For a finite field F of size n, the (patched) inverse permutation INV:FF computes the inverse of x over F when x0 and outputs 0 when x=0, and the ARKK (AddRoundKey) permutation adds a fixed constant to its input, i.e., We study the process of alternately applying the permutation followed by a random linear permutation , which is a random walk over the alternating (or symmetric) group that we call the {\em 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 . We show that rounds of the inverse walk over the field of size with rounds generate a permutation that is -close (in variation distance) to a uniformly random even permutation (i.e. a permutation from the alternating group ). Our result is provided with explicit constants, and is tight, up to logarithmic factors. Our result answers an open question from the work of Liu, Pelecanos, Tessaro, and Vaikuntanathan (CRYPTO 2023) by proving the -wise independence of (a variant of) AES for up to the square root of the field size, compared to the original result that only held for . It also constitutes a significant improvement on a result of Carlitz (Proc. American Mathematical Society, 1953) who showed a {\em reachability result}: namely, that every even permutation can be generated {\em eventually} by composing and . We show a {\em 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 an entirely new set of (functional analytic) tools to study their pseudorandomness, both of which we hope will prove useful in the study of block ciphers.

Note: 34 pages.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint.
Keywords
AESinformation theorySubstitution-Permutation Network
Contact author(s)
trl @ pku edu cn
apelecan @ berkeley edu
tessaro @ cs washington edu
vinodv @ mit edu
History
2025-05-16: revised
2024-11-03: received
See all versions
Short URL
https://ia.cr/2024/1795
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1795,
      author = {Tianren Liu and Angelos Pelecanos and Stefano Tessaro and Vinod Vaikuntanathan},
      title = {How Fast Does the Inverse Walk Approximate a Random Permutation?},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1795},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1795}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.