Quantum Security of XOR of Permutations via Fourier Analysis
Abstract
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≥ 2 random permutations over {0,1}n is indistinguishable from a random function by any q-query quantum algorithm with advantage O(min{q3/2rn,q1.5/(2(r−0.5)n),1/(2(r−1.5)n)}) for all q≪ 2n. In particular, XoP remains secure throughout the entire query range, far beyond the 2n/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≤ 2n/2 and ≈ 2n. 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 q3/2rn and q1.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.
Related
- Where Quantum Fourier Sampling Stops Short: A Three-Gate Audit Protocol for Delay-PUF Security Models
- Superadditivity of classical communication over quantum channels via random and deterministic permutations
- Security of quantum key distribution with passive basis choice and detection-efficiency mismatch for a realistic satellite setup
- Multi-path Security in Quantum Networks with Trusted Nodes
- Security Implications of Measurement Based Crosstalk on Superconducting Quantum Computers
BibTeX
@misc{choi2026quantum,
title = {{Quantum Security of XOR of Permutations via Fourier Analysis}},
author = {Wonseok Choi and Minki Hhan and Junyoung Jang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.34413},
eprint = {2609.34413},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.34413},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Quantum Security of XOR of Permutations via Fourier Analysis
AU - Wonseok Choi
AU - Minki Hhan
AU - Junyoung Jang
PY - 2026
DA - 2026/09/28
PB - arXiv
DO - 10.48550/arxiv.2609.34413
UR - https://arxiv.org/abs/2609.34413
AB - 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≥ 2 random permutations over {0,1}^n is indistinguishable from a random function by any q-query quantum algorithm with advantage O(min{q^3/2^rn,q^1.5/(2^(r−0.5)n),1/(2^(r−1.5)n)}) for all q≪ 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≤ 2^n/2 and ≈ 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.
ER -