Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
This work resolves the open problem of whether the XOR of independent random permutations (XoP) maintains beyond-birthday-bound security against quantum adversaries querying in superposition. By analyzing the construction under the quantum polynomial framework, the authors prove that $r \ge 2$ permutations yield a pseudorandom function indistinguishable from random up to quantum query advantage $O(\min\{q^3/2^{rn}, q^{1.5}/2^{(r-0.5)n}, 1/2^{(r-1.5)n}\})$. This provides the first permutation-based PRF construction with proven quantum beyond-birthday-bound security, holding far past the standard $2^{n/3}$ quantum collision barrier across the entire query range.
Quantum superposition attacks cannot break XOR of permutations at the classical $2^{n/3}$ collision threshold, establishing the first proof that permutation-based symmetric primitives retain beyond-birthday security in the quantum regime.
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.