The XOR of two or more independent random permutations (XoP) is the prototypical pseudorandom function built from permutations achieving security beyond the birthday bound. The classical security of the XoP construction is well established, but its security against quantum attacks that query XoP in superposition has remained widely open.
We prove that the XOR of $r\ge 2$ random permutations over $\{0,1\}^n$ is indistinguishable from a random function by any $q$-query quantum algorithm with advantage \[O\left(\min\left\{\frac{q^3}{2^{rn}},\frac{q^{1.5}}{2^{(r-0.5)n}},\frac{1}{2^{(r-1.5)n}}\right\}\right)\] for all $q\ll 2^n$. In particular, XoP remains secure throughout the entire query range, far beyond the $2^{n/3}$ bound due to quantum collision finding attacks. This is the first construction from permutations that achieves the quantum version of the beyond birthday bound security. We also present several heuristic attacks suggesting the tightness of our bounds in ranges $q\le 2^{n/2}$ and $\approx 2^n$.
We use a Fourier-analytic variant of the polynomial method: the advantage of any $q$-query quantum algorithm is controlled by the Fourier components of degree at most $2q$, or by $2q$ input-output data of the construction. The norms of most components are bounded well, proving the bound $2^{-(r-3/2)n}$.
The norm of low-degree components turn out to be too large for the bounds $q^3/2^{rn}$ and $q^{1.5}/2^{(r-0.5)n}$. We reinterpret these low-degree components as (sums of) advantages of the other problems. For example, the degree-2 and degree-4 terms are interpreted as the advantages against random functions with and without \emph{planted collisions}, which in turn are bounded using Zhandry's small-range distributions. Along the way, we prove a new bound for the small-range indistinguishability for (ironically) large ranges, which is of independent interest.
AI Summary
The paper studies whether XORing independent random permutations produces a pseudorandom function against adversaries making coherent superposition queries, beyond the $2^{n/3}$ quantum collision threshold for distinguishing a single permutation from a random function. It considers $\mathrm{XoP}_r(x)=P_1(x)\oplus\cdots\oplus P_r(x)$ on $n$-bit strings, with no adversarial access to the constituent permutations.
Writing $N=2^n$, it proves distinguishing advantage $O(\min\{q^3/N^r,\;q^{3/2}/N^{r-1/2},\;N^{3/2-r}\})$. The formal theorem covers $n\ge5$, $2\le r\le N/16$, and $q\le N/57774$, with asymptotic constants allowed to depend on $r$. For fixed $r\ge2$, this establishes negligible advantage throughout that query range, including beyond $N^{1/3}$ and $N^{1/2}$.
The proof combines the polynomial method with Fourier analysis over function space: a $q$-query algorithm’s acceptance probability has Fourier degree at most $2q$. Most density components are controlled by combinatorial norm bounds. Exceptional low-degree components are reinterpreted through random functions with planted collisions or XOR constraints. Small-range indistinguishability and compressed-oracle arguments bound these auxiliary problems, including a planted-collision bound $O(q^{3/2}/N^{3/2})$ and an improved large-range small-range-distribution bound.
Collision-based attacks are analyzed heuristically, suggesting matching scalings for $q\lesssim N^{1/2}$; tightness remains unresolved at intermediate larger query counts. A parity attack gives advantage $1/2$ at $N/2$ queries. Extension to keyed block ciphers requires an ideal-cipher model and sufficiently long independent keys, adding a loss of order $rq^2/2^\kappa$.
No sign of AI-generated textAI use disclosedOverclaims
The current paper is mostly written by human authors from scratch, while AI assisted in writing some paragraphs.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
The XOR of two or more independent random permutations (XoP) is the prototypical pseudorandom function built from permutations achieving security beyond the birthday bound. The classical security of the XoP construction is well established, but its security against quantum attacks that query XoP in superposition has remained widely open.
We prove that the XOR of r≥2 random permutations over {0,1}n is indistinguishable from a random function by any q-query quantum algorithm with advantage [O\left(\min\left{\frac{q^3}{2^{rn}},\frac{q^{1.5}}{2^{(r-0.5)n}},\frac{1}{2^{(r-1.5)n}}\right}\right)] for all q≪2n. In particular, XoP remains secure throughout the entire query range, far beyond the 2n/3 bound due to quantum collision finding attacks. This is the first construction from permutations that achieves the quantum version of the beyond birthday bound security. We also present several heuristic attacks suggesting the tightness of our bounds in ranges q≤2n/2 and ≈2n.
We use a Fourier-analytic variant of the polynomial method: the advantage of any q-query quantum algorithm is controlled by the Fourier components of degree at most 2q, or by 2q input-output data of the construction. The norms of most components are bounded well, proving the bound 2−(r−3/2)n.
The norm of low-degree components turn out to be too large for the bounds q3/2rn and q1.5/2(r−0.5)n. We reinterpret these low-degree components as (sums of) advantages of the other problems. For example, the degree-2 and degree-4 terms are interpreted as the advantages against random functions with and without \emph{planted collisions}, which in turn are bounded using Zhandry's small-range distributions. Along the way, we prove a new bound for the small-range indistinguishability for (ironically) large ranges, which is of independent interest.
The paper studies whether XORing independent random permutations produces a pseudorandom function against adversaries making coherent superposition queries, beyond the 2n/3 quantum collision threshold for distinguishing a single permutation from a random function. It considers XoPr(x)=P1(x)⊕⋯⊕Pr(x) on n-bit strings, with no adversarial access to the constituent permutations.
Writing N=2n, it proves distinguishing advantage O(min{q3/Nr,q3/2/Nr−1/2,N3/2−r}). The formal theorem covers n≥5, 2≤r≤N/16, and q≤N/57774, with asymptotic constants allowed to depend on r. For fixed r≥2, this establishes negligible advantage throughout that query range, including beyond N1/3 and N1/2.
The proof combines the polynomial method with Fourier analysis over function space: a q-query algorithm’s acceptance probability has Fourier degree at most 2q. Most density components are controlled by combinatorial norm bounds. Exceptional low-degree components are reinterpreted through random functions with planted collisions or XOR constraints. Small-range indistinguishability and compressed-oracle arguments bound these auxiliary problems, including a planted-collision bound O(q3/2/N3/2) and an improved large-range small-range-distribution bound.
Collision-based attacks are analyzed heuristically, suggesting matching scalings for q≲N1/2; tightness remains unresolved at intermediate larger query counts. A parity attack gives advantage 1/2 at N/2 queries. Extension to keyed block ciphers requires an ideal-cipher model and sufficiently long independent keys, adding a loss of order rq2/2κ.
In this work we give an efficient construction of unitary k-designs using O~(k⋅poly(n)) quantum gates, as well as an efficient construction of a parallel-secure pseudorandom unitary (PRU). Both results are obtained by giving an efficient quantum algorithm that lifts random permutations over S(N) to random unitaries over U(N) for N=2n. In particular, we show that products of exponentiated sums of S(N) permutations with random phases approximately match the first 2Ω(n) moments of the Haar measure. By substituting either O~(k)-wise independent permutations, or quantum-secure pseudorandom permutations (PRPs) in place of the random permutations, we obtain the above results. The heart of our proof is a conceptual connection between the large dimension (large-N) expansion in random matrix theory and the polynomial method, which allows us to prove query lower bounds at finite-N by interpolating from the much simpler large-N limit. The key technical step is to exhibit an orthonormal basis for irreducible representations of the partition algebra that has a low-degree large-N expansion. This allows us to show that the distinguishing probability is a low-degree rational polynomial of the dimension N.
We study classical and quantum indistinguishability of sums of independent random permutations and related transformations from permutations to functions. Let G be a finite abelian group of order N, and let π+k(x)=π1(x)+⋯+πk(x) for k≥2 independent uniform random permutations of G. We give a unified Fourier analytic treatment in which the construction is represented by its probability density and a distinguisher by its acceptance function, with the classical and quantum query models imposing different restrictions on the Fourier support of the latter. Classically, we obtain the bound Ok(q/Nk−1/2) for every $q
We prove near-optimal lower bounds for preprocessing attacks on quantum cryptography in the random oracle model. Specifically, we show that a T-query adversary with S qubits of non-uniform advice can recover a random key k from the n-qubit binary phase state ∣ψk⟩∝∑xR(k,x)∣x⟩ with probability at most O(NT2+ST) for N=2n. In contrast, the best known bound for post-quantum one-way functions is O(NT2+ST), with a trivial attack at S=N. This demonstrates a new advantage of quantum cryptography over classical cryptography: n qubits of communication suffice for security against preprocessing attacks with space up to N2 rather than N. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-quantum PRGs in QROM, achieving a distinguishing advantage bound of O(NT2+NST). (2) For unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight O(NS) bound for the pseudorandomness of random binary phase states against space S distinguishers.
The level-k ℓ1-Fourier weight of a Boolean function refers to the sum of absolute values of its level-k Fourier coefficients. Fourier growth refers to the growth of these weights as k grows. It has been extensively studied for various computational models, and bounds on the Fourier growth, even for the first few levels, have proven useful in learning theory, circuit lower bounds, pseudorandomness, and quantum-classical separations.In this work, we investigate the Fourier growth of certain functions that naturally arise from communication protocols for XOR functions (partial functions evaluated on the bitwise XOR of the inputs x and y to Alice and Bob). If a protocol C computes an XOR function, then C(x,y) is a function of the parity x⊕y. This motivates us to analyze the XOR-fiber of the communication protocol C, defined as h(z):=Ex,y[C(x,y)∣x⊕y=z].We present improved Fourier growth bounds for the XOR-fibers of randomized protocols that communicate d bits. For the first level, we show a tight O(d) bound and obtain a new coin theorem, as well as an alternative proof for the tight randomized communication lower bound for the Gap-Hamming problem. For the second level, we show an d3/2⋅polylog(n) bound, which improves the previous O(d2) bound by Girish, Raz, and Tal (ITCS 2021) and implies a polynomial improvement on the randomized communication lower bound for the XOR-lift of the Forrelation problem, which extends the quantum-classical gap for this problem.Our analysis is based on a new way of adaptively partitioning a relatively large set in Gaussian space to control its moments in all directions. We achieve this via martingale arguments and allowing protocols to transmit real values. We also show a connection between Fourier growth and lifting theorems with constant-sized gadgets as a potential approach to prove optimal bounds for the second level and beyond.
A central challenge in quantum algorithms and cryptography is reasoning about algorithms with oracle access to a random group element (e.g. a random function, permutation, or unitary). Can we efficiently simulate such algorithms? Can we determine what they know after t queries? A classical tool for this is lazy sampling: the oracle does not commit to the full group element upfront, but rather samples partial information about it on the fly. We study a quantum analog of lazy sampling: compressed oracles (or recording oracles). These are quantum data structures that allow on-the-fly simulation for quantum queries, originally introduced by Zhandry (CRYPTO '19) for random functions, and generalized to unitaries by Ma-Huang (STOC '25) and permutations by Carolan (STOC '26), and used to great effect in security proofs and lower bounds due to their interpretability.
We define and analyze a general-purpose and interpretable path-recording oracle, derived from first principles, that perfectly simulates random elements of any closed subgroup of U(N). Our oracle stores, in superposition, t input-output pairs, with updates described in terms of the commutant of the group's tensor power representation. This transparently records the information the algorithm has learned. Our oracle builds on recent work of Grinko-Yoshida (QIP '26), who gave a different general-purpose compressed oracle without clear interpretability.
One interesting application of our path-recording is allowing direct comparisons between compressed oracles of different groups, giving a new technique for proving pseudorandomness results. For example, comparing SN and U(N) yields what is arguably the simplest construction to date of pseudorandom unitaries: the product PC of a pseudorandom permutation and a random Clifford, improving on the prior PFC construction (Metger-Poremba-Sinha-Yuen, FOCS '24; Ma-Huang, STOC '25).
Due to their simple security assessments, permutation-based pseudo-random functions (PRFs) have become widely used in cryptography. It has been shown that PRFs using a single n-bit permutation achieve n/2 bits of security, while those using two permutation calls provide 2n/3 bits of security in the classical setting. This paper studies the security of permutation-based PRFs within the Q1 model, where attackers are restricted to classical queries and offline quantum computations. We present improved quantum-time/classical-data tradeoffs compared with the previous attacks. Specifically, under the same assumptions/hardware as Grover’s exhaustive search attack, i.e. the offline Simon algorithm, we can recover keys in quantum time Õ(2n/3), with O(2n/3) classical queries and O(n2) qubits. Furthermore, we enhance previous superposition attacks by reducing the data complexity from exponential to polynomial, while maintaining the same time complexity. This implies that permutation-based PRFs become vulnerable when adversaries have access to quantum computing resources. It is pointed out that the above quantum attack can be applied to several cryptographic schemes, including PDMMAC and pEDM, as well as general instantiations like XopEM, EDMEM, EDMDEM, and others.