PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Security of XOR of Permutations via Fourier Analysis

Wonseok Choi, Minki Hhan, Junyoung Jang

arXiv:2609.34413v1quant-phcs.CR

TL;DR

Permutation-based quantum PRFs have lacked beyond-birthday security guarantees despite the classical study of XoP. This paper analyzes XoP with Fourier methods and proves security near 2^n queries, while identifying limits on the model and attack tightness.

  • Problem

    Whether XORs of random permutations remain secure against quantum algorithms making superposition queries has been an open question, with prior permutation-based QPRFs not known secure beyond q = 2^(n/3).

    Source: §1 · p. 3

  • Method

    The proof uses a Fourier-analytic variant of the polynomial method to control q-query acceptance probabilities through Fourier components of degree at most 2q.

    Source: §1.2 · p. 4

  • Results

    XoP[r] for r ≥ 2 is secure up to q ≈ 2^n queries, and compressed-oracle analysis gives an O(q^1.5/N^1.5) bound for the planted-collision problem.

    Source: §1.1 · p. 3, §1.2 · p. 7

  • Takeaways & Limitations

    The paper presents the first QPRF construction in the quantum ideal cipher model whose security goes beyond 2^(n/3) quantum queries.

    Source: §1.1 · p. 4

    The theorem assumes adversaries have no access to the inner permutation queries.

    Source: §4 · p. 14

Abstract

from arXiv · show

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.

1 Introduction

Permutation-based quantum PRFs remain an open beyond-birthday problem because coherent queries complicate classical security methods. The introduction presents XoP as secure near 2^n queries and previews its Fourier analysis and heuristic attacks.

1 Introduction

  • Coherent quantum queries complicate permutation security proofs and leave beyond-birthday security for permutation-based QPRFs an open challenge.The introduction notes that prior results were lossy or restrictive and that known permutation-based QPRFs did not exceed q = 2^(n/3) queries.Source: §1 · p. 3

1.1 Our results

  • XoP[r] for r ≥ 2 remains secure up to q ≈ 2^n queries, extending permutation-based quantum PRFs beyond the prior 2^(n/3) frontier.The paper identifies this as the first such construction in the quantum ideal cipher model.Source: §1.1 · pp. 3–4, §1 · p. 3

1.2 Technical overview

  • A Fourier-analytic variant of the polynomial method bounds q-query acceptance probabilities using Fourier statistics of degree at most 2q.Low-degree terms are reinterpreted through other distinguishing problems, including planted collisions; a large-range small-range construction gives O(q^3/N^2), while compressed-oracle analysis gives O(q^1.5/N^1.5).Source: §1.2 · pp. 4–7

1.3 Heuristic Attacks

  • Heuristic attacks match the bounds for q ≲ N^1/2 and q ≈ N, but tightness remains unclear for N^1/2 ≲ q < N/2.Most attacks below N are related to collision statistics; the attack for q ≥ N/2 uses a quantum parity algorithm and achieves advantage 1/2.Source: §1.3 · p. 8

1.4 Related Works

  • Classical XoP security analysis developed multiple techniques and established tight bounds, especially for the r = 2 case.Related work also studied XoP-like constructions based on Even-Mansour encryption and tweakable permutations.Source: §1.4 · p. 8
  • Earlier quantum analysis studied XoP with classical queries to the construction, whereas this paper addresses quantum queries to XoP.The cited prior Q1 result gives a bound about rq^2/2^κ + q/2^n; the paper reports its Q2 bound is better for r ≥ 2.Source: §1.4 · pp. 8–9

2 Preliminaries

The preliminaries set notation for n-bit strings and probability distributions, then define the quantum oracle and distinguishing advantage used in the paper.

2 Preliminaries

  • N denotes 2n, and the paper uses uniform sampling notation both with and without replacement.The indicator notation JXK marks whether an event occurs.Source: §2 · p. 9
  • A quantum oracle for f coherently maps |x, y⟩ to |x, y + f(x)⟩.Distinguishing advantage compares an algorithm's output probabilities under two function distributions.Source: §2 · p. 9

3 Fourier Analysis of Functionals

The section develops Fourier analysis for functionals on function spaces and uses it to represent quantum-query algorithms by low-degree functionals. This representation reduces oracle distinguishing bounds to the low-degree Fourier components of a distribution's density.

3.1 Fourier analysis of the functionals

  • Characters form an orthonormal basis, yielding Fourier expansions whose coefficients define each functional's spectrum.A character is defined from the inner product over n-bit strings.Source: §3.1 · p. 10

3 Fourier Analysis of Functionals

  • Functionals are complex-valued maps on a function space, analyzed as functions with an exponentially long input.The paper denotes functionals by uppercase letters to distinguish them from ordinary functions.Source: §3.1 · p. 10, §3 · p. 10

3.1 Fourier analysis of the functionals

  • Fourier degree is the smallest degree containing a functional's support, and degrees add at most under multiplication.The paper also defines degree-d components and their low-degree sums.Source: §3.1 · p. 11
  • Convolution multiplies Fourier coefficients and represents the density of the XOR of two independent function samples.For functionals G and H, convolution is defined by averaging G(f + g)H(g) over uniform g.Source: §3.1 · p. 12

3.2 Quantum oracle algorithms as functional

  • A q-query quantum algorithm's output probability is represented by a functional of Fourier degree at most 2q.Its final-state amplitudes have degree at most q, and forming output probabilities doubles that bound.Source: §3.2 · pp. 12, 14
  • The distinguishing-advantage bound reduces analysis to the distribution density's degree-at-most-2q components.The density's degree-zero component is 1, so the theorem focuses on its nonconstant low-degree components.Source: §3.2 · p. 13

4 Quantum Security of XoP

This section defines the XOR-of-permutations construction and states its quantum security theorem under a bounded-query setting.

4 Quantum Security of XoP

  • XoP[r] is the bitwise XOR of r independent random permutations over n-bit strings.The paper denotes the distribution of this construction by DXoP[r].Source: §4 · p. 14
  • The adversary may query XoP[r] at most q times in quantum superposition but has no access to the inner permutations.The asymptotic formula hides multiplicative factors depending on r.Source: §4 · p. 14
  • Theorem 4.1 applies for n ≥ 5, 2 ≤ r ≤ 2n/16, and 0 ≤ q ≤ 2n/57774.The theorem is identified as the quantum security theorem for XoP.Source: §4 · p. 14

5 XoP Security for Many Quantum Queries

This section proves a many-query XoP security upper bound by controlling Fourier components, including explicit low-degree calculations and bounds for higher degrees. It also bounds the weight of a component, denoted p_k(j).

5 XoP Security for Many Quantum Queries

  • The Fourier-component bounds imply that the relevant terms are all O(1/N^(2r-3)), yielding an upper bound on the XoP-versus-random-function distinguishing advantage.Lemma 5.2 supplies the component bounds, which are used to prove Lemma 5.1.Source: §5 · p. 15

5.1.1 Degree-1 Component Vanishes

  • The degree-1 Fourier component of XoP is zero, eliminating the first item in the low-degree component bounds.The permutation coefficient vanishes at degree 1, and the XoP coefficient is its rth power.Source: §5.1.1 · p. 16

5.1.2 Degree-2 Component

  • The degree-2 component weight is at most 1/N^(2r-3), establishing the second low-degree bound.The calculation uses N/2 ≥ 2r − 2.Source: §5.1.2 · p. 17

5.1.3 Degree-3 Component

  • Inclusion-exclusion reduces the degree-3 coefficient calculation to the condition y1 + y2 + y3 = 0n, which is used to bound its component weight.The supplied passages establish the coefficient identity and say the resulting calculation proves the third item of Lemma 5.2.Source: §5.1.3 · pp. 17–18

5.1.4 Degree-4 Component

  • The degree-4 analysis bounds the relevant combinatorial counts by C2,2(γ) ≤ 3 and C4(γ) ≤ 1 to control the component magnitude and weight.The coefficient identity is derived using inclusion-exclusion over the six pairwise-equality events.Source: §5.1.4 · pp. 18–20

5.2 Proofs for high degrees

  • For higher degrees, the analysis extends low-degree calculations and separately bounds maximal component magnitude and the aggregate Fourier-component weight.The section states a high-degree weight lemma, while the maximal-magnitude bound is given in Lemma 5.4.Source: §5.2 · p. 20

5.3.1 Maximal magnitude of components

  • M_d[µP] ≤ (2d/N)^ceil(d/2) for 1 ≤ d ≤ N bounds the maximal magnitude of a degree-d Fourier component of a random permutation.The proof derives a recursion by conditioning on the final sampled point, then uses induction on d.Source: §5.2 · p. 20, §5.3.1 · pp. 22–23

5.3.2 Weight of components

  • The weight proof uses Fourier-transform Parseval and binomial inversion; polynomial-degree cancellations remove terms with 2k < d.These cancellations are used in bounding the weight of components.Source: §5.3.2 · pp. 24–25
  • For k≥1, 0 ≤ p_k(j) ≤ jk·2^(j+k−1), including j∈{0,1} because p_k(0)=p_k(1)=0.Source: §5.3.2 · p. 25

6 Few Quantum Query Security via Planted Collisions

This section bounds few-query XoP security by translating low-degree Fourier components into distinguishing problems involving random functions with planted constraints. These reductions yield an overall O(q^3/N^r) upper bound.

6 Few Quantum Query Security via Planted Collisions

  • O(q^3/N^r) bounds the few-query security contribution after the degree-2, 3, 4, and 6 components are treated separately.The remaining components use the query-independent norm bounds.Source: §6 · pp. 25–26

6.1 Preparation: Distributions with planted constraints

  • A small-range function is formed as h = g ◦ f, and conditioning on zero or one collision in f gives, respectively, a random function or a planted-collision function.For R ≥ N^2, the probability of exactly one collision is at least N^2.Source: §6.1 · p. 26

6.2 Degree-2 component as planted collision

  • The degree-2 component reduces to the distinguishing advantage between a planted-collision function and a random function.The reduction differs by a multiplicative factor N^2(N−1)^(r−1).Source: §6.2 · pp. 27–28

6.3 Degree-3 component as planted-three-collision

  • The degree-3 component is a linear combination of advantages for planted-three-collision and planted-collision functions.The planted-three-collision distinguishing advantage is O(q^2/N).Source: §6.3 · pp. 28–29

6.4 Degree-4 component as planted two collisions plus small terms

  • The last term can be interpreted as a linear sum of distinguishing advantage between random functions with planted collision(s) and uniformly random functions, and is O(q^3/N^r) because r ≥ 2.D4X samples four distinct x1, x2, x3, x4 from {0, 1}^n, then samples a uniform random f such that f(x1) + f(x2) + f(x3) + f(x4) = 0^n.Source: §6.4 · pp. 29–31

6.5 Degree-6 component as planted three collisions plus small terms

  • The degree-6 component is split by collision structure, and its terms are bounded using the planted-constraint lemmas to complete the proof.The analysis distinguishes cases by the number of collision patterns in the degree-six characters.Source: §6.5 · pp. 32–33

7 Middle Quantum Query Security via Improved Small-range Indistinguishability

This section improves the planted-collision indistinguishability bound for the middle query range and uses it to bound XoP security. Its proof uses the compressed oracle to control collisions in the database.

7 Middle Quantum Query Security via Improved Small-range Indistinguishability

  • For q^3 ≫ N, the planted-collision bound improves on the earlier O(q^3/N^2) bound, and it yields an alternative large-range small-range indistinguishability bound under stated conditions.The small-range result applies when R ≫ N^4/q^3.Source: §7 · p. 34

7.3 Proof of the planted-collision bound

  • The planted-collision bound is applied to the XoP term, while the remaining Fourier components are bounded using Lemma 5.2 to prove the section’s theorem.The proof assumes q ≥ N^(1/3) for this step and uses the earlier few-query result when q ≤ N^(1/3).Source: §7 · p. 34

7.1 Planted collisions in the compressed oracle

  • The compressed-oracle proof bounds planted-collision distinguishing by tracking collision operators in the database and their behavior under queries.The compressed oracle is described as perfectly indistinguishable from a quantum random oracle.Source: §7.1 · p. 35, §7.2 · p. 37

7.2 The number of collisions in the database

  • The proof tracks queried inputs and collision pairs with count operators; a lemma bounds their expectations after t ≤ N compressed-oracle queries.The collision-count bound is stated as sufficient, though not tight.Source: §7.2 · p. 36

A Collision Bias and Heuristic Attacks

The attacks are heuristic estimates based mainly on collision statistics, with a parity attack for the highest query range. Their predicted advantages connect collision-based scalings to the paper’s security bounds.

Small-query regime

Moderate-query regime

  • For N^(1/3) ≲ q ≲ N^(1/2), quantum counting estimates K with t = Θ(q) queries; comparing a difference with error Θ(N/q) heuristically suggests distinguishing advantage.K’s standard deviation Θ(√q) is smaller than this error in the regime.Source: A Collision Bias and Heuristic Attacks · p. 43

Large-query regime

  • At q = Θ(N), the heuristic attack scaling is Θ(N^(3/2−r)), matching the theorem’s second bound.This regime compares the expected count difference with typical fluctuations between random oracles.Source: A Collision Bias and Heuristic Attacks · p. 43

Parity attack (q ≥ N/2)

  • For q ≥ N/2, the parity distinguisher has advantage 1/2, while the attack discussion cautions that the other attacks are heuristic and need further analysis.The parity can be computed exactly with N/2 quantum queries.Source: A Collision Bias and Heuristic Attacks · p. 44

B.1 Several planted collisions

This appendix bounds distinguishing functions with multiple planted collisions by constructing hybrids that add collisions in pairs. A hybrid argument then relates their advantage to the planted-collision bound.

B.1 Several planted collisions

  • The reduction constructs h by replacing selected input pairs with shared sampled values, adding i−1 planted collisions while simulating each query to h with at most two queries to g.When g already has a planted collision, whether its pair remains in the unmodified domain determines whether h has i or i−1 planted collisions.Source: §B.1 · p. 44
  • For k ∈ {2, 3}, the hybrid argument gives distinguishing advantage O(q^3/N^2) between functions with k planted collisions and random functions.The comparison uses DPC,0 = DF and the adjacent hybrid distributions.Source: §B.1 · p. 45

B.2 A planted triple from a planted pair

A polynomial-method argument bounds quantum distinguishability between random functions and functions with a planted triple collision. A reduction converts the planted-pair test into this comparison.

B.2 A planted triple from a planted pair

  • O(q^2/N) bounds the q-query advantage for distinguishing D3PC from DF.The proof uses the decisional quantum search bound and a symmetrized acceptance polynomial of degree at most 2q.Source: §B.2 · p. 45
  • The reduction fixes two distinct inputs to the same uniform output and uses a Boolean oracle to add a third such input when its marked point is outside the fixed pair.A query to the simulated oracle costs at most two Boolean-oracle queries; a marked point inside the pair instead yields a planted pair.Source: §B.2 · p. 46

B.3 Planted 4-XOR by splitting outputs

Splitting outputs turns a planted collision into a planted 4-XOR tuple with probability at least 1/6. The resulting reductions give quantum distinguishing bounds for planted 4-XOR and planted collisions.

B.3 Planted 4-XOR by splitting outputs

  • O(q^3/N^2) bounds the q-query advantage for distinguishing D4X from DF.The reduction also gives 2q-query advantage O(q^3/N^2) for distinguishing DPC from DF.Source: §B.3 · pp. 46–47
  • Each simulated query to h requires at most two queries to g, where g is either a random function or a function with one planted collision.When g is a random function, h is a random function; when the collision pair is not both in the selected half, h is also a random function.Source: §B.3 · pp. 46–47
  • At least 1/6 of the time, splitting outputs maps a planted collision to a planted 4-XOR tuple.Conditioned on both collision inputs lying in the selected half of the domain, four outputs are uniform subject to their sum being zero.Source: §B.3 · pp. 46–47

C Missing Proofs for the Compressed Oracles

The missing compressed-oracle proofs analyze how queries change a collision-count operator. They use Fourier-response subspaces and induction to control its expectation across queries.

C Missing Proofs for the Compressed Oracles

  • A query changes the collision count through an operator whose commutators are bounded separately for Fourier-response components.The proof treats the zero response as the identity and bounds the nonzero-response operator's commutators with components of the collision-count operator.Source: C Missing Proofs for the Compressed… · pp. 47–48
  • The proof decomposes the state into orthogonal subspaces indexed by query input, Fourier response, and other database registers, then combines their bounds using Cauchy–Schwarz.The count tracks occupied database entries and collision pairs not involving the queried input.Source: C Missing Proofs for the Compressed… · pp. 47–48
  • Algorithm-register unitaries preserve the expected collision count, while unnormalized projections on those registers cannot increase it.The proof then uses induction over queries to bound the count's growth.Source: C Missing Proofs for the Compressed… · p. 48
Loading 2609.34413v1…