  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 $n \cdot
\tilde{O}(k^2)$, with each layer consisting of $\approx n/3$ random gates in a
fixed nearest-neighbor architecture, yields almost $k$-wise independent
permutations. The main technical component is showing that the Markov chain on
$k$-tuples of $n$-bit strings induced by a single random $3$-bit
nearest-neighbor gate has spectral gap at least $1/n \cdot \tilde{O}(k)$. This
improves on the original work of Gowers [Gowers96], who showed a gap of
$1/\mathrm{poly}(n,k)$ for one random gate (with non-neighboring inputs); and,
on subsequent work [HMMR05,BH08] improving the gap to $\Omega(1/n^2k)$ in the
same setting.
  From the perspective of cryptography, 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. We also show that the Luby--Rackoff construction of
pseudorandom permutations from pseudorandom functions can be implemented with
reversible circuits. From this, we make progress on the complexity of the
Minimum Reversible Circuit Size Problem (MRCSP), showing that block ciphers of
fixed polynomial size are computationally secure against arbitrary
polynomial-time adversaries, assuming the existence of one-way functions
(OWFs).
