Metraipolis › archive › dc_122ca840ee32

Quantum Security of XOR of Permutations via Fourier Analysis — arXiv:2609.34413

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.34413
License (as archived)
CC0-1.0
Archived
2026-10-07T22:35:07.387Z
SHA-256 of the archived text
62ca0bfe401264524301fe80e6b4cdf765e126a0a15215546d0c865bf33a5046
Stable URL of this page
https://metraipolis.com/documento/dc_122ca840ee32

How to cite

Quantum Security of XOR of Permutations via Fourier Analysis — arXiv:2609.34413 — arXiv (en), https://arxiv.org/abs/2609.34413 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_122ca840ee32 (Metraipolis archive dc_122ca840ee32, sha256 62ca0bfe401264524301fe80e6b4cdf765e126a0a15215546d0c865bf33a5046)
BibTeX
@misc{dc122ca840ee32,
  title = {Quantum Security of XOR of Permutations via Fourier Analysis — arXiv:2609.34413},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.34413},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_122ca840ee32; sha256 62ca0bfe401264524301fe80e6b4cdf765e126a0a15215546d0c865bf33a5046},
  year = {2026}
}

Archived text

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

The XOR of two or more independent random permutations (XoP) is the prototypical pseudorandom function built from permutations achieving security beyond the birthday bound. The classical security of the XoP construction is well established, but its security against quantum attacks that query XoP in superposition has remained widely open. We prove that the XOR of $r\ge 2$ random permutations over $\{0,1\}^n$ is indistinguishable from a random function by any $q$-query quantum algorithm with advantage \[O\left(\min\left\{\frac{q^3}{2^{rn}},\frac{q^{1.5}}{2^{(r-0.5)n}},\frac{1}{2^{(r-1.5)n}}\right\}\right)\] for all $q\ll 2^n$. In particular, XoP remains secure throughout the entire query range, far beyond the $2^{n/3}$ bound due to quantum collision finding attacks. This is the first construction from permutations that achieves the quantum version of the beyond birthday bound security. We also present several heuristic attacks suggesting the tightness of our bounds in ranges $q\le 2^{n/2}$ and $\approx 2^n$. We use a Fourier-analytic variant of the polynomial method: the advantage of any $q$-query quantum algorithm is controlled by the Fourier components of degree at most $2q$, or by $2q$ input-output data of the construction. The norms of most components are bounded well, proving the bound $2^{-(r-3/2)n}$. The norm of low-degree components turn out to be too large for the bounds $q^3/2^{rn}$ and $q^{1.5}/2^{(r-0.5)n}$. We reinterpret these low-degree components as (sums of) advantages of the other problems. For example, the degree-2 and degree-4 terms are interpreted as the advantages against random functions with and without \emph{planted collisions}, which in turn are bounded using Zhandry's small-range distributions. Along the way, we prove a new bound for the small-range indistinguishability for (ironically) large ranges, which is of independent interest.

Tema degli esploratori: fiducia digitale e crittografia (retro-catalogo arXiv: annunci del 2026-09-29 in cs.CR).
Categorie arXiv: Quantum Physics (quant-ph) ; Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2609.34413 — 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.791Z 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).