Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security
Abstract
We study classical and quantum indistinguishability of sums of independent random permutations and related transformations from permutations to functions. Let G be a finite abelian group of order N, and let πk+(x)=π1(x)+⋯+πk(x) for k≥2 independent uniform random permutations of G. We give a unified Fourier analytic treatment in which the construction is represented by its probability density and a distinguisher by its acceptance function, with the classical and quantum query models imposing different restrictions on the Fourier support of the latter. Classically, we obtain the bound Ok(q/Nk−1/2) for every q<N, and refine it below the birthday threshold to Ok(q2/Nk). In the quantum model, a simulation argument gives Ok(N−(k−3/2)) for q≤(N−1)/2, while Fourier interpolation gives concrete finite bounds up to q≤4N/15 and the query-dependent bounds O(min{N−1/2,q3/N2 + 1/N}) and Ok(min{q3/Nk,N−(k−3/2)}), for k=2 and k ≥ 3, respectively, throughout 1≤ q≤(N−1)/2. For q = 1, the first bound sharpens to O(N−2). Over G=𝔽2n, a one-query Fourier attack matches the order of our one-query bound, while an N/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 single-permutation 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.
Related
- Maximal Lehmer Codes for Permutations with Classical and Consecutive 321-Avoidance
- Superadditivity of classical communication over quantum channels via random and deterministic permutations
- Fourier analytic variants of the Furstenberg and Kakeya problems
- \textit{In situ} certification of multiparticle indistinguishability in a generic interferometer
- Topological and Geometric Perspectives on Homomorphism Indistinguishability
BibTeX
@misc{bhaumik2026indistinguishability,
title = {{Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security}},
author = {Ritam Bhaumik and Chun Guo and Xiaoning Guo and Ashwin Jha},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.35421},
eprint = {2609.35421},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35421},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security
AU - Ritam Bhaumik
AU - Chun Guo
AU - Xiaoning Guo
AU - Ashwin Jha
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.35421
UR - https://arxiv.org/abs/2609.35421
AB - We study classical and quantum indistinguishability of sums of independent random permutations and related transformations from permutations to functions. Let G be a finite abelian group of order N, and let π^k_+(x)=π_1(x)+⋯+π_k(x) for k≥2 independent uniform random permutations of G. We give a unified Fourier analytic treatment in which the construction is represented by its probability density and a distinguisher by its acceptance function, with the classical and quantum query models imposing different restrictions on the Fourier support of the latter. Classically, we obtain the bound O_k(q/N^k−1/2) for every q<N, and refine it below the birthday threshold to O_k(q^2/N^k). In the quantum model, a simulation argument gives O_k(N^−(k−3/2)) for q≤(N−1)/2, while Fourier interpolation gives concrete finite bounds up to q≤4N/15 and the query-dependent bounds O(min{N^−1/2,q^3/N^2 + 1/N}) and O_k(min{q^3/N^k,N^−(k−3/2)}), for k=2 and k ≥ 3, respectively, throughout 1≤ q≤(N−1)/2. For q = 1, the first bound sharpens to O(N^−2). Over G=𝔽_2^n, a one-query Fourier attack matches the order of our one-query bound, while an N/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 single-permutation 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.
ER -