Conceptio › Archive › arXiv CS

arXiv CSopen access

Quantum Security of XOR of Permutations via Fourier Analysis

Wonseok Choi et al. · arxiv_cs

arXiv CS · Papers · License: Open Access

Open Source ↗Direct PDF ↓

cryptography cybersecurity privacy security

cryptography, security, privacy, cybersecurity

Quantum Security of XOR of Permutations via Fourier Analysis Wonseok Choi1

Minki Hhan2 1

Junyoung Jang2

DGIST, Daegu, Korea [email protected]

arXiv:2609.34413v1 [quant-ph] 28 Sep 2026

KAIST, Daejeon, Korea

[email protected],

[email protected]

Abstract The XOR of two or more independent random permutations (XoP) is the prototypical pseudorandom function built from permutations achieving the security beyond the birthday bound. The security of the XoP construction is now well established against classical adversaries, however, its security against quantum adversaries that query the construction in superposition has remained widely open. We prove that the XOR of r ≥ 2 independent random permutations over {0, 1}n is indistinguishable from a random function by any q-query quantum algorithm with advantage 3 1 q 1.5 q O min , , 2rn 2(r−0.5)n 2(r−1.5)n for all q ≤ 2n /57774, where the hidden factors depend only on r. In particular, the XoP construction remains secure throughout the entire query range, far beyond the 2n/3 quantum birthday bound due to the quantum collision finding attack. To our knowledge, this is the first construction from permutations that achieves the quantum version of the beyond birthday bound security. We present several heuristic attacks suggesting the tightness of our bounds. For q ≲ 2n/2 , the quantum collision finding-based attacks heuristically give the advantage Ω(q 3 /2rn ) and Ω(q 1.5 /2(r−0.5)n ), and for q ≈ 2n , the heuristic collision counting-based attack appears to have the advantage about 2−(r−1.5)n . We use a Fourier-analytic variant of the polynomial method on the space of functions: the distinguishing advantage of any q-query quantum algorithm is controlled by the Fourier components of degree at most 2q, which is in turn controlled 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 turns out to be too large for the bound q 3 /2rn . We instead reinterpret these low-degree components as (sums of) distinguishing 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 planted collisions, which in turn are bounded using Zhandry’s small-range distributions. Finally, the q 1.5 /2(r−0.5)n bound can be proven using another bound for the planted collisions. This new bound is proven using the compressed oracle by interpreting the advantage as the other bound about random functions. It also gives a new bound for the small-range indistinguishability for (ironically) large ranges, which is of independent interest.

AI use disclosure. The Fourier-analytic approach to the quantum security of XoP was formulated by the authors, with assistance from ChatGPT 5.4 and 5.5 Pro in formalizing many technical details. From the authors’ perspective, the first nontrivial mathematical contribution from AI was a proof of the O(q 3 /N r ) bound of the degree-2 components (Lemma 6.7), obtained through a series of conversation with ChatGPT 5.5 Pro. Initial proofs of several other lemmas were also generated by ChatGPT 5.5, 5.6 Pro and Astra (in the Ultra mode), as well as Fable 5.0 and 5.1. The authors subsequently simplified these proofs and, in many cases, developed substantially different proofs that they considered more natural and accessible. The current paper is mostly written by human authors from scratch, while AI assisted in writing some paragraphs. 1

Contents 1 Introduction 1.1 Our results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Heuristic Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 3 4 8 8

2 Preliminaries

3 Fourier Analysis of Functionals 3.1 Fourier analysis of the functionals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Quantum oracle algorithms as functional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 10 12

4 Quantum Security of XoP

5 XoP Security for Many Quantum Queries 15 5.1 Proofs for low degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 5.2 Proofs for high degrees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 5.3 Maximal Magnitude and Weight of the components of µP . . . . . . . . . . . . . . . . . . . . 22 6 Few Quantum Query Security via Planted Collisions 25 6.1 Preparation: Distributions with planted constraints . . . . . . . . . . . . . . . . . . . . . . . . 26 6.2 Degree-2 component as planted collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 6.3 Degree-3 component as planted-three-collision . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 6.4 Degree-4 component as planted two collisions plus small terms . . . . . . . . . . . . . . . . . 29 6.5 Degree-6 component as planted three collisions plus small terms . . . . . . . . . . . . . . . . . 31 7 Middle Quantum Query Security via Improved Small-range Indistinguishability 33 7.1 Planted collisions in the compressed oracle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 7.2 The number of collisions in the database . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 7.3 Proof of the planted-collision bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 A Collision Bias and Heuristic Attacks

B Reductions between Planted Distributions 44 B.1 Several planted collisions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 B.2 A planted triple from a planted pair . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 B.3 Planted 4-XOR by splitting outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 C Missing Proofs for the Compressed Oracles

Introduction

Random permutations are arguably the most important idealized object in cryptography. Even in symmetrickey cryptography, the standard model assumes a keyed block cipher to be a private (pseudo)random permutation due to the wide adoption of the standardized block ciphers such as DES and AES [27, 1]. In this regard, earlier practical symmetric-key schemes are instantiated with block ciphers (i.e., random permutations) while the schemes could enjoy better security if instantiated with random functions [6, 38]. The representative examples are Wegman-Carter(-Shoup) MACs and counter mode [55, 53, 8]. The subsequent research on symmetric-key construction designs has sought to achieve better security, especially the security beyond the birthday bound— namely the beyond-birthday-bound security. In its heart, the Luby-Rackoff backward problem [6] asks how to construct (pseudo)random functions (PRFs) using random permutations. It has become a prominent cryptographic field intersecting theory and practice [6, 38, 41, 47, 43, 25, 36, 9, 18, 20, 37, 10, 19, 28, 29]. See the related works for a more detailed discussion. This paper studies the PRF constructions based on random permutations in the quantum setting, where the question becomes substantially more difficult. A quantum PRF (QPRF) [58] is a function that is indistinguishable from random functions even allowing coherent access to the function. The coherent queries prevent the classical security proofs as it potentially sees all data of the constructions. Worse, unlike the random functions, these coherent queries potentially reveal the correlation between the input-output pairs of the permutations, which hinders or complicates the beautiful compressed oracle method [57] for permutations; the known results are very lossy or restrictive [16, 39, 50, 2, 35, 24]. This difficulty appears in the current disappointing state-of-the-art, establishing tight quantum security of permutation-based cryptography remains very challenging. In particular, no permutation-based QPRFs is known to be secure beyond q = 2n/3 queries for n-bit permutations, which is already (and optimally) achieved by the plain random permutations [56, 15]. This leads to a practical concern for the future quantum cryptographic primitives. We are currently uncertain about the quantum security of any PRFs from permutations and applications [11, 12, 54, 3]. Importantly, any instantiation of these applications using block ciphers such as AES256 is only known to be secure up to 2128/3 ≈ 243 quantum queries, which is unsatisfactory to cryptographers. Resolving this question would give more efficient schemes for cryptography with quantum states and unitaries [40, 4, 45, 42] as well.

1.1

Our results

This paper shows that the exclusive-or of two or more permutations, i.e., the XoP constructions, also have a strong security in the quantum setting. This construction processes the input x by XoP[r](x) := P1 (x) + · · · + Pr (x), which we simply refer to as the XoP[r] construction, where + denotes bitwise XOR and P1 , ..., Pr are independent random permutations over n-bit strings. 2 q . In the classical setting, the tight security of the XoP construction for r = 2 was O min 2q2n , 21.5n The first bound dominates for q ≲ 20.5n and is proven in [30, 17]. The second bound dominates for q ≳ 20.5n and recently proven in [28, 31] using Fourier analysis. The latter bound can be generalized to q/2r−0.5 for r ≥ 2. These bounds are tight, matching the known attack by Patarin [47]. Our main theorem proves the quantum security of the XoP construction. Theorem 1.1 (Informal). Fix a constant r ≥ 2. For every 0 ≤ q ≪ 2n , any quantum distinguisher making q quantum queries to either the XoP[r] construction or the random functions has advantage at most 3 q q 1.5 1 O min , , . 2rn 2(r−0.5)n 2(r−1.5)n In particular, the XoP[r] construction for r ≥ 2 is secure up to q ≈ 2n queries. 3

The above theorem concerns an ideal setting where the adversary does not have access to the primitive queries to P1 , ..., Pr . In practice, the XoP constructions can be instantiated using block ciphers with independent random keys in the quantum ideal cipher model. When the underlying block cipher has a sufficiently long key, say κ-bit keys, the corresponding keyed permutations can be viewed as private random permutations in the quantum ideal cipher model, with the distinguishing advantage loss rq 2 /2κ by applying the quantum search bound r times [7, 13] (assuming there is no collisions in the r keys). Therefore, our result can be lifted to the quantum ideal cipher model with such a key length; for example, AES256 provides a heuristic instantiation with κ = 256. To our knowledge, this gives the first QPRF constructions in the quantum ideal cipher model whose security goes beyond the 2n/3 quantum queries. In fact, our theorem shows that the XoP construction is still indistinguishable from random functions near 2n queries; we are not even aware of any construction secure against 2n/2 queries.

1.2

Technical overview

We focus on the XOR of two permutations in this overview. Our proof can be viewed as a quantum analogue of the Fourier analytic security proofs developed in a recent line of works [31, 32, 28, 29], which have established tight classical security bounds for the XoP constructions. The main object in these analyses is the classical response transcript. More precisely, after fixing the q distinct query points, the corresponding response vector lies in ({0, 1}n )q . For the XoP construction, this vector is distributed as the sum of two vectors sampled without replacement, while this vector is uniform random for the truly random functions. The Fourier analysis compares these two distributions of vectors in the Fourier domain. Polynomial method. In our quantum setting, however, there is no proper notion of the transcript because of the coherent quantum queries. We instead employ a Fourier-analytic variant P of the polynomial method [5]. Our starting point is the following well-known observation. Let |b a⟩ := √12n z∈{0,1}n χa (z) |z⟩ = H ⊗n |a⟩ be a Fourier basis state where χa (z) = (−1)⟨a,z⟩ . For an oracle Of that evaluates a function f , i.e., that maps |x, y⟩ 7→ |x, y + f (x)⟩ coherently, we have Of |x, b a⟩ = (−1)⟨a,f (x)⟩ |x, b a⟩ = χa (f (x)) |x, b a⟩ . n

Motivated by this, we consider a vector γ = (γx )x∈{0,1}n ∈ ({0, 1}n )2 and define its Fourier degree by |γ| := |{x ∈ {0, 1}n : γ(x) ̸= 0n }|. Each vector gives its Fourier character defined by χγ (f ) := (−1)

x∈{0,1}n ⟨γ(x),f (x)⟩

χγ+η (f ) = χγ (f ) · χη (f ).

The above observation shows that the amplitudes of each basis vector can be written as a linear sum of the Fourier characters, and each query increases the degree of amplitudes by at most 1. The acceptance probability Pr AOf = 1 therefore must be represented by a low-degree polynomial of the Fourier characters. By regarding it as a function from f to the real number in [0, 1],1 the Fourier expansion gives i h X PA (f ) := Pr AOf = 1 = PbA (γ) · χγ (f ), PbA (γ) = Eg←F χγ (g)PA (g) . |γ|≤2q

Here, g ← F denotes a sample from the uniformly random functions. The degree bound ≤ 2q is because the amplitudes of the final state of a q-query algorithm are Fourier polynomials of degree at most q. This observation, or closely related variants in representation-theoretic language, has been used in many analyses of quantum algorithms [58, 51, 57, 50, 2]. It allows us to bound the probability of the oracle algorithm through their bounded-degree Fourier statistics. 1 That is, this is a functional that maps a function to a scalar. In the main body, we refer this Fourier analysis as the Fourier analysis of functionals to distinguish the different use of the term function.

Distinguishing advantage as an inner product. We introduce some definitions to proceed the overview. Let N := 2n , and let F = {f : {0, 1}n → {0, 1}n } be the space of functions. We write ⟨g, h⟩ := Ef ←F [g(f )h(f )]

and

∥g∥2 := ⟨g, g⟩.

With this notation, we can write Pr [AOf = 1] =

f ←F

X PA (f ) f ∈F

|F|

= Ef ←F [1(f )PA (f )] = ⟨1, PA ⟩

where 1 is a constant function with output 1. Similarly, define the density of the XoP distribution relative to this uniform measure by µXoP (f ) :=

PrP,Q←P [P + Q = f ] = N N Pr [P + Q = f ]. P,Q←P PrP ←F [P = f ]

An analogous calculation gives Pr [AOP +Q = 1] = ⟨µXoP , PA ⟩

P,Q←P

and the distinguishing advantage can be written as Pr [AOP +Q = 1] − Pr [AOf = 1] = ⟨PA , µXoP − 1⟩. f ←F

P,Q←P

The above discussion about the Fourier analysis applies on these probabilities, showing that PA has Fourier degree at most 2q and ∥PA ∥2 ≤ 1. Decomposition by Fourier degree. We consider the following two terms: 1. (·)=d that denotes the sum of all Fourier components of degree exactly d; 2. (·)≤d that denotes the sum of all Fourier components of degree ≤ d, i.e., the sum of all (·)=k for k ≤ d. The orthogonality of the Fourier components, following the so-called Efron–Stein orthogonal decomposition [46, Chapter 8], gives the advantage bound by |⟨PA , µXoP − 1⟩| = |⟨PA , (µXoP − 1)

≤2q

⟩| =

2q X

⟨PA , µ=k XoP ⟩ k=1

≤

2q X

|⟨PA , µ=k XoP ⟩|

k=1

where we use the fact that PA is of degree at most 2q in the first equality, and use (µXoP − 1)=0 = 0 and (1)=k = 0 for all k ≥ 1. The Cauchy–Schwarz inequality gives the first way to bound this: ≤

2q X

∥PA ∥2 µ=k XoP 2 ≤

k=1

2q X

µ=k XoP 2

k=1

where we use ∥PA ∥2 ≤ 1. For most degrees, we obtain the required bound directly by estimating µ=k XoP 2 through a delicate combinatorial argument. In particular, the second advantage bound 2−0.5n is obtained by this strategy alone. Turning Fourier term into planted collision distinguisher. To prove the security q 3 /22n for the XoP construction, the above strategy turns out to be insufficient. In particular, the degree-2,3,4,6 components have too large ℓ2 -norm. We use a different proof strategy; namely, we turn the Fourier-analytic components ⟨PA , µ=k XoP ⟩ to the distinguishing advantage to some other problems. We focus on the degree-2 component, or more precisely ⟨PA , µ=2 XoP ⟩, in this overview. The degree-2 term exhibits the statistics of two outputs of the functions, such as collisions. This component turns out to be the dominant term in the bound, which was the dominant term in the classical security as well [48, 28]. 5

This intuition holds in the quantum setting as well. Write JXK to denote the truth value of the statement X. We will establish the following identity at the end of the overview: µ=2 XoP (f ) =

1 N −1

2 X x<x′

(N Jf (x) = f (x′ )K − 1) ,

(1)

which means that the degree-two component can be understood as a collision statistic up to a multiplicative factor; the truth value Jf (x) = f (x′ )K is 1 if and only if f collides at x ̸= x′ . Fix x ̸= x′ and fix a function f . Observe that • N1N is the probability that f is sampled from F; • N1N · N Jf (x) = f (x′ )K is the probability that f is sampled from F conditioned on f (x) = f (x′ ).

From this observation, we can interpret µ=2 XoP (f ) as, up to a constant factor, the difference between the density functions of 1) the distribution of the true random function F and 2) the distribution of random functions conditioned on a planted collision f (x) = f (x′ ) for random x ̸= x′ . That is, we can reinterpret the inner product |⟨PA , µ=2 XoP ⟩| = O

Pr [AOf = 1] − Pr [AOf = 1]

f ←DPC

f ←F

as a distinguishing advantage of another problem: 1) a random function with a planted collision and 2) an unconditional random function. Here, DPC denote the planted collision distribution described above. Planted collisions vs. random functions. We directly prove the distinguishing advantage O(q 3 /N 2 ) of this problem using Zhandry’s small range distribution indistinguishability [58], which shows that the distinguishing advantage of the following two distributions is bounded above by O(q 3 /R): The first one is the uniformly random functions from {0, 1}n to {0, 1}n , and the second one is the distribution DR of random “small-range” functions, which are obtained by composing two independent random functions g ◦ h where h : {0, 1}n → [R] and g : Im(h) → {0, 1}n . Ironically, we use the large range function with R ≳ N 2 . In this case, h has a unique collision with a constant probability, in which case g ◦ h is distributed according to the planted collision distribution. Therefore, the distinguishing DR and F is closely related to the above problem. It turns out that any R ≳ N 2 exhibits such a relation; when there is no collision in h, the distribution of g ◦ h becomes the uniformly random function so that the related terms are canceled out, and R → ∞ makes the unique collision dominate among the other terms, deriving the upper bound O(q 3 /N 2 ). The other degrees are more involved, but similar strategies show the desired bounds. Very roughly, we connect the degree-3,4,6 terms with the other problems using similarly to Eq. (1); for example, the degree-3 term is related to the distinguishing advantage between the random functions and the random planted-3-collision functions with a constraint f (x1 ) = f (x2 ) = f (x3 ). The degree-4 term is related to the random functions with two planted collisions together with the random functions with the planted 4-XOR f (x1 ) + f (x2 ) + f (x3 ) + f (x4 ) = 0n . We reduce the hardness of these problems to the planted collision advantage similarly to the above (yet in a slightly more involved way). The bound for the degree-2 is tight in the relevant parameter range, as suggested by the corresponding quantum collision-statistics attack below. Another bound for the planted collisions. To derive the O(q 1.5 /N 1.5 ) security bound, we observe that the term in Eq. (1) can be interpreted some collision-related term in the language of the compressed oracle P [57, 22]. By writing the overall final state |Ψ⟩ of the algorithm and (purified) database by √ 1 N g |ψ g ⟩ |g⟩, N

the advantage can be expressed by " # X 2 1 ⟨µPC − 1, PA ⟩ = Ef ←F PA (f ) Jf (x) = f (y)K − N −1 N x<y ! X X 2 1 f g = N Colxy − I |f ⟩ ψq Π ψq ⟨g| N (N − 1) N x<y f,g∈F ! X 2 1 = ⟨Ψ| Π Colxy − I |Ψ⟩ N −1 N x<y where Π is the projection to the acceptance space of the algorithm, and Colxy is the indicator function for the database on inputs x, y. This expression can be bounded by O(q 1.5 /N 1.5 ) using the compressed oracle machinery alone, proving the desired result. Intriguingly, the above-discussed small-range to planted collision can be reversed, and q 1.5 /N 1.5 gives an alternative bound for the small-range distribution indistinguishability for large range. See Corollary 7.3. Proof of Eq. (1). We now discuss how to prove Eq. (1). Let P be the distribution of uniformly random permutations, and let µP (f ) = N N Prp←P [p = f ] be the density function of P. The degree-2 term expands, together with the convolution formula, X X µ=2 µ b=2 µ b2P (γ)χγ (f ). (2) XoP (f ) = XoP (γ)χγ (f ) = |γ|=2

|γ|=2

We extensively use the following basic observation x∈{0,1}n (−1)⟨a,x⟩ = N Ja = 0n K and its variations. For example, for y, y ′ ̸= 0n , we have X X X ′ ′ ′ (−1)⟨u,y⟩+⟨v,y ⟩ = (−1)⟨u,y⟩+⟨v,y ⟩ − (−1)⟨u,y+y ⟩ = −N Jy = y ′ K P

u,v

u̸=v

where all u, v ∈ {0, 1} . In the second equality, the first term vanishes because of Jy = 0n K = 0, and the last term is simplified using Jy + y ′ = 0n K = Jy = y ′ K. n Let γ = (γx )x∈{0,1}n ∈ ({0, 1}n )2 be such that |γ| = |supp(γ)| = 2 where supp(γ) = {x ∈ {0, 1}n : γ(x) ̸= 0n }. Let x, x′ be the elements of supp(γ). Observe that for a uniform random permutation p ← P, (p(x), p(x′ )) is uniform over ordered distinct pairs, hence X ′ ′ Jγ(x) = γ(x′ )K 1 (−1)p(x)·γ(x)+p(x )·γ(x ) = − . Ep←P [χγ (p)] = N (N − 1) N −1 ′ p(x)̸=p(x )

It is not hard to see that the above term coincides with µ bP (γ) using the definition of the Fourier coefficient and the fact that χγ is real-valued. We omit this proof in this overview. Now we go back to Eq. (2). Plugging the above identity gives X X Jγ(x) = γ(x′ )K2 χγ (f ) µ b2P (γ)χγ (f ) = (N − 1)2 ′ |γ|=2

supp(γ)={x<x }

where we use the lexicographic order in x < x′ . Writing γ(x) = γ(x′ ) = y ̸= 0n and using χγ (f ) = ′ (−1)⟨y,f (x)+f (x )⟩ , we can write this as X

′ X (−1)⟨y,f (x)+f (x′ )⟩ X (−1)⟨y,f (x)+f (x )⟩ 1 = − 2 2 (N − 1) (N − 1) (N − 1)2 ′ ′ n

x<x′ ,y̸=0

x<x ,y

x<x

X N Jf (x) = f (x′ )K − 1 (N − 1)2

x<x′

This proves Eq. (1). Similar calculations derive analogous algorithmic interpretations of different degrees. 7

1.3

Heuristic Attacks

We briefly discuss the (potential) distinguishing attack for the XoP constructions in Appendix A. The description focuses on the high-level ideas of the attack, with some statistical evidence or heuristic reasoning of their advantages. Formalizing them needs further analysis. Most attacks for q ≪ N are related to the pairwise statistics, i.e., collisions of the construction. On the other hand, the attack for q ≥ N/2 uses the quantum parity algorithm [34], achieving the advantage 1/2. Table 1 summarizes the different attacks and security bounds on XoP[r]. Our lower bounds match to the heuristic attacks for q ≲ N 1/2 and q ≈ N . It is unclear which is tight for the range N 1/2 ≳ q < N/2. Range q ≲ N 1/3 N 1/3 ≲ q ≲ N 1/2 N 1/2 ≲ q < N/2 q ≥ N/2

Classical 2 q Θ ⋆ r N 2 q Θ Nr q Θ N r−1/2 -

Q. attack q3 ? Nr 3/2 q ? N r−1/2 √ q ? N r−1 Θ(1)

Our bound 3 q O r N 3/2 q O N r−1/2 O N 3/2−r

Q. attack type

Collision counting

Parity

Collision finding Collision counting

Table 1: The classical results, quantum attacks and our bounds. ⋆ denotes that the security bound is only known for r = 2. The question mark (?) denotes that the attack analysis is heuristic.

Collision probability. All attacks above except for the parity attack exploit the collision statistics as follows from [48]. For two distinct inputs x, x′ , it holds that Pr [XoP[r](x) = XoP[r](x′ )] =

1 (−1)r + . N N (N − 1)r−1 r

(−1) On the other hand, the collision probability of random functions is 1/N , having the bias δr = N (N −1)r−1 ≈ r −r (−1) N in the collision probability in two cases. This bias allows the collision-based distinguishing attack. For example, running the quantum collision finding algorithm [15] and outputs 1 when a collision is found has the advantage q 3 /N r for q ≲ N 1/3 . The details of the attacks are described in Appendix A.

1.4

Related Works

Classical analyses of XoP and variants. Most of the security analysis of XoP is focused on the r = 2 case. Various proof techniques have been developed, and the XoP construction has been a testbed of the techniques. Lucks [41] first gave an early asymptotic analysis. Patarin [47] claimed to prove the bound O(q 2 /N 2 ), but the proof was incomplete. Dai, Hoang, and Tessaro [25] proved the bound O(q 1.5 /N 1.5 ). Dutta, Nandi, and Saha [30] resurrect the bound of Patarin [47]. The multi-user security was tightened by Chen, Choi, and Lee [17]. Independently, the tight bound O(q/N 1.5 ) was proven using the Fourier analysis by Eberhard [31] but had been unknown to the symmetric-key cryptography community. Dinur extended this to XoP[r] with r > 2 even in the multi-user setting [28], improving the previous analysis for r > 2 [23, 19]. There are XoP-like constructions based on other building blocks rather than block ciphers. For example, the sum of the Even-Mansour encryption [18] and the XOR of the tweakable permutation [21] have been studied in the literature. Quantum analyses of XoP and variants. As far as we are aware of, the only quantum result of the XoP construction is [44]. They study the XoP in the Q1 model, where the underlying block cipher can be quantumly accessible but the XoP is only available through classical queries. They proved the security

about rq 2 /2κ + q/2n in the Q1 model.2 Our result gives the Q2 model security bound about rq 2 /2κ + min(q 3 /2rn , 1/2(r−1.5)n ), which is even better than their Q1 bound for r ≥ 2. The variants have been studied in the quantum setting as well. The keyed sum of permutations and other variants are proven secure up to 2n/3 queries in the Q1 model [26]. For the sum of Even-Mansour, a polynomial time quantum attack is known in the Q2 model [52].

Preliminaries

n Let F2 = {0, 1} be the finite field of two elements 0 and 1. For x = (xi )i∈[n] , y = (yi )P i∈[n] ∈ {0, 1} , we n define their exclusive OR (XOR) by x + y := (xi ⊕ yi )i∈[n] and inner product by ⟨x, y⟩ := i=1 xi · yi mod 2. For a finite set S, we write s ← S to denote that s is sampled uniformly at random from S. We also write (s1 , ..., st ) ← S (∗t) to denote that the elements of {si }i∈[1..t] are sampled uniformly at random from S without replacement, i.e., {si }i∈[1..t] is pairwise distinct. For an event X, we write JXK for its indicator, i.e., JXK = 1 if X occurs and JXK = 0 otherwise. Throughout this paper, n denotes a fixed positive integer, and we write N := 2n . For integers a ≥ b ≥ 0, we write

(a)b := a(a − 1) · · · (a − b + 1). Probability distributions. For a probabilistic distribution DD over a finite set X, we write µD (x) = |X| · Pry←DD [x = y] = |X| · Pr[x ← DD ]. Observe that Ex←X [µD (x)] = 1 and the following identity Ex←X [µD (x) h(x)] =

X 1 Pr[x ← DD ] · · h(x) = Ex←DD [h(x)] |X| 1/|X|

(3)

x∈X

which shows that the multiplicative factor µD converts the expectation with respect to the uniform distribution on X into the expectation with respect to our interested distribution DD . Let F be a finite function space, and let DD and DE be two probability distributions over F. For f ∈ F, write Of for the quantum oracle associated with f . Namely, Of maps |x, y⟩ to |x, y + f (x)⟩ coherently. For a quantum oracle algorithm A, we define its distinguishing advantage between two distributions DD and DE by Advdist (DD , DE ; A) := Pr AOf → 1 − Pr AOf → 1 . f ←DD

f ←DE

For q ≥ 0, we define the advantage over all q-query algorithms Advdist q (DD , DE ) :=

max

q-query A

Advdist (DD , DE ; A)

where the maximum is over all quantum oracle algorithms making at most q quantum queries to the oracle.

Fourier Analysis of Functionals

We denote the set of all functions from n-bit inputs to n-bit outputs by Fn = {f : {0, 1}n → {0, 1}n }. When the bit-length is clear from the context, we omit the subscript and just denote them by F. The set F has a natural group structure by extending the XOR operation by (f + g)(x) = f (x) + g(x) for f, g ∈ F b with the elements denoted by Greek characters, e.g., γ and x ∈ {0, 1}n . We sometimes use the notation F b to denote or η, to denote the identical group (F, +) to distinguish their use.3 Looking ahead, we will use F the set of Fourier basis only. 2 To be precise, they assumed that the Grover algorithm is optimal in this attack for the concrete block cipher. This can be proven in the ideal cipher model using [7] as discussed above. 3F b denotes the (Pontryagin) dual group, which is isomorphic to F since it is finite.

Functionals.

We use the Fourier analysis on the set of functions of functions: H = {H : F → C} .

To clarify the difference, we use the term functionals to denote the elements in H with the upper case letters. n By identifying F as ({0, 1}n )2 , the Fourier analysis of the functionals is essentially equivalent to one of the Boolean functions with an exponentially long input. The set of functionals H is equipped with the inner product for H, G ∈ H i X H(f )G(f ) h ⟨H, G⟩ = Ef ←F H(f )G(f ) = . |F| f ∈F

The corresponding norm is defined by ∥H∥2 = |⟨H, H⟩|1/2 . The Cauchy–Schwarz inequality implies that ⟨H, G⟩ ≤ ∥H∥2 · ∥G∥2 .

3.1

Fourier analysis of the functionals

Characters. For a ∈ {0, 1}n , let χa : {0, 1}n → {−1, 1}, χa (x) := (−1)⟨a,x⟩ . These satisfy, for all a, b, x ∈ {0, 1}n , i h (4) χa (x)χb (x) = χa+b (x) and Ex←{0,1}n χa (x)χb (x) = Ja = bK. b the character χγ ∈ H is For γ ∈ F, χγ (f ) :=

P χγ(x) f (x) = (−1) x∈{0,1}n ⟨γ(x),f (x)⟩ .

(5)

x∈{0,1}n

b are The support and the degree of γ ∈ F supp(γ) := {x ∈ {0, 1}n : γ(x) ̸= 0n }

and

|γ| := |supp(γ)|,

so |γ| is the number of nontrivial factors in Eq. (5). Clearly |γ + η| ≤ |γ| + |η|. By Eq. (4), characters are b multiplicative and orthonormal: for γ, η ∈ F, i h ⟨χγ , χη ⟩ = Ef ←F χγ (f )χη (f ) = Jγ = ηK, (6) χγ χη = χγ+η , χγ (f + g) = χγ (f ) χγ (g). b = |F| = dim H, the characters form an orthonormal basis of H. Since |F| Fourier expansions. H ∈ H) as follows.

The orthonormal basis of characters gives the Fourier expansion of H : F → C (i.e.,

Theorem 3.1 (Fourier expansion of functionals). A functional H : F → C can be decomposed by h i X b b H(f ) = H(γ)χ such that H(γ) = ⟨χγ , H⟩ = Ef ←F χγ (f )H(f ) , γ (f ), b γ∈F

b where H(γ) is called the Fourier coefficient of H at γ.

Proof. Since {χγ }γ∈F b forms an orthonormal basis of H, every H ∈ H admits a unique expansion of the form H=

cγ χγ

b γ∈F

for some coefficients cγ ∈ C. Taking the inner product with χη and using orthonormality, we obtain X X ⟨χη , H⟩ = ⟨χη , cγ χγ ⟩ = cγ ⟨χη , χγ ⟩ = cη . b γ∈F

b γ∈F

Therefore, h i cη = ⟨χη , H⟩ = Ef ←F χη (f )H(f ) . b we have Since this holds for every η ∈ F, X b H(f ) = H(γ)χ γ (f ),

b H(γ) = ⟨χγ , H⟩.

b γ∈F

This proves the theorem. The Fourier spectrum of H is the collection of all Fourier coefficients

b H(γ)

. b γ∈F

b is nonzero. The Fourier support of H is the set of γ such that H(γ) The orthogonality of the characters show that for H, G ∈ H, ⟨H, G⟩ =

b G(γ). b H(γ)

(7)

b γ∈F

For a nonnegative integer d, the degree-d component of H, denoted by H =d , and the low-degree components of H up to degree d, denoted by H ≤d , are defined as follows: X X b H =d := H(γ)χ and H ≤d := H =i . γ, |γ|=d

i≤d

It is worth noting that H =0 = Ef ←F [H(f )]·1. We refer to the degree-d weight4 and the degree-d maximal magnitude of H as n o X 2 b b ∥H =d ∥22 = H(γ) , M =d [H] := max H(γ) (8) |γ|=d

|γ|=d

where the equality holds due to the orthogonality of the characters. For a functional H ∈ H, we say the Fourier degree of H, denoted by deg(H), by the minimum nonnegative integer d such that H = H ≤d holds, which means that H is the sum of Fourier characters of degree ≤ d. Constant functionals have Fourier degree 0. Taking conjugate does not change the degree. For H, G ∈ H, we have deg(H + G) ≤ max(deg(H), deg(G)),

deg(HG) ≤ deg(H) + deg(G).

4 Dinur [28] uses W =d [H] instead of ∥H =d ∥2 to refer to the degree-d weight of H. 2

(9)

Convolution.

The convolution of G, H ∈ H is (G ∗ H)(f ) := Eg←F [G(f + g)H(g)].

b G(γ). b \ Lemma 3.2. H ∗ G(γ) = H(γ) Proof. In [46, Theorem 1.27], the same statement for real-valued boolean functions is proven. It can be extended to our case as follows. i h \ H ∗ G(γ) = Ef ←F χγ (f )H ∗ G(f ) h i = Ef ←F χγ (f )Eg←F [H(f + g)G(g)] i h = Eg,h←F χγ (g + h)H(h)G(g) h i = Eg,h←F χγ (h)H(h)χγ (g)G(g) b G(γ) b = H(γ) since χγ = χγ and by Eq. (6). Distributions of XOR of functions. One main target of the functional Fourier analysis is the probabilistic density functions over F. Let DD , DE be distributions over F and write µD , µE to denote their ←DD ] density functions, i.e., µD (f ) = Pr[f1/|F| . Lemma 3.3. µD ∗µE is the density of the distribution of h = f +g where f ← D and g ← E are independent. Proof. Using µD (f ) = |F| PrD [f ], (µD ∗ µE )(h) =

X µD (h + g)µE (g) g∈F

|F|

= |F|

g∈F

= |F|

3.2

Pr [f = h + g] ′Pr [g ′ = g] g ←E

f ←D

f ←D, g←E

[f + g = h].

Quantum oracle algorithms as functional

Recall the quantum oracle Of for f computes Of : |x, y⟩ → |x, y + f (x)⟩ coherently. For a ∈ {0, 1}n , we define the state |b a⟩ by X 1 |b a⟩ := √ χa (z) |z⟩ = H ⊗n |a⟩ , n 2 z∈{0,1}n

(10)

Of |x, b a⟩ = (−1)⟨a,f (x)⟩ |x, b a⟩ = χa (f (x)) |x, b a⟩

(11)

then, it is immediate that

where χa is a character. This means that a single query increases the degree of the amplitudes by 1. The following theorem shows that this gives a polynomial-like representation of the success probability of the algorithm. Theorem 3.4. Let f be a function from {0, 1}n to {0, 1}n . Let A be a quantum oracle algorithm having access to Of and outputting a bit b ∈ {0, 1}. Then, there exists a functional PA (which may depend on the input of A, if any) of Fourier degree ≤2q such that the probability that A outputs 1 equals to PA (f ). In other words, the functional PA (f ) := Pr AOf → 1 has the Fourier degree ≤ 2q and can be decomposed by X Pr AOf → 1 = PA (f ) = PbA (γ)χγ (f ). |γ|≤2q

In particular, ∥PA ∥2 ≤ 1. 12

We call the functional PA above the representing polynomial of A. The proof of this theorem is essentially the same as the proof used in the lower bounds by polynomials [5]. We defer the proof of this theorem to the end of this section. We extensively use the following theorem derived from the above theorem. Theorem 3.5. Let DD be a distribution of the functions in F = {{0, 1}n → {0, 1}n }. Let A be a binary output quantum algorithm making at most q quantum queries to the oracle. Let PA = Pr AOf → 1 be the functional from Theorem 3.4. Then, it holds that Pr [AOf → 1] − Pr [AOf → 1] = ⟨µD − 1, PA ⟩ = ⟨(µD − 1)≤2q , PA ⟩

f ←DD

f ←F

where f ← F denotes the uniform random sampling and µD (f ) denotes the density function Pr[f ← DD ]/(1/|F|) of DD . Proof. For the random function f sampled from DD , the averaged probability that A outputs 1 is X Pr [AOf → 1] = Pr[f ← DD ] Pr AOf → 1 f ←DD

f ∈F

X 1 Pr[f ← DD ] PA (f ) = Ef ←F [µD (f )PA (f )] = ⟨µD , PA ⟩ = |F| 1/|F| f ∈F

where in the last equality we use the fact that µD is real-valued so µD = µD . Noting that the density function of the uniform distribution is the constant function 1, we have Pr [AOf → 1] − Pr [AOf → 1] = ⟨µD , PA ⟩ − ⟨1, PA ⟩ = ⟨µD − 1, PA ⟩.

f ←DD

f ←F

The final equality holds because PA is of Fourier degree ≤ 2q and Eq. (7). The theorem immediately yields the following advantage bound. Theorem 3.6. Let DF be the uniform distribution over F and DD be an arbitrary distribution over F. For any q-query quantum algorithm A, one has Advdist (DD , DF ; A) = ⟨(µD − 1)≤2q , PA ⟩ . By decomposing µD − 1 into the degree-d components for d ≤ 2q, we have ⟨(µD − 1)≤2q , PA ⟩ =

2q 2q X X ⟨(µD − 1)=d , PA ⟩ = ⟨µ=d D , PA ⟩ d=0

(12)

d=1

because the constant function 1 has degree 0 and µ=0 D = Ef ←F [µD (f )]1 = 1. Therefore, this theorem reduces the PRF advantage for f ← DD to analyze the low-degree components of µD . We now prove Theorem 3.4. Proof. We first show the following claim. Claim 3.7. The final state of a q-query algorithm (with the deferred measurement) can be written by X p(q) z (f ) |z⟩ z (q)

where pz

is a functional of degree ≤ q.

Proof of Claim. Note that a q-query algorithm is represented by an alternating sequence of oracle query Of and an oracle-independent unitary U . Applying unitary U , as a linear map, does not increase the Fourier degree. We only focus on the oracle queries. Before proceeding, observe that for each query for the Fourier basis (Eq. (10)) it holds that Of (χγ (f ) |x, b a⟩) = χγ (f ) · χa (f (x)) |x, b a⟩ = χγ+aδx (f ) |x, b a⟩ b is such that aδx (x) = a and aδx (y) = 0n for y ̸= x. We use Eq. (11) and Eq. (6) in the first where aδx ∈ F and second equality. It holds that |γ + aδx | ≤ |γ| + |aδx | ≤ |γ| + 1. (0)

We use the mathematical induction to prove the claim. For the state before any query, pz is independent of f , thus the base step holds. P (k−1) Next, consider the state before applying the k-th query z pz (f ) |z⟩ for k ≤ q. The Fourier degree of (k−1) pz is bounded above by k−1 by the inductive hypothesis. Then, a single query increases the Fourier degree (k−1) of each term in pz by at most 1, so that the degree after the query is bounded above by (k − 1) + 1 = k. This proves the claim. P Write |ϕq ⟩ = z pz (f ) |z⟩ to denote the final state of the algorithm where pz is a functional of Fourier degree ≤ q. Let (Π0 , Π1 = I − Π0 ) be the final binary measurement of the algorithm. Then, the probability that A outputs 1 is Pr AOf → 1 = ⟨ϕq | Π1 |ϕq ⟩ X ⟨z| pz (f )Π1 pw (f ) |w⟩ = z,w

⟨z| Π1 |w⟩ · pz (f )pw (f )

z,w

where deg(pz pw ) ≤ deg(pz )+ deg(pw ) ≤ 2q because of Eq. (9). Since the summation does not increase the Fourier degree, PA (f ) = Pr AOf → 1 is a functional of Fourier degree ≤ 2q. The final “in particular” part is obvious because |PA (f )| ≤ 1 for all f .

Quantum Security of XoP

This section introduces notation and states our main security theorem for XoP constructions. We first define the set of all permutations on n-bit strings by Pn = {p ∈ Fn : p is injective}. In the following, we fix n, omit the subscript, and just denote Pn by P. Recall that we defined the XOR of permutations XoP[r] := P1 + · · · + Pr where P1 , . . . , Pr ← P. We denote the distribution of XoP[r] as DXoP[r] . In particular, DXoP = DXoP[2] . We consider quantum-accessible XoP[r] constructions in which a quantum adversary can make at most q quantum queries to a given XoP[r] but has no access to the inner primitives Pr . We note that the asymptotic formula hides multiplicative factors depending on r, as r is typically chosen as a constant. In this setting, the quantum security of XoP can be stated as follows: Theorem 4.1 (Quantum security of XoP). Let n, r, q be integers such that n ≥ 5, 2 ≤ r ≤ 2n /16 and 0 ≤ q ≤ 2n /57774. Let N = 2n . It holds that 3 q q 3/2 1 Advdist (D , D ) = O min , , . F XoP[r] q N r N r−1/2 N r−3/2 We prove the last bound in Section 5, the first bound in Section 6, and the second bound in Section 7. 14

XoP Security for Many Quantum Queries

The goal of this section is to prove the following lemma. We assume that n ≥ 5, 2 ≤ r ≤ N/16, and q ≤ N/57774 hold in this section. N N Lemma 5.1. If n ≥ 5, r ≤ 16 , and q ≤ 57774 , then

Advdist q (DXoP[r] , DF ) = O

1 N r−1.5

To prove the above lemma, we will use Fourier analysis explained in Section 3. We denote the density function of XoP[r] as µXoP[r] . Then we can express the advantage of q-query quantum algorithm A attacking XoP[r] by Theorem 3.6 and Equation (12) as follows: Adv

dist

≤2q

(DXoP[r] , DF ; A) = ⟨(µXoP[r] − 1)

, PA ⟩ ≤

2q X

=d ⟨µ=d XoP[r] , PA ⟩ .

(13)

d=1

We bound the advantage using the Cauchy–Schwarz inequality as follows ≤

2q X

=d ∥µ=d XoP[r] ∥2 · ∥PA ∥2 ≤

2q X

! 12 2 ∥µ=d XoP[r] ∥2

(14)

d=1

P =d 2 where we use d ∥PA ∥2 ≤ ∥PA ∥22 ≤ 1 as shown in Theorem 3.4. The only remaining task is bounding the sum of µ=d XoP[r] . The following lemma shows such upper bounds. We separately deal with d ∈ {1, 2, 3, 4, 6}, which will be used in the later section. The remainder of this section will be dedicated to prove this lemma. Lemma 5.2. For r ≥ 2 and N = 2n ≥ max{16r, 96} and 5 ≤ dmax ≤ N/28887, • µ=1 XoP[r] = 0, 2 2r−3 • ∥µ=2 , XoP[r] ∥2 ≤ 1/N =3 2 4r−5 • ∥µXoP[r] ∥2 ≤ O 1/N , 2 4r−6 • ∥µ=4 ∥ ≤ O 1/N , XoP[r] 2 2 6r−9 • ∥µ=6 , and XoP[r] ∥2 ≤ O 1/N Pdmax =d =5 2 • ∥µXoP[r] ∥2 + d=7 ∥µXoP[r] ∥22 ≤ O 1/N 6r−8 . In particular, all of the above terms are bounded above by O(1/N 2r−3 ). Now we can give an upper bound of Equation (14) by plugging the last part of Lemma 5.2 by decomposing the summand accordingly. ! 12 21 2q X 1 1 =d 2 ∥µXoP[r] ∥2 ≤ O =O . N 2r−3 N r−1.5 d=1

which directly proves Lemma 5.1 as it is an upper bound of Advdist (DXoP[r] , DF ; A).

5.1

Proofs for low degrees

We first observe that the density function of the distribution of XoP[r] follows the convolution µP ∗ ... ∗ µP of r µP ’s because of Lemma 3.3. Then, by Lemma 3.2, we have µ bXoP[r] (γ) = µ bP (γ)r .

(15)

Therefore, our analysis boils down to analyze the Fourier coefficient µ bP (γ) of uniformly random permutations. We will use the following formula. Here, recall z1 , ..., zd ← ({0, 1}n )(∗d) denotes the sampling without replacement, i.e., zi ̸= zj for 1 ≤ i < j ≤ d. 15

Lemma 5.3. Suppose |γ| = d with supp(γ) = {x1 , ..., xd }. Then " d # Y µ bP (γ) = Ez1 ,...,zd ←(({0,1}n )(∗d) χγ(xi ) (zi ) . i=1

Proof. We expand µ bP (γ) using the Fourier expansion formula in Theorem 3.1 by µ bP (γ) = ⟨χγ , µP ⟩ = Ef ←F [χγ (f )µP (f )] = Ep←P [χγ (p)] where we use the property of density from Eq. (3) in the last equality. Using Eq. (5) and supp(γ) = {x1 , ..., xd }, we can compute this as follows " d # " d # Y Y Ep←P χγ(xi ) (p(xi )) = Ez1 ,...,zd ←(({0,1}n )(∗d) χγ(xi ) (zi ) i=1

i=1

which completes the proof. We also use the following identity occasionally, which can be easily seen by writing χy (z) = (−1)⟨y,z⟩ : X X χy (z) = N Jy = 0n K, and χy (z) = N Jz = 0n K. (16) z∈{0,1}n

5.1.1

y∈{0,1}n

Degree-1 Component Vanishes

b with |γ| = 1, then there exists a unique We first show that the degree-1 component becomes 0. Fix γ ∈ F n x1 such that γ(x1 ) = y1 ̸= 0 . Using Lemma 5.3 and Eq. (16), we have µ bP (γ) = Ez←{0,1}n [χy1 (z)] = 0. This shows the degree-1 Fourier coefficient of µ bXoP[r] (γ) = µ bP (γ)r is all zero, proving the first item of Lemma 5.2. 5.1.2

Degree-2 Component

b with supp(γ) = {x1 , x2 }. Write γ(x1 ) = y1 ̸= 0n , γ(x2 ) = y2 ̸= 0n . Lemma 5.3 gives For d = 2, fix γ ∈ F µ bP (γ) = Ez1 ,z2 ←({0,1}n )(∗2) [χy1 (z1 )χy2 (z2 )] =

X χy (z1 )χy (z2 ) 1

z1 ̸=z2

P =

z1 ,z1 χy1 (z1 )χy2 (z2 )

N (N − 1)

P −

z χy1 (z)χy2 (z)

N (N − 1)

where we omit z1 , z2 , z ∈ {0, 1}n in the last terms. By Eq. (16), the first term vanishes because y1 , y2 ̸= 0n , and the second term is computed by −

X z∈{0,1}

χy1 (z)χy2 (z) =− N (N − 1) n

χy1 +y2 (z) Jy1 + y2 = 0n K Jy1 = y2 K =− =− N (N − 1) N −1 N −1 n

z∈{0,1}

where we use the bilinearity (Eq. (4)) and Eq. (16). Consequently, the degree-2 component becomes µ=2 XoP[r] =

X |γ|=2

µ bP (γ)r χγ =

supp(γ)={x1 <x2 }

(−1)r Jy1 = y2 Kχγ (N − 1)r

(17)

where we use Jy1 = y2 Kr = Jy1 = y2 K. Consequently, the degree-2 weight is, by letting y = y1 (= γ(x1 )) = y2 (= γ(x2 )), computed as in Eq. (8) by X X X N 1 1 =2 2 2r = (N − 1) ∥µXoP[r] ∥2 = |b µP (γ)| = 2r 2 (N − 1) (N − 1)2r n x <x |γ|=2

2 y̸=0

1 N 1 ≤ = ≤ 2r−3 2r−2 2r−4 2(N − 1) 2N (N − 2r + 2) N where the last inequalities use N/2 ≥ 2r − 2. This proves the second item of Lemma 5.2. 5.1.3

Degree-3 Component

b with supp(γ) = {x1 , x2 , x3 }. Write γ(xi ) = yi ̸= 0n for i = 1, 2, 3. We first prove that Fix γ ∈ F µ bP (γ) =

Jy1 + y2 + y3 = 0n K . N −1

(18)

The proof of this equation uses some combinatorial argument using the inclusion-exclusion principle. The reader may skip the proof of this equation. Proof of Eq. (18).

By Lemma 5.3, this can be written as X

µ bP (γ) =

z1 ,z2 ,z3 distinct

z1 ,z2 ,z3 ∈{0,1}

χy1 (z1 )χy2 (z2 )χy3 (z3 ) (N )3

Jz1 , z2 , z3 distinctKχy1 (z1 )χy2 (z2 )χy3 (z3 ) . (N )3 n

For three variables z1 , z2 , z3 , applying the inclusion-exclusion principle to the three events Eij = [zi = zj ] gives X Jz1 , z2 , z3 distinctK = 1 − Jzi = zj K + 2Jz1 = z2 = z3 K. i<j

where the last term comes from JE12 ∩ E13 K + JE12 ∩ E23 K + JE13 ∩ E23 K − JE12 ∩ E13 ∩ E23 K, all of which are the same event [z1 = z2 = z3 ]. Applying this identity to the summation over all z1 , z2 , z3 , we have X

µ bP (γ) =

z1 ,z2 ,z3 ∈{0,1}

−

χy1 (z1 )χy2 (z2 )χy3 (z3 ) (N )3 n X

i<j z1 ,z2 ,z3 ∈{0,1}n :zi =zj

X z∈{0,1}

χy1 (z1 )χy2 (z2 )χy3 (z3 ) (N )3

χy1 (z)χy2 (z)χy3 (z) . (N )3 n

This can be factored into =

P P P ( z1 ∈{0,1}n χy1 (z1 ))( z2 ∈{0,1}n χy2 (z2 ))( z3 ∈{0,1}n χy3 (z3 )) (N )3 P P ( z∈{0,1}n χyi (z)χyj (z))( zk ∈{0,1}n χyk (zk ))

−

(N )3

1≤i<j≤3;k:=6−i−j

z∈{0,1}

χy1 (z)χy2 (z)χy3 (z) (N )3 n

where k is chosen P so that {i, j, k} = {1, 2, 3}. The first and second terms become 0 by Eq. (16), because they have a factor zw ∈{0,1}n χyw (zw ) = 0 for some w. Thus only the last term remains, proving X

µ bP (γ) =

z∈{0,1}

2χy1 (z)χy2 (z)χy3 (z) = (N )3 n

X z∈{0,1}

2χy1 +y2 +y3 (z) (N )3 n

Jy1 + y2 + y3 = 0n K 2N Jy1 + y2 + y3 = 0n K = , N −1 (N )3 2

where we use Eq. (16) in the third equality. Bounding the degree-3 component. Recall µ bXoP[r] (γ) = µ bP (γ)r from Eq. (15). Therefore, the degree-3 weight is X X Jy1 + y2 + y3 = 0n K 2 . ∥µ=3 |b µP (γ)|2r = 2r XoP[r] ∥2 = |γ|=3

supp(γ)={x1 <x2 <x3 } γ(xi )=yi ̸=0n

N −1 2

The last term is straightforward to calculate. The number of possible support is N3 , and the number of nonzero triples (y1 , y2 , y3 ) such that y1 + y2 + y3 = 0n is (N − 1)(N − 2).5 Therefore, N 1 22r−1 =3 2 ∥µXoP[r] ∥2 = (N − 1)(N − 2) = 2r−2 2r−2 2r N −1 3 3N 4r−5 1 − N1 1 − N2 2 ≤

22r 22r−1 22r−1 ≤ < . 3N 4r−5 N 4r−5 3N 4r−5 1 − 6r−6 N

where we use (1 − N1 )2r−2 (1 − N2 )2r−2 ≥ 1 − 6r−6 in the first inequality. The last two inequalities follow N from N/2 ≥ 6r − 6 and 3 > 2. This concludes the proof of the third item of Lemma 5.2. 5.1.4

Degree-4 Component

b with supp(γ) = {x1 , x2 , x3 , x4 }. Write γ(xi ) = yi ̸= 0n for i = 1, 2, 3, 4. We prove the following Fix γ ∈ F identity at the end of this section. µ bP (γ) =

N C2,2 (γ) − 6 C4 (γ) (N − 1)3

using the inclusion-exclusion principle similar to the proof of Eq. (18), where C2,2 (γ) := Jy1 = y2 KJy3 = y4 K + Jy1 = y3 KJy2 = y4 K + Jy1 = y4 KJy2 = y3 K, C4 (γ) := Jy1 + y2 + y3 + y4 = 0n K.

5 Choose y

1 ̸= 0

n and y

2 ̸= 0

n , y , then y is determined and nonzero. 1 3

(19)

In the main body, we derive the upper bound of the degree-4 component of the XoP[r] using this formula. Observe that 0 ≤ C2,2 (γ) ≤ 3 and 0 ≤ C4 (γ) ≤ 1. This gives the upper bound of the maximal magnitude M =4 [µP ] = max |b µP (γ)| ≤ |γ|=4

3N . (N − 1)3

Using (a − b)2 ≤ a2 + b2 for a, b ≥ 0, we have 2r−2 |b µP (γ)|2r ≤ M =4 [µP ] |b µP (γ)|2 2r−2 2 3N N C2,2 (γ)2 + 36C4 (γ) . ≤ (N − 1)3 ((N − 1)3 )2

(20)

Again, using 0 ≤ C2,2 (γ) ≤ 3 and 0 ≤ C4 (γ) ≤ 1, we can give upper bounds X X X N N C2,2 (γ)2 ≤ 3 C2,2 (γ) = 9 (N − 1)2 , C4 (γ) ≤ (N − 1)3 4 4 |γ|=4

|γ|=4

where N4 denotes the number of the support of γ, and (N −1)2 and (N −1)3 is the number of y1 , y2 , y3 , y4 ̸= 0n satisfying the constraints from C2,2 (γ) and C4 (γ), e.g., Jy1 = y2 KJy3 = y4 K. Therefore, Eq. (20) is bounded above by 2r−2 N 9N 2 (N − 1)2 + 36(N − 1)3 3N 32r−1 4 ≤ 4r−6 (21) 2 (N − 1)3 ((N − 1)3 ) N The detailed calculation is as follows: 2r−2 3N (N − 1)3

N 4

9N 2 (N − 1)2 + 36(N − 1)3 ((N − 1)3 )2 1 N −1 + 32r 24 6N 2 = 4r−6 2r−3 2r−1 2r−1 . N 1 2 3 1− 1− 1− N N N

−1 1 1 +N Observe that 24 6N 2 ≤ 12 for N ≥ 4 and

1−

1 N

2r−3 1−

2 N

2r−1 1−

3 N

2r−1 ≥1−

12r − 8 1 ≥ N 4

for N ≥ 16r. This bounds the above term by ≤

32r 32r−1 1/12 = · N 4r−6 1/4 N 4r−6

as desired. Hence

32r−1 . N 4r−6 This concludes the proof of the fourth item of Lemma 5.2. 2 ∥µ=4 XoP[r] ∥2 ≤

b with supp(γ) = {x1 , x2 , x3 , x4 }. Write γ(xi ) = yi ̸= 0n for i ∈ [4]. For Proof of Eq. (19). Fix γ ∈ F convenience, we recall Eq. (19): N C2,2 (γ) − 6 C4 (γ) µ bP (γ) = . (N − 1)3 19

By Lemma 5.3, X

µ bP (γ) =

z1 ,z2 ,z3 ,z4 distinct

χy1 (z1 )χy2 (z2 )χy3 (z3 )χy4 (z4 ) . (N )4

(22)

For four variables z1 , z2 , z3 , z4 , the inclusion-exclusion principle for the six events Eij = [zi = zj ] gives, after simplification, X X Jz1 , z2 , z3 , z4 distinctK = 1 − Jzi = zj K + 2 Jzi = zj = zk K i<j

i<j,k<ℓ,{i,j,k,ℓ}={1,2,3,4}

i<j<k

Jzi = zj ∧ zk = zℓ K − 6Jz1 = z2 = z3 = z4 K.

Applying this to Eq. (22) over all z1 , z2 , z3 , z4 , every term with a separated single vertex vanishes by Eq. (16). Hence only the last two terms remain: X

µ bP (γ) =

i<j,k<ℓ z,w∈{0,1} {i,j,k,ℓ}={1,2,3,4}

i<j,k<ℓ {i,j,k,ℓ}={1,2,3,4}

χyi +yj (z)χyk +yℓ (w) − (N )4 n

6χy1 +y2 +y3 +y4 (z) (N )4 n

z∈{0,1}

N Jyi = yj KJyk = yℓ K 6Jy1 + y2 + y3 + y4 = 0n K − (N − 1)3 (N − 1)3

N C2,2 (γ) − 6C4 (γ) , (N − 1)3

where we use Eq. (16) in the second equality. This proves Eq. (19).

5.2

Proofs for high degrees

We prove the high-degree upper bounds. The proof of the following two lemmas can be found in the next subsection. ⌈d/2⌉

Lemma 5.4. For 1 ≤ d ≤ N , it holds that M =d [µP ] ≤ (2d/N ) . P ⌊d/2⌋ Lemma 5.5. For 5 ≤ d ≤ N/16, it holds that |γ|=d |b µP (γ)|2 ≤ 33d (N/d) . Now we extend the low-degree calculations to the higher-degree terms. We prove the following lemma. 2 18 3 12 6r−9 and Lemma 5.6. For r ≥ 2 and 5 ≤ dmax ≤ N/28887, it holds that ∥µ=6 XoP[r] ∥2 ≤ 3 2 N 2 ∥µ=5 XoP[r] ∥2 +

dX max

2 22 11 ∥µ=d XoP[r] ∥2 ≤ 3 2

d=7

10 N

6r−8 ,

2 ∥µ=6 XoP[r] ∥2 = O

Proof. Lemmas 5.4 and 5.5 give, for every 5 ≤ d ≤ dmax , X 2 ∥µ=d |b µP (γ)|2r XoP[r] ∥2 = |γ|=d

2r−2 X ≤ M =d [µP ] |b µP (γ)|2 |γ|=d

≤

2d N

(2r−2)⌈d/2⌉

3d (2r−2)⌈d/2⌉

=3 2

d N

N d

⌊d/2⌋

(2r−1)⌈d/2⌉−d =: Wd ,

1 N 6r−9

where we use the following in the last line d d + = d. 2 2 Degree-6 is immediate by W6 , in particular N ≥ 96. We will prove Wd+2 1 ≤ Wd 2 for every 5 ≤ d ≤ dmax − 2. Since

d+2 2

d 2

+ 1, we have

(2r−1)⌈d/2⌉−d 2r−3 2 d+2 Wd+2 6 2r−2 . =3 2 1+ Wd d N For d ≥ 5, d 3d ≤ , 2 5 and hence (2r − 1)

6r − 8 d d. −d≤ 2 5

Using 1 + x ≤ ex , we obtain

2 1+ d

(2r−1)⌈d/2⌉−d

2 d ≤ exp (2r − 1) −d ≤ e(12r−16)/5 . d 2

In addition, we observe that, for all r ≥ 2, 1 · 288872r−3 . 2

36 22r−2 e(12r−16)/5 < Using the above, Wd+2 ≤ 36 22r−2 e(12r−16)/5 Wd

d+2 N

2r−3 ≤

1 2r−3 (28887) 2

dmax N

2r−3

Summing the odd and even degrees separately gives 2 ∥µ=5 XoP[r] ∥2 +

dX max

2 ∥µ=d XoP[r] ∥2 ≤ W5 +

d=7

≤

dX max

1 1 1 + + 2 + · · · (W5 + W8 ) = 2(W5 + W8 ). 2 2

Moreover, W5 56r−8 54 = 9 26r−38 N 2r−4 = 9 14 W8 3 ·2 3 ·2

125N 8192

2r−4 ≥

54 . 39 · 214

Consequently, dX max

39 · 214 1+ W5 54 d=7 6r−8 6r−8 39 · 214 15 6r−6 5 10 22 11 ≤2· 2 6 ·3 ·2 =3 2 . 3 ·2 N N

2 ∥µ=5 XoP[r] ∥2 +

2 ∥µ=d XoP[r] ∥2 ≤ 2 ·

≤

1 2

5.3

Maximal Magnitude and Weight of the components of µP

5.3.1

Maximal magnitude of components

The goal of this section is to prove Lemma 5.4, or more precisely ⌈d/2⌉ 2d . M =d [µP ] ≤ N b be a character with |γ| = d such that supp(γ) = {x1 < · · · < xd }. Write γ(xi ) = yi for i ∈ [d]. Let γ ∈ F As shown in Lemma 5.3, we can write " d # Y µ bP (γ) = E(z1 ,...,zd )←({0,1}n )(∗d) χyi (zi ) . i=1

We observe the following fact: The conditional distribution of zd given the other elements (z1 , . . . , zd−1 ) is uniform over the set {0, 1}n \ {z1 , . . . , zd−1 }, which has size N − d + 1. From this, we have Ezd ←{0,1}n \{z1 ,...,zd−1 } [χyd (zd )] X 1 χyd (z) = N −d+1 z ∈{z / 1 ,...,zd−1 }   d−1 X X 1  = χyd (z) − χyd (zi ) N −d+1 n i=1 z∈{0,1}

d−1 X

1 χy (zi ), N − d + 1 i=1 d P where the last equality follows from z∈{0,1}n χyd (z) = 0 because yd ̸= 0n . Using this equation, we have   d−1 Y µ bP (γ) = E(z ,...,z )←({0,1}n )(∗d) χyd (zd ) χyj (zj ) =−

j=1

 = E(z1 ,...,zd−1 )←({0,1}n )(∗(d−1)) Ezd ←{0,1}n \{z1 ,...,zd−1 } [χyd (zd )]

d−1 Y

 χyj (zj )

j=1

  d−1 d−1 X Y 1 =− E χyj (zj ) n (∗(d−1)) χyd (zi ) N − d + 1 i=1 (z1 ,...,zd−1 )←({0,1} ) j=1   d−1 d−1 X Y   1  =− E(z1 ,...,zd−1 )←({0,1}n )(∗(d−1)) χyi +yd (zi ) χyj (zj ) . N − d + 1 i=1 j=1 j̸=i

b by To simplify the above expression, define γ (i←d) ∈ F   yi + yd , x = xi , (i←d) γ (x) := yj , x = xj for some j ∈ [d − 1] \ {i},   n 0 , otherwise. If yi + yd = 0n , then γ (i←d) (xi ) = 0 and therefore γ (i←d) has degree d − 2. In other cases, γ (i←d) has degree d − 1. This gives the following recursion. 22

b satisfy |γ| = d. Then Lemma 5.7. Let 2 ≤ d ≤ N , and let γ ∈ F µ bP (γ) = −

d−1 X 1 µ bP γ (i←d) . N − d + 1 i=1

We are now ready to prove Lemma 5.4. Proof of Lemma 5.4. It is immediate that M =0 [µP ] = 1 and M =1 [µP ] = 0. Now fix 2 ≤ d ≤ N , and let b satisfy |γ| = d. By Lemma 5.7, γ∈F µ bP (γ) = −

d−1 X 1 µ bP γ (i←d) . N − d + 1 i=1

For each i ∈ [d − 1], the character γ (i←d) has support size either d − 1 or d − 2. Therefore, n o µ bP γ (i←d) ≤ max M =(d−1) [µP ], M =(d−2) [µP ] . Since the recursion holds for every degree-d character, taking absolute values gives n o d−1 M =d [µP ] ≤ max M =(d−1) [µP ], M =(d−2) [µP ] . N −d+1

(23)

We now prove the claimed bound by induction on d ≥ 2. If d > N/2, the bound is immediate as M =d [µP ] ≤ 1 ≤ (2d/N )⌈d/2⌉ . So let 2 ≤ d ≤ N/2 and assume the claim for all smaller degrees. Since 2d/N ≤ 1 and ⌈(d − 1)/2⌉ ≥ ⌈(d − 2)/2⌉, the induction hypothesis gives n o max M =(d−1) [µP ], M =(d−2) [µP ] ( ⌈(d−1)/2⌉ ⌈(d−2)/2⌉ ) ⌈(d−2)/2⌉ 2(d − 1) 2(d − 2) 2d ≤ max , ≤ . N N N 2d Moreover, Nd−1 −d+1 ≤ N for d ≤ N/2. Plugging both bounds into (23),

2d [µP ] ≤ N

2d N

⌈(d−2)/2⌉

2d N

⌈d/2⌉ ,

this completes the induction and proves the lemma. 5.3.2

Weight of components

We prove that, for 5 ≤ d ≤ N/16, it holds that X

|b µP (γ)| ≤ 3

|γ|=d

N d

⌊d/2⌋ .

Proof of Lemma 5.5. By Lemma 5.3, µ bP (γ) depends only on the labels of γ, so for a support S of size d the quantity X Bd := |b µP (γ)|2 supp(γ)=S

does not depend on S, and

µP (γ)| |γ|=d |b

N d

Bd . We will show that

j d X N d−j d Bd = (−1) j (N )j j=0 23

(24)

and d+1

Bd ≤ 2 Given (25), the lemma follows from X

N d

8d N

⌈d/2⌉ for 5 ≤ d ≤ N/16.

(25)

≤ (eN/d)d and d − ⌈d/2⌉ = ⌊d/2⌋:

d ⌈d/2⌉ 8d N eN d+1 |b µP (γ)| = Bd ≤ 2 d N d 2

|γ|=d

= 2d+1 8⌈d/2⌉ ed

N d

⌊d/2⌋

≤ 33d

N d

⌊d/2⌋ ,

where the last inequality uses 2d+1 8⌈d/2⌉ ≤ 8d for d ≥ 5 (equivalently, d + 1 ≤ 3⌊d/2⌋) and 8e < 27. b be the The identity Eq. (24). Fix S = {x1 , . . . , xd } and, for y = (y1 , . . . , yd ) ∈ ({0, 1}n )d , let γy ∈ F n n index with γy (xi ) = yi and γy (x) = 0 for x ∈ / S; thus supp(γy ) = {xi : yi ̸= 0 }. Let ν be the uniform distribution on ({0, 1}n )(∗d) , viewed as a probability mass function on ({0, 1}n )d . By (5.3) (which does not require the yi to be nonzero), µ bP (γy ) =

ν(z)

z∈({0,1}n )d

d Y

χyi (zi )

for all y ∈ ({0, 1}n )d ,

i=1

i.e., (b µP (γy ))y is N d times the Fourier transform of ν on the group ({0, 1}n )d . Parseval’s identity on ({0, 1}n )d therefore gives X

|b µP (γy )|2 = N 2d ·

y∈({0,1}n )d

1 Nd

ν(z)2 = N d ·

z∈({0,1}n )d

(N )d Nd = . 2 (N )d (N )d

On the other hand, if exactly the coordinates in J ⊆ [d] of y are nonzero, then µ bP (γy ) is the P Fourier coeffiP cient of a degree-|J| index, so grouping the y according to J yields y∈({0,1}n )d |b µP (γy )|2 = J⊆[d] B|J| = Pd Pd d d d j=0 j Bj , with B0 := 1. Hence N /(N )d = j=0 j Bj for every d ≥ 0, and binomial inversion gives Eq. (24). The bound Eq. (25). The right-hand side of Eq. (24) resembles the binomial expansion of (1 − 1)d = 0, and we exploit the resulting cancellations. Recall the elementary fact that d X d−j d p(j) = 0 (−1) j j=0 Write

for every polynomial p with deg(p) < d.

j−1

Y 1 Nj = = uj (1/N ), (N )j 1 − ℓ/N

uj (t) :=

ℓ=0

j−1 Y ℓ=0

(26)

X 1 = pk (j)tk , 1 − ℓt k≥0

where the last expression is the Taylor expansion of uj at t = 0, which converges absolutely for |t| < 1/(j −1), and in particular at t = 1/N for all j ≤ d ≤ N/16. Comparing the coefficients of tk in uj+1 (t) = uj (t)/(1 − P jt) = uj (t) ℓ≥0 j ℓ tℓ gives pk (j + 1) =

k X

j ℓ pk−ℓ (j),

pk (j + 1) − pk (j) =

i.e.,

ℓ=0

k X ℓ=1

j ℓ pk−ℓ (j),

with p0 (j) = 1 and pk (0) = 0 for k ≥ 1 (since u0 = 1). We claim that j 7→ pk (j) is a polynomial of degree at most 2k. This is clear for k = 0. If it holds for all k ′ < k, then each summand j ℓ pk−ℓ (j) on the right-hand side above has degree at most ℓ + 2(k −P ℓ) ≤ 2k − 1, so the forward difference pk (j +1)−pk (j) is a polynomial of degree at most 2k −1; since pk (j) = i<j (pk (i+ 1) − pk (i)) and partial sums of a polynomial of degree at most 2k − 1 form a polynomial of degree at most 2k, the claim follows. Consequently, by Eq. (24) and Eq. (26), all terms with 2k < d, i.e., with k < ⌈d/2⌉, cancel: X d X d Bd = (−1)d−j pk (j)N −k j j=0 k≥0

−k

(−1)

d−j

j=0

k≥0

d X

k≥⌈d/2⌉

−k

d pk (j) j

d X d−j d (−1) pk (j). j j=0

It remains to bound |pk (j)| for j ≤ d and k ≥ ⌈d/2⌉. For j ≥ 2, expanding each factor of uj (t) = Qj−1 −1 as a geometric series shows that ℓ=1 (1 − ℓt) pk (j) =

j−1 Y

ℓsℓ

s1 ,...,sj−1 ≥0 ℓ=1 s1 +···+sj−1 =k

is a sum of j+k−2 ≤ 2j+k−1 nonnegative terms, each at most j k ; hence 0 ≤ pk (j) ≤ j k 2j+k−1 , and this k also holds for j ∈ {0, 1} since pk (0) = pk (1) = 0 for k ≥ 1. For j ≤ d ≤ 2k we get |pk (j)| ≤ dk 2j+k−1 ≤ dk 23k = (8d)k . Therefore, using

d j

Bd ≤

= 2d and 8d/N ≤ 1/2, X

k≥⌈d/2⌉

−k

d X d j=0

|pk (j)| ≤ 2

⌈d/2⌉ X 8d k 8d d+1 ≤2 , N N

k≥⌈d/2⌉

which is Eq. (25).

Few Quantum Query Security via Planted Collisions

This section proves the following lemma. N N , and q ≤ 57774 , then Lemma 6.1. If n ≥ 5, 2 ≤ r ≤ 16

Advdist q (DXoP[r] , DF ) = O

q3 Nr

Recall that the query-independent ℓ2 -norm bounds in Lemma 5.2: For d = 5 and 7 ≤ d ≤ N/28887, that lemma give O(N −3r+4 ) = O(N −r ) upper bounds. We give the following alternative query-dependent bounds for d = 2, 3, 4, 6 in the subsections. N N Lemma 6.2. If n ≥ 5, 2 ≤ r ≤ 16 , and q ≤ 57774 , then

|⟨µ=d XoP[r] , PA ⟩| = O for d = 2, 3, 4, 6. 25

q3 Nr

Proof of Lemma 6.1. Let A be a q-query algorithm. As shown in Eq. (13), Theorem 3.6 and Eq. (12) gives Advdist (DXoP[r] , DF ; A) ≤

2q X

=d ⟨µ=d XoP[r] , PA ⟩.

d=1

By decomposing the above term for d = 2, 3, 4, 6 and the others, we have the following upper bound   X X =d  =d  ⟨µ=d + ∥µ=d XoP[r] , PA ⟩ XoP[r] ∥2 ∥PA ∥2 d=2,3,4,6

d=5,7≤d≤2q

where the second term is bounded above by the Cauchy–Schwarz as in Eq. (14)  21

 X

2 ∥µ=d XoP[r] ∥2



d=5,7≤d≤2q

1 N 3r−4

1 Nr

where we use the last inequality of Lemma 5.2 and r ≥ 2. The remainder terms are bounded by O(q 3 /N r ) Lemma 6.2 for d = 2, 3, 4, 6, we have the overall upper bound O(q 3 /N r ).

6.1

Preparation: Distributions with planted constraints

We will use the indistinguishability of the small-range distributions [58]. Definition 6.3 (Small-range distributions). For an integer R ≥ 1, the distribution SR over F = Fn is sampled as follows: 1. sample a uniformly random function f : {0, 1}n → [R] and let I be its image; 2. sample a uniformly random function g : I → {0, 1}n ; 3. output h := g ◦ f . Note that S∞ is identical to the distributions of random functions. The following result is proven in [58]. 3

27q Theorem 6.4. Advdist q (SR , S∞ ) ≤ R .

We use the several distributions of functions with some specific constraints. First one is the distribution DPC of random functions with a planted collision, which is defined as follows: DPC : Sample x1 ̸= x2 from {0, 1}n . Then, sample a uniform random f ← F such that f (x1 ) = f (x2 ). It is not hard to see that its density function is computed by −1 X N µPC (f ) = N Jf (x1 ) = f (x2 )K. 2

(27)

{x1 ,x2 }

We use the following observation. Lemma 6.5. Let N ≥ 4 and R ≥ N 2 . For h ← SR which is defined by h = g ◦ f , let Cf := |{{x, x′ } : x ̸= x′ , f (x) = f (x′ )}|. Then N2 N4 Pr[Cf = 1] ≥ , Pr[Cf ≥ 2] ≤ . 8R 8R2 Moreover, conditioned on Cf = 0, the distribution of h is identical to the uniform distribution DF . Conditioned on Cf = 1, the distribution of h is DPC .

Proof. Observe that Pr[f (x) = f (x′ )] = 1/R for any x ̸= x′ , and any two distinct pairs (x, x′ ) and (z, z ′ ) collide simultaneously with probability 1/R2 , even when they share an input. Thus (N2 ) N N4 Cf 2 . E[Cf ] = , E = 22 ≤ R 2 R 8R2 Using JC ≥ 2K ≤ C2 and JC = 1K ≥ C − 2 C2 for nonnegative integers C, we obtain Pr[Cf ≥ 2] ≤

N4 , 8R2

Pr[Cf = 1] ≥

N (N − 1) N2 N4 ≥ − . 2R 4R2 8R

where the last inequality uses N ≥ 4 and R ≥ N 2 . If Cf = 0, the values of h are independent and uniform because of g. If Cf = 1, the colliding pair of f is uniform by symmetry, thus the conditional distribution is exactly DPC . 3 2 Lemma 6.6. Advdist q (DPC , DF ) = O(q /N ).

Proof. Fix a q-query algorithm A. Recall ⟨µD , PA ⟩ = Prh←D [Ah = 1] for any oracle distribution D. Let r ≥ N 2 and choose h ← SR . Let p0 , p1 , p2 be the probabilities of Cf = 0, Cf = 1, and Cf ≥ 2, respectively, as defined in Lemma 6.5. By the same lemma, there exists a distribution RR such that, writing µR and ρR for the densities of SR and RR , respectively, N2 N4 , p2 ≤ 8R 8R2 where 1 denotes the density function of DF . Since p0 + p1 + p2 = 1, we have µR = p0 · 1 + p1 · µPC + p2 · ρR ,

p1 ≥

(28)

µR − 1 = p1 (µPC − 1) + p2 (ρr − 1). Taking inner products with PA and applying the triangle inequality gives 27q 3 + p2 R where we use Theorem 6.4 for the first term and |⟨ρR − 1, PA ⟩| ≤ 1 for the second term. This proves N4 8R 27q 3 216q 3 N2 + . |⟨µPC − 1, PA ⟩| ≤ 2 = + N R 8R2 N2 R p1 |⟨µPC − 1, PA ⟩| ≤ |⟨µR − 1, PA ⟩| + p2 |⟨ρR − 1, PA ⟩| ≤

Taking R sufficiently large, we have the same bound O(q 3 /N 2 ) for all q-query algorithms A. This completes the proof.

6.2

Degree-2 component as planted collision

We first prove Lemma 6.2 for d = 2. 3 q Lemma 6.7. |⟨µ=2 , P ⟩| = O A XoP[r] Nr . Proof. We start from the degree-2 component represented in Eq. (17). The equation shows that it suffices to b with the support {x1 < x2 } satisfying γ(x1 ) = γ(x2 ). Letting γ(x1 ) = γ(x2 ) = y consider the degree-2 γ ∈ F and plugging f , X (−1)r Jγ(x1 ) = γ(x2 )Kχγ (f ) µ=2 XoP[r] (f ) = (N − 1)r supp(γ)={x1 <x2 }

x1 <x2 ;y̸=0

(−1)r χy (f (x1 ) + f (x2 )) (N − 1)r n

(−1)r (−1)r · N (N · Jf (x ) = f (x )K − 1) = (µPC (f ) − 1) 1 2 (N − 1)r 2(N − 1)r−1 x <x X 1

where we use Eq. (16) in the third equality, and use Eq. (27) in the last equality. Therefore, |⟨µ=2 XoP[r] , PA ⟩| =

N |⟨µPC , PA ⟩ − ⟨1, PA ⟩| . 2(N − 1)r−1

The right hand side is the distinguishing advantage between the planted collision function and random N functions up to the multiplicative factor 2(N −1) r−1 . Plugging Lemma 6.6 here gives the desired upper bound.

6.3

Degree-3 component as planted-three-collision

To bound the degree-3 component, we need to define D3PC of random functions with a planted 3-collision, which is defined as follows: D3PC : Sample three distinct x1 , x2 , x3 from {0, 1}n . Then, sample a uniform random f ← F such that f (x1 ) = f (x2 ) = f (x3 ). Its density function is µ3PC (f ) =

1 (N )3

X (x1 ,x2 ,x3

)∈({0,1}n )∗3

N 2 Jf (x1 ) = f (x2 ) = f (x3 )K.

We prove the following lemma in Appendix B. 2 Lemma 6.8. Advdist q (D3PC , DF ) = O(q /N ).

We actually prove the following stronger bound than O(q 3 /N r ). 2 q Lemma 6.9. |⟨µ=3 XoP[r] , PA ⟩| = O N r . Proof. For supp(γ) = {x1 < x2 < x3 }, write yi = γ(xi ). Recall Jy1 + y2 + y3 = 0n K . N −1 r

µXoP[r] (γ) = µ bP (γ)r =

Expanding the degree-3 component with plugging f becomes r X N −1 µ=3 Jy1 + y2 + y3 = 0n Kχγ (f ) XoP (f ) = 2 supp(γ)={x1 <x2 <x3 } X = χy1 (f (x1 ))χy2 (f (x2 ))χy1 +y2 (f (x3 )) x1 <x2 <x3 y1 ̸=0n , y2 ̸=0n , y1 ̸=y2

χy1 (f (x1 ) + f (x3 ))χy2 (f (x2 ) + f (x3 )).

x1 <x2 <x3 y1 ̸=0n , y2 ̸=0n , y1 ̸=y2

For each x1 , x2 , x3 , observe that X

χy1 (f (x1 ) + f (x3 ))χy2 (f (x2 ) + f (x3 ))

y1 ̸=0n , y2 ̸=0n , y1 ̸=y2

χy1 (f (x1 ) + f (x3 ))χy2 (f (x2 ) + f (x3 )) −

y1 ̸=0n , y2 ̸=0n

χy (f (x1 ) + f (x2 ))

y̸=0

= (N Jf (x1 ) = f (x3 )K − 1)(N Jf (x2 ) = f (x3 )K − 1) − (N Jf (x1 ) = f (x2 )K − 1) 28

where we use Eq. (16) in the last equality. Noting that Jf (x1 ) = f (x3 )KJf (x2 ) = f (x3 )K = Jf (x1 ) = f (x2 ) = f (x3 )K, the overall sum becomes X N 2 Jf (x1 ) = f (x2 ) = f (x3 )K x1 <x2 <x3

− N Jf (x1 ) = f (x2 )K − N Jf (x1 ) = f (x3 )K − N Jf (x2 ) = f (x3 )K + 2 · 1 N = (µ3PC (f ) − 1) − 3(µPC (f ) − 1) . 3 Hence, |⟨µ=3 XoP[r] , PA ⟩| can be decomposed into a linear sum of the distinguishing advantage of the planted 3-collision and the planted collision functions from random functions up to the multiplicative factor N −1r N / . This gives 3 2 |⟨µ=3 XoP[r] , PA ⟩| ≤ O

2 2 3 q q q · O = O + O 2r−3 2 N N N Nr

where we omit the factor regarding r and use q ≤ N and Lemmas 6.6 and 6.8.

6.4

Degree-4 component as planted two collisions plus small terms

We define the distributions of random functions with multiple planted collisions to bound the degree-4 component. For k ∈ N, they are defined as follows. DPC,k : Sample a tuple (x1 , . . . , x2k ) ← ({0, 1}n )∗(2k) of distinct inputs. Then sample a uniform random f ← F such that f (x2j−1 ) = f (x2j ) for all j ∈ [k]. D4X : Sample four distinct x1 , . . . , x4 from {0, 1}n . Then, sample a uniform random f ← F such that f (x1 ) + f (x2 ) + f (x3 ) + f (x4 ) = 0n . The density functions of these distributions can be computed as follows µPC,k (f ) = µ4X (f ) =

1 (N )2k 1 (N )4

(x1 ,...,x2k )∈({0,1}n )∗(2k)

X (x1 ,...,x4 )∈({0,1}n )∗4

k Y j=1

Jf (x2j−1 ) = f (x2j )K,

N Jf (x1 ) + f (x2 ) + f (x3 ) + f (x4 ) = 0n K.

Note that DPC = DPC,1 and DPC,0 = DF . Similarly to the previous distributions, we prove the following two lemmas in Appendix B. 3 2 Lemma 6.10. Advdist q (DPC,k , DF ) = O(q /N ) for k = 2, 3. 3 2 Lemma 6.11. Advdist q (D4X , DF ) = O(q /N ).

We prove the following lemma in this subsection using the above lemmas. 3 q Lemma 6.12. |⟨µ=4 , P ⟩| = O A XoP[r] Nr . Proof. Let γ be such that |γ| = 4. For supp(γ) = {x1 < x2 < x3 < x4 }, write yi = γ(xi ). We begin with the degree-4 Fourier component from Eq. (19) µ bP (γ) =

N C2,2 (γ) − 6C4 (γ) (N − 1)3 29

where we recall the following for convenience. C2,2 (γ) = Jy1 = y2 KJy3 = y4 K + Jy1 = y3 KJy2 = y4 K + Jy1 = y4 KJy2 = y3 K, C4 (γ) = Jy1 + y2 + y3 + y4 = 0n K.

We write X, Y, Z to denote Jy1 = y2 KJy3 = y4 K, Jy1 = y3 KJy2 = y4 K, and Jy1 = y4 KJy2 = y3 K, respectively, so that C2,2 (γ) = X + Y + Z. Observe the following. 1. X 2 = X, Y 2 = Y, Z 2 = Z and C42 = C4 as they are in {0, 1}, 2. XY = Y Z = ZX = Jy1 = y2 = y3 = y4 K =: E(γ), 3. C2,2 (γ) ≥ 1 implies C4 (γ) = 1, thus C2,2 (γ)C4 (γ) = C2,2 (γ), 4. similarly C2,2 E = 3E and C4 E = E. k From this, we have C2,2 = C2,2 + (3k − 3)E inductively for k ∈ N. Further calculation based on the above gives the following identity r ar C2,2 (γ) + br E(γ) + cr C4 (γ) N C2,2 (γ) − 6C4 (γ) = µ bP (γ)r = (N − 1)3 (N − 1)r3

where ar = (N − 6)r − (−6)r , br = (3N − 6)r − 3(N − 6)r + 2(−6)r , cr = (−6)r . Now we compute µ=4 XoP[r] (f ) . Observe that C2,2 = X + Y + Z terms can be computed as follows, where 8 = 4!/3 comes from the order of x1 , x2 , x3 , x4 (4!) and the symmetry of X, Y, Z (3), X

C2,2 (γ)χγ (f ) =

|γ|=4

1 8

X supp(γ)={x1 ,x2 ,x3 ,x4 }

Jy1 = y2 KJy3 = y4 Kχγ (f )

χy1 (f (x1 ) + f (x2 ))χy3 (f (x3 ) + f (x4 ))

supp(γ)={x1 ,x2 ,x3 ,x4 } y1 ̸=0n , y3 ̸=0n

X 1 (N Jf (x1 ) = f (x2 )K − 1)(N Jf (x3 ) = f (x4 )K − 1) 8 x1 ,x2 ,x3 ,x4 distinct

(N )4 = ((µPC,2 (f ) − 1) − 2(µPC (f ) − 1)). 8 Here, the last term can be interpreted as a linear sum of distinguishing advantage between random functions with planted collision(s) and uniformly random functions. Lemmas 6.6 and 6.10 gives the bound P ⟨ |γ|=4 C2,2 (γ)χγ , PA ⟩ = O(q 3 N 2 ). For the E term, we have X X E(γ)χγ (f ) = Jy1 = y2 = y3 = y4 Kχγ (f ) |γ|=4

supp(γ)={x1 ,x2 ,x3 ,x4 }

χy (f (x1 ) + f (x2 ) + f (x3 ) + f (x4 )) =

supp(γ)={x1 ,x2 ,x3 ,x4 } y̸=0n

(N )4 (µ4X (f ) − 1), 24

P which gives ⟨ |γ|=4 E(γ)χγ , PA ⟩ = O(q 3 N 2 ) because of Lemma 6.11. For the last term with C4 , we can directly bound ⟨

|γ|=4

C4 (γ)χγ , PA ⟩ ≤

X |γ|=4

= O(N 4 ).

C4 (γ)χγ 2

Plugging three bounds on the expansion of ⟨µ=4 XoP[r] , PA ⟩ gives r 3 2 q3 N · q N + N r · q3 N 2 + N 4 = O |⟨µ=4 , P ⟩| = O A XoP[r] N 3r N 2r−2 which is O(q 3 /N r ) because r ≥ 2, as desired.

6.5

Degree-6 component as planted three collisions plus small terms

We use the following lemma. Lemma 6.13. For x, y ∈ R, |(x + y)r − xr | ≤ r|y|(|x| + |y|)r−1 . r−1 Proof. Noting that kr ≤ k kr = r k−1 for 1 ≤ k ≤ r, we have r

|(x + y) − x | ≤

r X r k=1

r−k k

y | ≤ r|y|

r X r−1 k=1

k−1

|x|r−k |y|k−1

which equals to r|y|(|x| + |y|)r−1 . Lemma 6.14. |⟨µ=6 XoP[r] , PA ⟩| = O

3 q Nr

Proof. We need to compute µ bP first. Let us define Z2,2,2 , Z2,4 , Z3,3 , Z6 by X Y Z2,2,2 := Jzi = zj K, M perfect matching of [6] {i,j}∈M

Z2,4 :=

{i,j}⊂[6] {i,j}∩{g,h,k,ℓ}=∅

Z3,3 :=

1∈{i,j,k}⊂[6] {i,j,k}∩{g,h,ℓ}=∅

Jzi = zj KJzg = zh = zk = zℓ K,

Jzi = zj = zk KJzg = zh = zℓ K,

Z6 := Jz1 = z2 = z3 = z4 = z5 = z6 K. By the inclusion-exclusion principle for the fifteen events Eij = [zi = zj ] gives, Jz1 , · · · , z6 distinctK = 1 − · · · − Z2,2,2 + 6Z2,4 + 4Z3,3 − 120Z6 , where the omitted terms correspond to partitions containing at least one singleton block, which will be vanished. Similarly, we define C2,2,2 , C2,4 , C3,3 , C6 by X Y C2,2,2 (γ) := Jyi = yj K, M perfect matching of [6] {i,j}∈M

C2,4 (γ) :=

X {i,j}⊂[6] {i,j}∩{g,h,k,ℓ}=∅

C3,3 (γ) :=

X 1∈{i,j,k}⊂[6] {i,j,k}∩{g,h,ℓ}=∅

Jyi = yj KJyg + yh + yk + yℓ = 0n K,

Jyi + yj + yk = 0n KJyg + yh + yℓ = 0n K,

C6 (γ) := Jy1 + y2 + y3 + y4 + y5 + y6 = 0n K.

By applying Eq. (16) and simplifying, we obtain µ bP (γ) =

−N 2 C2,2,2 (γ) + 6N C2,4 (γ) + 4N C3,3 (γ) − 120C6 (γ) . (N − 1)5

set R(γ) = 6N C2,4 (γ) + 4N C3,3 (γ) − 120C6 (γ). Note that R(γ) = O(N ). We rewrite r r (b µP (γ)(N − 1)5 χγ ) = − N 2 C2,2,2 (γ) + R(γ) χγ = S(γ)χγ + (−N 2 )r C2,2,2 (γ)χγ , r where S(γ) = − N 2 C2,2,2 (γ) + R(γ) − (−N 2 )r C2,2,2 (γ). For the second term, we have X

C2,2,2 (γ)χγ (f )

supp(γ)={x1 <...<x6 }

15 6!

X supp(γ)={x1 ,...,x6 }

Jy1 = y2 KJy3 = y4 KJy5 = y6 K(γ)χγ (f )

3 1 X Y (N Jf (x2s−1 ) = f (x2s )K − 1) 48 x1 ,...,x6 s=1 distinct

(N )6 (µPC,3 − 3µPC,2 + 3µPC − 1) = 48 (N )6 = ((µPC,3 − 1) − 3(µPC,2 − 1) + 3(µPC − 1)). 48 This will be routinely bounded using Lemmas 6.6 and 6.10 below. Now let us bound S(γ). Partition the degree-six characters into Γ0 := {γ : C2,2,2 (γ) = 0}, Γ1 := {γ : C2,2,2 (γ) = 1}, Γ≥2 := {γ : C2,2,2 (γ) ≥ 2}. For J ∈ {0, 1, ≥ 2}, let BJ := ⟨

γ∈ΓJ S(γ)χγ . Then we have

S(γ)χγ , PA ⟩ ≤ |⟨B0 , PA ⟩| + |⟨B1 , PA ⟩| + |⟨B≥2 , PA ⟩|

|γ|=6

and using Cauchy-Schwarz inequality 1/2

 |⟨BJ , PA ⟩| ≤ ∥BJ ∥2 ∥PA ∥2 ≤ ∥BJ ∥2 ≤ 

|S(γ)|2 

γ∈ΓJ

If γ ∈ Γ0 , then S(γ) = R(γ)r = O(N r ). 1/2

  |⟨B0 , PA ⟩| ≤  

|γ|=6 C2,2,2 (γ)=0

 |S(γ)|2  

≤ O(N 12 )O(N 2r )

1/2

= O(N r+6 ).

If γ ∈ Γ1 , we apply Lemma 6.13, which gives r − N 2 C2,2,2 (γ) + R(γ) − (−N 2 )r C2,2,2 (γ) r − N 2 + R(γ) − (−N 2 )r = O(N 2r−1 ).

|S(γ)| = =

Since C2,2,2 (γ) = 1, we have at most O(N 3 ) choices of labels per support. Hence, 1/2

 X

 |⟨B1 , PA ⟩| ≤  

|γ|=6 C2,2,2 (γ)=1

 |S(γ)|2  

1/2 ≤ O(N 3+6 )O(N (2r−1)·2 ) = O(N 2r+3.5 ). If γ ∈ Γ≥2 , then r − N 2 C2,2,2 (γ) + R(γ) − (−N 2 )r C2,2,2 (γ)

|S(γ)| =

= O(N 2 )r − (−N 2 )r O(1) = O(N 2r ). Since C2,2,2 (γ) ≥ 2, there exist indices i, j and g, h, k, l such that yi = yj and yg = yh = yk = yl . Hence, we have at most O(N 2 ) choices of labels per support. Hence, 1/2

  |⟨B≥2 , PA ⟩| ≤  

X |γ|=6 C2,2,2 (γ)≥2

 |S(γ)|2  

≤ O(N 2+6 )O(N 2r·2 )

1/2

= O(N 2r+4 )

Finally, |⟨µ=6 XoP[r] , PA ⟩| ≤ ≤

N 2r ⟨

|γ|=6 C2,2,2 (γ)χγ , PA ⟩

O(q 3 N 2r+4 ) + O(N

3r−4 N 3 q =O . Nr

J∈{0,1,≥2} |⟨BJ , PA ⟩|

(N − 1)r5 r+6 2r+3.5

) + O(N Θ(N 5r ) 1 + O 4r−6

) + O(N 2r+4 )

N 3r−3.5

N 3r−4

This concludes the proof.

Middle Quantum Query Security via Improved Small-range Indistinguishability

In this section, we prove the following theorem. As in Theorem 4.1, the asymptotic notation may hide a constant depending on r. N N Lemma 7.1. If n ≥ 5, r ≤ 16 , and q ≤ 57774 , then

Advdist q (DXoP[r] , DF ) = O 33

q 3/2 N r−1/2

The main result of this section is the following bound for the planted collision pseudorandomness. Compared to q 3 /N 2 bound in Lemma 6.6, the following lemma gives a better bound for q 3 ≥ N . 3/2 Lemma 7.2. Let N = 2n ≥ 2. For every integer q ≥ 0, it holds that Advdist /N 3/2 . q (DPC , DF ) = O q This lemma can be used to give an alternative bound for the small-range indistinguishability [58] for the large-range regime. This improves the bound in Theorem 6.4 when q 3 ≫ N and R is sufficiently large, or more precisely for q 3 ≫ N and R ≫ N 4 /q 3 . Corollary 7.3. Let N = 2n ≥ 4, q ≥ 1, and R ≥ N 2 be integers. Then ! √ N4 q 3/2 N dist + 2 . Advq (SR , S∞ ) = O R R In particular, if R ≥ N 7/2 /q 3/2 , then Advdist q (SR , S∞ ) = O

3/2 √ N

Proof. We use the fact from the proof of Lemma 6.6 that the acceptance probability of the small-range distribution can be decomposed into the random functions and the random functions with a planted collision as in Eq. (28). Using Lemma 6.5, the coefficient Pr[Cf = 1] of the planted collision part satisfies Pr[Cf = 1] ≤ E[Cf ] = N2 /R. By Lemma 7.2, we have ! √ N N4 q 3/2 N N4 dist dist 2 Advq (SR , S∞ ) ≤ Advq (DPC , DF ) + =O + 2 . R 8R2 R R √ The last claim follows from N 4 /R2 ≤ q 3/2 N /R when R ≥ N 7/2 /q 3/2 . We prove the main result. The remainder of this section is devoted to prove the above lemma. Proof of Lemma 7.1. If q ≤ N 1/3 , then Lemma 6.1 proves the desired result. We therefore assume q ≥ N 1/3 . Fix a q-query algorithm A. Recall from the proof of Lemma 6.7 that µ=2 XoP[r] =

(−1)r N (µPC − 1). 2(N − 1)r−1

Applying Lemma 7.2, we have ⟨µ=2 XoP[r] , PA ⟩ ≤

N Advdist q (DPC , DF ) = O 2(N − 1)r−1

q 3/2 N r−1/2

For the remaining components, Lemma 5.2 with dmax = 2q gives 2q X

2 ∥µ=d XoP[r] ∥2 = O

d=3

+ 4r−5

+ 4r−6

+ 6r−9

1 N 6r−8

N 4r−6

The conditions of that lemma follow from q ≥ N 1/3 , q ≤ N/57774, and N ≥ 16r. Since ∥PA ∥2 ≤ 1, the Cauchy–Schwarz inequality bounds the contribution of these components by 2q X

=d ⟨µ=d XoP[r] , PA ⟩

≤

d=3

2q X

!1/2 2 ∥µ=d XoP[r] ∥2

d=3

1 N 2r−3

Finally, r ≥ 2 and q ≥ N 1/3 imply q 3/2 . N N N r−1/2 Combining the above bounds with µ=1 XoP[r] = 0 and Theorem 3.6 proves the theorem. 1

≤ 2r−3

≤ r−1

7.1

Planted collisions in the compressed oracle

Fix a q-query algorithm A. By Eq. (27), we immediately have " # X 2 1 ⟨µPC − 1, PA ⟩ = Ef ←F PA (f ) . Jf (x) = f (y)K − N −1 N x<y

(29)

We express the expectation on the right-hand side using the compressed oracle [57]. We follow the formalization of [22]. The compressed oracle. We briefly explain the compressed oracle for random functions, which is perfectly indistinguishable from a quantum random oracle. The database consists of one register for each input x, P with basis {|⊥⟩} ∪ {|v⟩ : v ∈ {0, 1}n }. Write |+⟩ = N −1/2 v∈{0,1}n |v⟩, and let the compression operator Comp be the unitary that swaps |⊥⟩ and |+⟩ while fixing their orthogonal complement. For the compressed representation of v, we use the notation |⊥⟩ |+⟩ |b v ⟩ := Comp |v⟩ = |v⟩ − √ + √ . N N The vectors {|b v ⟩}v are orthonormal. Their span is the orthogonal complement of |+⟩ in the database register. Throughout the execution, each database register remains supported on this span. For f ∈ F, write E E N fb := x fd (x) . The empty database and a compressed query O satisfy E E X E ⊗N |∅⟩ = |⊥⟩ = N −N/2 fb , O |x, y⟩ fb = |x, y + f (x)⟩ fb . f ∈F

A compressed query applies Comp to the database register indexed by the query input, performs the usual quantum random oracle query, and applies Comp again. In particular, O† = O, and a query on input x acts only on database register x. Define the collision operators X X 1 (30) Colxy := (|b v ⟩⟨b v |)x ⊗ (|b v ⟩⟨b v |)y , ∆Col := Colxy − I . N v x<y They satisfy the following equations; see the similarity between the second equation and Eq. (29): E E E E X 1 Colxy fb = Jf (x) = f (y)K fb , ∆Col fb = fb . Jf (x) = f (y)K − N x<y Let ψqf be the final state of the purified algorithm A with oracle f . Let ΠA = |1⟩⟨1|Z ⊗ Irest be its acceptance projector on the output qubit Z, so PA (f ) = ψqf ΠA ψqf . On the joint algorithm–database space, write Π = ΠA ⊗ Idb . The final state of the compressed execution is E X |Ψq ⟩ = N −N/2 ψqf fb . f ∈F

E Expanding its acceptance expectation and using the orthogonality of { fb }f , we obtain E 1 X ⟨Ψq | Π∆Col |Ψq ⟩ = N ψqg ΠA ψqf ⟨b g | ∆Col fb N f,g∈F " # X 1 = Ef ←F PA (f ) Jf (x) = f (y)K − N x<y N −1 ⟨µPC − 1, PA ⟩. 2 √ Thus, it suffices to bound the left-hand side by O(q 3/2 / N ) to prove Lemma 7.2. =

(31)

7.2

The number of collisions in the database n

For a database D ∈ ({0, 1}n ∪ {⊥}){0,1} , define the two diagonal operators Dcnt |D⟩ := |{x : D(x) ̸= ⊥}| |D⟩ , X Colcnt |D⟩ := JD(x) = D(y) ̸= ⊥K |D⟩ . x<y

These count the queried inputs and collision pairs in the database, respectively. We prove the following bound in Appendix C; the second bound is not tight but sufficient for our purpose. Lemma 7.4. Let |Ξt ⟩ be the final state over the algorithm and database registers outputted by some algorithm after making t ≤ N queries to the compressed oracle O. Then ⟨Ξt | Dcnt |Ξt ⟩ ≤ t,

⟨Ξt | Colcnt |Ξt ⟩ ≤ 129t.

Write the compressed execution of A as W = Uq OUq−1 · · · U1 OU0 ,

|Ψq ⟩ = W |Ω⟩ ,

where |Ω⟩ = |0⟩ |∅⟩ is the initial algorithm state and the Ui are oracle-independent unitaries acting only on the algorithm registers. On each database register, define Q := I − |⊥⟩⟨⊥| . Observe the following identities Qx Qy Colxy |∅⟩ =

Colxy −

1 I |∅⟩ , N

Colxy Qx Qy |∅⟩ = 0

P followed by expanding Colxy |⊥, ⊥⟩ = N −1 v |b v , vb⟩. Define, using the commutator [A, B] = AB − BA, X T := [Qx Qy , Colxy ], R := ∆Col − T (32) x<y

that acts on the database registers. The two identities above gives X X 1 T |∅⟩ = (Qx Qy Colxy |∅⟩ − Colxy Qx Qy |∅⟩) = Colxy − I |∅⟩ = ∆Col |∅⟩ . N x<y x<y Since R = ∆Col − T acts only on the database registers, we also have R |Ω⟩ = 0. Using RW = W R + [R, W ], we therefore obtain RW |Ω⟩ = W R |Ω⟩ + [R, W ] |Ω⟩ = [R, W ] |Ω⟩ =

q X

(Uq O · · · OUj )[R, O](Uj−1 O · · · OU0 ) |Ω⟩ .

(33)

j=1

The last equality uses [R, Ui ] = 0 and the product rule for commutators. The first and last products are interpreted as Uq when j = q and U0 when j = 1, respectively. E We further observe that [R, O] = −[T, O]. The query O preserves each database state fb , while Colxy acts on it by multiplication by Jf (x) = f (y)K. This gives E E E Colxy O |z, w⟩ fb = Jf (x) = f (y)K |z, w + f (z)⟩ fb = OColxy |z, w⟩ fb . 36

Thus [Colxy , O] = 0 for every x < y, and hence [∆Col, O] = 0. Since R = ∆Col − T , it follows that [R, O] = [∆Col, O] − [T, O] = −[T, O]. Define the states immediately before a query and the corresponding backward states by |Φj ⟩ := Uj† O · · · OUq† Π |Ψq ⟩ .

Ψ− := Uj−1 O · · · OU0 |Ω⟩ , j

Note also that T † = −T and [Π, T ] = 0 because T acts on the database while Π acts on the algorithm’s register. This shows that the expectation of ΠT is purely imaginary. Therefore, ⟨Ψq | Π∆Col |Ψq ⟩ = Re ⟨Ψq | ΠR |Ψq ⟩ . Combining the preceding identities gives ⟨Ψq | Π∆Col |Ψq ⟩ = Re ⟨Ψq | ΠRW |Ω⟩ = Re ⟨Ψq | Π[R, W ] |Ω⟩ =

q X

Re ⟨Φj | [R, O] Ψ− j

j=1

=−

q X

Re ⟨Φj | [T, O] Ψ− j

(34)

j=1

7.3

Proof of the planted-collision bound

Proof of Lemma 7.2. The cases q = 0 and q > N/2 are immediate. We assume 1 ≤ q ≤ N/2. Define X X Bx := |⊥⟩⟨⊥|x Qy Colxy , B := |x⟩⟨x| ⊗ Bx , x

y̸=x

where the first register in B is the query input register. For a fixed query input x, we have [Qx Qy , Colxy ] = [Qy , Colxy ] − |⊥⟩⟨⊥|x Qy Colxy + Colxy Qy |⊥⟩⟨⊥|x . The first term commutes with the query. The last two terms, summed over y ̸= x, give −Bx + Bx† . All terms not involving x also commute with the query. Hence [T, O] = OB − BO + B † O − OB † .

(35)

We show in Appendix C that every joint algorithm-database state |Ξ⟩ whose database registers are E b supported on span{ f : f ∈ F} satisfies ∥B † |Ξ⟩ ∥2 ≤

4 ⟨Ξ| Dcnt + Colcnt |Ξ⟩ . N

(36)

− Each of the four vectors |Φj ⟩ , O |Φj ⟩ , Ψ− has norm at most one. Recall the states Ψ− and j , O Ψj j − O Ψj are obtained after j − 1 and j queries to O, respectively. To apply Lemma 7.4 to |Φj ⟩, consider an algorithm that runs W , copies its output bit to an auxiliary qubit using a CNOT gate, and then applies Uj† O · · · OUq† to the original registers. The component of the resulting state in which the auxiliary qubit is 1 is precisely |Φj ⟩. This algorithm makes 2q − j queries, since O† = O. One additional query gives the component O |Φj ⟩ and uses 2q − j + 1 ≤ 2q queries in total. Both count operators are positive and act only on the database registers, so their expectations in either component are at most their expectations in the corresponding full state. Thus, since 2q ≤ N , Lemma 7.4 gives

⟨Ξ| Dcnt |Ξ⟩ ≤ 2q,

⟨Ξ| Colcnt |Ξ⟩ ≤ 258q 37

for each of the four vectors |Ξ⟩ above. Applying Eq. (36), we obtain ∥B † |Ξ⟩ ∥2 ≤

1040q 4 (2q + 258q) = . N N

By the Cauchy–Schwarz inequality, each of the four terms in Eq. (35), between ⟨Φj | and Ψ− j , has p absolute value at most 1040q/N . For example, r 1040q − † Ψ ≤ ∥B O |Φ ⟩ ∥ ∥ ∥ ≤ ⟨Φj | OB Ψ− . j j j N It follows that

r ⟨Φj | [T, O]

Ψ− j

≤4

1040q . N

Using Eq. (34), we obtain |⟨Ψq | Π∆Col |Ψq ⟩| ≤

q X

r ⟨Φj | [T, O] Ψ− j

j=1

≤ 4q

√ q 3/2 1040q = 16 65 √ . N N

Finally, Eq. (31) concludes the proof of the lemma.

References [1] Advanced Encryption Standard (AES). National Institute of Standards and Technology, NIST FIPS PUB 197, U.S. Department of Commerce, November 2001. 3 [2] Akshima, Tyler Besselman, Kai-Min Chung, Siyao Guo, and Tzu-Yi Yang. Tight quantum time-space tradeoffs for permutation inversion. In Joan Daemen and Emmanuel Thomé, editors, Advances in Cryptology - EUROCRYPT 2026 - 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10-14, 2026, Proceedings, Part I, volume 16541 of Lecture Notes in Computer Science, pages 431–456. Springer, 2026. 3, 4 [3] Gorjan Alagic, Christian Majenz, Alexander Russell, and Fang Song. Quantum-access-secure message authentication via blind-unforgeability. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 788–817. Springer, Cham, May 2020. 3 [4] Prabhanjan Ananth, Luowen Qian, and Henry Yuen. Cryptography from pseudorandom quantum states. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part I, volume 13507 of LNCS, pages 208–236. Springer, Cham, August 2022. 3 [5] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald De Wolf. Quantum lower bounds by polynomials. Journal of the ACM (JACM), 48(4):778–797, 2001. 4, 13, 45 [6] Mihir Bellare, Ted Krovetz, and Phillip Rogaway. Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible. In Kaisa Nyberg, editor, EUROCRYPT’98, volume 1403 of LNCS, pages 266–280. Springer, Berlin, Heidelberg, May / June 1998. 3 [7] Charles H Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani. Strengths and weaknesses of quantum computing. SIAM journal on Computing, 26(5):1510–1523, 1997. 4, 9 [8] Daniel J. Bernstein. Stronger security bounds for Wegman-Carter-Shoup authenticators. In Ronald Cramer, editor, EUROCRYPT 2005, volume 3494 of LNCS, pages 164–180. Springer, Berlin, Heidelberg, May 2005. 3

[9] Srimanta Bhattacharya and Mridul Nandi. Full indifferentiable security of the xor of two or more random permutations using the χ2 method. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part I, volume 10820 of LNCS, pages 387–412. Springer, Cham, April / May 2018. 3 [10] Srimanta Bhattacharya and Mridul Nandi. Luby-Rackoff backwards with more users and more security. In Mehdi Tibouchi and Huaxiong Wang, editors, ASIACRYPT 2021, Part III, volume 13092 of LNCS, pages 345–375. Springer, Cham, December 2021. 3 [11] Dan Boneh and Mark Zhandry. Quantum-secure message authentication codes. In Thomas Johansson and Phong Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 592–608. Springer, Berlin, Heidelberg, May 2013. 3 [12] Dan Boneh and Mark Zhandry. Secure signatures and chosen ciphertext security in a quantum computing world. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 361–379. Springer, Berlin, Heidelberg, August 2013. 3 [13] Michel Boyer, Gilles Brassard, Peter Høyer, and Alain Tapp. Tight bounds on quantum searching. Fortschritte der Physik: Progress of Physics, 46(4-5):493–505, 1998. 4 [14] Gilles Brassard, Peter Høyer, Michele Mosca, and Alain Tapp. Quantum amplitude amplification and estimation. In Quantum Computation and Quantum Information: A Millennium Volume, volume 305 of Contemporary Mathematics, pages 53–74. American Mathematical Society, 2002. 42 [15] Gilles Brassard, Peter Høyer, and Alain Tapp. arXiv:quant-ph/9705002, 1997. 3, 8, 42

Quantum algorithm for the collision problem.

[16] Joseph Carolan. Compressed permutation oracles. In Proceedings of the 58th Annual ACM Symposium on Theory of Computing, pages 150–161. ACM, 2026. 3 [17] Yu Long Chen, Wonseok Choi, and Changmin Lee. Improved multi-user security using the squared-ratio method. In Helena Handschuh and Anna Lysyanskaya, editors, CRYPTO 2023, Part II, volume 14082 of LNCS, pages 694–724. Springer, Cham, August 2023. 3, 8 [18] Yu Long Chen, Eran Lambooij, and Bart Mennink. How to build pseudorandom functions from public random permutations. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part I, volume 11692 of LNCS, pages 266–293. Springer, Cham, August 2019. 3, 8 [19] Wonseok Choi, Hwigyeom Kim, Jooyoung Lee, and Yeongmin Lee. Multi-user security of the sum of truncated random permutations. In Shweta Agrawal and Dongdai Lin, editors, ASIACRYPT 2022, Part II, volume 13792 of LNCS, pages 682–710. Springer, Cham, December 2022. 3, 8 [20] Wonseok Choi, ByeongHak Lee, and Jooyoung Lee. Indifferentiability of truncated random permutations. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part I, volume 11921 of LNCS, pages 175–195. Springer, Cham, December 2019. 3 [21] Wonseok Choi, Jooyoung Lee, and Yeongmin Lee. Building PRFs from TPRPs: Beyond the block and the tweak length bounds. IACR Trans. Symm. Cryptol., 2024(1):35–70, 2024. 8 [22] Kai-Min Chung, Serge Fehr, Yu-Hsuan Huang, and Tai-Ning Liao. On the compressed-oracle technique, and post-quantum security of proofs of sequential work. In Anne Canteaut and François-Xavier Standaert, editors, EUROCRYPT 2021, Part II, volume 12697 of LNCS, pages 598–629. Springer, Cham, October 2021. 6, 35, 47 [23] Benoit Cogliati, Rodolphe Lampe, and Jacques Patarin. The indistinguishability of the XOR of k permutations. In Carlos Cid and Christian Rechberger, editors, FSE 2014, volume 8540 of LNCS, pages 285–302. Springer, Berlin, Heidelberg, March 2015. 8 39

[24] Alexandru Cojocaru, Minki Hhan, Qipeng Liu, Takashi Yamakawa, and Aaram Yun. Quantum lifting for invertible permutations and ideal ciphers. In CRYPTO 2025, Part II, LNCS, pages 481–512. Springer, Cham, August 2025. 3 [25] Wei Dai, Viet Tung Hoang, and Stefano Tessaro. Information-theoretic indistinguishability via the chi-squared method. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part III, volume 10403 of LNCS, pages 497–523. Springer, Cham, August 2017. 3, 8 [26] Nilanjan Datta, Avijit Dutta, Sougata Mandal, Hrithik Nandi, and Amlan Sinha. Post-quantum security of keyed sum of permutations and its siblings. In Advances in Cryptology – ASIACRYPT 2026. Springer, 2026. To appear. 9 [27] Data encryption standard. National Bureau of Standards, NBS FIPS PUB 46, U.S. Department of Commerce, January 1977. 3 [28] Itai Dinur. Tight indistinguishability bounds for the XOR of independent random permutations by Fourier analysis. In Marc Joye and Gregor Leander, editors, EUROCRYPT 2024, Part I, volume 14651 of LNCS, pages 33–62. Springer, Cham, May 2024. 3, 4, 5, 8, 11 [29] Itai Dinur. Combining outputs of a random permutation: New constructions and tight security bounds by fourier analysis. In EUROCRYPT 2025, Part I, LNCS, pages 244–273. Springer, Cham, June 2025. 3, 4 [30] Avijit Dutta, Mridul Nandi, and Abishanka Saha. Proof of Mirror Theory for ξmax = 2. IEEE Transactions on Information Theory, 68(9):6218–6232, 2022. 3, 8 [31] Sean Eberhard. More on additive triples of bijections. arXiv:1704.02407, 2017. 3, 4, 8 [32] Sean Eberhard, Freddie Manners, and Rudi Mrazović. Additive triples of bijections, or the toroidal semiqueens problem. Journal of the European Mathematical Society, 21(2):441–463, 2019. 4 [33] Hartmut Ehlich and Karl Zeller. Schwankung von polynomen zwischen gitterpunkten. Mathematische Zeitschrift, 86:41–44, 1964. 45 [34] Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. Limit on the speed of quantum computation in determining parity. Phys. Rev. Lett., 81:5442–5444, Dec 1998. 8, 44 [35] Ben Foxman, Alex Lombardi, Fermi Ma, Barak Nehoran, and John Wright. Quantum lazy sampling and path recording for any group, 2026. 3 [36] Shoni Gilboa, Shay Gueron, and Ben Morris. How many queries are needed to distinguish a truncated random permutation from a random function? Journal of Cryptology, 31(1):162–171, January 2018. 3 [37] Aldo Gunsing and Bart Mennink. The summation-truncation hybrid: Reusing discarded bits for free. In Daniele Micciancio and Thomas Ristenpart, editors, CRYPTO 2020, Part I, volume 12170 of LNCS, pages 187–217. Springer, Cham, August 2020. 3 [38] Chris Hall, David Wagner, John Kelsey, and Bruce Schneier. Building PRFs from PRPs. In Hugo Krawczyk, editor, CRYPTO’98, volume 1462 of LNCS, pages 370–389. Springer, Berlin, Heidelberg, August 1998. 3 [39] Yu-Hsuan Huang, Andreas Hülsing, Varun Maram, Silvia Ritsch, and Abishanka Saha. Feistel tools: Reprogramming and query-recording for QRPs. Cryptology ePrint Archive, Paper 2026/146, 2026. 3 [40] Zhengfeng Ji, Yi-Kai Liu, and Fang Song. Pseudorandom quantum states. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part III, volume 10993 of LNCS, pages 126–152. Springer, Cham, August 2018. 3 40

[41] Stefan Lucks. The sum of PRPs is a secure PRF. In Bart Preneel, editor, EUROCRYPT 2000, volume 1807 of LNCS, pages 470–484. Springer, Berlin, Heidelberg, May 2000. 3, 8 [42] Fermi Ma and Hsin-Yuan Huang. How to construct random unitaries. In 57th ACM STOC, pages 806–809. ACM Press, June 2025. 3 [43] Avradip Mandal, Jacques Patarin, and Valérie Nachef. Indifferentiability beyond the birthday bound for the xor of two public random permutations. In Guang Gong and Kishan Chand Gupta, editors, INDOCRYPT 2010, volume 6498 of LNCS, pages 69–81. Springer, Berlin, Heidelberg, December 2010. 3 [44] Bart Mennink and Alan Szepieniec. XOR of PRPs in a quantum world. In Tanja Lange and Tsuyoshi Takagi, editors, Post-Quantum Cryptography - 8th International Workshop, PQCrypto 2017, pages 367– 383. Springer, Cham, 2017. 8 [45] Tony Metger, Alexander Poremba, Makrand Sinha, and Henry Yuen. Simple constructions of lineardepth t-designs and pseudorandom unitaries. In 65th FOCS, pages 485–492. IEEE Computer Society Press, October 2024. 3 [46] Ryan O’Donnell. Analysis of boolean functions. Cambridge University Press, 2014. 5, 12 [47] Jacques Patarin. A proof of security in O(2n) for the xor of two random permutations. In Reihaneh Safavi-Naini, editor, ICITS 08, volume 5155 of LNCS, pages 232–248. Springer, Berlin, Heidelberg, August 2008. 3, 8 [48] Jacques Patarin. Generic attacks for the xor of k random permutations. In Michael J. Jacobson, Jr., Michael E. Locasto, Payman Mohassel, and Reihaneh Safavi-Naini, editors, ACNS 13International Conference on Applied Cryptography and Network Security, volume 7954 of LNCS, pages 154–169. Springer, Berlin, Heidelberg, June 2013. 5, 8 [49] Theodore J. Rivlin and Elliott W. Cheney. A comparison of uniform approximations on an interval and a finite subset thereof. SIAM Journal on Numerical Analysis, 3(2):311–320, 1966. 45 [50] Ansis Rosmanis. Tight bounds for inverting permutations via compressed oracle arguments, 2021. 3, 4 [51] Adrian She and Henry Yuen. Unitary property testing lower bounds by polynomials. In Yael Tauman Kalai, editor, 14th Innovations in Theoretical Computer Science Conference, ITCS 2023, MIT, Cambridge, Massachusetts, USA, January 10-13, 2023, volume 251 of LIPIcs, pages 96:1–96:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023. 4 [52] Kazuo Shinagawa and Tetsu Iwata. Quantum attacks on sum of Even–Mansour pseudorandom functions. Information Processing Letters, 173:106172, 2022. 9 [53] Victor Shoup. On fast and provably secure message authentication based on universal hashing. In Neal Koblitz, editor, CRYPTO’96, volume 1109 of LNCS, pages 313–328. Springer, Berlin, Heidelberg, August 1996. 3 [54] Fang Song and Aaram Yun. Quantum security of NMAC and related constructions - PRF domain extension against quantum attacks. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part II, volume 10402 of LNCS, pages 283–309. Springer, Cham, August 2017. 3 [55] Mark N. Wegman and Larry Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22:265–279, 1981. 3 [56] Mark Zhandry. A note on the quantum collision and set equality problems. Quantum Information and Computation, 15(7&8):557–567, 2015. 3

[57] Mark Zhandry. How to record quantum queries, and applications to quantum indifferentiability. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 239–268. Springer, Cham, August 2019. 3, 4, 6, 35 [58] Mark Zhandry. How to construct quantum random functions. Journal of the ACM (JACM), 68(5):1–43, 2021. 3, 4, 6, 26, 34

Collision Bias and Heuristic Attacks

We present a heuristic outline of the quantum attacks described in Section 1.3. Throughout, r ≥ 2 is fixed, and the oracle O is either a uniformly random function (O = rf) or the XoP[r] construction (O = XoP). The collision statistic calculations below are intended to explain the expected scalings of advantages. Recall the collision probability of XoP[r] Pr [XoP[r](x) = XoP[r](x′ )] =

(−1)r 1 , + N N (N − 1)r−1

δr :=

(−1)r N (N − 1)r−1

where δr is the difference between the collision probabilities of XoP[r] and a random function, and |δr | = Θ(N −r ). All attacks except the last one are based on the collision finding attack [15]. We actually count the number of the (parts of) collisions in the following way: 1. For an appropriate set S ⊂ {0, 1}n , compute the table TS := {O(x) : x ∈ S}, the set of distinct outputs obtained from the inputs in S. Define the indicator function fS (z) = JO(z) ∈ TS K for z ∈ {0, 1}n \ S. 2. Approximately count the number of z ∈ {0, 1}n \ S such that fS (z) = 1. Note that fS (z) = JO(z) ∈ TS K indicates that z is a part of the cross collision O(z) = O(x) for some x ∈ S. The first step makes s := |S| queries to the oracle O. Let K = |{z ∈ {0, 1}n \ S : fS (z) = 1}| be the number of inputs outside S whose outputs collide with one of the stored values in TS . Using quantum counting [14] e satisfying with t queries to O, we can obtain an estimate K ! p e K/(N − s) K K 1 − =O + 2 N −s N −s t t e − K| is with a constant probability. In other words, if s, t = Θ(q) and K = Θ(s), the additive error |K bounded by s ! N N O + 2 . q q We first compare the distribution of K under the two oracle choices. If O = rf, then conditioned on TS , the values O(z) for z ∈ / S are independent and uniform. Therefore, |TS | K | TS ∼ Bin N − s, . N In particular, for s = Θ(q) and s ≤ cN for a fixed constant c < 1, we have √ Erf [K] = Θ(q), stdrf (K) = Θ( q).

(37)

For XoP[r], the collision probability between every pair of distinct inputs differs from that of a random function by δr . As a heuristic approximation, we expect the number of cross collisions to differ by q |EXoP [K] − Erf [K]| ≈ (N − s)s|δr | = Θ , N r−1 where we use s = Θ(q) and N − s = Θ(N ). We use this heuristic estimate below to derive the expected advantage of the collision-based attacks. 42

Small-query regime: q ≲ N 1/3 . In this regime, it suffices to search for a collision rather than estimate K accurately. The algorithm first constructs TS using s = Θ(q) queries and then uses t = Θ(q) further queries to search for a z ∈ / S satisfying fS (z) = 1. For a fixed value of K, Grover search using t queries finds such a z with probability 2 t K Θ N 3 which coincides with Θ qN for our parameter choice when K = Θ(q). Using the heuristic estimate above for the difference in E[K], we expect the difference between the acceptance probabilities under the two oracle choices to be of order 2 3 t q Θ . |EXoP [K] − Erf [K]| = Θ N Nr Thus the collision-finding attack is expected to achieve advantage Θ(q 3 /N r ) in this regime. e Moderate-query regime: N 1/3 ≲ q ≲ N 1/2 . We now use quantum counting to estimate K. Let K be the estimate obtained using t = Θ(q) queries in the second step. The counting error discussed above (obtained with constant probability) is s s ! ! N N N e |K − K| = O + 2 =O q q q √ since q ≳ N 1/3 . Also note that the standard deviation Θ( q) of K in Eq. (37) is relatively smaller than this error in this regime. This comparison will be important in the next regime. Using the heuristic estimate above, we expect q |EXoP [K] − Erf [K]| = Θ . N r−1 p Comparing this difference with the quantum-counting error Θ( N/q) heuristically suggests distinguishing advantage of order ! 3/2 q/N r−1 q Θ p =Θ . N r−1/2 N/q Large-query regime: N 1/2 ≲ q ≲ N . Continue to use s = Θ(q) queries to construct the table and t = Θ(q) queries for quantum counting. The additive error of the estimate is, given q ≳ N 1/2 , s ! N N √ O + 2 = O( q). q q √ Note that the standard deviation of K in Eq. (37) is already Θ( q). This means that the values of K for √ two different random oracles may be of order Θ( q), which is no smaller than the estimation error. Using the heuristic estimate above, we expect q |EXoP [K] − Erf [K]| = Θ . N r−1 √ Comparing this difference with the above typical difference q of two random oracles suggests distinguishing advantage of order, heuristically, √ q q/N r−1 Θ =Θ . √ r−1 q N At q = Θ(N ), this heuristic scaling becomes Θ(N 3/2−r ), matching the second bound of Theorem 4.1. 43

Parity attack (q ≥ N/2). Finally, suppose that q ≥ N/2. Fix a nonzero a ∈ {0, 1}n and define the Boolean function gO (x) := ⟨a, O(x)⟩ for the oracle O, which can beLcomputed by a single query to O. For the XoP[r] construction, assuming n ≥ 2, the parity of gXoP[r] , i.e., x∈{0,1}n gXoP[r] (x) becomes 0 because * a,

+ M

XoP[r](x)

* =

r M

+ M

Pi (x)

* =

i=1 x∈{0,1}n

x∈{0,1}n

r M

+ M

= 0.

i=1 y∈{0,1}n

For a random function, this parity is a uniformly random bit. The parity of gO can be computed exactly with N/2 quantum queries by pairing up the N inputs and computing the XOR of each pair with Deutsch’s algorithm, which is optimal [34]. The distinguisher that outputs the parity thus has advantage 1/2.

Reductions between Planted Distributions

B.1

Several planted collisions

We recall the statement of the lemma for convenience. 3 2 Lemma 6.10. Advdist q (DPC,k , DF ) = O(q /N ) for k = 2, 3. Proof of Lemma 6.10. Fix i ∈ {1, 2, 3} and a q-query algorithm A. Let g be an oracle from DF or DPC . Given the oracle g, we will construct another oracle h as follows. Sample 2i − 2 distinct points z1 , . . . , z2i−2 ∈ [N ] uniformly and sample independent uniform values v1 , . . . , vi−1 ∈ [N ]. Let T = [N ] \ {z1 , ..., z2i−2 }. Define ( vj x ∈ {z2j−1 , z2j }, h(x) = g(x) x ∈ T. We define an algorithm Bi given the oracle g for i ∈ {1, 2, 3} as follows. Bi : It defines h as above, and executes A with oracle h. Note that one quantum query to h can be simulated using at most two queries to g. In more detail, for every x, z ∈ {0, 1}n , the simulation acts as follows: query to g

|x, 0n , z⟩ −−−−−−→ |x, g(x), z⟩ unitary

−−−−→ |x, g(x), z + h(x)⟩ query to g

−−−−−−→ |x, 0n , z + h(x)⟩. If g ∼ DF , then h ∼ DPC,i−1 because of newly planted collisions. On the other hand, if g ∼ DPC , both inputs of the original planted collision pair of g is contained in T with probability pi =

1 (N − 2i + 2)2 ≥ . (N )2 5

On this event, h ∼ DPC,i as there are i pairs of the planted collisions. If any of the inputs of the original planted collision of g is not contained in T , we can observe that g|T is a uniform random function (without planted collisions), as well as h|T . Also note that h|[N ]\T consists of i − 1 collisions, which shows that h ∼ DPC,i−1 in this case. Consequently, the distributions of h in the two cases, g ∼ DF and g ∼ DPC , are exactly DPC,i−1

and pi DPC,i + (1 − pi )DPC,i−1 .

Taking the difference of the two acceptance probabilities of Bi for the two cases gives dist pi Advdist (DPC , DF ; Bi ) ≤ Advdist q (DPC,i , DPC,i−1 ; A) = Adv 2q (DPC , DF ).

We can use the hybrid argument (or the triangle inequality) to show, using DPC,0 = D F , the following for k ∈ {2, 3}: Advdist q (DPC,k , DF ) ≤

k X

dist p−1 i Adv2q (DPC , DF )

i=1 3 2 ≤ 5kAdvdist 2q (DPC , DF ) = O(q /N ).

B.2

A planted triple from a planted pair

We first prove the decisional version of the quantum search bound using the polynomial method [5]. Claim B.1. Let ZM be the distribution that always outputs the all-zero function b∅ (j) = 0 for all j ∈ [M ]. Let SM be a distribution obtained by sampling z ← [M ] uniformly at random, and outputting the indicator function bz (j) = Jj = zK. Then, for every q, it holds that Advdist q (SM , ZM ) ≤

16q 2 M

Proof. Fix a q-query quantum algorithm A having access to an oracle b : [M ] → {0, 1}. Write x = (x1 , · · · , xM ) ∈ {0, 1}M be an alternative representation of b by choosing xi = b(i). Let P (x) = Pr[Ax → 1] be the acceptance probability of A given oracle x. It is clear that 0 ≤ P (x) ≤ 1 for all x ∈ {0, 1}M . The polynomial method for quantum query algorithms [5] shows that P can be written as a real multilinear polynomial of degree at most 2q on input x. We use the standard symmetrization argument in the original polynomial method paper [5, Section 3.1] by taking the average of all inputs. This shows that there exists a univariate real polynomial p of degree at most 2q such that or every k ∈ {0, · · · , M }, it holds that X 1 p(k) = M P (x). k

x∈{0,1}M ,|x|=k

In other words, p(k) is the average acceptance probability of A over all Boolean functions of Hamming weight k. In particular, it holds that p(0) and p(1) correspond to the acceptance probability of A with oracle from ZM and SM , respectively. It remains to give an upper bound of δ := |p(1)−p(0)|. By the mean value theorem, there exists z ∈ (0, 1) such that |p′ (z)| = δ. Since the degree of p is at most 2q and 0 ≤ p(k) ≤ 1 for every k ∈ {0, · · · , M }, the results from [33, 49] show that δM 4q 2 ≥ deg(p)2 ≥ . 1+δ If 16q 2 /M ≥ 1, there is nothing to prove. Otherwise, rearranging above gives δ≤

4q 2 16q 2 ≤ 2 M − 4q M

which proves the desired upper advantage bound. 2 Lemma 6.8. Advdist q (D3PC , DF ) = O(q /N ).

Proof of Lemma 6.8. Fix a q-query algorithm A. We first prove the intermediate bound Advdist q (D3PC , DPC ) ≤

64q 2 N −2

using the above lemma. Define an algorithm B with a Boolean oracle b : [N ] → {0, 1} as follows. 45

1. Sample uniformly distinct inputs a1 , a2 , a uniform output v, and R ← F, all independently. 2. Define hb : [N ] → [N ] by ( hb (x) :=

v if x ∈ {a1 , a2 } or b(x) = 1, R(x) otherwise.

3. Run A with the oracle Ohb . As one query to Ohb is simulated by two queries to Ob , B makes at most 2q queries to b. Suppose b ← ZN . As b(x) = 0 always, we have hb (a1 ) = hb (a2 ) = v and hb (x) = R(x) for x ∈ / {a1 , a2 }. Since v and the values R(x) for x ∈ / {a1 , a2 } are independent and uniform, hb is a uniform random function conditioned on hb (a1 ) = hb (a2 ). Since (a1 , a2 ) is chosen uniformly, hb ∼ DPC . Suppose b ∼ SN . Then we have b(x) = Jx = zK for a randomly sampled z ← [N ]. Let E be the event z ∈ {a1 , a2 }. Note that Pr[E] = 2/N . If E occurs, since b(x) = 1 implies z ∈ {a1 , a2 }, hb ∼ DPC by the above argument. If E does not occur, we have hb (a1 ) = hb (a2 ) = hb (z) = v and hb (x) = R(x) for x∈ / {a1 , a2 , z}. Since v and R are independent and uniform, hb is a uniform random function conditioned on hb (a1 ) = hb (a2 ) = hb (z). Since (a1 , a2 , z) is chosen uniformly, hb ∼ D3PC . Consequently, a q-query distinguisher for NN−2 D3PC + N2 DPC and DPC gives a 2q-query distinguisher for SN and ZN . By the claim, we have N N −2 2 dist dist Advq (D3PC , DPC ; A) = Advq D3PC + DPC , DPC ; A N −2 N N 2 N 64q = Advdist (S , Z ; B) ≤ . N N 2q N −2 N −2 The triangle inequality now gives exactly the desired comparison: dist dist Advdist q (D3PC , DF ) ≤ Advq (D3PC , DPC ) + Advq (DPC , DF ) 2 q q3 q2 =O + 2 =O , N N N

where we use q ≤ N in last equality.

B.3

Planted 4-XOR by splitting outputs

3 2 Lemma 6.11. Advdist q (D4X , DF ) = O(q /N ).

Proof of Lemma 6.11. Fix A be a q-query algorithm. Let g : {0, 1}n → {0, 1}n be either a uniform random function (from DF ) or a random function with a single planted collision (from DPC ). We define a function h using g that is either a uniform random function or a random function with a planted 4-xor tuple with a certain probability. Formally, we define h : {0, 1}n → {0, 1}n as follows. Let M = N/2 = 2n−1 . Sample a uniform random permutation π of {0, 1}n and independent and uniform random R1 , . . . , RM ∈ {0, 1}n . For each j ∈ {0, 1}n−1 , set h(π(j∥0)) = Rj , h(π(j∥1)) = Rj + g(j∥0) where ∥ denotes the concatenation. Let B be an algorithm that defines h as above, and executes A with oracle h. As noted before, each query to h requires at most two queries to g. We analyze two cases. If g ∼ DF , then it is not hard to see that h ∼ DF . Consider g ∼ DPC and let {u, v} be the planted collision pair of g. Define E by the event that both of u, v are included in {(j∥0) : j ∈ {0, 1}n−1 }. This event occurs with probability at least p=

(M )2 N −2 1 = ≥ . (N )2 4(N − 1) 6 46

Conditioned on E, write v = v0 ∥0 and u = u0 ∥0. The restriction of g to {(j∥0) : j ∈ {0, 1}n−1 } is uniform subject to g(u) = g(v). For h, this gives h(π(u0 ∥0)) + h(π(u0 ∥1)) + h(π(v0 ∥0)) + h(π(v0 ∥1)) = 0n . The outputs of h on those inputs π(u0 ∥0), π(u0 ∥1), π(v0 ∥0), π(v0 ∥1) are uniform conditioned on the sum being 0n , meaning that they becomes the planted 4-xor tuple. All other outputs are uniformly and randomly distributed. In other words, h ∼ D4X in this case. On the other hand, conditioned on ¬E, we can see that the h ∼ DF . Therefore, the distribution of the oracles given to A in this execution become DF and pD4X + (1 − p)DF , respectively. Subtracting acceptance probabilities gives pAdvdist (D4X , DF ; A) = Advdist (DPC , DF ; B) ≤ Advdist 2q (DPC , DF ). Taking the maximum over A proves dist 3 2 Advdist q (D4X , DF ) ≤ 6Adv2q (DPC , DF ) = O(q /N ).

Missing Proofs for the Compressed Oracles

Lemma 7.4. Let |Ξt ⟩ be the final state over the algorithm and database registers outputted by some algorithm after making t ≤ N queries to the compressed oracle O. Then ⟨Ξt | Dcnt |Ξt ⟩ ≤ t,

⟨Ξt | Colcnt |Ξt ⟩ ≤ 129t.

Proof. After s queries, the state is supported on databases D satisfying |{x : D(x) ̸= ⊥}| ≤ s. Since the state has norm at most one, this proves the first inequality. We now bound the increase in the collision count caused by a query. Write χb (v) := (−1)b·v ,

1 X |χb ⟩ := √ χb (v) |v⟩ N v

for the Fourier basis of the response register. In particular, |χ0 ⟩ = |+⟩. Fix a query input x and a response state |χb ⟩. For b ̸= 0, the query acts on database register x by the operator X Ob = Zb + |+⟩⟨+| − |+⟩ ⟨χb | − |χb ⟩ ⟨+| + |χb ⟩ ⟨⊥| + |⊥⟩ ⟨χb | , Zb := χb (v) |v⟩⟨v| , v

as follows from [22, Lemma 4.3]. For b = 0, the query is the identity. Also fix the computational-basis values of the database registers other than x, and put X X mv mv := |{y ̸= x : D(y) = v}|, ℓ := mv , c := . 2 v v Thus, ℓ is the number of inputs y ̸= x with D(y) ̸= ⊥, and c is the number of collision pairs not involving x. In particular, X m2v = ℓ + 2c. v

On this subspace, the collision-count operator is cI + A, where X A := mv |v⟩⟨v| v

acts on database register x and counts collision pairs involving x. We have ∥A |+⟩ ∥2 = ∥A |χb ⟩ ∥2 =

ℓ + 2c . N

Moreover, [A, Zb ] = 0 and A |⊥⟩ = p0. In the expansion of Ob , the commutator with each of |+⟩⟨+|, |+⟩ ⟨χb |, (ℓ + 2c)/N . The commutator with each of the remaining two terms has and |χb ⟩ ⟨+| has norm at most 2 p norm at most (ℓ + 2c)/N . Therefore, r ℓ + 2c ∥[A, Ob ]∥ ≤ 8 . N Since Ob is unitary, the change in the collision-count operator satisfies r ℓ + 2c † † . ∥Ob AOb − A∥ = ∥Ob [A, Ob ]∥ ≤ 8 N The same bound holds for b = 0, since the change is zero. Let |Ξs ⟩ denote the state after s queries and the subsequent algorithm operations, just before the next query, and put ks := ⟨Ξs | Colcnt |Ξs ⟩ . Both O and Colcnt preserve the subspaces specified by the query input x, the Fourier-basis response b, and the values of the other database registers. Index these mutually orthogonal subspaces by λ. Let pλ be the squared norm of the component of |Ξs ⟩ in subspace λ, and let ℓλ , cλ be the corresponding values of ℓ, c. Then X X pλ = ∥Ξs ∥2 ≤ 1, ℓλ ≤ s, pλ cλ ≤ ks . λ

The last inequality holds because cλ counts only collision pairs not involving the queried input. Applying the preceding operator bound in each subspace and then the Cauchy–Schwarz inequality gives ⟨Ξs | O† Colcnt O |Ξs ⟩ − ks 8 X p ≤√ pλ ℓλ + 2cλ N λ !1/2 !1/2 X X 8 pλ pλ (ℓλ + 2cλ ) ≤√ N λ λ r s + 2ks ≤8 . N A unitary acting only on the algorithm’s registers leaves the expectation of Colcnt unchanged. An orthogonal projection on those registers cannot increase this expectation, provided that the resulting state is not renormalized. Indeed, such a projection commutes with the positive operator Colcnt . Consequently, r s + 2ks ks+1 ≤ ks + 8 . (38) N Starting from k0 = 0, we prove ks ≤ 129s by induction. If ks ≤ 129s and s < N , then r √ 259s ks+1 ≤ 129s + 8 ≤ 129s + 8 259 ≤ 129(s + 1). N This proves the second inequality. 48

We E will prove that for every joint algorithm-database state |Ξ⟩ whose database registers b are supported on span{ f : f ∈ F}, it holds that Proof of Eq. (36).

4 ⟨Ξ| Dcnt + Colcnt |Ξ⟩ . N √ P v ⟩ : v ∈ {0, 1}n }. Put |zv ⟩ := |b v ⟩ − |⊥⟩ / N . Then ⟨zv |zw ⟩ = Jv = wK − 1/N and v |zv ⟩⟨zv | = Q on span{|b For a fixed query input x, define ∥B † |Ξ⟩ ∥2 ≤

nv :=

(|zv ⟩⟨zv |)y ,

y̸=x

1 X bv := √ (|⊥⟩ ⟨zv |)y . N y̸=x

The identities for |zv ⟩ give |⊥⟩⟨⊥|x X (nv + bv )† (nv + bv ), N v X 1 2 ⟨Ξ| Dcnt,̸=x |Ξ⟩ + 2 ⟨Ξ| Colcnt,̸=x |Ξ⟩ , ∥nv |Ξ⟩ ∥ = 1 − N v X N −1 ∥bv |Ξ⟩ ∥2 ≤ ⟨Ξ| Dcnt,̸=x |Ξ⟩ . N v Bx Bx† =

Here the subscript ̸= x means that database register x is omitted from the count, and the last line follows from the Cauchy–Schwarz inequality over the N − 1 database registers. Using ∥a + b∥2 ≤ 2∥a∥2 + 2∥b∥2 , dropping the projector |⊥⟩⟨⊥|x , and summing over the blocks corresponding to the query inputs proves Eq. (36).

Record · ID 1108641 · SHA-256 0f3054ca7b4d69ed
Retrieved via Conceptio — every document is proof-bundled with source, license, and retrieval metadata.