Pseudorandom Permutations from Random Reversible Circuits

William He, Ryan O'Donnell

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…