WorksPhysics and Astronomy
Birthday-Scale Non-Adaptive Security for Strong Pseudorandom Unitaries
Abstract
Pseudorandom unitaries (PRUs) are efficiently implementable unitary ensembles that are computationally indistinguishable from Haar-random unitaries, providing efficient substitutes for Haar-randomness in quantum information and cryptography. Strong PRUs require this indistinguishability to hold even when the adversary is given access to all of , , , and . In this work, we prove birthday-scale non-adaptive security for the DPFC (Clifford-Phase-Permutation-Clifford) strong PRU candidate. For an -dimensional unitary, allowing arbitrary entangled inputs and coherent superpositions of query types, we show that DPFC can withstand queries. This matches the best known query complexity even for PRUs that are not strong, compared with for in previous strong-PRU analyses. Our proof utilizes two techniques from previous works: the EPR-sector decomposition of Schuster et al. (arXiv 2025), previously used for unitary designs but not for PRUs, and the path-recording framework of Ma and Huang (STOC 2025), previously used for adaptive security analysis. We complement the non-adaptive security result with an upper bound in the adaptive setting, showing that DPFC cannot remain secure for queries.