aiqbench analysis
This research establishes a significant theoretical separation in quantum cryptography by proving that pseudorandom unitaries can exist even without quantum-computable one-way functions. The authors demonstrate this using a specific circuit construction involving diagonal phase layers and Hadamard transforms, securing it against powerful adversaries capable of solving classical-input QMA problems. This finding clarifies the foundational assumptions required for secure quantum protocols and challenges previous beliefs linking PRUs directly to the existence of quantum one-way functions.
How to Build Pseudorandom Unitaries in Microcrypt
arXiv:2610.03711v1 Announce Type: new Abstract: We provide the first evidence relative to a classical oracle that pseudorandom unitaries (PRUs) can exist without quantum-computable one-way functions. To obtain this result, we first prove that five independent random diagonal phase layers interleaved with Hadamard transforms \[ U=F_5HF_4HF_3HF_2HF_1 \] form a strong PRU with security under adaptive, controlled access to the unitary, its inverse, transpose, and complex conjugate. Our main result is that, when the phase layers are implemented using a classical random oracle O, the construction remains secure against uniform BQP adversaries with coherent access to suitable Boolean completions of classical-input $QMA^{PH}^{O}}$ decision problems. Such an adversary can invert (even quantum-computable) one-way functions and solve efficiently verifiable one-way puzzles defined relative to O. Our result therefore provides classical-oracle evidence that PRUs do not imply quantum-computable one-way functions, in the form of a black-box separation. We substantially strengthen the classical-oracle result of Kretschmer, Qian, and Tal (STOC 2025) by obtaining PRUs secure against these QMA-aided adversaries. Our construction also consists of a simple, efficient circuit that queries a random function, suggesting a route to concrete implementation via the random-oracle heuristic.
Abstract:We provide the first evidence relative to a classical oracle that pseudorandom unitaries (PRUs) can exist without quantum-computable one-way functions. To obtain this result, we first prove that five independent random diagonal phase layers interleaved with Hadamard transforms \[ U=F_5HF_4HF_3HF_2HF_1 \] form a strong PRU with security under adaptive, controlled access to the unitary, its inverse, transpose, and complex conjugate. Our main result is that, when the phase layers are implemented using a classical random oracle O, the construction remains secure against uniform BQP adversaries with coherent access to suitable Boolean completions of classical-input $QMA^{PH}^{O}}$ decision problems. Such an adversary can invert (even quantum-computable) one-way functions and solve efficiently verifiable one-way puzzles defined relative to O. Our result therefore provides classical-oracle evidence that PRUs do not imply quantum-computable one-way functions, in the form of a black-box separation. We substantially strengthen the classical-oracle result of Kretschmer, Qian, and Tal (STOC 2025) by obtaining PRUs secure against these QMA-aided adversaries. Our construction also consists of a simple, efficient circuit that queries a random function, suggesting a route to concrete implementation via the random-oracle heuristic.
arXiv:2610.03711 [quant-ph]
(or arXiv:2610.03711v1 [quant-ph] for this version)
https://doi.org/10.48550/arXiv.2610.03711 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 273 words
Related coverage
How Not to Build Microcrypt
arXiv · Sep 25, 2026
Quantum Designs Fail to Guarantee Randomness after Just Hundreds of Steps
Quantum Zeitgeist · Oct 2, 2026
Quantum States Imply One-Way Functions, Blocking Route to Microcrypt Security
Quantum Zeitgeist · Sep 17, 2026
Quantum Lazy Sampling and Path Recording for Any Group
arXiv · Oct 1, 2026