Pseudorandomness properties of random reversible circuits

DOI10.1007/978-3-032-01855-7_21MaRDI QIDQ6864031zbMATH OpenFDO

Authors William Gay, William He, Nicholas Kocurek, Ryan O'Donnell

Publication date 4 February 2026

Full work available at URL https://doi.org/10.1007/978-3-032-01855-7_21

zbMATH Keywords

block ciphersinformation-theoretic securityMarkov chains

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Information theory (general) (94A15) Cryptography (94A60)

Cites work

• An Almost m-wise Independent Random Permutation of the Cube
• Analysis of Boolean Functions
• Approximate unitary t-designs by short random quantum circuits using nearest-neighbor and long-range gates
• Black holes as mirrors: quantum information in random subsystems
• Derandomized constructions of \(k\)-wise (almost) independent permutations
• Efficient unitary designs with a system-size independent number of non-Clifford gates
• Explicit near-Ramanujan graphs of every degree
• Explicit orthogonal and unitary designs
• Layout graphs, random walks and the t-wise independence of SPN block ciphers
• Local random quantum circuits are approximate polynomial-designs
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Optimizing quantum process tomography with unitary2-designs
• Simple permutations mix even better
• Simple permutations mix well
• Symmetric groups and expander graphs.
• The \(t\)-wise independence of substitution-permutation networks
• The detectability lemma and quantum gap amplification
• The spectral gap for some spin chains with discrete symmetry breaking
• Theory of Cryptography

Cited in

(1)

• When simple permutations mix poorly. Limited independence does not imply pseudorandomness

This page was built for publication: Pseudorandomness properties of random reversible circuits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6864031)