International Association
for Cryptologic Research

Motivated by practical concerns in cryptography, we study pseudorandomness properties of permutations on $\{0,1\}^n$ computed by random circuits made from reversible $3$-bit gates (permutations on $\{0,1\}^3$). Our main result is that a random circuit of depth $\sqrt{n} \cdot \wt{O}(k^3)$, 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: \begin{enumerate} \item 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 \cdot \wt{O}(k)$. Then we infer that a random circuit with layers of random gates in a fixed \textit{one-dimensional} gate architecture yields approximate $k$-wise independent permutations of $\{0,1\}^n$ in depth $n\cdot \wt{O}(k^2)$ \item We show that if the $n$ wires are layed out on a \textit{two-dimensional} lattice of bits, then repeatedly alternating applications of approximate $k$-wise independent permutations of $\{0,1\}^{\sqrt n}$ to the rows and columns of the lattice yields an approximate $k$-wise independent permutation of $\{0,1\}^n$ in small depth. \end{enumerate} Our work improves on the original work of Gowers~\cite{gowers1996almost}, who showed a gap of $1/\poly(n,k)$ for one random gate (with non-neighboring inputs); and, on subsequent work~\cite{hoory2005simple,brodsky2008simple} improving the gap to $\Omega(1/n^2k)$ in the same setting.