REVIEW 3 major objections 3 minor 29 references
Pseudorandomness Properties of Random Reversible Circuits
T0 review · 3 major / 3 minor · reviewed 2026-08-08 · deepseek-v4-flash
Pith's one-line read This paper proves that random reversible circuits with a fixed two-dimensional nearest-neighbour architecture become approximate $k$-wise independent permutations in depth $\sqrt{n}\,e^{O(k^3)}$, giving a simple block-cipher construction…
desk verdict The 1D spectral gap result is real and interesting, but the 2D row-column construction has a fatal flaw: it preserves row-color classes, so Lemma 79 is false and Theorem 2 collapses. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is the spectral gap of the Markov chain on $k$-tuples of $n$-bit strings induced by one random reversible 3-bit gate, together with the detectability lemma from Hamiltonian complexity that lifts a one-gate spectral gap to a whole brickwork layer. The single nearest-neighbour gate has gap $1/(n\,e^{O(k)})$ (Theorem 8), the layer lifting gives gap at least $1/e^{O(k)}$ (Theorem 9), and mixing-time bounds convert that gap into circuit depth. For the two-dimensional result, the machinery is the alternating row-column operator $T_{P_R}(T_{P_C}T_{P_R})^t$ compared with the idealized operator $T_{G_R}(T_{G_C}T_{G_R})^t$, analysed by colour classes of $k$-tuples of grids and by escape probabilities from the 'collision' colour class.
What would settle it
Enumerate the one-layer brickwork random-walk operator's connected component for a small case such as $n = 15$, $k = 3$ and compute its second eigenvalue by exact diagonalization; if the spectral gap decays with $n$ rather than staying above $c/e^{O(k)}$, the layer-lifting claim (Theorem 9) is false. A cheaper check is to verify the operator-norm hypothesis of the Nachtergaele-type lifting, the bound in Theorem 29, for $m = 100$, $k = 4$, $\ell = 10\log k$ by direct computation, or to count non-commuting gate pairs in a layer and see whether any layer forces a gate to overlap many others.
Extended reading notes
Core claim
The central claim is Theorem 2: for $k \le 2^{O(\sqrt{n})}$, there is a class of random reversible circuits with a fixed gate architecture on a two-dimensional lattice that computes permutations which are $2^{-\sqrt{n}\,k}$-approximate $k$-wise independent, at depth $\sqrt{n}\,e^{O(k^3)}$. The proof has two parts. First, a single random nearest-neighbour 3-bit DES[2] gate induces a Markov chain on $k$-tuples of $n$-bit strings with spectral gap at least $1/(n\,e^{O(k)})$; the detectability lemma converts this into a $1/e^{O(k)}$ spectral gap for one full brickwork layer, yielding one-dimensional brickwork circuits of depth $n\,e^{O(k^2)}$ with error $2^{-nk}$. Second, an alternating row/column construction takes any such one-dimensional family on $\sqrt{n}$-bit strings and produces a two-dimensional permutation on $n$-bit strings with depth $\sqrt{n}\,e^{O(k^3)}$, by comparing the real circuit operator to an idealized fully random row/column operator and analysing colour classes of $k$-tuples of grids. The entire construction continues to work when every gate is of type DES[2].
Load-bearing premise
The load-bearing assumption is that one brickwork layer can be written as two products of commuting gates with each gate commuting with all but a constant number of other gates; if the fixed architecture ever forced a gate to interact with many others, the detectability step would incur an exponential-in-$n$ penalty and the claimed $\sqrt{n}\,e^{O(k^3)}$ depth would not follow.
Editorial extensions
If this is right
- There is a fixed-architecture block cipher using only DES[2] gates whose statistical advantage against any non-adaptive $k$-query distinguisher is at most $2^{-\sqrt{n}\,k}$ after $\sqrt{n}\,e^{O(k^3)}$ rounds.
- Setting $k = 4$ gives sublinear-depth circuits that resist higher-order differential attacks, and would become computationally secure pseudorandom permutations if the conjecture from [HMMR05] holds.
- The one-dimensional construction improves the prior nearest-neighbour bound from circuit size about $n^4k^2$ to depth $n\,e^{O(k^2)}$ with error $2^{-nk}$.
- The construction extends to $D$-dimensional lattices for $D$ up to $O(\log n/\log\log n)$, with depth $\exp(D)\,n^{1/D}\,e^{O(k^3)}$ and error $2^{-n^{1/D}}$, matching the light-cone lower bound up to $k$-dependent factors.
Reading between the lines
- A natural implementation step is to apply derandomized squaring to this construction, reducing the seed length to $O(nk)$ bits; the paper mentions this route but does not develop it, so its practical cost is a testable open question.
- Composing two independent draws, with the second inverted, should upgrade the statistical guarantee from non-adaptive to adaptive attackers via the Maurer-Pietrzak composition theorem, which is not stated as a theorem here.
- The colour-class and escape-probability analysis suggests that the $k^3$ exponent in the depth is the main practical bottleneck, so a focused numerical study of the one-layer spectral gap for small $k$ and moderate $n$ could calibrate whether sublinear depth is already sufficient at realistic block sizes.
- Because the gate set is fixed to nearest-neighbour DES[2] gates, the circuit family is a concrete candidate for hardware evaluation; a testable extension is whether the $k = 4$ case resists known algebraic and integral attacks beyond the proven statistical guarantees.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies random reversible circuits made of 3-bit permutations, with a focus on brickwork architectures on low-dimensional lattices. Its headline claim (Theorem 2) is that a fixed two-dimensional nearest-neighbor architecture yields 2^{-O(√n k)}-approximate k-wise independent permutations in depth √n · e^{O(k^3)}. The proof is split into a one-dimensional spectral-gap analysis (Theorems 3, 8, 9), which is claimed to give depth n · e^{O(k^2)} for 1D brickwork circuits, and a two-dimensional reduction (Theorem 4) that alternates row and column applications of such 1D circuits. The one-dimensional part is a substantial technical contribution, but the two-dimensional reduction is invalid: the row/column construction preserves the row-equality pattern of the k input grids, so the induced Markov chain is not irreducible on the set of distinct k-tuples. The claimed mixing bound for the idealized row/column process is therefore false, and Theorem 2 collapses.
Significance. If the main theorem were correct, it would be a significant step toward practical block ciphers with provable statistical security against non-adaptive k-query attacks, extending the line of work initiated by Gowers and continued by Brodsky–Hoory. The one-dimensional spectral-gap result (Theorem 8) is a genuine and interesting contribution: it improves the gate-locality regime to nearest-neighbor 1D brickwork circuits with a gap of 1/(n e^{O(k)}), and the proof uses nonstandard tools (Nachtergaele's method and the detectability lemma) in a way that appears internally coherent. However, the central two-dimensional construction, which is the paper's advertised main result, does not mix across row-color classes. Since the reduction in Theorem 4 is load-bearing for Theorem 2 and is not a local repair but a flaw in the construction itself, the paper's principal claim is not established.
major comments (3)
- [§7.1.2 and §7.5 (Lemma 79 / Lemma 84)] The row/column construction preserves every row-equivalence color class exactly. In the notation of Section 7.1.2, each row permutation π ∈ GR applies the same bijection σ_i to the i-th row of each of the k grids, and each column permutation applies the same bijection to each row. Consequently, for every i and every pair ℓ ≠ m, the predicate X^ℓ_{i,·} = X^m_{i,·} is invariant under both TGR and TGC. Thus Bsafe and Bcoll are closed sets for every operator appearing in P_t and G_t. Lemma 84 asserts that for every X ∈ D, Pr[X → TGC TGR Bcoll] ≤ 2√n k^2 / 2^{√n/16}, but for X ∈ Bcoll this probability is exactly 1 because Bcoll is closed. The proof of Lemma 84 only considers pairs ℓ,m that are not already equal in a row; it does not handle pairs that enter the process with a row collision, and such collisions are never removed. This invalidates Lemma 79, which is used in the inductive proof of Lemma 77 and hence in Lemma 73.
- [§7.3 (Theorem 71 and Lemma 73)] Because Bcoll is closed under both the real circuit operator TP_t and the idealized operator TG_t, the Markov chain is not irreducible on D. For any X ∈ Bcoll, the distribution of P_t(X) is supported on Bcoll, while the uniform distribution on D has mass |Bcoll|/|D| ≤ 2√n k^2 / 2^{√n} by Fact 66. Hence dTV(P_t(X), G_X) ≥ 1 − |Bcoll|/|D|, which tends to 1 for the parameter ranges claimed in Theorem 2. For example, when k = 2 and the two input grids differ in a single cell, the output distribution remains in a color class of size roughly 2^{n+√n} while |D| ≈ 2^{2n}, so the TV distance to uniform is ≈ 1. This contradicts the claimed 2^{-√n k} bound. The failure is not a missing technical lemma: even the idealized row/column process G_t has the same invariant, so Lemma 73's claim that G_t mixes in t = O(k log k) rounds is false for inputs in Bcoll.
- [§1, Theorem 4 and Appendix B] The higher-dimensional generalization in Theorem 5 inherits the same flaw. The induction in Appendix B defines P_{D'} by alternating permutations acting on (D'−1)-dimensional slices and on 1-dimensional columns; both types of operations apply the same permutation to each of the k grids, so every equality pattern among the k grids is preserved. In particular, the analogue of Bcoll is closed for every D' ≥ 2. The generalization therefore cannot be correct as stated, and the stated depth exp(D) · n^{1/D} e^{O(k^3)} for D-dimensional lattices is unsupported for the same reason as in the 2D case.
minor comments (3)
- [Abstract and §1] The phrase “layed out” in the abstract and in Section 1 is a typo for “laid out”.
- [Throughout] The notation e^{O(k)} is used without an explicit definition; the paper should state that it suppresses absolute constants, and similarly for the tilde notation in the abstract.
- [§1.4 and References] The discussion of subsequent work cites [GHP24] and [CHH+24] but does not always make clear which parameter regimes are incomparable; a short table of size/depth versus k, n, ε would improve readability.
Circularity Check
No circularity: the 1D spectral-gap proof is self-contained, and Theorem 4 is a conditional reduction that instantiates an assumed 1D object rather than assuming the 2D conclusion.
full rationale
The derivation chain is not circular. Theorem 2 follows from Theorem 3 (1D brickwork circuits) and Theorem 4 (2D reduction). Theorem 3 is proved from the brickwork spectral gap (Theorem 9) via standard Markov-chain mixing; Theorem 9 follows from the single-gate spectral gap (Theorem 8) via the external detectability lemma [BHH16, Section 4.A]. Theorem 8 is proved in-paper from Corollary 34, which combines the comparison method (Lemma 33, proved in Appendix A from the standard theorem [WLP09, Theorem 13.23]) with the external result Theorem 24 ([BH08]) and the in-paper Theorem 29. No fitted constants or data-dependent parameters appear anywhere; the approximate k-wise independence error is an analytically proved bound, not a fitted quantity. Theorem 4 is explicitly conditional: 'Suppose there exists a random reversible circuit with a fixed one-dimensional gate architecture that is 2^{-nk}-approximate k-wise independent. Then there exists a class of random reversible circuits ... on a two-dimensional lattice ...' This is a black-box reduction, not circularity: the assumed 1D object is strictly simpler than the 2D conclusion, and the 1D object is independently constructed in Theorem 3. The only self-citations are Lemma 26 ([OSP23], O'Donnell is an author) used in the secondary fully-random-gate Corollary 27, and the acknowledgment that the comparison-method appendix reuses arguments from [GHP24], which includes coauthor He. Both are standard linear-algebra/comparison lemmas, used as tools, not as restatements of the target k-wise-independence results, and neither is load-bearing for the main Theorem 2. The reader's flagged color-class invariance concern (that row/column permutations preserve row-equality patterns, so Lemma 79 may be false) is a mathematical correctness risk about Theorem 4, not a circularity: if valid, it would falsify the claimed mixing bound rather than reduce the theorem to its own inputs. Accordingly, the paper shows no significant circularity.
Assumptions & free parameters
assumptions (7)
- standard math Fourier characters of {+-1}^{nk} form an orthogonal basis (Fact 20).
- standard math Comparison method for Markov chains (Theorem 88 from WLP09) and its multigraph variant (Lemma 32).
- standard math Base spectral gap of Brodsky and Hoory (Theorem 24): for fully random m-bit resampling, the gap is Omega(1/(m^2 k)).
- standard math Nachtergaele spectral gap theorem (Theorem 28) for one-dimensional chains of projectors.
- standard math Detectability lemma from Aharonov et al., as stated in BHH16 Section 4.A.
- standard math Hoeffding's inequality and the sampling-without-replacement versus sampling-with-replacement bound of Fact 22.
- domain assumption The circuit model: each 3-bit gate is drawn independently and uniformly from the allowed gate set, with fixed nearest-neighbor positions on a 1D or 2D lattice.
Cite this review
Pith. "Pith review of Pseudorandomness Properties of Random Reversible Circuits." pith.science (2026). https://pith.science/paper/3IMIRKHP
@misc{pith2026250207159,
author = {Pith},
title = {Pith review of: Pseudorandomness Properties of Random Reversible Circuits},
year = {2026},
howpublished = {\url{https://pith.science/paper/3IMIRKHP}},
note = {Machine review of arXiv:2502.07159}
}
abstract
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 \tilde{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: 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 \cdot \tilde{O}(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,1\}^n$ in depth $n\cdot \tilde{O}(k^2)$ 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\}^{\sqrt n}$ to the rows and columns of the lattice yields an approximate $k$-wise independent permutation of $\{0,1\}^n$ in small depth. Our work improves on the original work of Gowers, who showed a gap of $1/\mathrm{poly}(n,k)$ for one random gate (with non-neighboring inputs); and, on subsequent work improving the gap to $\Omega(1/n^2k)$ in the same setting.
Figures
Reference graph
Works this paper leans on
-
[2]
Simple Permutations Mix Even Better
Alex Brodsky and Shlomo Hoory. Simple Permutations Mix Even Better . Random Structures & Algorithms , 32(3):274--289, 2008
work page 2008
-
[1]
The Detectability Lemma and Quantum Gap Amplification
Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. The Detectability Lemma and Quantum Gap Amplification . In Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing , pages 417--426, 2009
work page 2009
-
[3]
Fernando G.S.L. Brandao, Aram W. Harrow, and Micha Horodecki. Local Random Quantum Circuits are Approximate Polynomial-Designs . Communications in Mathematical Physics , 346:397--434, 2016
work page 2016
-
[4]
Efficient Unitary T-designs from Random Sums
Chi-Fang Chen, Jordan Docter, Michelle Xu, Adam Bouland, and Patrick Hayden. Efficient Unitary T-designs from Random Sums . arXiv preprint arXiv:2402.09335 , 2024
work page Pith review arXiv 2024
-
[5]
Incompressibility and spectral gaps of random circuits
Chi-Fang Chen, Jeongwan Haah, Jonas Haferkamp, Yunchao Liu, Tony Metger, and Xinyu Tan. Incompressibility and spectral gaps of random circuits. arXiv preprint arXiv:2406.07478 , 2024
arXiv 2024
-
[6]
Exact and approximate unitary 2-designs and their application to fidelity estimation
Christoph Dankert, Richard Cleve, Joseph Emerson, and Etera Livine. Exact and approximate unitary 2-designs and their application to fidelity estimation. Physical Review A—Atomic, Molecular, and Optical Physics , 80(1):012304, 2009
work page 2009
-
[7]
Dynamics of Pseudoentanglement
Xiaozhou Feng and Matteo Ippoliti. Dynamics of pseudoentanglement. arXiv preprint arXiv:2403.09619 , 2024
work page Pith review arXiv 2024
-
[8]
Lucas Gretta, William He, and Angelos Pelecanos. More efficient approximate k -wise independent permutations from random reversible circuits via log-sobolev inequalities. Cryptology ePrint Archive , 2024
work page 2024
Show all 29 references
-
[9]
W.T. Gowers. An Almost m-wise Independent Random Permutation of the Cube . Combinatorics, Probability and Computing , 5(2):119--130, 1996
1996
-
[10]
Improved Spectral Gaps for Random Quantum Circuits: Large Local Dimensions and All-to-All Interactions
Jonas Haferkamp and Nicholas Hunter-Jones. Improved Spectral Gaps for Random Quantum Circuits: Large Local Dimensions and All-to-All Interactions . Physical Review A , 104(2):022417, 2021
2021
-
[11]
Unitary Designs from Statistical Mechanics in Random Quantum Circuits
Nicholas Hunter-Jones. Unitary Designs from Statistical Mechanics in Random Quantum Circuits . arXiv preprint arXiv:1905.12053 , 2019
1905 arXiv
-
[12]
Predicting many properties of a quantum system from very few measurements
Hsin-Yuan Huang, Richard Kueng, and John Preskill. Predicting many properties of a quantum system from very few measurements. Nature Physics , 16(10):1050--1057, 2020
2020
-
[13]
Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates
Aram W Harrow and Saeed Mehraban. Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates. Communications in Mathematical Physics , 401(2):1531--1626, 2023
2023
-
[14]
Efficient Unitary Designs with a System-Size Independent Number of non-Clifford Gates
Jonas Haferkamp, Felipe Montealegre-Mora, Markus Heinrich, Jens Eisert, David Gross, and Ingo Roth. Efficient Unitary Designs with a System-Size Independent Number of non-Clifford Gates . Communications in Mathematical Physics , 397(3):995--1041, 2023
2023
-
[15]
Simple Permutations Mix Well
Shlomo Hoory, Avner Magen, Steven Myers, and Charles Rackoff. Simple Permutations Mix Well . Theoretical Computer Science , 348(2-3):251--261, 2005
2005
-
[16]
Black Holes as Mirrors: Quantum Information in Random Subsystems
Patrick Hayden and John Preskill. Black Holes as Mirrors: Quantum Information in Random Subsystems . Journal of High Energy Physics , 2007(09):120, 2007
2007
-
[17]
Symmetric Groups and Expander Graphs
Martin Kassabov. Symmetric Groups and Expander Graphs . Inventiones Mathematicae , 170(2):327--354, 2007
2007
-
[18]
Derandomized Constructions of k-wise (almost) Independent Permutations
Eyal Kaplan, Moni Naor, and Omer Reingold. Derandomized Constructions of k-wise (almost) Independent Permutations . Algorithmica , 55(1):113--133, 2009
2009
-
[19]
Layout Graphs, Random Walks and the t-Wise Independence of SPN Block Ciphers
Tianren Liu, Angelos Pelecanos, Stefano Tessaro, and Vinod Vaikuntanathan. Layout Graphs, Random Walks and the t-Wise Independence of SPN Block Ciphers . In Annual International Cryptology Conference , pages 694--726. Springer, 2023
2023
-
[20]
The t-wise independence of substitution-permutation networks
Tianren Liu, Stefano Tessaro, and Vinod Vaikuntanathan. The t-wise independence of substitution-permutation networks. In Advances in Cryptology--CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16--20, 2021, Proceedings, Part IV ...
2021
-
[21]
How to construct random unitaries
Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. arXiv preprint arXiv:2410.10116 , 2024
2024 arXiv
-
[22]
Explicit Near-Ramanujan Graphs of Every Degree
Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes. Explicit Near-Ramanujan Graphs of Every Degree . In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing , pages 510--523, 2020
2020
-
[23]
Composition of Random Systems: When Two Weak Make One Strong
Ueli Maurer and Krzysztof Pietrzak. Composition of Random Systems: When Two Weak Make One Strong . In Theory of Cryptography Conference , pages 410--427. Springer, 2004
2004
-
[24]
Simple constructions of linear-depth t-designs and pseudorandom unitaries
Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Simple constructions of linear-depth t-designs and pseudorandom unitaries. arXiv preprint arXiv:2404.12647 , 2024
2024 arXiv
-
[25]
The Spectral Gap for Some Spin Chains with Discrete Symmetry Breaking
Bruno Nachtergaele. The Spectral Gap for Some Spin Chains with Discrete Symmetry Breaking . Communications in Mathematical Physics , 175:565--606, 1996
1996
-
[26]
Analysis of B oolean F unctions
Ryan O'Donnell. Analysis of B oolean F unctions . Cambridge University Press, 2014
2014
-
[27]
Servedio, and Pedro Paredes
Ryan O’Donnell, Rocco A. Servedio, and Pedro Paredes. Explicit Orthogonal and Unitary Designs . In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) , pages 1240--1260. IEEE, 2023
2023
-
[28]
Optimizing quantum process tomography with unitary 2-designs
Andrew James Scott. Optimizing quantum process tomography with unitary 2-designs. Journal of Physics A: Mathematical and Theoretical , 41(5):055308, 2008
2008
-
[29]
Wilmer, David A
E.L. Wilmer, David A. Levin, and Yuval Peres. Markov Chains and Mixing Times . American Mathematical Soc., Providence , 2009
2009
Reviewed August 8, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.