Quantum information · Theory (AI-assisted)

Birthday-Scale Non-Adaptive Security for Strong Pseudorandom Unitaries

Zvika Brakerski, Lior Ozer, Shahar Silberstein

arXiv:2611.25038v1 ↗PDF ↗Submitted 18 November 2026

Question
Pseudorandom unitaries are efficient ensembles that no efficient observer can tell apart from Haar-random unitaries. Strong ones must stay indistinguishable when the observer can also apply \(U^\dagger\), \(U^*\) and \(U^T\). The standard candidate, DPFC, sandwiches a random phase function \(F\) and a random permutation \(P\) between random Cliffords \(C\) and \(D\). Without the outer Clifford \(D\), the construction is known to be secure against forward queries up to the birthday scale \(t\approx\sqrt N\), with \(N=2^n\). Existing proofs for strong queries reached only \(t\approx N^\alpha\), with \(\alpha\) between 1/32 and 1/16. Does DPFC withstand about \(\sqrt N\) strong queries?
Result
For non-adaptive queries it does. The adversary may make any mixture or coherent superposition of the four query types, with entangled inputs. When \(C\) and \(D\) come from any exact unitary 2-design, the diamond distance between the \(t\)-query channels of DPFC and of a Haar unitary is at most \(2(1+e^{t^2/4N})\sqrt{4t^2/N+e^{t^2/2N}-1}\). For \(t^2\le N/16\) this simplifies to \(10t/\sqrt N\). For adaptive queries the scale cannot be beaten. When the endpoints are Cliffords, the \(N-1\) Pauli operators \(Q=C^\dagger Z^sC\) satisfy a strong property: \(UQU^\dagger\) expands only into mutually commuting Paulis. A four-query Bell-sampling test accepts these Paulis with certainty, while for Haar unitaries every Pauli passes with probability at most about \(\tfrac12\). An adaptive amplitude-amplification search for such a Pauli then distinguishes DPFC with advantage at least 0.09, using \(O(\sqrt N)\) queries to \(U\) and \(U^\dagger\), for \(N\ge2^{15}\).

The paper in detail

Pseudorandom unitaries are useful wherever Haar-random unitaries are: in models of scrambling and thermalisation, and in quantum cryptography. Haar-random unitaries cannot be implemented efficiently. Constructions are first proved secure in an idealised model in which some components are truly random, and then instantiated with cryptographic primitives. In every known case the bound has the form "distinguishing advantage at most \(f(t,N)\)". The base PFC construction (Clifford, phase, permutation) reaches the birthday scale, roughly \(t^2/N\), which is meaningful up to \(t\approx\sqrt N\). Strong security matters because many applications let the adversary run the process backwards or transposed. Adding a second Clifford \(D\) after the permutation is necessary even for inverse queries, but the existing analyses of DPFC lost most of the exponent.

The proof replaces the permutation–phase layer by a path-recording operator, a quantum form of lazy sampling. Instead of fixing a whole permutation and phase function, the recorder sends each query to a uniform superposition of outputs and stores the signed input–output pairs in a database register. On databases without collisions, where all inputs and all outputs are distinct, the recorder and the true layer agree exactly up to a normalisation \(1+O(t^2/N)\). Two further facts close the argument. Random 2-design endpoints make collisions as rare as among \(t\) random elements of \([N]\). And a Gram-operator bound prevents the non-isometric recorder from inflating colliding inputs. With all queries made in parallel, the endpoints can be moved exactly from the query registers onto the database, so after tracing out the database the result does not depend on them. This exact move fails adaptively. There, the recorder has to erase relations when \(U\) is followed by \(U^\dagger\), and the errors accumulate.

Conjugate and transpose queries add a new obstacle: invariant states. An EPR pair shared by a \(U\) slot and a \(U^*\) slot passes through unchanged, \((U\otimes U^*)\ket{\Omega}=\ket\Omega\), but a recorder entangles every query with its database and destroys it. Projectors onto EPR pairs at different positions do not commute, so the input cannot simply be split into "EPR pairs here" and "the rest". The paper adopts the EPR-sector decomposition of Schuster et al. It is a unitary change of coordinates into sectors with a fixed number of invariant pairs. Each sector is a tensor product of a multiplicity register, recording where the pairs sit, and an EPR-free data register on which the query action looks like ordinary queries. Running the recorder argument in each sector and assembling sectors and query patterns coherently gives the stated \(O(t/\sqrt N)\) diamond-norm bound.

The attack uses the structure that the security proof sets aside. Cliffords map Paulis to Paulis, a diagonal phase commutes with diagonal Paulis, and a permutation maps diagonal operators to diagonal operators. Hence for \(Q=C^\dagger Z^sC\), the operator \(UQU^\dagger\) is \(D\) times a diagonal operator times \(D^\dagger\), whose Pauli expansion lies in one commuting family. Bell sampling twice from \(UQU^\dagger\) and checking commutation detects this with four queries. Since a fraction \(1/(N+1)\) of Paulis are witnesses, amplitude amplification finds one in \(O(\sqrt N)\) queries. A recursive search avoids an extra logarithmic factor from the test's imperfect rejection. The authors leave open whether any efficiently implementable construction reaches the birthday scale, or beyond, against adaptive strong queries.

Transferable methods

  1. A parallel path recorder compared on collision-free relations

    Averaging \(t\) parallel queries over a random permutation and phase function is hard to handle directly. The recorder replaces "sample everything in advance" with "remember only what was asked", which makes the dependence on the endpoints removable. The two descriptions disagree only when inputs or outputs collide, so the whole error reduces to bounding collision weight.

    Purify the permutation–phase layer by keeping \(\pi\) and \(f\) in an environment. For \(p\) forward inputs \(\mathbf x\) and \(q\) inverse inputs \(\mathbf y\), the output strings \((\mathbf u,\mathbf v)\) come with environment states \(\ket{\mathsf{pf}_{S_+,S_-}}\), where \(S_+=\{(x_i,u_i)\}\) and \(S_-=\{(v_j,y_j)\}\). If all \(t\) domain labels and all \(t\) image labels are distinct, exactly \((N-t)!\) permutations are consistent. Normalising the environment then gives each output string the amplitude \(\sqrt{(N-t)!/N!}\). The recorder gives every string \(N^{-t/2}\), so the ratio is (editorial evaluation) \[\sqrt{\frac{N^t(N-t)!}{N!}}=\prod_{k<t}\Bigl(1-\frac kN\Bigr)^{-1/2}=1+O\Bigl(\frac{t^2}N\Bigr).\] On this bijective subspace the two maps match exactly after rescaling, under the isometry \(\ket{\mathsf{pf}_{S_+,S_-}}\leftrightarrow\ket{S_+,S_-}\).

    The rest of the argument bounds the weight off that subspace. Because the queries are parallel, the endpoint Cliffords commute through to the database, where they act on each stored input and output separately. This is exact unitary invariance, Eq. (6). With 2-design endpoints, a collision among the stored labels is then as unlikely as among \(t\) random elements of \([N]\), at most \(O(t^2/N)\). The recorder is not an isometry, since a database with repeated entries has a larger projection onto the symmetric subspace. The bound \(E^\dagger E-I\preceq(e^{t^2/2N}-1)I\) caps that inflation. Cross terms between the bijective and colliding parts then give a diamond distance \(O(\sqrt{t^2/N})=O(t/\sqrt N)\), which is why the bound is linear in \(t\) rather than quadratic.

    How to reuse it

    Recording only the queried input–output relations, and comparing with the true process on collision-free records, is the quantum counterpart of lazy sampling in classical random-oracle proofs. The same pattern, combined with an EPR-sector decomposition when conjugate access is allowed, suits other primitives built from random permutations and Clifford layers: pseudorandom state and isometry constructions, and time-reversal-invariant scrambling models.

  2. Pauli witnesses: Cliffords preserve commutation, permutations preserve diagonality

    A security bound is credible only if no attack contradicts it. The construction's middle layer is diagonal-preserving, and its outer layers are Clifford. Those two properties together create a hidden family of Pauli operators whose conjugates stay inside a commuting family, a structure that Haar unitaries lack. Detecting it needs only Bell sampling, and finding a witness is a search problem with density \(1/N\).

    Expand \(UQU^\dagger=\sum_ar_aP_a\), with \(r_a=\operatorname{tr}(P_aUQU^\dagger)/N\) real and \(\sum_ar_a^2=1\). Applying \(UQU^\dagger\) to half of an EPR pair and measuring in the Bell basis returns \(a\) with probability \(r_a^2\). Doing this twice and accepting when the two labels commute gives \[q_Q(U)=\sum_{[a,b]=0}r_a^2r_b^2=\frac12\Bigl(1+\sum_{a,b}(-1)^{[a,b]}r_a^2r_b^2\Bigr),\] using four queries in the order \(U^\dagger,U,U^\dagger,U\). For a Haar unitary the weights \(r_a^2\) are spread over almost all Paulis, and the signed sum is \(O(\log N/N)\) uniformly over \(Q\) with high probability (Lemma 5.3).

    For \(U=DPFC\) and \(Q_s=C^\dagger Z^sC\), the phase \(F\) commutes with \(Z^s\), so (Eq. (161)) \[UQ_sU^\dagger=\pm D\,(PZ^sP^\dagger)\,D^\dagger.\] Here \(PZ^sP^\dagger\) is diagonal, so it is a combination of the commuting \(Z^v\). Conjugation by the Clifford \(D\) keeps them Pauli and keeps them commuting, so \(q_{Q_s}=1\) for all \(N-1\) non-zero \(s\). That is a fraction \(1/(N+1)\) of the non-identity labels, so an amplitude-amplified search needs \(O(\sqrt N)\) test calls. The editorial check at \(N=16\) found exactly 15 perfect witnesses for DPFC, against a largest acceptance of 0.52 for Haar unitaries.

    How to reuse it

    To audit any construction that sandwiches a structured core between Clifford layers, ask which Pauli operators stay inside a commuting or stabilizer family under conjugation by the core. Bell sampling of \(UQU^\dagger\) then gives a cheap test. Candidate targets include PFC-type pseudorandom states, Clifford-based approximate designs, and scrambling circuits built from random phases and permutations.

Source: Section 1.2 (technical overview: parallel recorder, Eqs. (2)–(7); EPR-sector decomposition, Eqs. (8)–(11)); Theorem 4.10; Section 5 (Theorem 5.1, Eqs. (156)–(161), Lemmas 5.2–5.4). Based on the linked paper version. Derivations marked as editorial, and suggested uses in other problems, are editorial guidance rather than results of the paper.

Context & limitations

Why it matters. The birthday scale is the best known for any efficiently implementable pseudorandom unitary, so non-adaptive strong security now costs nothing extra. The attack shows that Clifford-endpoint DPFC cannot be proved secure beyond the birthday scale against adaptive strong queries, which settles the ceiling for this construction. What remains is to reach the birthday scale adaptively. Strong pseudorandom unitaries underlie quantum commitments, and arguments that Hayden–Preskill decoding is computationally hard.

Limitations. Security is proved only for non-adaptive queries. The adaptive strong bounds remain the earlier \(N^{\alpha}\) ones. The analysis is in an idealised model in which \(P\) and \(F\) are truly random; cryptographic security needs post-quantum pseudorandom functions and permutations. A bound of order \(t/\sqrt N\) gives only constant security at \(t\approx\sqrt N\), and it says nothing once \(t\gtrsim\sqrt N/5\), where it exceeds 2. The attack uses inverse queries and Clifford endpoints, and its stated constants need \(N\ge2^{15}\). The paper reports extensive use of ChatGPT models (GPT-5.5 SOL, GPT-5.6 SOL, GPT-6 ASTRA, GPT-6.1 SOL). According to the disclosure, the parallel recorder construction and the adaptive attack emerged from discussions between the authors and AI, and AI was used to draft, review and simplify the manuscript.

Description based on the full arXiv HTML of v1, read 2026-11-22: Section 1 (results, technical overview, AI disclosure), the statement of Theorem 4.10 and the start of its proof, and Section 5 (Theorem 5.1, Algorithm 1, Lemmas 5.2–5.4). The definitions in Sections 2–4 and the appendix proofs (Gram bound, EPR-sector decomposition, collision bound, search lemma) were skimmed but not reproduced. Editorial checks: for \(n=4\) (\(N=16\)) the construction was built with \(C\) and \(D\) as random Clifford circuits of depth 300 in \(H\), \(S\) and CNOT, a random permutation and random ternary phases. The test's acceptance probability \(q_Q(U)\), computed exactly for all 255 non-identity Paulis, was 1 for exactly 15 of them, which is \(N-1\), and averaged 0.53 over the rest. For three Haar unitaries the largest \(q_Q\) was 0.52 and the mean 0.50. The bound (150) evaluates to 0.265 at \(N=2^{20}\), \(t=32\), below the simplified \(10t/\sqrt N=0.3125\).