William He: Pseudorandomness Properties of Random Reversible Circuits

CMU Theory Lunch Talk

Speaker: William He
Date: September 25, 2024
Title: Pseudorandomness Properties of Random Reversible Circuits

Abstract: Motivated by cryptography, quantum information theory, circuit complexity, and derandomization, there has been significant recent progress in the study of random permutations resembling a completely random permutation of n-bit strings. Of particular interest is the case where the measure of "resemblance" is approximation of the k-th moments of the matrix representations. Such random permutations are known as approximate k-wise independent permutations.

In this talk I will discuss some recent results that show that small random reversible circuits compute approximate k-wise independent permutations:

i) We show that a random reversible circuit with ~O(nk)
gates computes a constant-approximate k-wise independent permutation. This result implies a generalization of Shannon's circuit lower bound argument.

ii) We show that a random reversible circuit with ~O(nk2)
layers of 1D-local gates arranged in a brickwork architecture computes a exp(−nk)-approximate k-wise independent permutation; connections to block ciphers exist.

Based on joint works with William Gay, Lucas Gretta, Nicholas Kocurek, Ryan O'Donnell, and Angelos Pelecanos.