How to Build Pseudorandom Unitaries in Microcrypt
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=F5HF4HF3HF2HF1 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 QMAPHO 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.
Related
- Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States
- Function-like pseudorandom unitaries generate pseudorandom quantum processes
- How Not to Build Microcrypt
- Distinctness threshold for pseudorandom unitaries
- Instantiating Microcrypt: Obstacles and opportunities via tailored state certification
BibTeX
@misc{gulati2026build,
title = {{How to Build Pseudorandom Unitaries in Microcrypt}},
author = {Aditya Gulati and Dakshita Khurana and Kabir Tomer},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.03711},
eprint = {2610.03711},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.03711},
}
RIS
TY - UNPB
TI - How to Build Pseudorandom Unitaries in Microcrypt
AU - Aditya Gulati
AU - Dakshita Khurana
AU - Kabir Tomer
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.03711
UR - https://arxiv.org/abs/2610.03711
AB - 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.
ER -