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 \widetilde{O}(k^3)\) , with each layer consisting of \(\varTheta (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: Our work improves on the original work of Gowers [8], who showed a gap of \(1/\textrm{poly}(n,k)\) for one random gate (with non-neighboring inputs); and, on subsequent work [3, 14] improving the gap to \(\varOmega (1/n^2k)\) in the same setting.