Running summarizing tools on a new article

Check the paper below, then start its synthesis.


Birthday-Scale Non-Adaptive Security for Strong Pseudorandom Unitaries

Zvika Brakerski, Lior Ozer, Shahar Silberstein

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 $U$, $U^\dagger$, $U^*$, and $U^T$. In this work, we prove birthday-scale non-adaptive security for the DPFC (Clifford-Phase-Permutation-Clifford) strong PRU candidate. For an $N$-dimensional unitary, allowing arbitrary entangled inputs and coherent superpositions of query types, we show that DPFC can withstand $t \approx \sqrt{N}$ queries. This matches the best known query complexity even for PRUs that are not strong, compared with $t \approx N^α$ for $α< 1/2$ 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 $t \gg \sqrt{N}$ queries.

Submitted to arXiv on 18 Nov. 2026