Pseudorandomness Properties of Random Reversible Circuits

Motivated by practical concerns in cryptography, we study pseudorandomness properties of permutations on 0,1n computed by random circuits made from reversible 3-bit gates (permutations on 0,13). Our main result is that a random circuit of depth √n · tildeO(k3), with each layer consisting of Theta(n) random gates in a fixed two-dimensional nearest-neighbor architecture, yields approximate k-wise independent permutations. Our result can be seen as a particularly simple/practical block cipher construction that gives provable statistical security against attackers with access to k~input-output pairs within few rounds. The main technical component of our proof consists of two parts: 1. We show that the Markov chain on k-tuples of n-bit strings induced by a single random 3-bit one-dimensional nearest-neighbor gate has spectral gap at least 1/n · tildeO(k). Then we infer that a random circuit with layers of random gates in a fixed one-dimensional gate architecture yields approximate k-wise independent permutations of 0,1n in depth n· tildeO(k2) 2. We show that if the n wires are layed out on a two-dimensional lattice of bits, then repeatedly alternating applications of approximate k-wise independent permutations of 0,1√ n to the rows and columns of the lattice yields an approximate k-wise independent permutation of 0,1n in small depth. Our work improves on the original work of Gowers, who showed a gap of 1/poly(n,k) for one random gate (with non-neighboring inputs); and, on subsequent work improving the gap to Omega(1/n2k) in the same setting.