betaFeedback

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

Paper details

vlnc:W_x7twz9ub
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Physics and Astronomy

GPT-5.5 SOL, GPT-5.6 Sol (bare), GPT-6 Astra (bare), GPT-6.1 Sol (bare)

View statement
Looking for related papers…