Indistinguishability of Sum of Permutations: A Fourier Analytic Route to Classical and Quantum Security
Fourier analysis bounds classical and quantum security of sums of random permutations.
The paper gives a Fourier-analytic treatment of classical and quantum indistinguishability for sums of k independent random permutations of a finite abelian group of order N. Classically, the advantage is O_k(q/N^{k-1/2}) for every q below N, and O_k(q^2/N^k) below the birthday threshold. Quantum results include O_k(N^{-(k-3/2)}) for q up to (N-1)/2, sharper query-dependent bounds for k=2 and k at least 3, and security bounds for linear postprocessing and Dinur's LXoP construction.
- Classical advantage is O_k(q/N^{k-1/2}) for q below N.
- Below the birthday bound the classical bound is O_k(q^2/N^k).
- A one-query Fourier attack matches the one-query bound order.
- Results also cover linear postprocessing and Dinur's LXoP.
From the original article
1 min read at arxiv.orgWe 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)+\cdots+π_k(x)$ for $k\geq2$ independent uniform random permutations of $G$.
By Ritam Bhaumik · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.