Metraipolis › archive › dc_5f67ff2b4f32

Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security — arXiv:2609.35421

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.35421
License (as archived)
CC0-1.0
Archived
2026-10-07T22:34:56.472Z
SHA-256 of the archived text
365f21ace64898de95a14dbfef337e669557d7138b58f65448fa59ee609b245d
Stable URL of this page
https://metraipolis.com/documento/dc_5f67ff2b4f32

How to cite

Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security — arXiv:2609.35421 — arXiv (en), https://arxiv.org/abs/2609.35421 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5f67ff2b4f32 (Metraipolis archive dc_5f67ff2b4f32, sha256 365f21ace64898de95a14dbfef337e669557d7138b58f65448fa59ee609b245d)
BibTeX
@misc{dc5f67ff2b4f32,
  title = {Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security — arXiv:2609.35421},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.35421},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5f67ff2b4f32; sha256 365f21ace64898de95a14dbfef337e669557d7138b58f65448fa59ee609b245d},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.35421. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\pi^k_+(x)=\pi_1(x)+\cdots+\pi_k(x)$ for $k\geq2$ 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\leq(N-1)/2$, while Fourier interpolation gives concrete finite bounds up to $q\leq4N/15$ and the query-dependent bounds $O\left(\min\left\{N^{-1/2},q^3/N^2 + 1/N\right\}\right)$ and $O_k\left(\min\left\{q^3/N^k,N^{-(k-3/2)}\right\}\right)$, for $k=2$ and $k \geq 3$, respectively, throughout $1\leq q\leq(N-1)/2$. For $q = 1$, the first bound sharpens to $O(N^{-2})$. Over $G=\mathbb F_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, $\mathsf{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.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-29 in cs.CR).
Categorie arXiv: Cryptography and Security (cs.CR) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.35421 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T22:13:03.747Z dalla pagina https://arxiv.org/catchup/cs.CR/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).