Indistinguishability of Sum of Permutations A Fourier Analytic Route to Classical and Quantum Security
Ritam Bhaumik1 , Chun Guo2,3,4 , Xiaoning Guo2,3,4 , and Ashwin Jha5 1 CRC, TII, Abu Dhabi, UAE
[email protected] 2 School of Cyber Science and Technology; 3 State Key Laboratory of Cryptography and Digital Economy Security; 4 Key Laboratory of Cryptologic Technology and Information Security of Ministry of Education,
arXiv:2609.35421v1 [cs.CR] 28 Sep 2026
Shandong University, Qingdao, China [email protected],[email protected] 5 University of Wuppertal, Wuppertal, Germany [email protected]
Abstract. We study classical and quantum indistinguishability of sums of independent random permutations and related transformations from permutations to functions. Let 𝐺 be a finite abelian group 𝑘 (𝑥) = 𝜋 (𝑥) + · · · + 𝜋 (𝑥) for 𝑘 ≥ 2 independent uniform random permutations of order 𝑁, and let 𝜋+ 1 𝑘 of 𝐺. We give a unified Fourier analytic treatment in which the construction is represented by its probability density and a distinguisher by its acceptance function, with the classical and quantum query models imposing different restrictions on the Fourier support of the latter. Classically, we obtain the bound 𝑂 𝑘 (𝑞/𝑁 𝑘−1/2 ) for every 𝑞 < 𝑁, and refine it below the birthday threshold to 𝑂 𝑘 (𝑞 2 /𝑁 𝑘 ). In the quantum model, a simulation argument gives 𝑂 𝑘 (𝑁 −(𝑘−3/2) ) for 𝑞 ≤ (𝑁 − 1)/2, while Fourier interpolation gives concrete finite bounds up to 𝑞 ≤ 4𝑁/15 and the query-dependent bounds
𝑂 min 𝑁 −1/2 ,
𝑞3 𝑁
+ 2
1 𝑁
,
𝑂 𝑘 min
𝑞3 𝑁𝑘
, 𝑁 −(𝑘−3/2)
,
for 𝑘 = 2 and 𝑘 ≥ 3, respectively, throughout 1 ≤ 𝑞 ≤ (𝑁 − 1)/2. For 𝑞 = 1, the first bound sharpens to 𝑂(𝑁 −2 ). Over 𝐺 = F2𝑛 , a one-query Fourier attack matches the order of our one-query bound, while an 𝑁/2-query parity attack with advantage 1/2 shows that our bounds reach the constant-advantage query threshold. We further study two variants of sum of permutations over binary vector spaces. First, we allow arbitrary surjective linear postprocessing, which includes truncation, and obtain classical and quantum bounds that retain the output-size dependence. Second, we analyse Dinur’s variable-output singlepermutation construction, LXoP, for every fixed output width, and derive its classical and quantum security bounds; for one- and two-block outputs, we give concrete quantum security bounds. Keywords: sum of permutations, LXoP, Fourier analysis, quantum security, PRP-to-PRF conversion
1
Introduction
Block ciphers, or pseudorandom permutation (PRP) candidates, are among the most thoroughly studied primitives in symmetric-key cryptography, while many applications [RS06, Che22, Nan24] require a pseudorandom function (PRF). Apart from a few examples like SURF [Ber97], SipHash [AB12], and some AES-based constructions [MN17b, BIL+ 21, FGL+ 24], relatively few dedicated PRF candidates have been proposed or analysed. This makes permutation-to-function transformation a natural route to pseudorandom function designs. It is well-known [Rao66,Fre77,BKR94,CN08] that a random permutation itself can be√distinguished from a random function by looking for collisions, with constant advantage after about 𝑁 classical queries, where 𝑁 denotes the ambient group size. A natural question is therefore how to combine a small number of random permutation calls so that the resulting function remains indistinguishable from random well beyond the birthday bound. In this line of research, three simple constructions are the sum of permutations [BKR98], encrypted Davies-Meyer [CS16] and its dual [MN17a]. In particular, the sum of permutations construction has received a lot of attention from the community. Let 𝐺 be a finite abelian group of order 𝑁, written additively, and let 𝜋1 , . . . , 𝜋 𝑘 be independent uniform random permutations of 𝐺. For 𝑘 ≥ 2, define the sum of 𝑘 permutations by 𝜋+𝑘 (𝑥) ≔ 𝜋1 (𝑥) + · · · + 𝜋 𝑘 (𝑥).
2
R. Bhaumik, C. Guo, X. Guo, A. Jha
When 𝐺 = F2𝑛 , this is the usual XOR-of-permutations construction. The two-permutation case goes back to Bellare et al. [BKR98], and the 𝑘-permutation generalisation [Luc00] is due to Lucks. The construction is simple to evaluate: the permutation calls are independent and can be made in parallel, followed by a group addition. Its security analysis, however, has proved considerably more involved, and has occupied the community for more than two decades. Classical security of sum of permutations. A long line of work [BI99, Luc00, Pat08, CLP15, MP15, Ebe17, DHT17, DNS22, CP20, Din24] has investigated how much security this simple transformation provides. Adding independent permutation outputs allows collisions, so the absence of collisions no longer distinguishes the construction from a random function. The outputs nevertheless remain dependent, because each constituent permutation samples without replacement. An analysis must bound the effect of these dependencies on the joint distribution of all queried outputs, including when the number of queries is close to 𝑁. Over the years, different proof techniques have been used to prove this result when 𝐺 = F2𝑛 , with various degrees of success. The first verifiable proof [Luc00] was given by Lucks who employed the game-playing technique to prove PRF advantage of 𝑂(𝑞 3 /𝑁 2 ), where 𝑞 is the number of queries. Bellare and Impagliazzo, p and later, Dai et al. devised new statistical techniques [BI99,DHT17] to show bounds of 𝑂 𝑛 (𝑞/𝑁) and 𝑂( 𝑞 3 /𝑁 3 ), respectively. Patarin’s mirror theory [Pat08, Pat10, Pat16] has been the main tool to study the problem from a combinatorial viewpoint, and a verified proof [DNS22] of the mirror theory result yields a bound of√ 𝑂(𝑞 2 /𝑁 2 ) for 𝑞 ≤ 𝑁/17 (see also [CP20] for the singlepermutation variant). On the other phand, for 𝑁 ≤ 𝑞 < 𝑁, the best-known attack [Pat13] due to Patarin only achieved an advantage of Ω( 𝑞 2 /𝑁 3 ), leaving a tightness gap. This gap was recently filled [Din24] p √ by Dinur who established a bound of 𝑂( 𝑞 2 /𝑁 3 ) for 𝑞 < 𝑁/2 and 𝑁 ≥ 1000, which is tight for 𝑞 ≥ 𝑁. Shortly after, it came to light that Eberhard had already proved [Ebe17] the same bound for any finite abelian group and for every 𝑞 < 𝑁, in a work [Ebe17] that was largely unknown in the cryptography community. Both Eberhard and Dinur applied Fourier analytic techniques to study the problem. Dinur also studied the sum of 𝑘 permutations construction, and obtained a bound of 𝑞/𝑁 𝑘−1/2 for 𝑞 < 𝑁/2 queries. Variants of sum of permutations. Several variants of the sum of permutations have been proposed to obtain shorter outputs or to generate several output blocks from a single permutation. For shorter outputs, summation can be combined with the truncation technique [HWKS98]. Let 𝐺 = F2𝑛 , with |𝐺| = 𝑁, and let 𝜏 : 𝐺 → 𝐻 be a surjective linear map, where |𝐻| = 𝑀 ≤ 𝑁. The corresponding construction is 𝑥 ↦−→ 𝜏 𝜋1 (𝑥) + 𝜋2 (𝑥) ,
where 𝜋1 and 𝜋2 are independent random permutations of 𝐺. When 𝜏 is a coordinate projection, Choi p et al. [CKLL22] proved a classical distinguishing bound of 𝑂(𝑞 𝑞𝑀/𝑁 2 ) for 𝑞 ≤ 𝑁/4. For outputs in the larger range 𝐺 𝑤 , Iwata’s XORP[𝑤] construction [Iwa06] uses a single random permutation 𝜋 : 𝐺 → 𝐺 and is given by 𝑥 ↦−→ 𝜋(0 ∥ 𝑥) + 𝜋(1 ∥ 𝑥), . . . , 𝜋(0 ∥ 𝑥) + 𝜋(𝑤 ∥ 𝑥) .
Here the prefixes are encoded in 𝑠 = ⌈log2 (𝑤 + 1)⌉ bits and 𝑥 ∈ F2𝑛−𝑠 . The construction produces 𝑤 output blocks using 𝑤 + 1 permutation calls. For fixed 𝑤, its classical distinguishing advantage is 𝑂 𝑤 (𝑞/𝑁) [Pat16,IMV16,BN18]. Dinur [Din25] introduced the LXoP family, which also produces 𝑤 output blocks from 𝑤 + 1 calls, but combines consecutive permutation outputs using a linear automorphism 𝜎 : 𝐺 → 𝐺: 𝑥 ↦−→ 𝜋(0 ∥ 𝑥) + 𝜎(𝜋(1 ∥ 𝑥)), . . . , 𝜋((𝑤 − 1) ∥ 𝑥) + 𝜎(𝜋(𝑤 ∥ 𝑥)) . For 𝑤 ∈ {1, 2}, he proved a classical distinguishing advantage bound of 𝑂(𝑞/𝑁 3/2 ) for 𝑞 ≤ 𝑁/16 and 𝑞 ≤ 𝑁/32, respectively, and 𝑁 ≥ 1024. Quantum security of sum of permutations. The quantum setting raises a different difficulty. For these input-symmetric constructions, a classical distinguisher can be reduced to observing the outputs on a fixed set of queried inputs. This remains true even when the queries are adaptive, as the labels of fresh inputs do not affect the distribution of the next answer. A quantum distinguisher may instead query a superposition of inputs and combine information from different positions by interference. Its behaviour is therefore not determined by the output distribution on any one fixed set of 𝑞 inputs.
Indistinguishability of Sum of Permutations
3
Quantum security of XOR-of-PRP constructions has been studied [MS17] by Mennink and Szepieniec, including key-recovery attacks and a security analysis. There, the construction oracle is queried classically, while the adversary may use offline quantum computation. This is the so-called Q1 security model. In this paper, we study information-theoretic security in the Q2 model, where the adversary can make quantum superposition queries to the construction. The adversary is computationally unbounded, and we count only queries to the construction. Thus the question concerns what can be learned from the oracle itself, independently of the time complexity of processing its answers. The sum of permutations has a global constraint that makes this question particularly interesting. Every complete truth table satisfies Õ Õ 𝜋+𝑘 (𝑥) = 𝑘 𝑦. 𝑥∈𝐺
𝑦∈𝐺
For a uniform random function, the sum on the left is uniform on 𝐺, so the same equality holds with probability exactly 1/𝑁. The complete-table distribution of 𝜋+𝑘 therefore has statistical distance at least 1 − 1/𝑁 from uniform. At the same time, the classical bounds show that every proper restriction is close to uniform. How much of this dependence can a quantum algorithm detect with few queries? At what query count does the checksum become visible? Our bounds give a sharp answer to the second question in the binary setting. For every fixed 𝑘 ≥ 2, the advantage tends to zero for all 𝑞 ≤ 𝑁/2 − 1, whereas an 𝑁/2-query parity algorithm has advantage 1/2. For 𝑞 < 𝑁/2, we exploit the well-known fact [BBC+ 98, Zha12b] that the acceptance probability of a 𝑞-query quantum adversary depends only on the joint distributions of oracle outputs on all sets of at most 2𝑞 inputs. This allows us to focus on dependencies among small collections of outputs, even though each quantum query may involve a superposition over the entire domain. 1.1
Our Results
We develop a common analytic framework for classical and quantum distinguishing games, and apply it to sums of independent permutations, linear-output variants, and a variable-output construction based on a single permutation. In what follows, all bounds are information-theoretic, and the number 𝑘 of independent permutations, or the output width 𝑤, is fixed in the corresponding asymptotic statements. Sum of independent permutations. For every finite abelian group 𝐺 of order 𝑁, we prove the classical bounds 0 ≤ 𝑞 ≤ 1, 0, √ 𝑘 2 𝑘 𝜋+ − g (𝑞) ≤ 𝑂 𝑘 (𝑞 /𝑁 ), 2 ≤ 𝑞 ≤ 𝑁, √ 𝑂 𝑘 (𝑞/𝑁 𝑘−1/2 ), 𝑁 < 𝑞 < 𝑁,
where g : 𝐺 → 𝐺 is a uniform random function. This gives a single proof over arbitrary finite abelian √ groups, and refines the bound when 𝑞 < 𝑁. For 𝑘 = 2, the bound above that threshold is Eberhard’s bound; our proof extends it to every fixed 𝑘 ≥ 2. For quantum queries, we obtain |𝜋2+ ⟩ − |g⟩ (𝑞) ≤ 𝑂
min 𝑁
|𝜋+𝑘 ⟩ − |g⟩ (𝑞) ≤ 𝑂 𝑘 min
−1/2
𝑞3 𝑁
𝑞3 1 , 2+ 𝑁 𝑁
, 𝑁 −(𝑘−3/2) 𝑘
,
(𝑘 ≥ 3),
throughout 1 ≤ 𝑞 ≤ (𝑁 − 1)/2. For 𝑘 = 2 and 𝑞 = √ 1, the bound improves to 𝑂(𝑁 −2 ). The bounds 3 involving 𝑞 describe the behaviour in the range 𝑞 < 𝑁, while the bounds independent of 𝑞 remain small throughout the stated range. We also give concrete bounds for 𝑁 ≥ 1024 and 𝑞 ≤ 4𝑁/15. Over 𝐺 = F2𝑛 , a one-query algorithm has advantage 1/(2(𝑁 − 1) 𝑘 ), matching the order of our upper bound at one query. For 𝑛 ≥ 2, the 𝑁/2-query parity attack, together with the uniform bound of 𝑂 𝑘 (𝑁 −(𝑘−3/2) ) throughout 𝑞 ≤ 𝑁/2 − 1, establishes the exact number of queries required to achieve a constant advantage. Linear-output-postprocessing. For 𝐺 = F2𝑛 , let 𝜏 : 𝐺 → 𝐻 = F2𝑚 be surjective and linear, and put 𝑀 = 2𝑚 . √ We prove a classical bound 𝑂 𝑘 (𝑞 𝑀/𝑁 𝑘 ) for 𝜏𝜋+𝑘 throughout 𝑞 < 𝑁. In particular, for the truncated conp struction considered [CKLL22] by Choi et al., our bound improves their single-user bound 𝑂(𝑞 𝑞𝑀/𝑁 2 ) √ by a factor 𝑞. We also obtain quantum bounds that retain the same dependence on 𝑀, both for small query counts and throughout 𝑞 ≤ (𝑁 − 1)/2.
4
R. Bhaumik, C. Guo, X. Guo, A. Jha
Variable output from a single permutation. We analyse Dinur’s LXoP family for every fixed width 𝑤, under the admissibility condition stated in Section 6. The construction produces 𝑤 output blocks using 𝑤 + 1 permutation calls. We obtain classical advantage 𝑂 𝑤 (𝑞/𝑁 3/2 ) and quantum advantage 𝑂 𝑤 (𝑁 −1/2 ) for query counts up to a sufficiently small constant fraction of the construction’s input-domain size. We also give concrete quantum bounds for 𝑤 = 1, 2. 1.2
Technical Overview and Organisation
Densities and query restrictions. In Section 2, we represent the construction by its probability density 𝜑 and a distinguisher by its acceptance probability function 𝑎. Relative to the reference product measure, the distinguishing advantage is then given by the inner product |⟨𝑎, 𝜑 − 1⟩|. To analyse this inner product, we first choose an orthonormal basis for functions on the output set, with respect to the reference output distribution, containing the constant function 1 . We use this same basis for each truth-table entry 𝑓 (𝑥). Taking products of these basis functions, with one factor for each input, gives an orthonormal basis for functions of the complete truth-table. We expand 𝑎 and 𝜑 in this product basis and group the terms according to the set 𝑆 of inputs at which the factor is nonconstant. These groups give the orthogonal pure-support components. A component indexed by 𝑆 depends only on the outputs at inputs in 𝑆, and averaging over any one of these outputs, with the others fixed, gives zero. Orthogonality then expresses the distinguishing advantage as the absolute value of a sum of inner products between 𝑎- and 𝜑-components with matching supports. This decomposition is defined for an arbitrary product measure, and the grouped components do not depend on the particular basis chosen. Under the uniform measure on a finite abelian group, we may choose the group characters as our basis. The components are then precisely the terms of the Fourier expansion grouped by their support. For the constructions studied in this paper, input symmetry lets us restrict a classical distinguisher to a fixed set 𝑄 of 𝑞 inputs. Only supports contained in 𝑄 can contribute to its advantage. For a quantum distinguisher, Lemma 2, shows that only components supported on at most 2𝑞 inputs can contribute, although different components may involve different inputs. Since 0 ≤ 𝑎 ≤ 1, Cauchy-Schwarz bounds the remaining inner product by one half of the 𝐿2 norm of the corresponding density projection. This yields the Fourier interpolation bound of Theorem 1. Injection moments and the first nonzero level. Section 3 applies this framework to sums of independent permutations. On a fixed set of distinct inputs, the outputs of one permutation form a uniformly random injection. Summing independent permutation outputs convolves their densities, so the Fourier coefficients of the sum are powers of those of one injection. Eberhard’s fourth-moment bound [Ebe17], together with a bound on the largest nonconstant coefficient, gives the global classical bound for every 𝑘 ≥ 2. We also derive a higher-moment bound for the Fourier coefficients of the injection density, which controls the components involving three or more inputs. In the classical analysis, we apply it to the joint output distribution on 𝑞 fixed inputs. In the quantum analysis, we apply it to the corresponding components of the distribution of the complete truth table, retaining only those involving at most 2𝑞 inputs. The detailed coefficient bounds and moment calculations are given in Appendices A and B. We call the collection of components supported on exactly 𝑡 inputs level 𝑡. Since the one-point marginals are uniform, level one vanishes. To obtain a more precise bound at small query counts, we treat level two separately before applying Cauchy-Schwarz. This component is a scalar multiple of the difference between the number of output collisions and its expected value under a uniform random function. The classical proof bounds its contribution in 𝐿1 by summing over the queried pairs. For quantum queries, Appendix C bounds the correlation of this collision count with the acceptance function. We obtain an 𝑂(𝑞 3 ) bound using Zhandry’s small-range method [Zha12a]: the centred collision count is the first-order deviation from a uniform function when outputs are sampled through a large but finite intermediate range. The common moment estimate bounds the remaining levels. Simulation from the checksum. To reach every quantum query count below 𝑁/2, in Section 4, we use Eberhard’s bound along with a checksum-based simulation argument. Any 𝑁−1 outputs of 𝜋+𝑘 determine the last output. Start instead with independent uniform values on 𝑁 − 1 inputs and complete the table using the same checksum. The resulting function is uniform among all functions with that checksum and is (𝑁 − 1)-wise independent. It is therefore indistinguishable from a uniform random function whenever 2𝑞 ≤ 𝑁 − 1. It remains to compare the sum of permutations with this completed reference function. Both complete tables are determined by their restrictions to the chosen 𝑁 − 1 inputs, so their statistical distance is bounded by the classical estimate on those inputs. This gives the quantum bound 𝑂 𝑘 (𝑁 −(𝑘−3/2) ) throughout the required range.
Indistinguishability of Sum of Permutations
5
Linear-output-postprocessing and shared permutation calls. Section 5 considers applying a surjective linear map 𝜏 to each output. A Fourier character of the projected output 𝜏(𝑦) can also be viewed as a character of the original output 𝑦: its index 𝜂 is replaced by 𝜏⊤ 𝜂. Thus only indices in the subspace Im(𝜏⊤ ), which has size 𝑀, enter the analysis. To bound their contribution, we use the fact that applying the same invertible linear map to every output of a random injection preserves its distribution. This symmetry lets us average over subspaces of size 𝑀 and compare the Fourier moments restricted to such a subspace with the unrestricted moments. This is where the output size 𝑀 enters the bounds. For the refined quantum estimate, we also distinguish tuples of character indices according to the dimension of their span. The probability that all indices lie in a random subspace of size 𝑀 depends on this dimension. Keeping this dependence gives a sharper bound for the higher levels. For the LXoP family studied in Section 6, each construction output consists of 𝑤 blocks obtained from 𝑤 + 1 permutation calls. Expanding a character of the construction output gives a product of characters of the underlying permutation outputs, with one index for each call. These permutation outputs form a random injection, so we can again use its Fourier coefficients. The shared calls force the indices associated with each construction input to satisfy a linear relation. We exploit this relation when applying a Dinur-style recursive identity [Din25] that replaces an injection coefficient by a sum of coefficients involving fewer permutation outputs. To obtain a bound on the sum of squared coefficients, we must control how many original index tuples can give the same tuple after a reduction. By choosing the reductions in a suitable order, the linear relation and the admissibility condition let us recover the removed index. This controls the number of times each reduced coefficient is counted and gives the required second-moment bound. Summing over the supports permitted in each query model then gives the classical and quantum bounds.
2
Fourier Analytic Framework
This section first fixes the notation used throughout the paper and then develops a unified analytic framework for classical and quantum distinguishing games. The framework is inspired by the Fourier analytic methods employed by Eberhard [Ebe17] and Dinur [Din24, Din25]. Notation. For a positive integer 𝑛, write [𝑛] ≔ {1, . . . , 𝑛} and [0] ≔ ∅. For 0 ≤ 𝑘 ≤ 𝑛, let (𝑛) 𝑘 ≔ 𝑛(𝑛 − 1) · · · (𝑛 − 𝑘 + 1), with (𝑛)0 = 1. Empty sums and products are understood as zero and one, respectively. The constants in 𝑂 𝑘 (·) and 𝑂 𝑤 (·) may depend only on the indicated fixed parameter. Let Q be a probability measure on a non-empty finite set Ω. We write 𝑥 ∼ Q to mean that 𝑥 is drawn according to Q, and write supp(Q) for its support. We denote the uniform measure on Ω by UΩ , abbreviated to U when Ω is clear. A density relative to Q is a function 𝜑 : supp(Q) → R≥0 satisfying E𝑥∼Q [𝜑(𝑥)] = 1. We sometimes identify 𝜑 with the probability distribution that assigns mass 𝜑(𝑧)Q(𝑧) to each 𝑧 ∈ supp(Q), when the reference measure is clear. The reference measure Q itself has density 1 . Let 𝐿2 (Q) be the space of complex-valued functions on supp(Q). For ℎ, 𝑔 ∈ 𝐿2 (Q) and 1 ≤ 𝑝 < ∞, write 1/𝑝 ∥ℎ∥𝑝,Q ≔ E𝑥∼Q [|ℎ(𝑥)|𝑝 ] . ⟨ℎ, 𝑔⟩Q ≔ E𝑥∼Q [ℎ(𝑥)𝑔(𝑥)], For densities 𝜑 and 𝜓 relative to Q, their statistical distance is given by TVDQ (𝜑, 𝜓) ≔
1 ∥𝜑 − 𝜓∥1,Q , 2
TVDQ (𝜑, 𝜓) ≤
1 ∥𝜑 − 𝜓∥2,Q . 2
whence by Cauchy-Schwarz,
2.1
(1)
Product Spaces and Support Decomposition
We recall the standard support decomposition on a finite product space (see [O’D14, Sections 8.1 and 8.3]), which requires no algebraic structure on the output set. Let 𝒳 and 𝒴 be finite sets, with 𝒴 ≠ ∅. Fix a probability measure P on 𝒴 and equip 𝒴 𝒳 with the product measure P𝒳 . Unless stated otherwise, densities, expectations, inner products, and norms on this space are taken with respect to P𝒳 , whose subscript is omitted.
6
R. Bhaumik, C. Guo, X. Guo, A. Jha
Let 𝐿02 (P) ≔ 𝑔 ∈ 𝐿2 (P) : E 𝑦∼P [𝑔(𝑦)] = 0 . Choose an orthonormal basis 𝐵0 of 𝐿02 (P) and put 𝐵 = {1 } ∪ 𝐵0 . For 𝜆 = (𝜆 𝑥 )𝑥∈𝒳 ∈ 𝐵𝒳 , define
Φ𝜆 ( 𝑓 ) ≔
Ö
𝜆 𝑥 ( 𝑓 (𝑥)),
supp(𝜆) ≔ {𝑥 ∈ 𝒳 : 𝜆 𝑥 ≠ 1 }.
𝑥∈𝒳
We call supp(𝜆) the pure support of Φ𝜆 . The functions Φ𝜆 form an orthonormal basis of 𝐿2 (P𝒳 ). For 𝑆 ⊆ 𝒳 , let Π𝑆 be the orthogonal projection onto the subspace ℋ𝑆 ≔ Span{Φ𝜆 : supp(𝜆) = 𝑆}. Then 𝐿2 (P𝒳 ) =
Ê
ℋ𝑆 ,
ℎ=
𝑆⊆𝒳
Õ
Π𝑆 ℎ,
∥ℎ∥22 =
𝑆⊆𝒳
Õ
∥Π𝑆 ℎ∥22 .
(2)
𝑆⊆𝒳
The spaces ℋ𝑆 depend only on the orthogonal decomposition 𝐿2 (P) = Span{1} ⊕ 𝐿02 (P), and not on the particular basis chosen for 𝐿02 (P). The space ℋ∅ consists of the constant functions, so Π∅ ℎ = E[ℎ] · 1 . In particular, Π∅ 𝜑 = 1 for every density 𝜑. If the distribution represented by 𝜑 has marginal P at 𝑥, then Π{𝑥} 𝜑 = E[𝜑 | 𝑓 (𝑥)] − 1 = 0.
(3)
For integers 𝑡, 𝑑 ≥ 0, write ℎ =𝑡 ≔
Õ
Π𝑆 ℎ,
Õ
Π≤𝑑 ℎ ≔
Π𝑆 ℎ.
𝑆⊆𝒳 |𝑆|≤𝑑
|𝑆|=𝑡
We shall repeatedly use the following coordinate dependence property of the product basis. A function ℎ ∈ 𝐿2 (P𝒳 ) depends only on the coordinates in 𝑄 ⊆ 𝒳 if and only if Π𝑆 ℎ = 0
for every 𝑆 ⊈ 𝑄.
(4)
If these projections vanish, the expansion of ℎ contains only basis functions supported in 𝑄, which depend only on 𝑄. Conversely, if ℎ depends only on 𝑄, every coefficient involving a mean zero basis function at a coordinate outside 𝑄 vanishes after averaging over that coordinate. 2.2
Distinguishing Advantage and Query Support Cutoffs
For any function 𝑓 ∈ 𝒴 𝒳 , we denote the classical oracle corresponding to 𝑓 by the function itself, while the quantum oracle is denoted by | 𝑓 ⟩. Let 𝒪0 and 𝒪1 be oracles sampled according to densities 𝜑 and 𝜓 relative to P𝒳 , respectively, and accessed in the same model. For an oracle algorithm 𝒜 and a fixed function 𝑓 , let 𝑎( 𝑓 ) ∈ [0, 1] be the probability that 𝒜 outputs 1 given oracle access to 𝑓 . Define ∥𝒪0 − 𝒪1 ∥𝒜 ≔ Pr[𝒜 𝒪0 = 1] − Pr[𝒜 𝒪1 = 1] . We write ∥𝒪0 − 𝒪1 ∥(𝑞) for the supremum over all algorithms making at most 𝑞 queries in the indicated access model. We work in the information-theoretic setting: algorithms may be computationally unbounded, and only oracle queries are counted. Then, ∥𝒪0 − 𝒪1 ∥𝒜 = E[𝑎𝜑] − E[𝑎𝜓] = ⟨𝑎, 𝜑 − 𝜓⟩ ≤ TVDP𝒳 (𝜑, 𝜓),
(5)
where the final inequality follows by writing ⟨𝑎, 𝜑 − 𝜓⟩ = E[(𝑎 − 21 )(𝜑 − 𝜓)], since E[𝜑 − 𝜓] = 0 and |𝑎 − 12 | ≤ 12 , so that the inner product is at most 12 ∥𝜑 − 𝜓∥1 . For the remainder of this paper, we assume 𝜓 = 1. We next apply the support decomposition (2) to the inner product in (5). The constant component of 𝜑 − 1 is zero, and its projection onto every non-empty support 𝑆 is Π𝑆 𝜑. Orthogonality therefore gives ∥𝒪0 − 𝒪1 ∥𝒜 =
Õ
⟨Π𝑆 𝑎, Π𝑆 𝜑⟩ .
∅≠𝑆⊆𝒳
For 𝑗 ≥ 1, put Δ 𝑗 (𝑎, 𝜑) ≔
Õ
⟨Π𝑆 𝑎, Π𝑆 𝜑⟩.
𝑆⊆𝒳 |𝑆|=𝑗
The first two levels will often be treated directly, while the remaining levels are bounded in 𝐿2 .
(6)
Indistinguishability of Sum of Permutations
7
Lemma 1. Let 𝒪0 ∼ 𝜑 and 𝒪1 ∼ 1 be function oracles in the same access model. Suppose Π𝑆 𝑎 = 0 whenever |𝑆| > 𝑑. Then, for every integer 0 ≤ 𝑟 ≤ 𝑑, 1/2 𝑟 Õ
© ª 1 Õ ® |Δ 𝑗 (𝑎, 𝜑)| + ∥Π𝑆 𝜑∥22 ® ∥𝒪0 − 𝒪1 ∥𝒜 ≤ ® 2 𝑗=1 𝑆⊆𝒳 «𝑟+1≤|𝑆|≤𝑑 ¬
.
If 𝑎 depends only on the coordinates in 𝑄 ⊆ 𝒳 , the sum in the remainder may be restricted to 𝑆 ⊆ 𝑄. Proof. By (6), only non-empty supports contribute to the advantage. Since Π𝑆 𝑎 = 0 for |𝑆| > 𝑑, we have ⟨𝑎, 𝜑 − 1⟩ =
𝑟 Õ 𝑗=1
Δ 𝑗 (𝑎, 𝜑) +
Õ
⟨Π𝑆 𝑎, Π𝑆 𝜑⟩.
𝑆⊆𝒳 𝑟<|𝑆|≤𝑑
Put 𝑚 = E[𝑎]. Since 0 ≤ 𝑎 ≤ 1,
Õ
∥Π𝑆 𝑎∥22 = ∥𝑎 − 𝑚∥22 = E[𝑎 2 ] − 𝑚 2 ≤ 𝑚 − 𝑚 2 ≤
∅≠𝑆⊆𝒳
1 . 4
By Cauchy-Schwarz, 1/2
© ª 1 Õ ® ∥Π𝑆 𝜑∥22 ® ⟨Π𝑆 𝑎, Π𝑆 𝜑⟩ ≤ ® 2 𝑆⊆𝒳 𝑆⊆𝒳 𝑟<|𝑆|≤𝑑 «𝑟<|𝑆|≤𝑑 ¬ Õ
.
The triangle inequality gives the claim. If 𝑎 depends only on 𝑄, then (4) gives Π𝑆 𝑎 = 0 whenever 𝑆 ⊈ 𝑄, so these supports may also be omitted. ⊔ ⊓ Remark 1. The constructions considered below are invariant in distribution under input permutations, as is the product reference measure. Thus, for 𝑞 ≤ |𝒳 |, a classical 𝑞-query distinguisher may be restricted to any fixed set 𝑄 of size 𝑞: answer its 𝑗-th fresh query using the 𝑗-th point of 𝑄, and replay answers to repeated queries. Input symmetry preserves the transcript distribution under both oracle distributions. By (4), the resulting acceptance function satisfies Π𝑆 𝑎 𝑄 = 0 whenever 𝑆 ⊈ 𝑄. For a 𝑞-query quantum distinguisher, every nonzero pure-support component of the acceptance probability involves at most 2𝑞 input coordinates. We use the standard quantum function-oracle model, with a fixed injective encoding of 𝒴 into a finite abelian group and translation by the encoded output; all applications below instantiate it by the usual addition oracle on a finite abelian output group. Lemma 2. Let 𝒜 be a quantum algorithm making at most 𝑞 queries to a function 𝑓 : 𝒳 → 𝒴 , and let 𝑎( 𝑓 ) be its acceptance probability. Then Π𝑆 𝑎 = 0 whenever |𝑆| > 2𝑞. Proof. Write the function oracle as 𝑈 𝑓 |𝑥, 𝑟, 𝑧⟩ = |𝑥⟩ ⊗ 𝑉 𝑓 (𝑥) |𝑟⟩ ⊗ |𝑧⟩ , where 𝑉𝑦 |𝑟⟩ = |𝑟 + enc(𝑦)⟩ translates the answer register by the fixed encoding of 𝑦 ∈ 𝒴 , and 𝑧 denotes the internal registers of the algorithm. For a basis label 𝑢 = (𝑥, 𝑟, 𝑧), every matrix entry ⟨𝑢|𝑈 𝑓 |𝑢 ′ ⟩ therefore depends on 𝑓 only through the coordinate 𝑓 (𝑥). Let 𝜌𝑡 ( 𝑓 ) denote the density matrix of the algorithm after the 𝑡-th query and the subsequent oracleindependent operation, with 𝜌0 the initial state. We prove inductively that every matrix entry of 𝜌𝑡 ( 𝑓 ), viewed as a function of 𝑓 , is a linear combination of functions each depending on at most 2𝑡 input coordinates. The claim is immediate for 𝑡 = 0, since 𝜌0 is independent of 𝑓 . Suppose it holds after 𝑡 − 1 queries, and consider the state immediately after the next oracle call, 𝜌′𝑡 ( 𝑓 ) = 𝑈 𝑓 𝜌𝑡−1 ( 𝑓 )𝑈 †𝑓 .
8
R. Bhaumik, C. Guo, X. Guo, A. Jha
For basis labels 𝑢 = (𝑥, 𝑟, 𝑧) and 𝑣 = (𝑥 ′ , 𝑟 ′ , 𝑧 ′ ), we have ⟨𝑢|𝜌′𝑡 ( 𝑓 )|𝑣⟩ =
Õ
⟨𝑢|𝑈 𝑓 |𝑢 ′ ⟩ ⟨𝑣|𝑈 𝑓 |𝑣 ′ ⟩
𝑢 ′ ,𝑣 ′
· ⟨𝑢 ′ |𝜌𝑡−1 ( 𝑓 )|𝑣 ′ ⟩. The first two factors depend only on 𝑓 (𝑥) and 𝑓 (𝑥 ′ ). By the induction hypothesis, the last factor is a linear combination of functions each depending on a set 𝑄 ⊆ 𝒳 with |𝑄| ≤ 2(𝑡 − 1). Multiplying any such function by the first two factors produces a function depending only on 𝑄 ∪ {𝑥, 𝑥 ′ }, which has size at most 2𝑡. Hence every entry of 𝜌′𝑡 ( 𝑓 ) has the required form. If Φ𝑡 denotes the oracle-independent operation following the query, then every entry of 𝜌𝑡 ( 𝑓 ) = Φ𝑡 (𝜌′𝑡 ( 𝑓 )) is a fixed linear combination of entries of 𝜌′𝑡 ( 𝑓 ), with coefficients independent of 𝑓 . We emphasise that the density-matrix formulation also allows mixed initial states, classical randomness, and intermediate measurements, with their outcomes retained in the internal registers. The same coordinatedependence bound therefore holds for 𝜌𝑡 ( 𝑓 ). This completes the induction. Finally, for a fixed acceptance measurement operator 𝑀, 𝑎( 𝑓 ) = Tr(𝑀𝜌 𝑞 ( 𝑓 )) is a fixed linear combination of entries of 𝜌 𝑞 ( 𝑓 ). Thus 𝑎 is a linear combination of functions each depending on at most 2𝑞 input coordinates. For any such function ℎ, depending only on 𝑄, and any 𝑆 with |𝑆| > 2𝑞, we have 𝑆 ⊈ 𝑄. By (4), Π𝑆 ℎ = 0. Linearity of Π𝑆 now gives Π𝑆 𝑎 = 0
whenever |𝑆| > 2𝑞.
⊔ ⊓
Lemmas 1 and 2, with 𝑟 = 0 and 𝑑 = 2𝑞, yield the following Fourier interpolation result, which we use repeatedly. Theorem 1 (Fourier interpolation). Let 𝒪0 ∼ 𝜑 and 𝒪1 ∼ 1 be quantum function oracles. For every 𝑞 ≥ 0, 1/2
© ª 1 Õ 1 ® ∥Π𝑆 𝜑∥22 ® ∥𝒪0 − 𝒪1 ∥(𝑞) ≤ ∥Π≤2𝑞 (𝜑 − 1)∥2 = ® 2 2 𝑆⊆𝒳 «1≤|𝑆|≤2𝑞 ¬ 2.3
.
Character Bases over Finite Abelian Groups
We now instantiate the support decomposition of Subsection 2.1. Let 𝐺 be a finite abelian group of order 𝑁 ≥ 2, written additively, and set 𝒴 = 𝐺 and P = U𝐺 . Unless stated otherwise, all densities, expectations, inner products, and norms below are relative to the corresponding uniform measures. b denote the character group of 𝐺. A character 𝜓 : 𝐺 → C satisfies 𝜓(𝑥 + 𝑦) = 𝜓(𝑥)𝜓(𝑦) and Let 𝐺 |𝜓(𝑥)| = 1, with 𝜓−1 (𝑥) = 𝜓(𝑥). The principal character 1̂ is the constant function 1 . The characters form a canonical orthonormal basis of 𝐿2 (U𝐺 ), abbreviated to 𝐿2 (𝐺); the nonprincipal characters form b \ {1̂} and 𝐵 = 𝐺. b We refer a basis of its mean zero subspace. Thus, in Section 2.1, we may take 𝐵0 = 𝐺 to [Ter99, Bab02] for the standard background in Fourier analysis. b𝒳 , the corresponding product basis function from Section 2.1 is For 𝜒 = (𝜒𝑥 )𝑥∈𝒳 ∈ 𝐺 𝜒( 𝑓 ) ≔ Φ𝜒 ( 𝑓 ) =
Ö
𝜒𝑥 ( 𝑓 (𝑥)),
supp(𝜒) = {𝑥 ∈ 𝒳 : 𝜒𝑥 ≠ 1̂},
|𝜒| ≔ | supp(𝜒)|.
𝑥∈𝒳
For ℎ : 𝐺 𝒳 → C, define its Fourier coefficient at 𝜒 by
b ℎ(𝜒) ≔ ⟨ℎ, 𝜒⟩ = E 𝑓 ∼U𝐺𝒳 [ℎ( 𝑓 )𝜒( 𝑓 )]. Fourier inversion and Parseval’s identity give ℎ=
Õ b𝒳 𝜒∈𝐺
b ℎ(𝜒)𝜒,
∥ℎ∥22 =
Õ b𝒳 𝜒∈𝐺
|b ℎ(𝜒)|2 .
(7)
Indistinguishability of Sum of Permutations
9
The support projections from Section 2.1 become Π𝑆 ℎ =
Õ
b ℎ(𝜒)𝜒,
ℎ=𝑡 =
Õ
b ℎ(𝜒)𝜒.
|𝜒|=𝑡
supp(𝜒)=𝑆
b the diagonal subgroup of 𝐺 b𝒳 Thus ℎ =𝑡 is the level 𝑡 Fourier component. We call {(𝜓, . . . , 𝜓) : 𝜓 ∈ 𝐺} (𝒳 ) 𝒳 and write 1̂ for the principal character on 𝐺 . For ℓ > 0, Õ
|b ℎ(𝜒)|ℓ
|𝜒|=𝑡
is the ℓ -th Fourier moment of ℎ at level 𝑡. For functions ℎ 1 , ℎ2 on 𝐺 𝒳 , define their convolution by (ℎ 1 ∗ ℎ 2 )( 𝑓 ) ≔ E 𝑔∼U𝐺𝒳 [ℎ 1 (𝑔)ℎ 2 ( 𝑓 − 𝑔)]. Then ∗𝑘 (𝜒) = b ℎc ℎ(𝜒) 𝑘 .
b b ℎ 1 ∗ ℎ 2 (𝜒) = ℎ 1 (𝜒) ℎ 2 (𝜒),
Walsh masks. When 𝐺 = F2𝑛 , we identify 𝐺 with its character group through 𝜒𝑤 (𝑥) = (−1)⟨𝑤,𝑥⟩ ,
𝜒𝑢 𝜒𝑣 = 𝜒𝑢+𝑣 .
Here ⟨·, ·⟩ is the binary dot product. We call 𝑤 a mask and use the same term for tuples of masks. The principal character corresponds to 0. For a linear map 𝐿 between binary vector spaces, 𝜒𝜂 (𝐿𝑥) = 𝜒𝐿⊤ 𝜂 (𝑥), so pulling a character back through 𝐿 corresponds to applying 𝐿⊤ to its mask. 2.4
Injection Densities and Fourier Coefficients
Let Ω be a finite ambient set and let ∅ ≠ 𝐴 ⊆ Ω. Write 1𝐴 for its indicator and 𝜇𝐴 =
|Ω| 1𝐴 |𝐴|
for the density of U𝐴 relative to the ambient measure UΩ . Uniform Density on Injections. For 0 ≤ 𝑑 ≤ 𝑁, let ℐ𝑑 denote the set of injections [𝑑] → 𝐺. Its density relative to U𝐺 𝑑 is given by 𝑁𝑑 𝜇ℐ 𝑑 = 1ℐ . (𝑁)𝑑 𝑑 We also refer to this as the injection density over 𝐺 𝑑 . Fixing an ordering of 𝐺 identifies ℐ𝑁 with the set 𝒮 of permutations of 𝐺, and 𝐺 𝑁 with the complete function space 𝐺 𝐺 . In particular, 𝜇𝒮 =
𝑁𝑁 1𝒮 . 𝑁!
Restricting a uniform element of ℐ𝑑 to any 𝑡-subset 𝑆 ⊆ [𝑑] gives a uniform element of ℐ𝑡 . Indeed, each injective assignment of 𝑡 distinct outputs to 𝑆 has (𝑁 − 𝑡)𝑑−𝑡 extensions to an injection on [𝑑], and b𝑑 has support 𝑆 = {𝑖1 , . . . , 𝑖 𝑡 }, with 𝑖1 < · · · < 𝑖 𝑡 , then (𝑁)𝑑 = (𝑁)𝑡 (𝑁 − 𝑡)𝑑−𝑡 . Accordingly, if 𝜒 ∈ 𝐺
c 𝜇c ℐ𝑑 (𝜒) = 𝜇 ℐ𝑡 (𝜒 𝑖 1 , . . . , 𝜒 𝑖 𝑡 ).
(8)
Stated differently, inserting principal characters does not change the corresponding Fourier coefficient of the injection density. We also use (8) when 𝑑 = 𝑁, with 𝜇ℐ𝑁 identified with 𝜇𝒮 . Two further symmetries will be useful. Negating every output preserves the injection distribution, so its Fourier coefficients are real. Translating every output by a fixed 𝑧 ∈ 𝐺 also preserves this distribution. Consequently, 𝜇c ℐ𝑑 (𝜒) = 0
unless
𝑑 Ö 𝑖=1
𝜒𝑖 = 1̂.
10
R. Bhaumik, C. Guo, X. Guo, A. Jha
Indeed, translation multiplies the coefficient by 𝑖 𝜒𝑖 (𝑧), which must be one for every 𝑧 if the coefficient is nonzero. Since permuting the input coordinates preserves the uniform injection distribution, the fixed-support moments of the injection density depend only on the size of the support. For 1 ≤ 𝑡 ≤ 𝑁 and ℓ > 0, we write Õ ℓ Θ𝑡,ℓ B 𝜇c Λ𝑡 B max 𝜇c ℐ𝑡 (𝛼) , ℐ𝑡 (𝛼) ,
Î
b 1̂})𝑡 𝛼∈(𝐺\{
b 1̂})𝑡 𝛼∈(𝐺\{
and abbreviate Θ𝑡 B Θ𝑡,2 . Thus, Θ𝑡,ℓ is the ℓ -th Fourier moment of 𝜇ℐ𝑑 on one fixed support of size 𝑡, while Λ𝑡 is the corresponding maximum Fourier coefficient. Accordingly, for every 1 ≤ 𝑡 ≤ 𝑑 ≤ 𝑁,
Õ
ℓ
𝜇c ℐ𝑑 (𝜒) =
b𝑑 𝜒∈𝐺
𝑑 Θ𝑡,ℓ , 𝑡
Õ
and
ℓ
𝜇c ℐ𝑑 (𝜒) =
b𝑑 𝜒∈𝐺
𝑑 Õ 𝑑 𝑡=1
𝑡
Θ𝑡,ℓ ,
𝜒≠1̂(𝑑)
|𝜒|=𝑡
where the first quantity is the ℓ -th Fourier moment of 𝜇ℐ𝑑 at level 𝑡. The quantities Θ𝑡 and 𝑑𝑡 Θ𝑡 are referred to as the Fourier weights for 𝜇ℐ𝑡 and 𝜇ℐ𝑑 at level 𝑡 in [Din24], respectively. For 𝑘 ≥ 2, bounding all but two factors by the maximum gives
Θ𝑡,2𝑘 ≤ Λ2𝑘−2 Θ𝑡 . 𝑡 We shall also use Eberhard’s coefficient-merging identity [Ebe17, Section 4]. For 2 ≤ 𝑡 ≤ 𝑁 and nonprinb cipal characters 𝜒1 , . . . , 𝜒𝑡 ∈ 𝐺, 𝑡−1
𝜇c ℐ𝑡 (𝜒1 , . . . , 𝜒𝑡 ) = −
Õ 1 𝜇d ℐ𝑡−1 (𝜒1 , . . . , 𝜒 𝑖 𝜒𝑡 , . . . , 𝜒𝑡−1 ). 𝑁 −𝑡+1
(9)
𝑖=1
Condition on the first 𝑡 − 1 distinct outputs 𝑦1 , . . . , 𝑦𝑡−1 . Since 𝜒𝑡 is nonprincipal, 𝑡−1
i
h
E 𝜒𝑡 (𝑦𝑡 ) | 𝑦1 , . . . , 𝑦𝑡−1 = −
Õ 1 𝜒𝑡 (𝑦 𝑖 ). 𝑁 −𝑡+1 𝑖=1
Multiplying by 𝑡−1 𝑗=1 𝜒 𝑗 (𝑦 𝑗 ) and taking expectation over the uniform injection on the first 𝑡 −1 coordinates gives the identity.
Î
3
Sum of Independent Permutations
Given 𝑘 ≥ 2 independent uniform random permutations 𝜋1 , . . . , 𝜋 𝑘 of 𝐺, define 𝜋+𝑘 (𝑥) ≔ 𝜋1 (𝑥) + · · · + 𝜋 𝑘 (𝑥),
𝑥 ∈ 𝐺.
For 𝐺 = F2𝑛 , this is the usual 𝑘-XOR-of-permutations construction. We use 𝑘 for the number of permutations and reserve 𝑡 for a Fourier level. The density on any fixed set of 𝑑 < 𝑁 distinct inputs is 𝜑 𝑑,𝑘 = 𝜇∗𝑘 ℐ𝑑 , 𝑘 so its Fourier coefficients are 𝜇c ℐ𝑑 (𝜒) . We first record the two global estimates that will be used throughout the section, starting with Eberhard’s result for 𝑘 = 2.
Proposition 1 (Theorem 1.5 in [Ebe17]). Let 𝐺 be a finite abelian group of order 𝑁. For every 1 ≤ 𝑑 < 𝑁, 𝑑 Õ 𝑑 𝑡=1
𝑡
Θ𝑡,4 =
Õ b𝑑 \{1̂(𝑑) } 𝜒∈𝐺
|𝜇c ℐ𝑑 (𝜒)|
4
2 = ∥𝜇∗2 ℐ𝑑 − 1∥2 ≤ 𝑂
𝑑2 . 𝑁3
Proof. The inequality follows directly from [Ebe17, Theorem 1.5]. The two equalities follow from Parseval, convolution-multiplication duality, and a grouping of the characters by their Fourier level. ⊔ ⊓
Indistinguishability of Sum of Permutations
11
We next record a slight generalisation of the smoothing argument used by Dinur that isolates the only additional step needed for 𝑘 > 2.
b𝑑 \ {1̂(𝑑) }, Proposition 2. For every 1 ≤ 𝑑 < 𝑁, every 𝑘 ≥ 2, and every set Γ ⊆ 𝐺 Õ 𝜒∈Γ
where 𝜆 𝑁 ≔
2𝑘 2𝑘−4 |𝜇c ℐ𝑑 (𝜒)| ≤ 𝜆 𝑁
Õ 𝜒∈Γ
4 |𝜇c ℐ𝑑 (𝜒)| ,
(10)
𝑁 −1/2 . In particular, 2 𝑑 Õ 𝑑
𝑡
𝑡=1
Θ𝑡,2𝑘 ≤ 𝑂 𝑘
𝑑2
𝑁 2𝑘−1
.
(11)
b𝑁 . By (8), Proof. Fix 𝜒 ≠ 1̂(𝑑) , and pad it with principal characters to a character 𝜒 ′ ∈ 𝐺 c𝒮 (𝜒′ ). 𝜇c ℐ𝑑 (𝜒) = 𝜇 Since 𝑑 < 𝑁 and 𝜒 is nonprincipal, the padded tuple has both a principal and a nonprincipal coordinate, and is not diagonal. Eberhard’s non-diagonal coefficient bound [Ebe17, Proof of Theorem 1.4, p. 18], after multiplication by 𝑁 𝑁 /𝑁! to pass to densities, gives |𝜇c ℐ𝑑 (𝜒)| ≤ 𝜆 𝑁 . Hence 2𝑘 2𝑘−4 4 c |𝜇c ℐ𝑑 (𝜒)| ≤ 𝜆 𝑁 |𝜇 ℐ𝑑 (𝜒)| .
Summing over Γ proves (10). Taking all nonprincipal characters and applying Proposition 1 gives (11). ⊔ ⊓ Remark 2. The same bound also applies to the complete permutation density 𝜇𝒮 for every character b𝐺 with 1 ≤ |𝜒| < 𝑁. Indeed, if 𝑆 = supp(𝜒) and |𝑆| = 𝑡 < 𝑁, then the restriction of a uniform 𝜒 ∈ 𝐺 c𝒮 (𝜒) = 𝜇c permutation to 𝑆 is a uniform injection, and hence 𝜇 ℐ𝑡 (𝜒|𝑆 ). The next estimate controls the levels above two in both query models. The parameter 𝑚 counts the input positions over which these levels are summed: we use 𝑚 = 𝑞 for the classical case and 𝑚 = 𝑁 for the quantum case. Lemma 3. Let 𝐺 be a finite abelian group of order 𝑁 ≥ 1024. For every integer 3 ≤ 𝑇 ≤ 8𝑁/15, 𝑇 Õ 𝑁 𝑡=3
𝑡
Θ𝑡,4 <
13 , 4𝑁 2
(12)
and
−1/2 𝑁 4
.
(13)
−(𝑘−2) 𝑚 13 𝑁 3 . 𝑁 4𝑁 2 4 3
(14)
max Λ𝑡 ≤ 3≤𝑡≤𝑇
Consequently, for integers 𝑘 ≥ 2 and 𝑇 ≤ 𝑚 ≤ 𝑁, 𝑇 Õ 𝑚 𝑡=3
𝑡
Θ𝑡,2𝑘 ≤
The proof is given in Appendix B. 3.1
Refined Classical Security
The 𝑂 𝑘 (𝑞/𝑁 𝑘−1/2 ) bound for every 𝑞 < 𝑁 follows from the preceding smoothing argument. To improve the bound below the birthday threshold, we first compute the two-point distribution and then apply the moment bound to the levels above two. Lemma 4. Let 𝑥 ≠ 𝑥 ′ and let 𝐹 = 𝜋+𝑘 . The density 𝜑2,𝑘 of (𝐹(𝑥), 𝐹(𝑥 ′ )) on 𝐺2 satisfies ′
′
𝜑2,𝑘 (𝑦, 𝑦 ) − 1 = 𝜂 𝑘 𝑁 1{𝑦} (𝑦 ) − 1 ,
1 𝜂𝑘 = − 𝑁 −1
𝑘
.
If 𝜏 : 𝐺 → 𝐻 is a surjective homomorphism and |𝐻| = 𝑀, the two-point density 𝜈2,𝑘 of 𝜏𝐹 satisfies 𝜈2,𝑘 (𝑦, 𝑦 ′ ) − 1 = 𝜂 𝑘 𝑀 1{𝑦} (𝑦 ′ ) − 1 .
(15)
12
R. Bhaumik, C. Guo, X. Guo, A. Jha
Proof. For each permutation, put 𝑍 𝑖 = 𝜋 𝑖 (𝑥 ′ ) − 𝜋 𝑖 (𝑥). The variable 𝜋 𝑖 (𝑥) is uniform on 𝐺, 𝑍 𝑖 is uniform on 𝐺 \ {0}, and the two are independent. The pairs are independent across 𝑖. Hence 𝐹(𝑥) is uniform and independent of 𝑆 𝑘 = 𝑍1 + · · · + 𝑍 𝑘 , while 𝐹(𝑥 ′ ) = 𝐹(𝑥) + 𝑆 𝑘 . If 𝑝 𝑗 (𝑧) = Pr[𝑆 𝑗 = 𝑧], then convolution with the uniform distribution on 𝐺 \ {0} gives 𝑝 𝑗+1 (𝑧) =
1 − 𝑝 𝑗 (𝑧) 𝑁 −1
.
Subtracting 1/𝑁 and iterating from 𝑝 1 (0) = 0, 𝑝1 (𝑧) = 1/(𝑁 − 1) for 𝑧 ≠ 0, yields 𝑝 𝑘 (𝑧) =
1 1 + 𝜂 𝑘 1{0} (𝑧) − . 𝑁 𝑁
The claimed density identity follows from 𝜑2,𝑘 (𝑦, 𝑦 ′ ) = 𝑁 2 Pr[𝐹(𝑥) = 𝑦, 𝐹(𝑥 ′ ) = 𝑦 ′ ] = 𝑁 𝑝 𝑘 (𝑦 ′ − 𝑦). Pushing forward through 𝜏 sends uniform measure on 𝐺 to uniform measure on 𝐻, yielding (15). ⊔ ⊓ For a fixed pair {𝑥, 𝑥 ′ }, the corresponding support-two density projection therefore has ∥Π{𝑥,𝑥 ′ } 𝜑∥22 = (𝑁 − 1)|𝜂 𝑘 |2 , and its total-variation contribution is
1 1 = . |𝜂 𝑘 | 1 − 𝑁 𝑁(𝑁 − 1) 𝑘−1 Consequently, after restricting to a fixed set 𝑄 of 𝑞 inputs (by Remark 1),
s 𝑞 |𝜂 | 𝑞 𝑘 2 |Δ2 | ≤ min , (𝑁 − 1) . 𝑘−1 𝑁(𝑁 − 1) 2 2
(16)
The first estimate uses the pairwise total variation and the triangle inequality: since Π{𝑥,𝑥 ′ } 𝜑 has mean zero, |⟨Π{𝑥,𝑥 ′ } 𝑎, Π{𝑥,𝑥 ′ } 𝜑⟩| = |⟨𝑎 − 12 , Π{𝑥,𝑥 ′ } 𝜑⟩| ≤ 12 ∥Π{𝑥,𝑥 ′ } 𝜑∥1 , as in (5). The second is Cauchy-Schwarz on level two. Theorem 2. Fix 𝑘 ≥ 2, and let g : 𝐺 → 𝐺 be uniform. For every 𝑞 < 𝑁,
0, 0 ≤ 𝑞 ≤ 1, √ 𝑘 2 𝑘 𝜋+ − g (𝑞) ≤ 𝑂 𝑘 (𝑞 /𝑁 ), 2 ≤ 𝑞 ≤ 𝑁, √ 𝑂 𝑘 (𝑞/𝑁 𝑘−1/2 ), 𝑁 < 𝑞 < 𝑁. In particular, 𝜋+𝑘 − g (𝑞) ≤ 𝑂 𝑘 (𝑞/𝑁 𝑘−1/2 ) throughout 𝑞 < 𝑁. Proof. The case 𝑞 = 0 is immediate. For the global estimate with 𝑞 ≥ 1, Remark 1 reduces the analysis to a fixed set of 𝑞 inputs. The density there is 𝜑 𝑞,𝑘 = 𝜇∗𝑘 , and Proposition 1, followed by Proposition 2, ℐ𝑞 gives 𝑞 . ∥𝜑 𝑞,𝑘 − 1∥2 ≤ 𝑂 𝑘 𝑁 𝑘−1/2 The statistical-distance bound follows from (1). For √ 𝑞 ≤ 1, the advantage is zero because every one-point marginal is uniform. Assume now 2 ≤ 𝑞 ≤ 𝑁. By Remark 1, fix a set 𝑄 of 𝑞 queried inputs. Equation (3) removes level one, while (16) gives 𝑂 𝑘 (𝑞 2 /𝑁 𝑘 ) at level two. For 𝑁 ≥ 1024 and 𝑞 ≥ 3, apply (14) with 𝑚 = 𝑇 = 𝑞. Lemma 1 then bounds the remainder by 3/2 2 𝑞 𝑞 𝑂𝑘 = 𝑂𝑘 . 2𝑘−3/2 𝑁𝑘 𝑁 For 𝑞 = 2, the remainder is empty. The finitely many smaller group orders are absorbed into the implicit constant. ⊔ ⊓
Indistinguishability of Sum of Permutations
3.2
13
Quantum Security
We first state the bounds for the full range 2𝑞 < 𝑁. They combine a direct analysis of the low-support Fourier components with the simulation argument of Section 4. Theorem 3. Let 𝐺 be a finite abelian group of order 𝑁, and let g : 𝐺 → 𝐺 be uniform. For 1 ≤ 𝑞 ≤ (𝑁 − 1)/2,
|𝜋2+ ⟩ − |g⟩ (𝑞) ≤ 𝑂 min 𝑁 −1/2 ,
𝑞3 1 + 𝑁2 𝑁
.
For every fixed 𝑘 ≥ 3, |𝜋+𝑘 ⟩ − |g⟩ (𝑞) ≤ 𝑂 𝑘
𝑞3
min
𝑁𝑘
,√
1
.
𝑁 2𝑘−3
For 𝑞 = 1, the 𝑘 = 2 bound sharpens to 𝑂(𝑁 −2 ). The bounds independent of 𝑞 follow from Corollary 2. Appendix C treats level two using Zhandry’s small-range distributions and proves the query-dependent bounds, including the one-query refinement. The direct Fourier calculation also gives explicit constants. Lemma 3 applies up to support size 8𝑁/15, which allows 𝑞 ≤ 4𝑁/15 quantum queries. This extends the range 𝑞 ≤ 𝑁/4 obtained from moment estimates restricted to support size at most 𝑁/2. Corollary 1. Let 𝐺 be a finite abelian group of order 𝑁 ≥ 1024, fix 𝑘 ≥ 2, and let g : 𝐺 → 𝐺 be uniform. For 0 ≤ 𝑞 ≤ 4𝑁/15, we have
s |𝜋+𝑘 ⟩ − |g⟩ (𝑞) ≤
−(𝑘−2)
13 𝑁 𝑁 + 2𝑘−2 16𝑁 2 4 8(𝑁 − 1)
√
< 0.355
𝑁 . (𝑁 − 1) 𝑘−1
Proof. The case 𝑞 = 0 is immediate, so assume 𝑞 ≥ 1. Regrouping the complete-table Fourier coefficients by support, and using Remark 2 and Θ1 = 0, gives
Õ
c𝒮 (𝜒)| |𝜇
2𝑘
=
2𝑞 Õ 𝑁 𝑡=2
1≤|𝜒|≤2𝑞
𝑡
Θ𝑡,2𝑘 .
The exact support-two contribution is 𝑁/(2(𝑁 − 1)2𝑘−2 ), by Lemma 4. Equation (14), with 𝑚 = 𝑁 and 𝑇 = 2𝑞, bounds the remaining contribution; this remainder is zero when 𝑞 = 1. Consequently,
Õ
c𝒮 (𝜒)| |𝜇
2𝑘
−(𝑘−2)
𝑁 13 𝑁 ≤ + 2(𝑁 − 1)2𝑘−2 4𝑁 2 4
.
1≤|𝜒|≤2𝑞
Theorem 1 gives the first inequality. For the second, (𝑁 − 1)2 ≤ bound, after division by 𝑁/(𝑁 − 1)2𝑘−2 , is at most 1 13(𝑁 − 1)2 (𝑁 − 1)2 + 𝑁 8 16𝑁 3
𝑁 4 when 𝑁 ≥ 1024, so the square of the
! 𝑘−2 ≤
1 13 + < 0.3552 . 8 16 · 1024
⊔ ⊓
4
3.3
Quantum Attacks over F𝒏 2
We now take 𝐺 = F2𝑛 and 𝑁 = 2𝑛 . For distinct 𝑥, 𝑥 ′ ∈ 𝐺 and nonzero 𝜆 ∈ 𝐺, there exists a one-query quantum algorithm that returns 𝑏𝜆 (𝑥, 𝑥 ′ ) = ⟨𝜆, 𝑓 (𝑥) ⊕ 𝑓 (𝑥 ′ )⟩ with certainty. This is the usual two-point phase-query algorithm, written with an arbitrary output mask; see also Bonnetain et al. [BLNPS21]. The algorithm and its proof are given in Appendix D. Proposition 3. For every 𝑘 ≥ 2, there exists a one-query quantum algorithm that distinguishes |𝜋+𝑘 ⟩ from |g⟩ with advantage 1/(2(𝑁 − 1) 𝑘 ). Proof. Fix distinct 𝑥, 𝑥 ′ ∈ 𝐺 and nonzero 𝜆 ∈ 𝐺. The one-query algorithm computes 𝑏𝜆 (𝑥, 𝑥 ′ ). Use the ′ acceptance function 𝑎( 𝑓 ) = 12 (1+(−1)𝑏𝜆 (𝑥,𝑥 ) ), which accepts exactly when 𝑏𝜆 (𝑥, 𝑥 ′ ) = 0. This bit is uniform ′ under g. By Lemma 4, E[(−1)𝑏𝜆 (𝑥,𝑥 ) ] = (−1/(𝑁 − 1)) 𝑘 under 𝜋+𝑘 . Hence the distinguishing advantage is 1/(2(𝑁 − 1) 𝑘 ). ⊔ ⊓
14
R. Bhaumik, C. Guo, X. Guo, A. Jha
Proposition 4. For 𝑛 ≥ 2 and 𝑘 ≥ 2, there exists an 𝑁/2-query quantum algorithm that distinguishes |𝜋+𝑘 ⟩ from |g⟩ with advantage 1/2. Proof. Fix nonzero 𝜆 ∈ 𝐺 and partition 𝐺 into 𝑁/2 É disjoint pairs. Applying the one-query algorithm 𝑘 to each pair and XORing the outputs computes 𝑥∈𝐺 ⟨𝜆, É𝑓 (𝑥)⟩ using 𝑁/2 queries. For 𝑓 = 𝜋+ , this bit is zero because every permutation ranges over 𝐺 and 𝑦∈𝐺 𝑦 = 0 for 𝑛 ≥ 2. Under g, it is uniform. Accepting when it is zero gives advantage 1/2. ⊔ ⊓ For 𝐺 = F2𝑛 with 𝑛 ≥ 2, the one-query attack matches the asymptotic order of our quantum upper bound at 𝑞 = 1. The matching half-domain threshold is discussed in Section 4.
4
Quantum Security by Completion
We next use the checksum invariance property to extend quantum security to every query count below half the domain size. The argument applies more generally when any prescribed values on a fixed number of inputs have a unique completion within a given class of functions. Completing independent uniform values gives a reference function with limited independence, to which the quantum support cutoff applies. Theorem 4. Let 𝒳 be a finite set of size 𝐷, let 𝐺 be a finite abelian group, and fix 1 ≤ 𝑑 ≤ 𝐷. Let 𝒞 ⊆ 𝐺𝒳 be such that, for every 𝑆 ⊆ 𝒳 of size 𝑑, the restriction map 𝒞 −→ 𝐺 𝑆 ,
𝑓 ↦−→ 𝑓 |𝑆 ,
is a bijection. Let 𝐹 : 𝒳 → 𝐺 be a random function taking values in 𝒞 , and let g : 𝒳 → 𝐺 be uniform. For every 𝑞 with 2𝑞 ≤ 𝑑, ∥|𝐹⟩ − |g⟩∥(𝑞) ≤ ∥𝐹 − g∥(𝑑) . Proof. Fix a set 𝑆 of size 𝑑, and let 𝐸𝑆 : 𝐺 𝑆 → 𝒞 be the inverse restriction map. Then 𝐸𝑆 (𝐹|𝑆 ) = 𝐹, whereas 𝐹𝒞 ≔ 𝐸𝑆 (g|𝑆 ) is uniform on 𝒞 . The restriction hypothesis for every 𝑑-point set implies that 𝐹𝒞 is 𝑑-wise independent. Lemma 2 therefore gives (2𝑞 ≤ 𝑑),
∥|𝐹𝒞 ⟩ − |g⟩∥(𝑞) = 0
equivalently by Zhandry’s theorem [Zha12b, Theorem 3.1]. For a fixed 𝑞-query distinguisher 𝒜, let 𝑎 𝑆 (𝑇) be its acceptance probability when given the complete oracle 𝐸𝑆 (𝑇). A computationally unbounded classical distinguisher can query all points of 𝑆 and accept with probability 𝑎 𝑆 (𝑇). Its acceptance probabilities against 𝐹 and g are exactly those of 𝒜 against 𝐹 and 𝐹𝒞 . Thus ∥|𝐹⟩ − |g⟩∥𝒜 = ∥|𝐹⟩ − |𝐹𝒞 ⟩∥𝒜 ≤ ∥𝐹 − g∥(𝑑) . Taking the supremum over 𝒜 proves the claim.
⊔ ⊓
The sum of permutations construction falls in the 𝑑 = 𝐷 − 1 case. Indeed, we can use its checksum to reconstruct the final output. Corollary 2. Let 𝐺 be a finite abelian group of order 𝑁. Fix some 𝑘 ≥ 2, and 𝑞 ≤ (𝑁 − 1)/2. Let g : 𝐺 → 𝐺 denote a uniform random function. Then,
|𝜋+𝑘 ⟩ − |g⟩ (𝑞) ≤ 𝑂 𝑘 𝑁 −(𝑘−3/2) . Proof. Let 𝑐 𝑘 ≔ 𝑘
Í
𝑦∈𝐺 𝑦 and define the set
( 𝒞𝑘 ≔
) 𝐺
𝑓 ∈𝐺 :
Õ
𝑓 (𝑥) = 𝑐 𝑘 .
𝑥∈𝐺
Then, for any 𝑟 ∈ 𝐺 and 𝑆 = 𝐺 \ {𝑟}, the restriction map 𝒞 𝑘 −→ 𝐺 𝑆 ,
𝑓 ↦−→ 𝑓 |𝑆 ,
Indistinguishability of Sum of Permutations
15
is a bijection. Indeed, given any 𝑓 ′ ∈ 𝐺 𝑆 , we get a unique 𝑓 ∈ 𝒞 𝑘 defined as follows: ′ 𝑥 ≠ 𝑟, 𝑓 (𝑥),Õ 𝑓 (𝑥) ≔ 𝑐 − ′ ′ 𝑓 (𝑥 ), 𝑥 = 𝑟. 𝑘 𝑥 ′ ≠𝑟
Every realisation of 𝜋+𝑘 satisfies
Õ
𝜋+𝑘 (𝑥) = 𝑘
𝑥∈𝐺
Õ
𝑦 = 𝑐𝑘 ,
𝑦∈𝐺
and hence 𝜋+𝑘 ∈ 𝒞 𝑘 . Theorem 4 with 𝑑 = 𝑁 − 1, followed by Theorem 2 at 𝑁 − 1 classical queries, gives |𝜋+𝑘 ⟩ − |g⟩ (𝑞) ≤ 𝜋+𝑘 − g (𝑁−1) ≤ 𝑂 𝑘
𝑁 −1 . 𝑁 𝑘−1/2
This proves the claimed bound for 2𝑞 ≤ 𝑁 − 1.
⊔ ⊓
Sharp query threshold for the binary setting. When 𝐺 = F2𝑛 with 𝑛 ≥ 2, Corollary 2 and Proposition 4 meet at consecutive query counts. For every fixed 𝑘 ≥ 2, the advantage is 𝑂 𝑘 (𝑁 −(𝑘−3/2) ) for every 𝑞 ≤ 𝑁/2 − 1, while an 𝑁/2-query algorithm has advantage at least 1/2. Thus 𝑁/2 is the asymptotic constant-advantage quantum query threshold for the binary construction.
5
Linear-Output-Postprocessing Variants
Throughout this section, 𝐺 = F2𝑛 , 𝑁 = 2𝑛 , and we identify characters with Walsh masks. For a mask tuple 𝜒 ∈ 𝐺𝒳 , write 𝑟(𝜒) ≔ dim Span{𝜒𝑥 : 𝑥 ∈ 𝒳 }. For 𝐿 ∈ GL(𝑛, 2) and 𝑥 = (𝑥 1 , . . . , 𝑥 𝑑 ), write 𝐿𝑥 = (𝐿𝑥 1 , . . . , 𝐿𝑥 𝑑 ). The injection density is invariant under this diagonal action, since 𝐿 preserves pairwise distinctness. Averaging over the general linear group therefore controls the Fourier mass inside a fixed subspace. Proposition 5. Suppose 𝑓 : 𝐺 𝑑 → R is invariant under the diagonal action of GL(𝑛, 2), and let ℓ > 0. For every 𝑚-dimensional subspace 𝑊 ≤ 𝐺,
Õ
|b 𝑓 (𝜒)|ℓ ≤
𝜒∈𝑊 𝑑 𝜒≠0
|𝑊| − 1 Õ b ℓ | 𝑓 (𝜒)| . 𝑁 −1 𝑑 𝜒∈𝐺 𝜒≠0
Proof. For 𝑆 ⊆ 𝐺 𝑑 , write 𝑀ℓ (𝑆) ≔
Õ
|b 𝑓 (𝜒)|ℓ .
𝜒∈𝑆 𝜒≠0
Using the invariance of 𝑓 , we have b 𝑓 (𝐿⊤ 𝜒) = b 𝑓 (𝜒) for all 𝐿 ∈ GL(𝑛, 2). It follows that 𝑀ℓ (𝑊 𝑑 ) = ⊤ 𝑑 𝑀ℓ ((𝐿 𝑊) ). Averaging over 𝐿 ∼ UGL(𝑛,2) gives 𝑀ℓ (𝑊 𝑑 ) =
Õ
|b 𝑓 (𝜒)|ℓ Pr Span{𝜒1 , . . . , 𝜒𝑑 } ⊆ 𝐿⊤𝑊 .
𝜒∈𝐺 𝑑
𝐿
(17)
𝜒≠0
We claim that |𝑊| − 1 . (18) |𝐺| − 1 Let 𝑟 = 𝑟(𝜒). The subspace 𝐿⊤𝑊 is uniform among the 𝑚-dimensional subspaces of 𝐺. For 𝑟 ≤ 𝑚, its probability of containing a fixed 𝑟-dimensional subspace is Pr Span{𝜒1 , . . . , 𝜒𝑑 } ⊆ 𝐿⊤𝑊 ≤
𝑝 𝑛,𝑚 (𝑟) =
𝑛−𝑟 𝑟−1 𝑚 Ö 2 − 2𝑖 𝑚−𝑟 2 = , 𝑛 2𝑛 − 2 𝑖 𝑚 2 𝑖=0
(19)
and 𝑝 𝑛,𝑚 (𝑟) = 0 for 𝑟 > 𝑚. Here 2 denotes the Gaussian binomial coefficient. Since 𝑝 𝑛,𝑚 (𝑟) ≤ 𝑝 𝑛,𝑚 (1) = (|𝑊| − 1)/(𝑁 − 1) for 𝑟 ≥ 1, claim (18) follows. Substituting it in (17) proves the result. ⊔ ⊓
The same argument applies after restricting to any set of masks invariant under the diagonal action; in particular, support size and rank may be fixed simultaneously.
16
5.1
R. Bhaumik, C. Guo, X. Guo, A. Jha
Generalised and Truncated Sums of Permutations
Fix 0 ≤ 𝑚 ≤ 𝑛, let 𝐻 = F2𝑚 , 𝑀 = 2𝑚 , and let 𝜏 : 𝐺 → 𝐻 be a surjective linear map. Define 𝜏𝜋+𝑘 (𝑥) ≔ 𝜏(𝜋+𝑘 (𝑥)) = 𝜏(𝜋1 (𝑥)) + · · · + 𝜏(𝜋 𝑘 (𝑥)). Projection onto 𝑚 fixed coordinates recovers the truncated sum of permutations studied in [CKLL22]. Proposition 5 and (11) give the following improved classical indistinguishability bound for 𝜏𝜋+𝑘 . Theorem 5. Fix 𝑘 ≥ 2 and 𝑞 < 𝑁, and let g : 𝐺 → 𝐻 be uniform. Then √ ! 𝑞 𝑀 𝑘 𝜏𝜋+ − g (𝑞) ≤ 𝑂 𝑘 . 𝑁𝑘 Proof. The cases 𝑞 = 0 and 𝑀 = 1 are immediate. By Remark 1, fix a set of 𝑞 distinct inputs, and let 𝜈 𝑘 be the density of the construction on 𝐻 𝑞 . Character pullback gives ⊤ 𝑘 b 𝜈 𝑘 (𝜂) = 𝜇c ℐ 𝑞 (𝜏 𝜂) .
(20)
Since 𝜏 is surjective, 𝜏⊤ identifies 𝐻 with the subspace 𝑊 = 𝜏⊤ (𝐻) ≤ 𝐺, of size 𝑀. Parseval’s identity, Proposition 5, and (11) give
Õ
∥𝜈 𝑘 − 1∥22 =
𝜒∈𝑊 𝑞 \{0}
|𝜇c ℐ 𝑞 (𝜒)|
2𝑘
𝑞2 𝑞2 𝑀 𝑀−1 ≤ 𝑂𝑘 = 𝑂 . 𝑘 𝑁 −1 𝑁 2𝑘−1 𝑁 2𝑘
⊔ ⊓
The statistical-distance bound proves the claim. √
For 𝑘 = 2, this improves the 𝑂(𝑞 𝑞𝑀/𝑁 2 ) single-user bound of [CKLL22] by a factor 𝑞 in their common parameter range.
p
5.2
Quantum Security
The quantum bounds retain the dependence on the output size 𝑀. As in the unprojected case, we combine a bound from completion with a more precise treatment of level two. Keeping the rank of the pulled-back masks improves the bound for the remaining levels. Theorem 6. Let g : 𝐺 → 𝐻 be uniform. For 1 ≤ 𝑞 ≤ (𝑁 − 1)/2, √ 𝑀 𝑞3 + 𝑀 2 |𝜏𝜋+ ⟩ − |g⟩ (𝑞) ≤ 𝑂 min . , 𝑁 𝑁2 For every fixed 𝑘 ≥ 3, |𝜏𝜋+𝑘 ⟩ − |g⟩ (𝑞) ≤ 𝑂 𝑘
min
𝑞3 𝑁
, 𝑘
√
𝑀
𝑁 𝑘−1
(21)
.
For 𝑞 = 1, the 𝑘 = 2 bound sharpens to 𝑂(𝑁 −2 ). For 𝑀 = 1, the advantage is zero. The proof is given in Appendix C.3. We record the simulation bound and the concrete Fourier bound below. The projected checksum determines the final output from the other 𝑁 − 1 outputs, so Theorem 4 applies. Corollary 3. Let 𝐺 = F2𝑛 , 𝐻 = F2𝑚 , 𝑁 = 2𝑛 , 𝑀 = 2𝑚 , and let 𝜏 : 𝐺 → 𝐻 be surjective and linear. Fix 𝑘 ≥ 2, and let g : 𝐺 → 𝐻 be uniform. For every 𝑞 ≤ (𝑁 − 1)/2, √ 𝑀 𝑘 |𝜏𝜋+ ⟩ − |g⟩ (𝑞) ≤ 𝑂 𝑘 . 𝑁 𝑘−1 Proof. Every realisation 𝑓 = 𝜏𝜋+𝑘 satisfies 𝑥∈𝐺 𝑓 (𝑥) = 𝜏(𝑘 𝑦∈𝐺 𝑦). Any 𝑁 − 1 values determine the remaining value uniquely. Theorem 4, with output group 𝐻 and 𝑑 = 𝑁 − 1, followed by Theorem 5, gives √ (𝑁 − 1) 𝑀 𝑘 𝑘 . ⊔ ⊓ |𝜏𝜋+ ⟩ − |g⟩ (𝑞) ≤ 𝜏𝜋+ − g (𝑁−1) ≤ 𝑂 𝑘 𝑁𝑘
Í
Í
Indistinguishability of Sum of Permutations
17
For explicit constants, we restrict the Fourier mass in Corollary 1 to masks in the image of 𝜏⊤ . Corollary 4. Assume 𝑁 ≥ 1024, fix 𝑘 ≥ 2, and let g : 𝐺 → 𝐻 be uniform. For 0 ≤ 𝑞 ≤ 4𝑁/15, we have |𝜏𝜋+𝑘 ⟩ − |g⟩ (𝑞) ≤
v u t
−(𝑘−2) !
𝑁 13 𝑁 𝑀−1 + 2𝑘−2 𝑁 − 1 8(𝑁 − 1) 16𝑁 2 4
.
Proof. For the complete function table, the pullback identity (20) holds with ℐ𝑞 replaced by 𝒮. The map 𝜏⊤ preserves support. Proposition 5, restricted to levels at most 2𝑞, therefore multiplies the Fourier mass used in Corollary 1 by at most (𝑀 − 1)/(𝑁 − 1). Theorem 1 proves the claim. ⊔ ⊓
6
The Variable-Output LXoP Family
Throughout this section, 𝐺 = F2𝑛 and 𝑁 = 2𝑛 . We identify characters with Walsh masks. Iwata’s XORP[𝑤] construction [Iwa06] produces 𝑤 output blocks from 𝑤 + 1 domain-separated permutation calls. Dinur defined [Din25] the following LXoP family and proposed the admissibility condition below, leaving its general-𝑤 security analysis to future work. We use our notation for this family and give classical and quantum bounds for every fixed 𝑤. Fix 𝑤 ≥ 1, put 𝑠 = ⌈log2 (𝑤 + 1)⌉, and assume 𝑠 < 𝑛. The construction has input domain F2𝑛−𝑠 , of size 𝐷 = 𝑁/2𝑠 , and produces 𝑤 elements of 𝐺 on each input. For 𝑗 ∈ {0, . . . , 𝑤}, let 𝜄 𝑗 : F2𝑛−𝑠 −→ 𝐺,
𝜄 𝑗 (𝑥) = ⟨𝑗⟩𝑠 ∥ 𝑥,
where ⟨𝑗⟩𝑠 denotes the 𝑠-bit binary representation of 𝑗. We call 𝜎 ∈ GL(𝑛, 2) 𝑤-admissible if 𝐼 + 𝜎 𝑟 ∈ GL(𝑛, 2)
for every 1 ≤ 𝑟 ≤ 𝑤.
(22)
For 𝑤 = 1, this is the linear orthomorphism condition on 𝜎. The same condition suffices for 𝑤 = 2, since 𝐼 + 𝜎 2 = (𝐼 + 𝜎)2 over F2 . Given a uniform random permutation 𝜋 of 𝐺, define 𝜋+𝜎,𝑤 : F2𝑛−𝑠 → 𝐺 𝑤 by 𝜋+𝜎,𝑤 (𝑥) ≔ 𝜋(𝜄0 (𝑥)) + 𝜎(𝜋(𝜄 1 (𝑥))), . . . , 𝜋(𝜄 𝑤−1 (𝑥)) + 𝜎(𝜋(𝜄 𝑤 (𝑥))) .
(23)
In particular, 𝜋+𝜎,1 and 𝜋+𝜎,2 are respectively the constructions LXoP[𝜎, 𝑛] and LXoP[𝜎, 2, 𝑛] of Dinur. The condition (22) is non-vacuous for every fixed 𝑤. For example, after identifying 𝐺 with F2𝑛 , multiplication by a primitive field element gives a 𝑤-admissible linear map whenever 𝑤 < 2𝑛 − 1. The domain separators ensure that all (𝑤 + 1)𝑞 permutation inputs used by 𝑞 distinct construction inputs are distinct. Thus their outputs form a uniform injection, even though the 𝑤 output blocks at one input share permutation calls. We must account for these shared calls when bounding the Fourier moments. The resulting classical bound is as follows. Theorem 7. Fix 𝑤 ≥ 1. There exists a constant 𝑐 𝑤 > 0, depending only on 𝑤, such that the following holds. Let 𝜎 be 𝑤-admissible, let g𝑤 : F2𝑛−𝑠 → 𝐺 𝑤 be a uniform random function, and let 1 ≤ 𝑞 ≤ 𝑐 𝑤 𝐷. Then 𝜋+𝜎,𝑤 − g𝑤 (𝑞) ≤ 𝑂 𝑤
𝑞
𝑁 3/2
.
We prove the theorem using a fixed-support moment bound that will also be used for quantum queries. The full recursive calculation is given in Appendix E; here we describe the masks to which it applies. Pulling an output character back through the linear combining map gives a character on the underlying permutation outputs. Write 𝐴 = 𝜎⊤ and define 𝑇𝜎,𝑤 (𝛼 1 , . . . , 𝛼 𝑤 ) ≔ 𝛼 1 , 𝐴𝛼1 + 𝛼 2 , . . . , 𝐴𝛼 𝑤−1 + 𝛼 𝑤 , 𝐴𝛼 𝑤 ∈ 𝐺 𝑤+1 .
(24)
For example, for 𝑤 = 2 the output character (𝛼 1 , 𝛼2 ) pulls back to (𝛼 1 , 𝐴𝛼1 + 𝛼 2 , 𝐴𝛼2 ). Extending the notation, given a mask 𝛼 = (𝛼 (1) , . . . , 𝛼 (𝑞) ) ∈ (𝐺 𝑤 )𝑞 , where 𝛼 (𝑖) = (𝛼 𝑖,1 , . . . , 𝛼 𝑖,𝑤 ) ∈ 𝐺 𝑤 , we apply 𝑇𝜎,𝑤 separately to each tuple 𝛼(𝑖) and use the same notation for the resulting map: 𝑇𝜎,𝑤 (𝛼) ≔ 𝑇𝜎,𝑤 (𝛼 (1) ), . . . , 𝑇𝜎,𝑤 (𝛼 (𝑞) ) ∈ (𝐺 𝑤+1 )𝑞 .
18
R. Bhaumik, C. Guo, X. Guo, A. Jha
We distinguish between construction masks and injection masks. A construction mask 𝛼 = (𝛼 (1) , . . . , 𝛼 (𝑞) ) ∈ (𝐺 𝑤 )𝑞 assigns one tuple of labels to each construction input. Its construction level is the number of inputs for which 𝛼(𝑖) ≠ 0. Here a nonzero tuple may still have some zero entries. Its pullback 𝛽 = 𝑇𝜎,𝑤 (𝛼) ∈ (𝐺 𝑤+1 )𝑞 is an injection mask, with one label for each underlying permutation-output position. Its injection level is the number of nonzero entries of 𝛽. Writing 𝛽(𝑖) = (𝛽 𝑖,0 , . . . , 𝛽 𝑖,𝑤 ) ∈ 𝐺 𝑤+1 ,
𝛽 = (𝛽(1) , . . . , 𝛽 (𝑞) ),
we call 𝛽 (𝑖) the 𝑖-th block of the injection mask. (𝜎,𝑤) Let 𝜉𝑛,𝑞 denote the density on any fixed set of 𝑞 distinct construction inputs. Expanding each output character through the linear combining map gives
(𝜎,𝑤)
𝜉𝑛,𝑞 (𝛼) = 𝜇 ℐ(𝑤+1)𝑞 𝑇𝜎,𝑤 (𝛼) .
(25)
Indeed, ⟨𝛼, 𝜎(𝑦)⟩ = ⟨𝐴𝛼, 𝑦⟩, so the character on one block has labels (𝛼 1 , 𝐴𝛼1 + 𝛼 2 , . . . , 𝐴𝛼 𝑤 ) on the corresponding permutation outputs. Those outputs form a uniform injection. For 1 ≤ 𝑡 ≤ 𝐷, write 𝐿𝑡 ≔
Õ
Õ
(𝜎,𝑤)
|𝜉𝑛,𝑡 (𝛼)|2 =
2 |𝜇 ℐ(𝑤+1)𝑡 𝑇𝜎,𝑤 (𝛼) | .
𝛼∈(𝐺 𝑤 )𝑡
𝛼∈(𝐺 𝑤 )𝑡
𝛼(𝑖) ≠0 for all 𝑖
𝛼 (𝑖) ≠0 for all 𝑖
(26)
Thus 𝐿𝑡 is the second Fourier moment on one fixed support of 𝑡 construction inputs. The corresponding injection coefficients need not all lie at the same level, because some coordinates can vanish after applying 𝑇𝜎,𝑤 . We record the structure of the pullback before stating the moment bound. For one block, write 𝐶 𝑗 = 𝐴𝑤−𝑗 .
𝛽 = 𝑇𝜎,𝑤 (𝛼) = (𝛽0 , . . . , 𝛽 𝑤 ), By (24) 𝑤 Õ
𝐶𝑗 𝛽𝑗 =
𝑤 Õ
𝐴𝑤−𝑗 𝛽 𝑗 = 0.
(27)
𝑗=0
𝑗=0
Indeed, after substitution, each 𝛼 𝑗 occurs twice and cancels. Conversely, the original labels are recovered by 𝛼1 = 𝛽0 and 𝛼 𝑗+1 = 𝛽 𝑗 +𝐴𝛼 𝑗 for 1 ≤ 𝑗 < 𝑤. Hence 𝑇𝜎,𝑤 is injective. Since every 𝐶 𝑗 is invertible, a nonzero construction block 𝛼 (𝑖) cannot have a pullback 𝛽 (𝑖) with exactly one nonzero entry: otherwise (27) would force that entry to be zero. Hence each nonzero construction block contributes between 2 and 𝑤 + 1 nonzero entries to the injection mask. Consequently, construction level 𝑡 pulls back to injection levels between 2𝑡 and (𝑤 + 1)𝑡. To bound 𝐿𝑡 , we partition the pullbacks by their exact injection support and iterate (9). At each step we choose a coordinate in an untouched block. The block relation and 𝑤-admissibility let us recover the removed label, so distinct masks remain distinct within each branch. Each merge touches at most two blocks, allowing ⌈𝑡/2⌉ steps. Appendix E gives the recovery argument and the resulting bounds. Lemma 5. Fix 𝑤 ≥ 1 and let 𝜎 be 𝑤-admissible. The fixed-support moments satisfy 𝐿1 = 𝑂 𝑤 (𝑁 −3 ).
(28)
There is a constant 𝐶𝑤 , depending only on 𝑤, such that for 𝑡 ≥ 2 with (𝑤 + 1)𝑡 ≤ 𝑁/8, 𝑡 3/2 𝐿𝑡 ≤ 𝐶𝑤 3/2 𝑁
𝑡
.
(29)
The proof is given in Appendix E. (𝜎,𝑤)
Proof of Theorem 7. Let 𝜉𝑞 = 𝜉𝑛,𝑞 , and recall 𝐿𝑡 from (26). Each 𝐿𝑡 is the contribution of one fixed set of 𝑡 construction inputs. There are 𝑞𝑡 such supports among the 𝑞 queried inputs. Thus input symmetry and Parseval give ∥𝜉𝑞 − 1 ∥22 =
𝑞 Õ 𝑞 𝑡=1
𝑡
𝐿𝑡 .
(30)
Indistinguishability of Sum of Permutations
19
Put 𝑎 = 𝑤+1. Lemma 5 bounds level one and, whenever 𝑎𝑞 ≤ 𝑁/8, every level up to 𝑞. Using 𝑞𝑡 ≤ (𝑒 𝑞/𝑡)𝑡 , we obtain √ !𝑡 𝑞 ′ 𝑞 𝑡 𝐿𝑡 ≤ 𝐶𝑤 3/2 . 𝑡 𝑁 p √ The ratio of consecutive terms on the right is at most 𝐶𝑤′′ 𝑞 𝑞 + 1/𝑁 3/2 , where 𝐶𝑤′′ = 𝑒𝐶𝑤′ absorbs the √ factor ((𝑡 + 1)/𝑡)𝑡/2 ≤ 𝑒. Choose 𝑐 𝑤 > 0 sufficiently small so that 𝑐 𝑤 ≤ (8𝑎)−1 and √ this ratio is at most p 3/2 1/2 whenever 𝑞 ≤ 𝑐 𝑤 𝐷 ≤ 𝑐 𝑤 𝑁. Such a choice is possible since 𝑞 𝑞 + 1/𝑁 ≤ 2(𝑞/𝑁)3/2 for 𝑞 ≥ 1. The same choice ensures 𝑎𝑡 ≤ 𝑎𝑞 ≤ 𝑁/8 for every 𝑡 ≤ 𝑞. The contribution of all 𝑡 ≥ 2 in (30) is then 𝑂 𝑤 (𝑞 2 /𝑁 3 ). Together with (28),
∥𝜉𝑞 − 1 ∥22 ≤ 𝑂 𝑤
𝑞2 𝑞2 𝑞 + = 𝑂 , 𝑤 𝑁3 𝑁3 𝑁3
since 𝑞 ≥ 1. Taking square roots and using statistical distance at most one half of the 𝐿2 distance proves the result. ⊔ ⊓ 6.1
Quantum Security
The same fixed-support moments control quantum distinguishing advantage as well. We now count supports in the complete construction domain and sum only the levels up to 2𝑞, as required by Theorem 1. Corollary 5. Fix 𝑤 ≥ 1. There exists a sufficiently small constant 𝑐 𝑤 > 0, depending only on 𝑤, such that the following holds. Let 𝑠 = ⌈log2 (𝑤 + 1)⌉, let 𝜎 be 𝑤-admissible, and let g𝑤 : F2𝑛−𝑠 → 𝐺 𝑤 be uniform. For every 0 ≤ 𝑞 ≤ 𝑐 𝑤 𝐷, 1 𝜎,𝑤 . |𝜋+ ⟩ − |g𝑤 ⟩ (𝑞) ≤ 𝑂 𝑤 √ 𝑁 Proof. The case 𝑞 = 0 is immediate; assume 𝑞 ≥ 1. Let 𝐷 = 𝑁/2𝑠 be the size of the actual domain, let 𝜉 denote the density of the complete 𝜋+𝜎,𝑤 function, and let 𝐿𝑡 denote the fixed-support second Fourier moment from (26). By input symmetry,
Õ
𝐷 2 b |𝜉(𝛼)| = 𝐿𝑡 . 𝑡
|𝛼|=𝑡
By Lemma 5, 𝐿1 = 𝑂 𝑤 (𝑁 −3 ) and 𝐿𝑡 ≤ (𝐶𝑤 𝑡 3/2 /𝑁 3/2 )𝑡 when (𝑤 + 1)𝑡 ≤ 𝑁/8. Hence, for 𝑡 ≥ 2, 𝐷 𝐿𝑡 ≤ 𝐶𝑤′ 𝑡
r
𝑡 𝑁
!𝑡 C 𝐴𝑡 ,
𝐴𝑡+1 ≤ 𝐶𝑤′′ 𝐴𝑡
r
𝑡+1 . 𝑁
Shrink 𝑐 𝑤 from Theorem 7, if necessary, so that
𝑐 𝑤 ≤ min 2−𝑠−1 ,
1 1 . , 16(𝑤 + 1) 8(𝐶𝑤′′ )2
Since 𝑞 ≤ 𝑐 𝑤 𝐷 ≤ 𝑐 𝑤 𝑁, we have 2𝑞 ≤ min{𝐷, 𝑁/(8(𝑤 + 1))}, so Lemma 5 applies at every level 𝑡 ≤ 2𝑞, and the ratio is at most 1/2 for 2 ≤ 𝑡 < 2𝑞. Hence 2𝑞 Õ 𝐷 𝑡=2
𝑡
𝐿𝑡 ≤ 𝑂 𝑤 (𝐴2 ) = 𝑂 𝑤 (1/𝑁),
while the level-one contribution is 𝐷𝐿1 = 𝑂 𝑤 (𝑁 −2 ). Therefore
Õ
|b 𝜉(𝛼)|2 ≤ 𝑂 𝑤 (1/𝑁).
1≤|𝛼|≤2𝑞
The result follows from Theorem 1.
⊔ ⊓
20
R. Bhaumik, C. Guo, X. Guo, A. Jha
Concrete bounds for one- and two-block output. For 𝑤 ∈ {1, 2}, Dinur gives sharper fixed-support moments. Applying Theorem 1 to these estimates gives the following concrete bounds. The proof is given in Appendix F. Corollary 6. Let 𝑁 = 2𝑛 ≥ 210 , and let 𝜎 be 1-admissible (equivalently, 2-admissible). For a uniform function g : F2𝑛−1 → 𝐺, |𝜋+𝜎,1 ⟩ − |g⟩
r ≤ (𝑞)
1887 𝑁
(0 ≤ 𝑞 ≤ 𝑁/64).
For a uniform function g2 : F2𝑛−2 → 𝐺2 , |𝜋+𝜎,2 ⟩ − |g2 ⟩
r (𝑞)
<
37 2𝑁
(0 ≤ 𝑞 ≤ 𝑁/384).
The two constants are not comparable, as they come from different estimates: for 𝑤 = 1 we bound the level sums by a geometric series with a crude ratio, whereas for 𝑤 = 2 we evaluate the first few levels numerically and bound only the tail by a geometric series. The same numerical treatment would also reduce the constant 𝑤 = 1.
Acknowledgements The authors would like to thank Benoît Cogliati and the GAPS 2025 discussion group — Wonseok Choi, Chandranan Dhar, Ravindra Jejurikar, Jannis Leuther, Jordan Naccache, Abishanka Saha, André Schrottenloher, and Rentaro Shiba — for valuable discussions on the topic. A part of this result was conceived while A.J. was supported (in parts) by the German Research Foundation (DFG) within the framework of the Excellence Strategy of the Federal Government and the States – EXC 2092 CaSa – 390781972, and the Chair of Symmetric Cryptography at Ruhr University Bochum. This work was funded (in parts) by the German Federal Ministry of Education and Research (BMBF) under grant number 16KIS1802. The authors are responsible for the content of this publication. Responsible Disclosure of AI Usage. We used ChatGPT 6, GPT-5.6, and Google Search prompts (powered by Gemini). AI tools were primarily used as a writing aid: to polish some passages, check the language, and check consistency throughout the paper. A secondary application was in certain numerical computations appearing in some proofs, where the human authors gave precise prompts to optimise certain functions and compute the resulting bounds, much as a numerical computing tool would be used in this context. All text and all technical claims, AI-assisted or not, were ultimately reviewed and validated by the authors, and they take full responsibility for the content of this paper.
References AB12.
Bab02. BBC+ 98.
Ber97. BI99.
BIL+ 21.
BKR94.
Jean-Philippe Aumasson and Daniel J. Bernstein. Siphash: A fast short-input PRF. In Steven D. Galbraith and Mridul Nandi, editors, Progress in Cryptology - INDOCRYPT 2012, 13th International Conference on Cryptology in India, Kolkata, India, December 9-12, 2012. Proceedings, volume 7668 of Lecture Notes in Computer Science, pages 489–508. Springer, 2012. doi:10.1007/978-3-642-34931-7\_28. (cited on p. 1.) László Babai. The fourier transform and equations over finite abelian groups. Online Lecture Notes, 2002. URL: https://people.cs.uchicago.edu/~laci/reu02/fourier.pdf. (cited on p. 8.) Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. In 39th Annual Symposium on Foundations of Computer Science, FOCS 1998, Palo Alto, California, USA, November 8-11, 1998, pages 352–361. IEEE Computer Society, 1998. doi: 10.1109/SFCS.1998.743485. (cited on p. 3.) Daniel J. Bernstein. SURF: simple unpredictable random function, 1997. URL: http://cr.yp.to/ papers/surf.pdf. (cited on p. 1.) M. Bellare and R. Impagliazzo. A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion. Cryptology ePrint Archive, Paper 1999/024, 1999. URL: https://eprint.iacr.org/1999/024. (cited on p. 2.) Subhadeep Banik, Takanori Isobe, Fukang Liu, Kazuhiko Minematsu, and Kosei Sakamoto. Orthros: A low-latency PRF. IACR Trans. Symmetric Cryptol., 2021(1):37–77, 2021. doi:10.46586/TOSC.V2021.I1. 37-77. (cited on p. 1.) Mihir Bellare, Joe Kilian, and Phillip Rogaway. The Security of Cipher Block Chaining. In CRYPTO 1994, volume 839 of LNCS, pages 341–358. Springer, 1994. doi:10.1007/3-540-48658-5\_32. (cited on p. 1.)
Indistinguishability of Sum of Permutations BKR98.
21
Mihir Bellare, Ted Krovetz, and Phillip Rogaway. Luby-rackoff backwards: Increasing security by making block ciphers non-invertible. In Kaisa Nyberg, editor, Advances in Cryptology - EUROCRYPT ’98, International Conference on the Theory and Application of Cryptographic Techniques, Espoo, Finland, May 31 June 4, 1998, Proceeding, volume 1403 of Lecture Notes in Computer Science, pages 266–280. Springer, 1998. doi:10.1007/BFB0054132. (cited on pp. 1 and 2.) BLNPS21. Xavier Bonnetain, Gaetan Leurent, Maria Naya-Plasencia, and Andre Schrottenloher. Quantum linearization attacks. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2021, Part I, volume 13090 of Lecture Notes in Computer Science, pages 422–452, Cham, 2021. Springer. doi:10.1007/978-3-030-92062-3_15. (cited on pp. 13 and 31.) BN18. Srimanta Bhattacharya and Mridul Nandi. Revisiting variable output length XOR pseudorandom function. IACR Transactions on Symmetric Cryptology, 2018(1):314–335, 2018. doi:10.13154/tosc.v2018.i1. 314-335. (cited on p. 2.) Che22. Lily Chen. Recommendation for key derivation using pseudorandom functions. Special Publication 800-108r1-upd1, NIST, U.S. Department of Commerce, 2022. doi:10.6028/NIST.SP.800-108r1-upd1. (cited on p. 1.) CKLL22. 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, Advances in Cryptology ASIACRYPT 2022 - 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, December 5-9, 2022, Proceedings, Part II, volume 13792 of Lecture Notes in Computer Science, pages 682–710. Springer, 2022. doi:10.1007/978-3-031-22966-4\_23. (cited on pp. 2, 3, and 16.) CLP15. Benoît Cogliati, Rodolphe Lampe, and Jacques Patarin. The indistinguishability of the XOR of 𝑘 permutations. In Carlos Cid and Christian Rechberger, editors, Fast Software Encryption – FSE 2014, volume 8540 of Lecture Notes in Computer Science, pages 285–302, Berlin, Heidelberg, 2015. Springer. doi:10.1007/978-3-662-46706-0_15. (cited on p. 2.) CN08. Donghoon Chang and Mridul Nandi. A Short Proof of the PRP/PRF Switching Lemma. Cryptology ePrint Archive, Report 2008/078, 2008. URL: http://eprint.iacr.org/2008/078. (cited on p. 1.) CP20. Benoît Cogliati and Jacques Patarin. Mirror Theory: A simple proof of the 𝑃𝑖 ⊕𝑃 𝑗 Theorem with 𝜉max = 2. Cryptology ePrint Archive, Paper 2020/734, 2020. URL: https://eprint.iacr.org/2020/734. (cited on p. 2.) CS16. Benoît Cogliati and Yannick Seurin. EWCDM: an efficient, beyond-birthday secure, nonce-misuse resistant MAC. In Matthew Robshaw and Jonathan Katz, editors, Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I, volume 9814 of Lecture Notes in Computer Science, pages 121–149. Springer, 2016. doi:10.1007/978-3-662-53018-4\_5. (cited on p. 1.) DHT17. Wei Dai, Viet Tung Hoang, and Stefano Tessaro. Information-theoretic indistinguishability via the chisquared method. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology - CRYPTO 2017 - 37th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 20-24, 2017, Proceedings, Part III, volume 10403 of Lecture Notes in Computer Science, pages 497–523. Springer, 2017. doi:10.1007/ 978-3-319-63697-9\_17. (cited on p. 2.) Din24. Itai Dinur. Tight indistinguishability bounds for the XOR of independent random permutations by fourier analysis. In Marc Joye and Gregor Leander, editors, Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part I, volume 14651 of Lecture Notes in Computer Science, pages 33–62. Springer, 2024. doi:10.1007/978-3-031-58716-0\_2. (cited on pp. 2, 5, 10, and 24.) Din25. Itai Dinur. Combining outputs of a random permutation: New constructions and tight security bounds by fourier analysis. In Serge Fehr and Pierre-Alain Fouque, editors, Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part I, volume 15601 of Lecture Notes in Computer Science, pages 244–273. Springer, 2025. doi:10.1007/978-3-031-91107-1\_9. (cited on pp. 2, 5, 17, 31, 32, 33, and 36.) DNS22. Avijit Dutta, Mridul Nandi, and Abishanka Saha. Proof of mirror theory for 𝜉max = 2. IEEE Trans. Inf. Theory, 68(9):6218–6232, 2022. doi:10.1109/TIT.2022.3171178. (cited on p. 2.) Ebe17. Sean Eberhard. More on additive triples of bijections, 2017. URL: https://arxiv.org/abs/1704.02407, arXiv:1704.02407. (cited on pp. 2, 4, 5, 10, 11, 23, and 32.) FGL+ 24. Antonio Flórez-Gutiérrez, Lorenzo Grassi, Gregor Leander, Ferdinand Sibleyras, and Yosuke Todo. General practical cryptanalysis of the sum of round-reduced block ciphers and ZIP-AES. In Kai-Min Chung and Yu Sasaki, editors, Advances in Cryptology - ASIACRYPT 2024 - 30th International Conference on the Theory and Application of Cryptology and Information Security, Kolkata, India, December 9-13, 2024, Proceedings, Part IX, volume 15492 of Lecture Notes in Computer Science, pages 280–311. Springer, 2024. doi:10.1007/978-981-96-0947-5\_10. (cited on p. 1.) Fre77. David Freedman. A Remark on the Difference between Sampling with and without Replacement. J. American Stat. Association, 72(359):681–681, 1977. doi:10.1080/01621459.1977.10480637. (cited on p. 1.) HWKS98. Chris Hall, David A. Wagner, John Kelsey, and Bruce Schneier. Building prfs from prps. In Hugo Krawczyk, editor, Advances in Cryptology - CRYPTO ’98, 18th Annual International Cryptology Conference,
22
IMV16. Iwa06.
Luc00.
MN17a.
MN17b. MP15.
MS17.
Nan24.
O’D14. Pat08.
Pat10.
Pat13.
Pat16. Rao66.
RS06.
Ter99. Zha12a.
Zha12b.
R. Bhaumik, C. Guo, X. Guo, A. Jha Santa Barbara, California, USA, August 23-27, 1998, Proceedings, volume 1462 of Lecture Notes in Computer Science, pages 370–389. Springer, 1998. doi:10.1007/BFB0055742. (cited on p. 2.) Tetsu Iwata, Bart Mennink, and Damian Vizár. CENC is optimally secure. Cryptology ePrint Archive, Paper 2016/1087, 2016. URL: https://eprint.iacr.org/2016/1087. (cited on p. 2.) Tetsu Iwata. New blockcipher modes of operation with beyond the birthday bound security. In Matthew J. B. Robshaw, editor, Fast Software Encryption, 13th International Workshop, FSE 2006, Graz, Austria, March 15-17, 2006, Revised Selected Papers, volume 4047 of Lecture Notes in Computer Science, pages 310–327. Springer, 2006. doi:10.1007/11799313\_20. (cited on pp. 2 and 17.) Stefan Lucks. The sum of prps is a secure PRF. In Bart Preneel, editor, Advances in Cryptology EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding, volume 1807 of Lecture Notes in Computer Science, pages 470–484. Springer, 2000. doi:10.1007/3-540-45539-6\_34. (cited on p. 2.) Bart Mennink and Samuel Neves. Encrypted Davies–Meyer and its dual: Towards optimal security using mirror theory. In Jonathan Katz and Hovav Shacham, editors, Advances in Cryptology – CRYPTO 2017, Part III, volume 10403 of Lecture Notes in Computer Science, pages 556–583, Cham, 2017. Springer. doi:10.1007/978-3-319-63697-9_19. (cited on p. 1.) Bart Mennink and Samuel Neves. Optimal prfs from blockcipher designs. IACR Trans. Symmetric Cryptol., 2017(3):228–252, 2017. doi:10.13154/TOSC.V2017.I3.228-252. (cited on p. 1.) Bart Mennink and Bart Preneel. On the XOR of multiple random permutations. In Stanislaw Jarecki and Dieter Gollmann, editors, Applied Cryptography and Network Security – ACNS 2015, volume 9092 of Lecture Notes in Computer Science, pages 619–634, Cham, 2015. Springer. doi:10.1007/978-3-319-28166-7_30. (cited on p. 2.) Bart Mennink and Alan Szepieniec. XOR of PRPs in a quantum world. In Tanja Lange and Tsuyoshi Takagi, editors, Post-Quantum Cryptography – PQCrypto 2017, volume 10346 of Lecture Notes in Computer Science, pages 367–383, Cham, 2017. Springer. doi:10.1007/978-3-319-59879-6_21. (cited on p. 3.) Mridul Nandi. Improving tightness gap of GGM construction and its applications. In Sourav Mukhopadhyay and Pantelimon Stanica, editors, Progress in Cryptology - INDOCRYPT 2024 - 25th International Conference on Cryptology in India, Chennai, India, December 18-21, 2024, Proceedings, Part I, volume 15495 of Lecture Notes in Computer Science, pages 28–50. Springer, 2024. doi:10.1007/978-3-031-80308-6\_2. (cited on p. 1.) Ryan O’Donnell. Analysis of Boolean Functions. Cambridge University Press, Cambridge, 2014. doi: 10.1017/CBO9781139814782. (cited on p. 5.) Jacques Patarin. A proof of security in o(2n) for the xor of two random permutations. In Reihaneh Safavi-Naini, editor, Information Theoretic Security, Third International Conference, ICITS 2008, Calgary, Canada, August 10-13, 2008, Proceedings, volume 5155 of Lecture Notes in Computer Science, pages 232–248. Springer, 2008. doi:10.1007/978-3-540-85093-9\_22. (cited on p. 2.) Jacques Patarin. Introduction to mirror theory: Analysis of systems of linear equalities and linear non equalities for cryptography. Cryptology ePrint Archive, Paper 2010/287, 2010. URL: https://eprint. iacr.org/2010/287. (cited on p. 2.) Jacques Patarin. Generic attacks for the XOR of 𝑘 random permutations. In Michael J. Jacobson Jr., Michael E. Locasto, Payman Mohassel, and Reihaneh Safavi-Naini, editors, Applied Cryptography and Network Security – ACNS 2013, volume 7954 of Lecture Notes in Computer Science, pages 154–169, Berlin, Heidelberg, 2013. Springer. doi:10.1007/978-3-642-38980-1_10. (cited on p. 2.) Jacques Patarin. Mirror theory and cryptography. Cryptology ePrint Archive, Paper 2016/702, 2016. URL: https://eprint.iacr.org/2016/702. (cited on p. 2.) J. N. K. Rao. On the comparison of sampling with and without replacement. Revue de l’Institut International de Statistique / Review of the International Statistical Institute, 34(2):125–138, 1966. doi:10.2307/1401762. (cited on p. 1.) Phillip Rogaway and Thomas Shrimpton. A provable-security treatment of the key-wrap problem. In Serge Vaudenay, editor, Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pages 373–390. Springer, 2006. doi: 10.1007/11761679\_23. (cited on p. 1.) Audrey Terras. Fourier Analysis on Finite Groups and Applications, volume 43 of London Mathematical Society Student Texts. Cambridge University Press, 1999. doi:10.1017/CBO9780511626265. (cited on p. 8.) Mark Zhandry. How to construct quantum random functions. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 679–687. IEEE Computer Society, 2012. doi:10.1109/FOCS.2012.37. (cited on pp. 4 and 28.) Mark Zhandry. Secure identity-based encryption in the quantum random oracle model. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 758–775. Springer, 2012. doi:10.1007/978-3-642-32009-5\_44. (cited on pp. 3 and 14.)
Indistinguishability of Sum of Permutations
A
23
Injection Coefficient Estimates
The following coefficient bound is due to [Ebe17, Lemma 4.1], written in our density normalisation. Proposition 6. Let 𝐺 be a finite abelian group of order 𝑁 ≥ 2. Then, for all 1 ≤ 𝑡 ≤ ⌊𝑁/2⌋,
−1/2 Λ𝑡 ≤
𝑁 𝑡
.
Proof. From [Ebe17, Lemma 4.1],
−1/2 |1̂𝒮 (𝜒)| ≤
𝑁 𝑡
𝑁! 𝑁𝑁
(|𝜒| = 𝑡 ≤ 𝑁/2).
Multiplying by 𝑁 𝑁 /𝑁! gives the corresponding density coefficient, and (8) then gives the stated bound on Λ𝑡 . ⊔ ⊓
A.1
Small Supports
At support size one, every nonprincipal character has zero coefficient, so Θ1 = Λ1 = 0. For nonprincipal b 𝜒1 , 𝜒2 ∈ 𝐺, 𝑁(𝑁 − 1)𝜇c ℐ2 (𝜒1 , 𝜒2 ) =
Õ
𝜒1 (𝑦1 )𝜒2 (𝑦2 ) = −
𝑦1 ≠𝑦2
Õ
(𝜒1 𝜒2 )(𝑦).
𝑦∈𝐺
The unrestricted sum over 𝐺 2 is zero, since each character is nonprincipal. Subtracting the equal-output assignments gives the last equality. By character orthogonality,
( 𝜇c ℐ2 (𝜒1 , 𝜒2 ) =
−1/(𝑁 − 1), 0,
𝜒1 𝜒2 = 1̂, otherwise.
There are 𝑁 − 1 such ordered pairs, one for each choice of 𝜒1 , since 𝜒2 = 𝜒1−1 is then forced. Hence Λ2 = 1/(𝑁 − 1) and Θ2 = 1/(𝑁 − 1). For 𝑁 ≥ 3 and three nonprincipal characters, inclusion–exclusion removes the three possible pairwise equalities. The unrestricted sum and each single-pair sum vanish, since an unrestricted nonprincipal character sums to zero. The all-equal term has coefficient two, so (𝑁)3 𝜇c ℐ3 (𝜒1 , 𝜒2 , 𝜒3 ) = 2
Õ
(𝜒1 𝜒2 𝜒3 )(𝑦).
𝑦∈𝐺
Consequently,
( 𝜇c ℐ3 (𝜒1 , 𝜒2 , 𝜒3 ) =
2/((𝑁 − 1)(𝑁 − 2)), 0,
𝜒1 𝜒2 𝜒3 = 1̂, otherwise.
There are (𝑁 −1)(𝑁 −2) such ordered triples: choose 𝜒1 ≠ 1̂, then 𝜒2 ∉ {1̂, 𝜒1−1 }, and finally 𝜒3 = (𝜒1 𝜒2 )−1 . Thus 4 2 Λ3 = , Θ3 = . (𝑁 − 1)(𝑁 − 2) (𝑁 − 1)(𝑁 − 2)
B
Proof of Lemma 3
We retain the notation Θ𝑡 = Θ𝑡,2 and Λ𝑡 for the actual fixed-support moment and maximum. Throughout this appendix, 𝑁 ≥ 1024, and 3 ≤ 𝑇 ≤ 8𝑁/15. All logarithms in this appendix are natural.
24
R. Bhaumik, C. Guo, X. Guo, A. Jha
Exact second moments. Parseval gives
Õ
2 2 |𝜇c ℐ 𝑗 (𝛼)| = ∥𝜇ℐ 𝑗 ∥2 =
b𝑗 𝛼∈𝐺
𝑁𝑗 . (𝑁) 𝑗
Separating these characters by their support, and using (8), yields 𝑗 Õ 𝑗
𝑡
𝑡=0
𝑁𝑗 , (𝑁) 𝑗
Θ𝑡 =
where we take Θ0 = 1. Binomial inversion therefore gives the exact identity Θ𝑡 =
𝑡 Õ
(−1)
𝑡−𝑗
𝑗=0
𝑡 𝑁𝑗 . 𝑗 (𝑁) 𝑗
(31)
This is the expression obtained in [Din24, Proposition 20] in the binary setting. The preceding calculation also makes clear that it depends only on the cardinality 𝑁. Let 𝑉 be an auxiliary real random variable with density, relative to Lebesgue measure, 𝑣 𝑁 𝑒 −𝑣 𝑁!
𝑝𝑉 (𝑣) =
(𝑣 > 0),
𝑍=
𝑁 − 1. 𝑉
For 0 ≤ 𝑗 ≤ 𝑁, direct integration gives
" E
𝑁 𝑉
𝑗# =
𝑁 𝑗 (𝑁 − 𝑗)! 𝑁𝑗 = . 𝑁! (𝑁) 𝑗
Consequently, the binomial-inversion identity (31) gives Θ𝑡 = E[𝑍 𝑡 ]
(0 ≤ 𝑡 ≤ 𝑁).
(32)
This variable only represents the numerical moment sequence; it is not part of the oracle distribution. Its even moments allow us to interpolate between support sizes using Hölder’s inequality. We also use the generating function 𝑁𝑧 𝐹𝑁 (𝑧) = (1 − 𝑧) exp , 1−𝑧
𝑁
𝑁 Θ𝑡 𝑡
𝑡
[𝑧 ]𝐹𝑁 (𝑧) =
(0 ≤ 𝑡 ≤ 𝑁).
(33)
Indeed, substituting (31) and interchanging the finite sums yields 𝑁 Õ 𝑁 𝑡=0
𝑡
𝑡
Θ𝑡 𝑧 = (1 − 𝑧)
𝑁
𝑗 𝑁 Õ 1 𝑁𝑧 𝑗=0
𝑗! 1 − 𝑧
.
The coefficients through degree 𝑁 agree with those of 𝐹𝑁 . Moreover, 𝐹𝑁 (𝑧) = exp 𝑁
© «
∞ Õ 𝑗 − 1 𝑗ª 𝑧® 𝑗 𝑗=2 ¬
has non-negative coefficients. Hence, for every 0 < 𝜌 < 1, [𝑧 𝑡 ]𝐹𝑁 (𝑧) 𝜌𝑡 ≤ 𝐹𝑁 (𝜌), and therefore [𝑧 𝑡 ]𝐹𝑁 (𝑧) ≤ ′ 𝜌−𝑡 𝐹𝑁 (𝜌). Differentiating gives (1 − 𝑧)2 𝐹𝑁 (𝑧) = 𝑁 𝑧𝐹𝑁 (𝑧), and comparison of coefficients gives Θ𝑡+1 =
𝑡 (2Θ𝑡 + Θ𝑡−1 ) 𝑁 −𝑡
(1 ≤ 𝑡 < 𝑁),
Θ0 = 1,
Θ1 = 0.
In particular, 3(𝑁 + 6) , (𝑁 − 1)(𝑁 − 2)(𝑁 − 3) 8(5𝑁 + 12) Θ5 = , (𝑁 − 1)(𝑁 − 2)(𝑁 − 3)(𝑁 − 4) 5(3𝑁 2 + 86𝑁 + 120) Θ6 = . (𝑁 − 1)(𝑁 − 2)(𝑁 − 3)(𝑁 − 4)(𝑁 − 5)
Θ4 =
(34)
Indistinguishability of Sum of Permutations
25
Extending the maximum beyond 𝑁/2. To control the remaining levels, we use Eberhard’s coefficientb write merging identity. For 2 ≤ 𝑡 ≤ 𝑁 and nonprincipal 𝜒1 , . . . , 𝜒𝑡 ∈ 𝐺, 𝜒(𝑖) = (𝜒1 , . . . , 𝜒𝑖 𝜒𝑡 , . . . , 𝜒𝑡−1 ). Then using (9) 𝑡−1
𝜇c ℐ𝑡 (𝜒1 , . . . , 𝜒𝑡 ) = −
Õ 1 (𝑖) 𝜇d ℐ𝑡−1 (𝜒 ). 𝑁 −𝑡+1 𝑖=1
The merged coordinate 𝜒𝑖 𝜒𝑡 is either nonprincipal or principal, so the resulting character lies at level 𝑡 − 1 or 𝑡 − 2. Taking absolute values and using (8) gives Λ𝑡 ≤ Put 𝑚0 = ⌊𝑁/2⌋ and 𝐶 = which gives Λ𝑡 ≤
𝑡−1 max{Λ𝑡−1 , Λ𝑡−2 } 𝑁 −𝑡+1
(3 ≤ 𝑡 ≤ 𝑁).
(35)
𝑁 𝑚0 . We apply this recurrence for 𝑡 ≥ 𝑚0 + 1, starting from Proposition 6,
𝑁 −1/2 for 1 ≤ 𝑡 ≤ 𝑁/2. We claim that 𝑡
√ Λ𝑡 ≤
𝐶
(𝑚0 ≤ 𝑡 ≤ 𝑁).
𝑁 𝑡
(36)
At 𝑡 = 𝑚0 , this is exactly the sparse bound. At 𝑡 = 𝑚0 + 1, if 𝑁 = 2𝑚0 , the recurrence factor is one and
𝑁 𝑚0 − 1
−1/2
1 =√ 𝐶
r
𝑚0 + 1 ≤ 𝑚0
√
𝐶
𝑁 𝑚0 +1
.
If 𝑁 = 2𝑚0 + 1, the factor is 𝑚0 /(𝑚0 + 1) and 𝑚0 𝑁 𝑚0 + 1 𝑚0 − 1
−1/2
1 =√ 𝐶
p
𝑚0 (𝑚0 + 2) 1 ≤√ = 𝑚0 + 1 𝐶
√
𝐶
𝑁 𝑚0 +1
.
For 𝑡 ≥ 𝑚0 + 2, the binomial coefficients are non-increasing, so the induction step follows from 𝑡−1 1 𝑡−1 1 1 ≤ 𝑁 . = 𝑁 𝑁 −𝑡+1 𝑁 𝑡 𝑡−1
𝑡
𝑡
This proves (36) and extends the maximum bound beyond 𝑁/2. The levels up to 𝑁/2. Put 𝐿 = 2⌊𝑁/4⌋, so 𝐿 is even and is either 𝑚0 or 𝑚0 − 1. Since the largest binomial coefficient is at least 2𝑁 /(𝑁 + 1), 𝑁 2𝑁 ≥ . 𝐿 2(𝑁 + 1) Using (33) at 𝑧 = 2/5 therefore gives 𝑁
Θ𝐿 ≤ 2(𝑁 + 1)𝛽 ,
3 2/3 𝛽= 𝑒 10
r
5 < 𝑒 −1/13 . 2
Also, Θ6 ≥ 15/𝑁 3 by (34). For 𝑁 ≥ 1024, Θ𝐿 ≤ 2(𝑁 + 1)𝑒 −𝑁/13 ≤
15 −(𝐿−6)/10 𝑒 ≤ Θ6 𝑒 −(𝐿−6)/10 . 𝑁3
(37)
For the middle inequality, it suffices, using 𝐿 ≤ 𝑁/2, to check
2(𝑁 + 1)𝑁 3 7𝑁 3 − log + > 0. 260 15 5 The left-hand side is greater than 2.45727 at 𝑁 = 1024, and its derivative is 7/260 − 1/(𝑁 + 1) − 3/𝑁 > 0 in the required range.
26
R. Bhaumik, C. Guo, X. Guo, A. Jha
Both 6 and 𝐿 are even. Hölder’s inequality applied to (32), followed by (37), gives, for 6 ≤ 𝑡 ≤ 𝐿, Θ𝑡 ≤ E[|𝑍|𝑡 ] ≤ Θ6
(𝐿−𝑡)/(𝐿−6)
(𝑡−6)/(𝐿−6)
Θ𝐿
≤ Θ6 𝑒 −(𝑡−6)/10 .
Hence 𝐿 Õ
Θ𝑡 ≤ Θ4 + Θ5 +
𝑡=4
Θ6 < Θ4 + Θ5 + 11Θ6 . 1 − 𝑒 −1/10
(38)
For 4 ≤ 𝑡 ≤ 𝐿, the sparse maximum gives 𝑁 𝑁 2 Θ𝑡,4 ≤ Λ𝑡 Θ𝑡 ≤ Θ𝑡 . 𝑡 𝑡
The support-three contribution is given exactly by Appendix A: 𝑁 8𝑁 Θ3,4 = . 3 3(𝑁 − 1)2 (𝑁 − 2)2
The remaining levels. For 𝐿 < 𝑡 ≤ 𝑇, we have 𝑡 ≥ 𝑚0 . Using (36) and then (33) at 𝑧 = 2/5,
𝑁
2𝑁 3 𝑁 𝐶 Θ𝑡,4 ≤ 𝑁 Θ𝑡 ≤ 2 𝑁 5 𝑡
𝑡
𝑒
𝑡 2𝑁/3
5 2
.
𝑡
For 𝑥 = 𝑡/𝑁, put ℎ(𝑥) = −𝑥 log 𝑥 − (1 − 𝑥) log(1 − 𝑥). The binomial probability with parameters 𝑁 , 𝑥 is largest at 𝑡, and is at least 1/(𝑁 + 1) there. Thus 𝑁 𝑒 𝑁 ℎ(𝑥) . ≥ 𝑡 𝑁 +1
It follows that 𝑁 Θ𝑡,4 ≤ (𝑁 + 1)2 𝑒 𝑁 𝐽(𝑥) , 𝑡
𝐽(𝑥) = log
5 6 2 + + 𝑥 log − 2ℎ(𝑥). 5 3 2
Here 𝑥 ≥ 𝑚0 /𝑁 > 0.49, and 𝐽 ′ (𝑥) = log(5/2) − 2 log((1 − 𝑥)/𝑥) > 0 throughout the required interval. A direct evaluation gives 1 𝐽(8/15) < −0.04417000 < − . 23 There are fewer than 𝑁 remaining levels, so
Õ 𝑁 𝐿<𝑡≤𝑇
𝑡
Θ𝑡,4 ≤ 𝑁(𝑁 + 1)2 𝑒 −𝑁/23 .
(39)
This also covers the possible odd level just below 𝑁/2. Combining (38), (39), and the support-three contribution gives 𝑇 Õ 𝑁 𝑡=3
𝑡
Θ𝑡,4 <
8𝑁 + Θ4 + Θ5 + 11Θ6 + 𝑁(𝑁 + 1)2 𝑒 −𝑁/23 . 3(𝑁 − 1)2 (𝑁 − 2)2
(40)
After multiplication by 𝑁 2 , each rational term decreases with 𝑁: write it as a polynomial with nonnegative coefficients in 1/𝑁, divided by products of 1 − 𝑖/𝑁. The exponential term decreases as well, since 𝑑 3 2 1 log 𝑁 3 (𝑁 + 1)2 𝑒 −𝑁/23 = + − < 0. 𝑑𝑁 𝑁 𝑁 + 1 23 At 𝑁 = 1024, the normalised right-hand side of (40) is less than 3.245641 < 13/4. This proves (12).
Indistinguishability of Sum of Permutations
27
A common maximum for all these levels. At support three, 𝑁(𝑁 − 3) 𝑁 < 1. = 4 6(𝑁 − 1)(𝑁 − 2)
Λ23 For 4 ≤ 𝑡 ≤ 𝑚0 , we have
−1/2 Λ𝑡 ≤
𝑁 𝑡
−1/2 ≤
𝑁 4
.
For 𝑚0 < 𝑡 ≤ 8𝑁/15, the entropy estimate and (36) give
Λ𝑡 ≤ (𝑁 + 1) exp 𝑁
1 log 2 − ℎ(𝑡/𝑁) 2
≤ (𝑁 + 1)𝑒 −𝑁/3 < 𝑁 −2 <
−1/2 𝑁 4
.
Indeed, ℎ(8/15) − 12 log 2 > 1/3, and (𝑁 + 1)𝑒 −𝑁/3 < 𝑁 −2 holds at 𝑁 = 1024 and persists since 2/𝑁 + 1/(𝑁 + 1) − 1/3 < 0. This proves (13). Now let 𝑚 be any integer with 𝑇 ≤ 𝑚 ≤ 𝑁. For 3 ≤ 𝑡 ≤ 𝑇 ≤ 𝑚 ≤ 𝑁, the ratio 𝑚𝑡 / 𝑁𝑡 is at most 𝑚 𝑁 2𝑘−4 Θ𝑡,4 . Thus the two estimates just proved give 3 / 3 . Also, Θ𝑡,2𝑘 ≤ Λ𝑡 𝑇 Õ 𝑚 𝑡=3
𝑡
Θ𝑡,2𝑘 ≤
𝑇 𝑚 −(𝑘−2) Õ 𝑁 𝑁 3 Θ𝑡,4 ≤ 𝑁 4 𝑡 𝑡=3 3
−(𝑘−2) 𝑚 13 𝑁 3 . 𝑁 4𝑁 2 4 3 ⊔ ⊓
This proves (14).
C
Query-dependent Quantum Bounds for Sums of Permutations
Let 𝐹 : 𝒳 → 𝐻 have density 𝜑 and uniform one-point marginals, and let g : 𝒳 → 𝐻 be uniform. For a 𝑞-query quantum distinguisher 𝒜 with acceptance function 𝑎, Lemmas 1 and 2, with 𝑟 = 2, give 1 ∥|𝐹⟩ − |g⟩∥𝒜 ≤ |E[𝑎𝜑=2 ]| + ∥𝑅 𝑞 ∥2 , 2
𝑅𝑞 =
2𝑞 Õ
𝜑=𝑡 ,
(41)
𝑡=3
for 𝑞 ≥ 1. We apply this bound to the unprojected and projected sums. Their level-two components follow from Lemma 4; the common injection estimate (14) controls the higher levels.
C.1
A Bound for the Centred Collision Count
We first bound the correlation of a quantum acceptance function with the centred collision count. We state it for an arbitrary finite input set and a finite abelian output group, so that it also applies to truncation. Lemma 6. Let 𝒳 be a finite set, let 𝐻 be a finite abelian group of order 𝑀, and define, for 𝑓 : 𝒳 → 𝐻, 𝐾𝐻 ( 𝑓 ) ≔
Õ
𝑀 1{ 𝑓 (𝑥)= 𝑓 (𝑦)} − 1 ,
{𝑥,𝑦}⊆𝒳
where the sum is over unordered pairs of distinct inputs, and the expectation below is with respect to U𝐻 𝒳 . If 𝑎 is the acceptance probability of a 𝑞-query quantum algorithm, then |EU [𝑎𝐾 𝐻 ]| ≤
𝜋2 (2𝑞 − 1)3 = 𝑂(𝑞 3 ) 6
(𝑞 ≥ 1).
For 𝑞 = 0, the expectation is zero. The implicit constant is independent of 𝒳 and 𝐻. Notice that 𝐾 𝐻 has mean zero.
28
R. Bhaumik, C. Guo, X. Guo, A. Jha
Proof. If 𝑞 = 0, 𝑀 = 1, or |𝒳 | < 2, the claim follows from E[𝐾 𝐻 ] = 0 or 𝐾 𝐻 = 0. Assume otherwise. For a positive integer 𝑟, sample independent uniform random functions 𝑏 : 𝒳 → [𝑟] and 𝑐 : [𝑟] → 𝐻, and set 𝐹𝑟 = 𝑐 ◦ 𝑏. For 𝑧 = 1/𝑟, let 𝑝(𝑧) = E[𝑎(𝐹𝑟 )]. We first make the small-range bound concrete. By Lemma 2, the Fourier expansion of 𝑎 uses supports of size at most 2𝑞. On a support of size 𝑠 ≥ 1, the labels assigned by 𝑏 induce a partition. A fixed partition with 𝑗 ≥ 1 blocks has probability (𝑟) 𝑗 𝑟𝑠
=𝑧
𝑠−𝑗
𝑗−1 Ö
(1 − 𝑖𝑧),
𝑖=0
which has degree at most 𝑠 − 1, since the factor at 𝑖 = 0 is one. The conditional character expectation depends on the partition but not on 𝑟. Thus 𝑝 is a polynomial of degree at most 2𝑞 − 1, with 𝑝(0) = EU [𝑎] and 0 ≤ 𝑝(1/𝑟) ≤ 1 for every positive integer 𝑟. Its coefficients are real, since its values at these real points are real. Zhandry’s polynomial bound [Zha12a, Theorem B.1, with Δ = 1] yields |E[𝑎(𝐹𝑟 )] − EU [𝑎]| ≤
𝑞3 𝜋2 (2𝑞 − 1)3 ≤ 𝐶SR , 6𝑟 𝑟
4𝜋2 . 3
𝐶SR =
(42)
Here the support cutoff applies directly to the addition oracle on 𝐻. Let 𝐷 = |𝒳 |, and let 𝜚 𝑟 be the density of 𝐹𝑟 on 𝐻 𝒳 . As 𝑟 → ∞, the probability that 𝑏 is injective is 𝐷
(𝑟)𝐷 = 1 − 2 + 𝑂 𝐷 (𝑟 −2 ). 𝑟 𝑟𝐷 For each fixed pair {𝑥, 𝑦}, the probability that this is the only collision of 𝑏 is (𝑟)𝐷−1 1 = + 𝑂 𝐷 (𝑟 −2 ). 𝐷 𝑟 𝑟 Conditioned on the first event, the values of 𝑐 at the distinct labels chosen by 𝑏 are independent and uniform, so 𝐹𝑟 is a uniform random function. Conditioned on the second event, the outputs at 𝑥 and 𝑦 are equal, and all other outputs remain independent and uniform. The density of this distribution is 𝑀 1{ 𝑓 (𝑥)= 𝑓 (𝑦)} . All other collision patterns have total probability 𝑂 𝐷 (𝑟 −2 ). Consequently, 𝜚𝑟 = 1 +
𝐾𝐻 + 𝑂 𝐷,𝑀 (𝑟 −2 ), 𝑟
where the error is uniform on the finite space 𝐻 𝒳 , with 𝒳 and 𝐻 fixed. Thus, lim 𝑟 (E[𝑎(𝐹𝑟 )] − EU [𝑎]) = EU [𝑎𝐾 𝐻 ].
𝑟→∞
Multiplying (42) by 𝑟 and taking the limit proves the claim. The limit is taken with 𝒳 , 𝐻 and the algorithm fixed. Although the vanishing error can depend on 𝐷, 𝑀, the surviving constant 𝐶SR does not. ⊔ ⊓ C.2
Proof of Theorem 3
Fix 𝑘 ≥ 2, and let 𝜑 𝑘 = 𝜇∗𝑘 be the density of the complete table of 𝜋+𝑘 . Its one-point marginals are uniform. 𝒮 Since the two-point marginals determine the level-two projection, Lemma 4 gives
1 𝜂𝑘 = − 𝑁 −1
ℎ2,𝑘 ≔ (𝜑 𝑘 )=2 = 𝜂 𝑘 𝐾 𝐺 ,
𝑘
.
(43)
Thus Lemma 6 implies, for every 𝑞-query acceptance function 𝑎, |E[𝑎 ℎ2,𝑘 ]| ≤
𝜋2 (2𝑞 − 1)3 6(𝑁 − 1) 𝑘
.
For 𝑞 = 1, there is no remainder, proving √ the one-query bounds. Suppose 𝑁 ≥ 1024 and 2 ≤ 𝑞 ≤ 𝑁. By Parseval’s identity, convolution-multiplication duality, and (14) with 𝑚 = 𝑁 and 𝑇 = 2𝑞, ∥𝑅 𝑞,𝑘 ∥22 =
2𝑞 Õ 𝑁 𝑡=3
−(𝑘−2)
13 𝑁 Θ𝑡,2𝑘 ≤ 𝑡 4𝑁 2 4
,
𝑅 𝑞,𝑘 =
2𝑞 Õ
(𝜑 𝑘 )=𝑡 .
𝑡=3
Indistinguishability of Sum of Permutations
29
The remainder in (41) is therefore 𝑂 𝑘 (𝑁 −2𝑘+3 ). For 𝑘 = 2, this gives 𝑂(𝑞 3 /𝑁 2 + 1/𝑁); for 𝑘 ≥ 3, it gives 𝑂 𝑘 (𝑞 3 /𝑁 𝑘 ). The finitely many orders 𝑁 < 1024 are absorbed into the implicit constants. √ Corollary 2 gives the uniform bound 𝑂 𝑘 (𝑁 −(𝑘−3/2) ) throughout 2𝑞 < 𝑁. For 𝑞 > 𝑁, this is no larger than 𝑞 3 /𝑁 𝑘 . Combining the local and uniform bounds proves the theorem. ⊔ ⊓ Keeping the constants in the preceding calculation gives the following bound for 𝑞 < 4𝑁/15. Corollary 7. Let 𝐺 be a finite abelian group of order 𝑁 ≥ 1024, fix 𝑘 ≥ 2, and let g : 𝐺 → 𝐺 be uniform. For 2 ≤ 𝑞 ≤ 4𝑁/15,
(s |𝜋+𝑘 ⟩ − |g⟩ (𝑞) ≤ min
−(𝑘−2)
𝑁 13 𝑁 , + 2𝑘−2 16𝑁 2 4 8(𝑁 − 1) √ −(𝑘−2)/2 ) 𝜋2 (2𝑞 − 1)3 13 𝑁 + . 𝑘 4𝑁 4 6(𝑁 − 1)
(44)
For 𝑞 = 1, the advantage is at most 𝜋2 /(6(𝑁 − 1) 𝑘 ); for 𝑞 = 0, it is zero. Proof. The first bound is Corollary 1. For the second, the two-input identity (43), which also holds for 𝑘 = 2, and Lemma 6 give 𝜋2 (2𝑞 − 1)3 . |EU [𝑎 ℎ 2,𝑘 ]| ≤ 6(𝑁 − 1) 𝑘 For the remaining levels, (14) gives ∥𝑅 𝑞,𝑘 ∥22 =
−(𝑘−2)
2𝑞 Õ 𝑁 𝑡=3
13 𝑁 Θ𝑡,2𝑘 ≤ 𝑡 4𝑁 2 4
.
Apply (41), retaining its factor 1/2 on the remainder. For 𝑞 = 1, the remainder is empty, and for 𝑞 = 0 the oracles are not queried. ⊔ ⊓ C.3
Proof of Theorem 6
The same decomposition gives a bound that retains the output-size dependence for the construction from Section 5.1. The additional observation is that the proof of Proposition 5 retains the rank of the span of the character coordinates. Keeping this rank information gives a finer estimate on the remainder than applying the proposition directly. Throughout this subsection, take 𝐺 = F2𝑛 , 𝐻 = F2𝑚 , 𝑁 = 2𝑛 , and 𝑀 = 2𝑚 , with 0 ≤ 𝑚 ≤ 𝑛. Let 𝜏 : 𝐺 → 𝐻 be surjective and linear. Two permutations. For 𝑀 = 1, both oracles are the unique function into the trivial group. Assume 𝑀 ≥ 2. As before, the finitely many orders 𝑁 < 1024 can be absorbed into the asymptotic constant. Fix a 𝑞-query distinguisher 𝒜 with acceptance probability 𝑎. Let 𝜈 be the density of 𝜏𝜋2+ on 𝐻 𝐺 , and set 𝑊 = 𝜏⊤ (𝐻). As in the proof of Theorem 5, b c𝒮 (𝜏⊤ 𝜂)2 . 𝜈 (𝜂) = 𝜇 (45) Here 𝜏⊤ acts coordinatewise and is injective, so it preserves support size. Write Π≤2𝑞 (𝜈 − 1 ) = ℎ 2 + 𝑅 𝑞 ,
ℎ2 = 𝜈=2 ,
𝑅𝑞 =
2𝑞 Õ
𝜈=𝑡 .
𝑡=3
The pushforward identity (15) gives ℎ2 ( 𝑓 ) =
𝐾𝐻 ( 𝑓 ) , (𝑁 − 1)2
|EU [𝑎 ℎ 2 ]| ≤ 𝑂(𝑞 3 /𝑁 2 ),
where the second inequality follows √ from Lemma 6. For 𝑞 = 1, 𝑅 𝑞 = 0. For 2 ≤ 𝑞 ≤ 𝑁, Parseval and (45) give ∥𝑅 𝑞 ∥22 =
Õ 𝜒∈𝑊 𝐺 3≤|𝜒|≤2𝑞
c𝒮 (𝜒)|4 . |𝜇
(46)
30
R. Bhaumik, C. Guo, X. Guo, A. Jha
The subspace-averaging identity (17), restricted to the support levels in (46), gives
Õ
∥𝑅 𝑞 ∥22 =
c𝒮 (𝜒)|4 . 𝑝 𝑛,𝑚 (𝑟(𝜒))|𝜇
(47)
3≤|𝜒|≤2𝑞
Here 𝑝 𝑛,𝑚 is the same probability function as in (19). The restriction to these levels is allowed because the diagonal action of GL(𝑛, 2) preserves support size. In particular, 𝑝 𝑛,𝑚 (1) =
𝑀−1 , 𝑁 −1
(𝑀 − 1)(𝑀 − 2) (𝑁 − 1)(𝑁 − 2)
𝑝 𝑛,𝑚 (𝑟) ≤ 𝑝 𝑛,𝑚 (2) =
(𝑟 ≥ 2).
A rank-one tuple over F2 has the same nonzero character at every position in its support. Its permutation coefficient vanishes when the support size is odd, by translating all outputs by a vector on which this character takes value −1. There are (𝑁 − 1) 𝑁𝑡 rank-one tuples of support size 𝑡. For √ −1/2 . Thus, 4 ≤ 𝑡 ≤ 2𝑞 ≤ 2 𝑁 < 𝑁/2, Proposition 6 gives Λ𝑡 ≤ 𝑁𝑡
Õ
c𝒮 (𝜒)| ≤ (𝑁 − 1) |𝜇 4
3≤|𝜒|≤2𝑞 𝑟(𝜒)=1
2𝑞 −1 Õ 𝑁
𝑡
𝑡=4
(48)
= 𝑂(𝑁 −3 ). √ −1 For the last step, the successive ratio of 𝑁𝑡 is (𝑡 + 1)/(𝑁 − 𝑡) = 𝑂(𝑁 −1/2 ) throughout 4 ≤ 𝑡 < 2𝑞 ≤ 2 𝑁. Here 𝑁 ≥ 1024 suffices. Applying (48) to the rank-one part of (47), and (14), with 𝑘 = 2 and 𝑚 = 𝑁, to the remaining part, gives ∥𝑅 𝑞 ∥22 ≤ 𝑝 𝑛,𝑚 (1)𝑂(𝑁 −3 ) + 𝑝 𝑛,𝑚 (2)𝑂(𝑁 −2 ) ≤𝑂
𝑀 𝑀2 + 4 = 𝑂(𝑀 2 /𝑁 4 ). 4 𝑁 𝑁
Hence ∥𝑅 𝑞 ∥2 = 𝑂(𝑀/𝑁 2 ). Now, (41) yields |𝜏𝜋2+ ⟩ − |g⟩ (𝑞) ≤ 𝑂
𝑞 +𝑀 𝑁2
3
√
(𝑞 ≤
𝑁).
(49)
Again, 𝑅 𝑞 = 0 for 𝑞 = 1. Finally, Corollary 3 with 𝑘 = 2 gives √ |𝜏𝜋2+ ⟩ − |g⟩ (𝑞) ≤ 𝑂( 𝑀/𝑁)
(2𝑞 < 𝑁).
√ Combining this with (49) proves (21). For 𝑞 > 𝑁, the minimum selects the uniform bound, since √ 3 2 −1/2 𝑞 /𝑁 > 𝑁 ≥ 𝑀/𝑁. √ 3 2 For 𝑀 1/3 ≤ 𝑞 ≤ 𝑁, the local √ bound (49) is 𝑂(𝑞 /𝑁 ). In particular, for a fixed-size output group, this holds throughout 1 ≤ 𝑞 ≤ 𝑁, with the implicit constant allowed to depend on that fixed size. The improvement from 1/𝑁 to 𝑀/𝑁 2 in the remainder is a consequence of separating rank-one characters from the characters of rank at least two. Three or more permutations. The case 𝑀 = 1 is immediate, and the finitely many orders 𝑁 < 1024 can be absorbed into the constant depending on 𝑘. Fix a √ 𝑞-query distinguisher 𝒜 with acceptance probability 𝑘 𝐺 𝑎, and let 𝜈 𝑘 be the density of 𝜏𝜋+ on 𝐻 . For 𝑞 ≤ 𝑁, split its low-support part into ℎ 2,𝑘 + 𝑅 𝑞,𝑘 . By (15), ℎ2,𝑘 ( 𝑓 ) =
(−1) 𝑘 𝐾 𝐻 ( 𝑓 ), (𝑁 − 1) 𝑘
and hence Lemma 6 gives a contribution 𝑂 𝑘 (𝑞 3 /𝑁 𝑘 ).
Indistinguishability of Sum of Permutations
31
If 𝑞 = 1, the remainder is zero. Otherwise, the pullback formula (45) and the convolution identity show that each coefficient of the 𝑘-sum is the corresponding coefficient of the two-sum multiplied by c𝒮 (𝜒) 𝑘−2 . As above, Lemma 3 gives 𝜇
c𝒮 (𝜒)| ≤ max |𝜇
3≤|𝜒|≤2𝑞
−1/2 𝑁 4
√
= 𝑂(𝑁 −2 )
(𝑞 ≤
𝑁).
Together with the estimate ∥𝑅 𝑞,2 ∥2 = 𝑂(𝑀/𝑁 2 ) proved above, this gives ∥𝑅 𝑞,𝑘 ∥2 ≤ 𝑂 𝑘 (𝑁
−2𝑘+4
𝑀 𝑀 . ) 2 = 𝑂𝑘 𝑁 𝑁 2𝑘−2
Since 𝑀 ≤ 𝑁 and 𝑘 ≥ 3, this√is at most 𝑂 𝑘 (𝑁 −𝑘 ), and therefore at most 𝑂 𝑘 (𝑞 3 /𝑁 𝑘 ). This proves the √ local √ 3 𝑘 𝑘−1 bound 𝑂 𝑘 (𝑞 /𝑁 ) for 𝑞 ≤ 𝑁. Corollary 3 gives the uniform bound 𝑂 𝑘 ( 𝑀/𝑁 ). For 𝑞 > 𝑁, the uniform bound is no larger than 𝑁 −(𝑘−3/2) < 𝑞 3 /𝑁 𝑘 , and the result follows. ⊔ ⊓ Remark 3. The query-dependent refinement uses the exact centred-collision form of the support-two component for sums of independent permutations. For LXoP this component has a different linear structure, so the same refinement does not follow from the preceding argument.
D
A Deutsch-Type One-Query Algorithm
We give the standard two-point phase-query algorithm with an arbitrary nonzero output mask; see also Bonnetain et al. [BLNPS21]. Let 𝐺 = F2𝑛 and let 𝑈 𝑓 |𝑢⟩𝑋 |𝑣⟩𝑌 = |𝑢⟩𝑋 |𝑣 ⊕ 𝑓 (𝑢)⟩𝑌 be the standard quantum oracle. For distinct 𝑥, 𝑥 ′ ∈ 𝐺 and nonzero 𝜆 ∈ 𝐺, there exists a one-query quantum algorithm that returns 𝑏𝜆 (𝑥, 𝑥 ′ ) = ⟨𝜆, 𝑓 (𝑥) ⊕ 𝑓 (𝑥 ′ )⟩ with certainty. The algorithm uses a one-qubit register 𝐵 and two 𝑛-qubit registers 𝑋 and 𝑌. Algorithm. 1. Prepare |0⟩𝐵 |0𝑛 ⟩𝑋 |𝜆⟩𝑌 . 2. Apply 𝐻 to 𝐵 and 𝐻 ⊗𝑛 to 𝑌. 3. XOR 𝑥 into 𝑋 if 𝐵 = 0, and XOR 𝑥 ′ into 𝑋 if 𝐵 = 1. 4. Apply 𝑈 𝑓 once to 𝑋 and 𝑌. 5. Undo Step 3. 6. Apply 𝐻 to 𝐵, measure it, and return the outcome.
Adding 𝑧 ∈ 𝐺 to 𝐻 ⊗𝑛 |𝜆⟩ contributes the phase (−1)⟨𝜆,𝑧⟩ . Hence, after the oracle query and Step 5, register 𝐵 is in the state (−1)⟨𝜆, 𝑓 (𝑥)⟩ |0⟩ + (−1)⟨𝜆, 𝑓 (𝑥 )⟩ |1⟩ √ 2 ′
⟨𝜆, 𝑓 (𝑥)⟩ |0⟩ + (−1)
= (−1)
𝑏𝜆 (𝑥,𝑥 ′ ) |1⟩
√ 2
= (−1)⟨𝜆, 𝑓 (𝑥)⟩ 𝐻 |𝑏𝜆 (𝑥, 𝑥 ′ )⟩ .
Since 𝐻 2 = 𝐼, the final Hadamard transform leaves 𝐵 in |𝑏𝜆 (𝑥, 𝑥 ′ )⟩ up to a global phase. Measuring 𝐵 returns the required value with certainty. Only Step 4 queries 𝑈 𝑓 . ⊔ ⊓
E
The Recursive Moment Argument for LXoP
Throughout this appendix, 𝐺 = F2𝑛 and 𝑁 = 2𝑛 . We prove Lemma 5. The argument follows Dinur’s recursive moment bound [Din25], beginning with (9) and keeping track of a family of masks when bounding its second Fourier moment. We first prove the following more precise estimate for 𝑡 ≥ 2.
32
R. Bhaumik, C. Guo, X. Guo, A. Jha
Proposition 7. Fix 𝑤 ≥ 1, let 𝜎 be 𝑤-admissible, and let 𝑡 ≥ 2 satisfy (𝑤 + 1)𝑡 ≤ 𝑁/8. Put 𝑑𝑡 = ⌈𝑡/2⌉. Then 𝐿𝑡 ≤ 2
𝑑𝑡 +(𝑤+1)𝑡
(𝑤 + 1)𝑡 𝑁 − (𝑤 + 1)𝑡
𝑡+𝑑𝑡
.
(50)
We use Dinur’s fixed-support second-moment estimate [Din25, Lemma 2], 𝑘 Θ𝑘 ≤ 𝑁−𝑘
E.1
𝑘/2
,
1 ≤ 𝑘 ≤ 𝑁/2.
(51)
From Coefficient Merging to the Moment Bound
Let 𝑆 be a finite set and 𝑇 : 𝑆 → 𝐺 𝑟 , with 1 ≤ 𝑟 ≤ 𝑁, be injective. Suppose the masks 𝑇(𝛼) have the same support, of size 𝑘 0 , and fix an integer 𝑑 ≥ 0 with 2𝑑 < 𝑘0 ≤ 𝑁/8. At each nonempty internal node, the primary coordinate is chosen from the common support using only the initial data and the previous merge indices and zero/nonzero outcomes. We assume that, for every secondary choice and each nonempty outcome, the removed entry is uniquely determined by the child mask and these known indices and outcomes. We derive the bound under this assumption, and verify it for the LXoP family in Appendix E.2. A current mask is a tuple 𝛽 ∈ 𝐺 𝑟 . For distinct indices 𝑗, 𝑖 in its support, define the merged mask by ℓ = 𝑗, ℓ = 𝑖, ℓ ∉ {𝑖, 𝑗}.
0,
(𝑗,𝑖) 𝛽ℓ = 𝛽 𝑖 + 𝛽 𝑗 , 𝛽ℓ ,
We keep the zero coordinates rather than delete them, so the positions retain their original names. This does not affect the Fourier coefficient, by (8). If the support of 𝛽 is 𝐽, with |𝐽| = 𝑘 ≥ 2, Equation (9), applied to the nonzero entries and with the primary entry placed last, gives 𝜇c ℐ𝑟 (𝛽) = −
Õ 1 (𝑗,𝑖) 𝜇c ). ℐ𝑟 (𝛽 𝑁 −𝑘+1 𝑖∈𝐽\{𝑗}
This is exactly the identity used in [Din25, Proposition 8], attributed there to [Ebe17, Section 4]. Taking absolute values gives the maximum recurrence used in Appendix B. For the present purpose, we instead square the identity and apply Cauchy–Schwarz: 2 |𝜇c ℐ𝑟 (𝛽)| ≤
Õ 𝑘−1 (𝑗,𝑖) 2 |𝜇c )| . ℐ𝑟 (𝛽 (𝑁 − 𝑘 + 1)2
(52)
𝑖∈𝐽\{𝑗}
This is the one-step estimate of [Din25, Proposition 9]. The distinction is that we will sum it over the structured family, rather than replace each term by a maximum coefficient. A recursion node. At a node 𝑣, let 𝑆𝑣 ⊆ 𝑆 be the set of original masks still under consideration, and let 𝑇𝑣 map them to their current masks. Write 𝐽𝑣 for their common support and 𝑘 𝑣 = |𝐽𝑣 |. At the root, these are 𝑆, 𝑇, and the initial support of size 𝑘 0 . Choose one primary index 𝑗 ∈ 𝐽𝑣 for this entire family, using the initial data and the merge history as above. Before depth 𝑑, we have 𝑘 𝑣 ≥ 𝑘 0 − 2(𝑑 − 1) > 2, so a secondary index is available. For each secondary index 𝑖 ∈ 𝐽𝑣 \ {𝑗}, put 𝑇𝑣,𝑖 (𝛼) = 𝑇𝑣 (𝛼)(𝑗,𝑖) , and split 𝑆𝑣 into 𝑆𝑣,𝑖,0 = {𝛼 ∈ 𝑆𝑣 : 𝑇𝑣,𝑖 (𝛼)𝑖 = 0}, 𝑆𝑣,𝑖,1 = {𝛼 ∈ 𝑆𝑣 : 𝑇𝑣,𝑖 (𝛼)𝑖 ≠ 0}. The zero branch has common support 𝐽𝑣 \ {𝑗, 𝑖}, while the nonzero branch has common support 𝐽𝑣 \ {𝑗}. Thus the support remains fixed within each child, even though the two children lie at different Fourier levels. Summing (52) gives
Õ 𝛼∈𝑆𝑣
≤
2 |𝜇c ℐ𝑟 (𝑇𝑣 (𝛼))|
Õ 𝑘𝑣 − 1 2 (𝑁 − 𝑘 𝑣 + 1)
Õ
Õ
𝑖∈𝐽𝑣 \{𝑗} 𝑏∈{0,1} 𝛼∈𝑆𝑣,𝑖,𝑏
(53) 2 |𝜇c ℐ𝑟 (𝑇𝑣,𝑖 (𝛼))| .
Indistinguishability of Sum of Permutations
33
For a fixed 𝑖, the two branches partition 𝑆𝑣 . Different choices of 𝑖 need not give disjoint images; each such choice is already a separate term in (53). Why recovery is needed. By the recovery assumption, the removed primary entry 𝛽 𝑗 is determined by the child mask and the known branch. The secondary value is then recovered from 𝛽 𝑖 = (𝛽 𝑖 + 𝛽 𝑗 ) + 𝛽 𝑗 , and the other coordinates have not changed. Hence the full parent mask is determined. Starting from the injective map 𝑇, this proves inductively that the map at each node is injective. This is Dinur’s applicability condition [Din25, Proposition 11]. It cannot be dropped, since initial injectivity alone does not imply injectivity after a merge. For example, all masks of the form (𝛾, 𝛾) collapse to (0, 0) when their two coordinates are merged. At a leaf 𝑣, trim the common zero coordinates. The resulting masks are distinct elements of (𝐺 \{0}) 𝑘𝑣 , so Õ 2 |𝜇c (54) ℐ𝑟 (𝑇𝑣 (𝛼))| ≤ Θ 𝑘 𝑣 . 𝛼∈𝑆𝑣
𝑟
No factor 𝑘𝑣 is needed here, because the leaf has one fixed support. Without recovery, a trimmed mask could occur repeatedly on the left, and the comparison with Θ 𝑘𝑣 would not follow. Summing the recursion. We stop at depth 𝑑 and apply the fixed-support estimate (51) at each leaf. After 𝑑 merges, every nonempty leaf has 𝑘0 − 2𝑑 ≤ 𝑘 𝑣 ≤ 𝑘0 − 𝑑. In particular, 𝑘 𝑣 > 0 by 2𝑑 < 𝑘 0 , and 𝑘 𝑣 ≤ 𝑘0 ≤ 𝑁/8. Since 𝑘 0 /(𝑁 − 𝑘 0 ) < 1, the leaf contribution is at most 𝑘𝑣 /2 𝑘0 /2−𝑑 𝑘0 𝑘𝑣 ≤ . Θ 𝑘𝑣 ≤ 𝑁 − 𝑘𝑣 𝑁 − 𝑘0 Each node has at most 2(𝑘 𝑣 − 1) ≤ 2𝑘0 children, and the factor preceding the child sums in (53) is at most 𝑘0 /(𝑁 − 𝑘 0 )2 . There are therefore at most (2𝑘0 )𝑑 nonempty leaves, with exactly 𝑑 such factors along each root-to-leaf path. Iterating (53) and then applying (54) gives
Õ 𝛼∈𝑆
2 𝑑 |𝜇c ℐ𝑟 (𝑇(𝛼))| ≤ (2𝑘 0 )
= 2𝑑
𝑘0 (𝑁 − 𝑘 0 )2
𝑘0 𝑁 − 𝑘0
𝑑
𝑘0 /2+𝑑
𝑘0 𝑁 − 𝑘0
𝑘0 /2−𝑑 (55)
.
For 𝑑 = 0, the same calculation is just the leaf estimate. This is the weaker of the two bounds in [Din25, Lemma 3], which is sufficient for the general-𝑤 analysis. Relative to the direct bound Θ 𝑘0 ≤ (𝑘 0 /(𝑁 − 𝑘0 )) 𝑘0 /2 , the right-hand side gains a factor (2𝑘 0 /(𝑁 − 𝑘0 ))𝑑 . The purpose of the block relations is to make this recursion possible for sufficiently many steps.
E.2
Recovering Labels from an Untouched Block
We retain 𝐶 𝑗 = 𝐴𝑤−𝑗 from (27). At a fixed recursion node, choose a primary coordinate in an untouched block, meaning that none of its entries has been selected as primary or secondary in the previous merges. Suppressing the block index, write 𝛽 = (𝛽0 , . . . , 𝛽 𝑤 ) for its entries before the merge, and 𝛽ℓ′ for its entries after the merge. The indices in the following two calculations are local to this block. The relation 𝑤 Õ
𝐶ℓ 𝛽ℓ = 0
ℓ =0
is available because the block is untouched. We do not assume that every block still satisfies this relation after a merge. In fact, the merged masks need not remain in the image of 𝑇𝜎,𝑤 .
34
R. Bhaumik, C. Guo, X. Guo, A. Jha
The secondary coordinate is in another block. Only the primary coordinate 𝑗 changes within the chosen block. Thus 𝛽ℓ′ = 𝛽ℓ for ℓ ≠ 𝑗, and Õ 𝛽 𝑗 = 𝐶 −1 𝑗
𝐶ℓ 𝛽ℓ′ .
ℓ ≠𝑗
The secondary value in the other block is then recovered by adding 𝛽 𝑗 to its post-merge value. No relation in that other block is needed. The secondary coordinate is in the same block. Let 𝑖 ≠ 𝑗 be its index. Since 𝛽 ′𝑖 = 𝛽 𝑖 + 𝛽 𝑗 , substitution in the block relation gives Õ (𝐶 𝑖 + 𝐶 𝑗 )𝛽 𝑗 = 𝐶 𝑖 𝛽 ′𝑖 + 𝐶ℓ 𝛽ℓ′ . ℓ ∉{𝑖,𝑗}
Now 𝐶 𝑖 + 𝐶 𝑗 = 𝐴𝑤−max{𝑖,𝑗} (𝐼 + 𝐴|𝑖−𝑗| ) is invertible: 𝐴 = 𝜎⊤ is invertible, and 𝐼 +𝐴|𝑖−𝑗| = (𝐼 +𝜎 |𝑖−𝑗| )⊤ is invertible by 𝑤-admissibility. Consequently, 𝛽 𝑗 = (𝐶 𝑖 + 𝐶 𝑗 )−1 𝐶 𝑖 𝛽 ′𝑖 +
Õ
©
𝐶ℓ 𝛽ℓ′ ® ,
𝛽 𝑖 = 𝛽′𝑖 + 𝛽 𝑗 .
ª
ℓ ∉{𝑖,𝑗}
¬
«
This also covers 𝛽′𝑖 = 0. The zero value and its coordinate position are retained, and do not remove any information needed by the recovery formula. These formulas determine the parent mask within each branch, establishing the recovery assumption used to derive (55). An example with two output blocks. For 𝑤 = 2, one block satisfies 𝐴2 𝛽 0 + 𝐴𝛽 1 + 𝛽 2 = 0. If coordinate 0 is primary and coordinate 1 is secondary, the child block is (0, 𝛾, 𝛿), where 𝛾 = 𝛽 0 + 𝛽1 and 𝛿 = 𝛽2 . The parent is recovered by 𝛽0 = (𝐴2 + 𝐴)−1 (𝐴𝛾 + 𝛿),
𝛽1 = 𝛾 + 𝛽0 ,
𝛽2 = 𝛿.
The formula applies equally when 𝛾 = 0. Here 𝐴2 + 𝐴 = 𝐴(𝐼 + 𝐴) is invertible. This is precisely where the linear combining map is needed: it lets us reverse a merge that would otherwise lose one character label. Proof of Proposition 7. Fix 𝑡 ≥ 2 with (𝑤 + 1)𝑡 ≤ 𝑁/8, and put 𝑟 = (𝑤 + 1)𝑡 and 𝑑𝑡 = ⌈𝑡/2⌉. Let 𝑆𝑡 = {𝛼 ∈ (𝐺 𝑤 )𝑡 : 𝛼(𝑖) ≠ 0 for all 𝑖 ∈ [𝑡]}. Partition 𝑆𝑡 according to the exact support of 𝑇𝜎,𝑤 (𝛼). There are at most 2𝑟 support patterns. Fix a nonempty part 𝑆 with injection support 𝐽0 ⊆ [𝑟], and let 𝑇 be the restriction of 𝑇𝜎,𝑤 to 𝑆. The map 𝑇 is injective, and all its masks have the same support, of size 𝑘0 = |𝐽0 |. Each nonzero construction block gives between 2 and 𝑤 + 1 nonzero injection entries, so 2𝑡 ≤ 𝑘 0 ≤ (𝑤 + 1)𝑡 ≤ 𝑁/8. Also 2𝑑𝑡 ≤ 𝑡 + 1 < 2𝑡 ≤ 𝑘 0 , since 𝑡 ≥ 2. Each merge touches at most two original blocks. At depth ℓ < 𝑑𝑡 , at least 𝑡 − 2ℓ > 0 blocks have not been touched. Their original entries are still present, and each such block has a nonzero entry. Choose the first untouched block and its first nonzero coordinate as primary. This choice is the same for all masks at the node and is determined by the initial support and the previous merge indices and outcomes, not by the values of the entries. The preceding recovery formulas apply for every secondary choice, including when the merged entry is zero. Thus each child map remains injective, and the recursion can be continued to depth 𝑑𝑡 . No primary selection is needed at a leaf. Applying (55) to this fixed part gives
Õ 𝛼∈𝑆
𝜇c ℐ𝑟 (𝑇𝜎,𝑤 (𝛼)) ≤ 2
𝑑𝑡
≤2
𝑑𝑡
2
𝑘0 /2+𝑑𝑡
𝑘0 𝑁 − 𝑘0
(𝑤 + 1)𝑡 𝑁 − (𝑤 + 1)𝑡
𝑡+𝑑𝑡
.
Indistinguishability of Sum of Permutations
35
For the last inequality, the ratio is at most ((𝑤 + 1)𝑡)/(𝑁 − (𝑤 + 1)𝑡) < 1, while 𝑘0 /2 ≥ 𝑡. Summing over at most 2(𝑤+1)𝑡 support patterns and using the pullback equality in (26) proves (50). To obtain (29), note that 𝑑𝑡 ≤ 3𝑡/4, 𝑡 + 𝑑𝑡 ≥ 3𝑡/2, and 𝑁 − (𝑤 + 1)𝑡 ≥ 7𝑁/8. Since (𝑤 + 1)𝑡/(𝑁 − (𝑤 + 1)𝑡) < 1, the extra factors are absorbed into a constant 𝐶𝑤 raised to the power 𝑡. ⊔ ⊓ E.3
The One-Input Moment
We give the remaining calculation for (28). Put 𝑎 = 𝑤 + 1 and first assume 𝑁 ≥ 8𝑎. For this single construction block, suppress the block index and partition the nonzero masks 𝛼 ∈ 𝐺 𝑤 according to the support of their pullback 𝛽 = 𝑇𝜎,𝑤 (𝛼). Each support has size between 2 and 𝑎. Translation invariance of the injection distribution, as recorded in the preliminaries, gives 𝜇c ℐ 𝑎 (𝛽) = 0
unless
𝑤 Õ
𝛽 𝑗 = 0.
𝑗=0
For a pullback of support size two, at positions 𝑖, 𝑗, this requires 𝛽 𝑖 = 𝛽 𝑗 . The block relation would then give (𝐶 𝑖 + 𝐶 𝑗 )𝛽 𝑖 = 0, contradicting 𝑤-admissibility and 𝛽 𝑖 ≠ 0. Thus these coefficients vanish. Consider next a fixed support of size three, at positions 𝑖, 𝑗, ℓ . A nonzero coefficient requires 𝛽ℓ = 𝛽 𝑖 + 𝛽 𝑗 . Substitution in (27) gives (𝐶 𝑖 + 𝐶ℓ )𝛽 𝑖 + (𝐶 𝑗 + 𝐶ℓ )𝛽 𝑗 = 0. Both matrices are invertible. After choosing the nonzero value 𝛽 𝑖 , the values 𝛽 𝑗 and 𝛽ℓ are determined. Hence there are at most 𝑁 − 1 contributing masks for this support. By Appendix A, their nonzero coefficient has magnitude 2/((𝑁 − 1)(𝑁 − 2)). Their total second moment is therefore at most
(𝑁 − 1)
2 (𝑁 − 1)(𝑁 − 2)
2 =
4 = 𝑂(𝑁 −3 ). (𝑁 − 1)(𝑁 − 2)2
The injectivity of 𝑇𝜎,𝑤 ensures that each such injection mask corresponds to at most one construction mask. For a fixed pullback support of size 𝑘 0 ≥ 4, apply the recursive estimate (55) with 𝑟 = 𝑎 and 𝑑 = 1. Indeed, 2 < 𝑘 0 ≤ 𝑎 ≤ 𝑁/8, and the sole original block is untouched before that merge, so the recovery argument of Appendix E.2 applies. The contribution is at most 𝑘0 2 𝑁 − 𝑘0
𝑘0 /2+1
= 𝑂 𝑤 (𝑁 −3 ).
Since 𝑤 is fixed, there are only 𝑂 𝑤 (1) support patterns. Summing their contributions gives 𝐿1 = 𝑂 𝑤 (𝑁 −3 ). The finitely many 𝑁 < 8𝑎 are absorbed into the implicit constant. All these estimates are uniform over the 𝑤-admissible maps under consideration.
F
Proofs of Concrete Bounds for Dinur’s LXoP
We prove the two bounds in Corollary 6. F.1
One-Block Output
The case 𝑞 = 0 is immediate; assume 𝑞 ≥ 1. Let 𝜉 denote the density of the complete 𝜋+𝜎,1 function on its (𝜎,1) actual domain, of size 𝐷 = 𝑁/2. By input symmetry and the definition of 𝜉𝑛,𝑡 ,
Õ |𝛼|=𝑡
|b 𝜉(𝛼)|2 =
𝐷 𝑡
Õ 𝛼∈(𝐺\{0})𝑡
(𝜎,1)
|𝜉𝑛,𝑡 (𝛼)|2 .
36
R. Bhaumik, C. Guo, X. Guo, A. Jha
The 𝑡 = 1 term is zero by the support-two calculation in Appendix E.3, as also shown in [Din25, Proposition 15]. For 𝑡 ≥ 2, [Din25, Proposition 16] gives
Õ
(𝜎,1)
|𝜉𝑛,𝑡 (𝛼)|2 ≤
𝛼∈(𝐺\{0})𝑡
23𝑡/2+3𝑐𝑡 𝑡 𝑡+2𝑐𝑡 (𝑡 − 2𝑐 𝑡 )𝑡/2−𝑐𝑡 , (𝑁 − 2𝑡)3𝑡/2+𝑐𝑡
where 𝑐 𝑡 = 0 for even 𝑡 and 𝑐 𝑡 = 1/2 for odd 𝑡. Proposition 16 applies for 2 ≤ 𝑡 ≤ 𝑁/16, which contains every level used below. Suppose 2 ≤ 𝑡 ≤ 𝑁/32. Using 𝐷 = 𝑁/2, 𝐷𝑡 ≤ (𝑒𝐷/𝑡)𝑡 , 𝑁 − 2𝑡 ≥ 15𝑁/16, and 𝑐 𝑡 ≤ 1/2, we obtain
Õ
√ 16 3/2 2 3/2 b |𝜉(𝛼)| ≤ 2 𝑡 𝑒 2 15
r
𝑡 𝑁
!𝑡 .
|𝛼|=𝑡
Since 𝑒 2 (16/15)3 < 9 and 𝑡/𝑁 ≤ 1/32,
Õ
|b 𝜉(𝛼)|2 ≤
𝑡−2
51 2 3 𝑡 𝑁 4
.
|𝛼|=𝑡
Therefore, for 𝑞 ≤ 𝑁/64, ∞
Õ
|b 𝜉(𝛼)|2 ≤
𝑡−2
51 Õ 2 3 𝑡 𝑁 4
=
𝑡=2
1≤|𝛼|≤2𝑞
7548 . 𝑁 ⊔ ⊓
Theorem 1 then yields the first bound in Corollary 6. F.2
Two-Block Output
The case 𝑞 = 0 is immediate; assume 𝑞 ≥ 1. Let 𝜉 denote the density of the complete 𝜋+𝜎,2 function, whose actual domain has size 𝐷 = 𝑁/4. In the one-input calculation of Appendix E.3, exactly the 𝑁 − 1 construction masks (𝛾, 𝛾) with 𝛾 ≠ 0 contribute. Each has coefficient 2/((𝑁 − 1)(𝑁 − 2)). Thus, as in [Din25, Lemma 8], 2 Õ 𝑁 (𝜎,2) . (56) 𝐷 𝜉𝑛,1 (𝛼) = (𝑁 − 1)(𝑁 − 2)2 2 𝛼∈𝐺 \{0}
For 2 ≤ 𝑡 ≤ 𝑁/32, Proposition 19 of the same work, together with input symmetry, gives
Õ
𝐷 7𝑡/2+3𝑐𝑡 2 b |𝜉(𝛼)| ≤ 2 𝑡
𝑡 𝑁 − 2𝑡
3𝑡/2+𝑐𝑡
C 𝐴𝑡 ,
|𝛼|=𝑡
where 𝑐 𝑡 = 0 for even 𝑡 and 𝑐 𝑡 = 1/2 for odd 𝑡. Since 2𝑞 ≤ 𝑁/192, this estimate applies at every required level. For two consecutive levels of the same parity with 4 ≤ 𝑡 and 𝑡 + 2 ≤ 2𝑞, a direct calculation gives (𝐷 − 𝑡)(𝐷 − 𝑡 − 1) 𝐴𝑡+2 𝑡+2 = 27 𝐴𝑡 𝑁 − 2𝑡 − 4 (𝑡 + 1)(𝑡 + 2)
3 (57)
(𝑡 + 2)(𝑁 − 2𝑡) · 𝑡(𝑁 − 2𝑡 − 4)
3𝑡/2+𝑐𝑡
< 0.855.
We give some details for the uniform numerical bound. For fixed 𝑡, the displayed expression decreases with 𝑁 when 𝑁 ≥ 192(𝑡 + 2). Substituting 𝑁 = 192(𝑡 + 2) and using 𝑐 𝑡 ≤ 1/2 bounds it by
128 (47𝑡 + 96)(47𝑡 + 95) 192 1+ 95𝑡 (𝑡 + 1)(𝑡 + 2) 1903
3𝑡/2+1/2
<
128 · 472 288/95 𝑒 < 0.855. 1903
The middle inequality holds for 𝑡 ≥ 4, using log(1 + 𝑥) ≤ 𝑥 − 𝑥 2 /(2(1 + 𝑥)). This proves the bound uniformly in 𝑁 and 𝑡.
Indistinguishability of Sum of Permutations
37
We next evaluate the first few levels. For 𝑁 ≥ 2048, their scaled upper bounds decrease with 𝑁, and their values at 𝑁 = 2048 give 𝑁 𝐴2 < 32.126,
𝑁 𝐴3 < 1.277,
𝑁 𝐴4 < 5.397,
𝑁 𝐴5 < 0.406.
The right-hand side of (56) is smaller than 0.001/𝑁. Using the ratio 0.855 in (57), separately for the even and odd tails, yields 2𝑞
Õ 1≤|𝛼|≤2𝑞
|b 𝜉(𝛼)|2 ≤
Õ 𝑁 + 𝐴𝑡 2 (𝑁 − 1)(𝑁 − 2) 𝑡=2
1 5.397 + 0.406 74 < 0.001 + 32.126 + 1.277 + < . 𝑁 1 − 0.855 𝑁 Missing low levels when 𝑞 is small can be added as positive upper bounds. For 𝑁 = 1024, we have 𝑞 ≤ 2, and direct evaluation of the levels 𝑡 ≤ 4 gives total second Fourier moment less than 46/𝑁 < 74/𝑁. Theorem 1 now proves the second bound in Corollary 6. ⊔ ⊓