arXiv:2610.03711
How to Build Pseudorandom Unitaries in Microcrypt
Aditya Gulati, Dakshita Khurana, Kabir Tomer
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.
AI Summary
The paper asks whether pseudorandom unitaries (PRUs) can be constructed without relying on quantum-computable one-way functions, and whether alternating random diagonal phases with Hadamards suffice. It proves that $U=F_5HF_4HF_3HF_2HF_1$, with five independent random phase tables, is indistinguishable from Haar under adaptive, coherently controlled access to $I,U,U^\dagger,U^T,\overline U$. For $N=2^n$ and $t$ queries, the advantage is $O(t^2N^{-1/8})$ when $3(2t)^{16}\le N$. Quantum-query-secure PRFs give a plain-model instantiation. The main result implements the phase tables using a public classical random oracle and proves security against uniform polynomial-time quantum adversaries with coherent access to specially sampled Boolean completions of classical-input $\mathsf{QMA}$ decision problems, also extending to $\mathsf{QMA}(2)$ and $\mathsf{PH}$ access. These decision oracles invert quantum-computable classical-output functions evaluated using the base oracle. This yields a classical-oracle fully black-box separation between strong PRUs and such one-way functions. The proof encodes Haar-style path records in the three central phase tables, with outer layers suppressing endpoint and XOR collisions. Random restrictions and sensitivity bounds for maxima of bounded low-degree polynomials establish verifier-score stability under row replacement; weighted estimates handle correlations created by challenge queries. The separation is not a full oracle separation: inversion does not cover functions evaluated using the added completion or quantum-state challenges. Completion verifiers cannot access the challenge or completion oracles. Replacing the random oracle with public hashes is proposed only heuristically, not proved secure.
We also used AI to draft and revise substantial portions of the manuscript, with input and direction from the authors.
Central claim may not hold: The supplied text omits the appendix specifying and proving the fully black-box separation, leaving its formal model and quantum-computable-function inversion argument unverified. The supplied text omits proofs of essential security estimates, including the core-bit derivative bound needed for security against correlated QMA completion oracles.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.