Pseudorandomness Properties of Random Reversible Circuits

• URL: http://arxiv.org/abs/2502.07159v1
• Date: Tue, 11 Feb 2025 00:54:24 GMT
• Title: Pseudorandomness Properties of Random Reversible Circuits
• Authors: William Gay, William He, Nicholas Kocurek, Ryan O'Donnell,
• Abstract summary: We show that a random circuit of depth $sqrtn cdot tildeO(k3)$, 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.
• Score: 1.593690982728631
• License:
• 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.

Related papers

• The Communication Complexity of Approximating Matrix Rank [50.6867896228563]
  We show that this problem has randomized communication complexity $Omega(frac1kcdot n2log|mathbbF|)$. As an application, we obtain an $Omega(frac1kcdot n2log|mathbbF|)$ space lower bound for any streaming algorithm with $k$ passes.
  arXiv  Detail & Related papers  (2024-10-26T06:21:42Z)
• Incompressibility and spectral gaps of random circuits [2.359282907257055]
  reversible and quantum circuits form random walks on the alternating group $mathrmAlt (2n)$ and unitary group $mathrmSU (2n)$, respectively. We prove that the gap for random reversible circuits is $Omega(n-3)$ for all $tgeq 1$, and the gap for random quantum circuits is $Omega(n-3)$ for $t leq Theta(2n/2)$.
  arXiv  Detail & Related papers  (2024-06-11T17:23:16Z)
• Efficient unitary designs and pseudorandom unitaries from permutations [35.66857288673615]
  We show that products exponentiated sums of $S(N)$ permutations with random phases match the first $2Omega(n)$ moments of the Haar measure. The heart of our proof is a conceptual connection between the large dimension (large-$N$) expansion in random matrix theory and the method.
  arXiv  Detail & Related papers  (2024-04-25T17:08:34Z)
• Pseudorandom Permutations from Random Reversible Circuits [1.9567015559455132]
  We show that a random circuit of depth $n cdot tildeO(k2)$, with each layer consisting of $approx n/3$ random gates in a fixed nearest-neighbor architecture, yields almost $k$-wise independent permutations. We also show that the Luby-Rack-off construction of pseudorandom permutations from pseudorandom functions can be implemented with reversible circuits.
  arXiv  Detail & Related papers  (2024-04-23T00:50:57Z)
• On the average-case complexity of learning output distributions of quantum circuits [55.37943886895049]
  We show that learning the output distributions of brickwork random quantum circuits is average-case hard in the statistical query model. This learning model is widely used as an abstract computational model for most generic learning algorithms.
  arXiv  Detail & Related papers  (2023-05-09T20:53:27Z)
• On the moments of random quantum circuits and robust quantum complexity [0.0]
  We prove new lower bounds on the growth of robust quantum circuit complexity. We show two bounds for random quantum circuits with local gates drawn from a subgroup of $SU(4)$.
  arXiv  Detail & Related papers  (2023-03-29T18:06:03Z)
• Random matrices in service of ML footprint: ternary random features with no performance loss [55.30329197651178]
  We show that the eigenspectrum of $bf K$ is independent of the distribution of the i.i.d. entries of $bf w$. We propose a novel random technique, called Ternary Random Feature (TRF) The computation of the proposed random features requires no multiplication and a factor of $b$ less bits for storage compared to classical random features.
  arXiv  Detail & Related papers  (2021-10-05T09:33:49Z)
• An Algorithm for Reversible Logic Circuit Synthesis Based on Tensor Decomposition [0.0]
  An algorithm for reversible logic synthesis is proposed. Map can be written as a tensor product of a rank-($2n-2$) tensor and the $2times 2$ identity matrix.
  arXiv  Detail & Related papers  (2021-07-09T08:18:53Z)
• Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample Complexity [59.34067736545355]
  Given an MDP with $S$ states, $A$ actions, the discount factor $gamma in (0,1)$, and an approximation threshold $epsilon > 0$, we provide a model-free algorithm to learn an $epsilon$-optimal policy. For small enough $epsilon$, we show an improved algorithm with sample complexity.
  arXiv  Detail & Related papers  (2020-06-06T13:34:41Z)
• A Randomized Algorithm to Reduce the Support of Discrete Measures [79.55586575988292]
  Given a discrete probability measure supported on $N$ atoms and a set of $n$ real-valued functions, there exists a probability measure that is supported on a subset of $n+1$ of the original $N$ atoms. We give a simple geometric characterization of barycenters via negative cones and derive a randomized algorithm that computes this new measure by "greedy geometric sampling" We then study its properties, and benchmark it on synthetic and real-world data to show that it can be very beneficial in the $Ngg n$ regime.
  arXiv  Detail & Related papers  (2020-06-02T16:38:36Z)
• Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness [151.67113334248464]
  We show that extending the smoothing technique to defend against other attack models can be challenging. We present experimental results on CIFAR to validate our theory.
  arXiv  Detail & Related papers  (2020-02-08T22:02:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.