技术摘要：通过傅里叶分析研究置换异或（XoP）的量子安全性

1. 问题陈述

本文研究了**置换异或（XOR of Permutations, XoP）**构造的量子安全性。XoP 是一种基于独立随机置换构建的基础伪随机函数（PRF），其定义为：
$$\text{XoP}[r](x) := P_1(x) \oplus \cdots \oplus P_r(x)$$
其中 $P_1, \dots, P_r$ 是在 $n$ 位字符串上的独立随机置换。

虽然 XoP 对经典攻击者的安全性已有成熟结论（实现了“超越生日界”的安全性），但其针对能够进行叠加查询（Q2 模型）的量子攻击者的安全性仍是一个开放问题。现有的基于置换的量子 PRF 的结果局限于“生日界” $q \approx 2^{n/3}$，这一限制是由量子碰撞查找攻击（例如 Brassard-Høyer-Tapp）造成的。作者旨在确定 XoP 是否能在量子设定下实现显著超越该界的安全性。

2. 方法论

作者采用了一种应用于泛函空间的傅里叶分析变体多项式方法。该方法将近期的经典技术应用于量子设定，因为在量子设定中，由于相干查询的存在，传统的“响应轨迹（response transcript）”概念并不存在。

核心框架

1. 泛函表示： 一个 $q$ 次查询量子算法 $A$ 相对于均匀随机函数 $F$ 的区分优势被表示为一个内积：
   $$\text{Adv} = \langle \mu_D - 1, P_A \rangle$$
   其中 $\mu_D$ 是分布 $D$ 的密度函数，$P_A(f) = \Pr[A^{O_f} \to 1]$ 是代表算法接受概率的泛函。
2. 傅里叶展开： 泛函 $P_A$ 被证明其傅里叶次数（Fourier degree）至多为 $2q$。密度函数 $\mu_D - 1$ 被分解为 $d$ 阶傅里叶分量。优势由这些分量的内积之和来界定：
   $$\text{Adv} \leq \sum_{d=1}^{2q} |\langle \mu_D^{=d}, P_A^{=d} \rangle|$$
3. 分量分析： 作者分析了 XoP 分布的傅里叶分量 $\mu_{\text{XoP}}^{=d}$ 的范数。
   • 高阶项 ($d \geq 5$)： 他们利用组合论论证以及源自随机置换性质的递归关系，直接对这些分量的 $\ell_2$ 范数进行了界定。
   • 低阶项 ($d \in \{2, 3, 4, 6\}$)： 直接进行范数界定是不够的。相反，作者将这些傅里叶分量重新解释为其他问题的区分优势，特别是将它们与具有“植入碰撞（planted collisions）”的分布联系起来（例如，在给定 $f(x) = f(x')$ 条件下的随机函数）。

关键技术工具

• 植入碰撞分布： 二阶分量被证明与均匀随机函数与带有植入碰撞的函数之间的差异成正比。该子问题的安全性通过 Zhandry 的小范围分布不可区分性结果进行分析。
• 压缩 Oracle（Compressed Oracle）： 为了推导出植入碰撞问题更紧致的界（特别是针对 $O(q^{1.5}/N^{1.5})$ 这一区间），作者使用了压缩 Oracle 技术。他们将区分优势解释为对数据库状态的期望，从而能够界定数据库中的碰撞数量，并得出植入碰撞问题的界为 $O(q^{1.5}/N^{1.5})$。
• 归约（Reductions）： 作者建立了 XoP 的傅里叶分量与区分随机函数与带有植入 $k$-碰撞或植入 XOR 约束函数之间的优势之间的归约关系。

3. 核心贡献与结果

主定理

本文证明，对于 $r \geq 2$ 个独立的随机置换，XoP 与随机函数是不可区分的，任何 $q$ 次查询量子算法的优势均受限于：
$$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)$$
对于所有 $q \leq 2^{n/57774}$ 均成立。

具体安全界

该结果意味着 XoP 在整个查询范围内保持安全，远超 $2^{n/3}$ 的量子生日界：

1. 低查询区间 ($q \lesssim 2^{n/2}$): 优势由 $O(q^3 / 2^{rn})$ 主导。这与启发式的量子碰撞查找攻击相匹配。
2. 中查询区间: 优势被界定为 $O(q^{1.5} / 2^{(r-0.5)n})$。该界是通过利用压缩 Oracle 改进后的植入碰撞分析得出的。
3. 高查询区间 ($q \approx 2^n$): 优势被界定为 $O(2^{-(r-1.5)n})$。这确保了即使在查询次数接近定义域大小时，只要 $r \geq 2$，系统依然是安全的。

启发式紧致性

作者提出了启发式攻击以表明其界的紧致性：

• 对于 $q \lesssim 2^{n/2}$，量子碰撞查找攻击表明优势为 $\Omega(q^3/2^{rn})$ 和 $\Omega(q^{1.5}/2^{(r-0.5)n})$。
• 对于 $q \approx 2^n$，启发式碰撞计数攻击表明优势约为 $2^{-(r-1.5)n}$。

4. 重要性与主张

• 首个超越生日界的量子 PRF： 据作者所知，这是第一个从置换构造出的实现量子安全性超越 $2^{n/3}$ 生日界的构造。
• 实际意义： 该结果表明，在量子理想密码模型中使用块加密（如 AES-256）实例化 XoP，只要密钥长度足够，可以在 $q \approx 2^n$ 次查询下保持安全。这解决了关于基于置换的密码原语量子安全性的一个重要不确定性。
• 方法论进展： 本文引入了一种新颖的技术，即将低阶傅里叶分量重新解释为植入碰撞问题的区分优势，从而弥合了傅里叶分析与压缩 Oracle 方法之间的鸿沟。
• 辅助结果： 对植入碰撞问题 $O(q^{1.5}/N^{1.5})$ 界限的证明，也为大范围情形下小范围分布的不可区分性提供了一个新的、改进的界，这具有独立的学术价值。

作者指出，虽然他们使用了 AI 工具（ChatGPT 5.4/5.5 Pro）来辅助形式化技术细节并生成特定引理（特别是针对二阶分量的 $O(q^3/N^r)$ 界）的初步证明，但论文的核心数学贡献、证明的简化以及整体结构均由人类作者开发。