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.
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.
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
The Forrelation problem, first introduced by Aaronson [Scott Aaronson, 2010] and Aaronson and Ambainis [Scott Aaronson and Andris Ambainis, 2015], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [Scott Aaronson and Andris Ambainis, 2015]; the first separation between poly-logarithmic quantum query complexity and bounded-depth circuits of super-polynomial size, a result that also implied an oracle separation of the classes BQP and PH [Ran Raz and Avishay Tal, 2019]; and improved separations between quantum and classical communication complexity [Uma Girish et al., 2021]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than ≈ 1/√N, that is, the success probability is larger than ≈ 1/2 + 1/√N. This is unavoidable as ≈ 1/√N is the correlation between two coordinates of an input that is sampled from the Forrelation distribution, and hence there are simple classical protocols that achieve advantage ≈ 1/√N, in all these models. To achieve separations when the classical protocol has smaller advantage, we study in this work the xor of k independent copies of (a variant of) the Forrelation function (where k≪ N). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level 2k is bounded by α^k (that is, the sum of the absolute values of all Fourier coefficients at level 2k is bounded by α^k), cannot compute the xor of k independent copies of the Forrelation function with advantage better than O((α^k)/(N^{k/2})). This is a strengthening of a result of [Eshan Chattopadhyay et al., 2019], that gave a similar statement for k = 1, using the technique of [Ran Raz and Avishay Tal, 2019]. We give several applications of our result. In particular, we obtain the following separations: Quantum versus Classical Communication Complexity. We give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N) (where Alice and Bob also share polylog(N) EPR pairs), and such that, any classical randomized protocol of communication complexity at most õ(N^{1/4}), with any number of rounds, has quasipolynomially small advantage over a random guess. Previously, only separations where the classical protocol has polynomially small advantage were known between these models [Dmitry Gavinsky, 2016; Uma Girish et al., 2021]. Quantum Query Complexity versus Bounded Depth Circuits. We give the first example of a partial Boolean function that has a quantum query algorithm with query complexity polylog(N), and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess. Previously, only separations where the constant-depth circuit has polynomially small advantage were known [Ran Raz and Avishay Tal, 2019].
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 Forrelation problem, first introduced by Aaronson [Scott Aaronson, 2010] and Aaronson and Ambainis [Scott Aaronson and Andris Ambainis, 2015], is a well studied computational problem in the context of separating quantum and classical computational models. Variants of this problem were used to give tight separations between quantum and classical query complexity [Scott Aaronson and Andris Ambainis, 2015]; the first separation between poly-logarithmic quantum query complexity and bounded-depth circuits of super-polynomial size, a result that also implied an oracle separation of the classes BQP and PH [Ran Raz and Avishay Tal, 2019]; and improved separations between quantum and classical communication complexity [Uma Girish et al., 2021]. In all these separations, the lower bound for the classical model only holds when the advantage of the protocol (over a random guess) is more than ≈ 1/√N, that is, the success probability is larger than ≈ 1/2 + 1/√N. This is unavoidable as ≈ 1/√N is the correlation between two coordinates of an input that is sampled from the Forrelation distribution, and hence there are simple classical protocols that achieve advantage ≈ 1/√N, in all these models.
To achieve separations when the classical protocol has smaller advantage, we study in this work the xor of k independent copies of (a variant of) the Forrelation function (where k≪ N). We prove a very general result that shows that any family of Boolean functions that is closed under restrictions, whose Fourier mass at level 2k is bounded by α^k (that is, the sum of the absolute values of all Fourier coefficients at level 2k is bounded by α^k), cannot compute the xor of k independent copies of the Forrelation function with advantage better than O((α^k)/(N^{k/2})). This is a strengthening of a result of [Eshan Chattopadhyay et al., 2019], that gave a similar statement for k = 1, using the technique of [Ran Raz and Avishay Tal, 2019]. We give several applications of our result. In particular, we obtain the following separations:
Quantum versus Classical Communication Complexity. We give the first example of a partial Boolean function that can be computed by a simultaneous-message quantum protocol with communication complexity polylog(N) (where Alice and Bob also share polylog(N) EPR pairs), and such that, any classical randomized protocol of communication complexity at most o(N^{1/4}), with any number of rounds, has quasipolynomially small advantage over a random guess. Previously, only separations where the classical protocol has polynomially small advantage were known between these models [Dmitry Gavinsky, 2016; Uma Girish et al., 2021].
Quantum Query Complexity versus Bounded Depth Circuits. We give the first example of a partial Boolean function that has a quantum query algorithm with query complexity polylog(N), and such that, any constant-depth circuit of quasipolynomial size has quasipolynomially small advantage over a random guess. Previously, only separations where the constant-depth circuit has polynomially small advantage were known [Ran Raz and Avishay Tal, 2019].
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.