Quantum Security of XOR of Permutations via Fourier Analysis

约 2559 字大约 9 分钟

2026-09-30

作者: Wonseok Choi, Minki Hhan, Junyoung Jang

1. 核心物理图象

• 核心问题：在量子计算机可以“相干地”查询密码函数（即一次性查询所有输入输出关系的叠加态）的威胁模型下，如何用最基础的密码组件——随机置换（可以想象成 AES 加密）——构造出安全的伪随机函数？

• 传统困境：过去人们证明，仅靠单个随机置换，安全性最多只能维持到约 (2^{n/3}) 次量子查询（(n) 是输出比特数）。超过这个界限，量子算法就能找到碰撞从而区分出这不是真正的随机函数。这是量子密码学中一个长期未突破的瓶颈。

• 本文贡献：论文证明了，如果把两个或多个独立随机置换的输出按位异或（XOR） 在一起，这个构造（称为 XoP）在量子攻击下几乎是完美的伪随机函数——即使攻击者进行多达约 (2^n) 次量子查询（即穷举整个输入空间），也无法有效区分它和真正的随机函数。这是第一个从置换出发、在量子设置下突破“生日界限”(2^{n/3}) 的伪随机函数构造。

• 直观印象：就像把几块独立的拼图（置换）按特定方式叠加后，拼图的花纹变得极其复杂，以至于量子计算机也无法通过“相干查询”这个超级放大镜看出任何破绽，安全性一直保持到几乎用完所有可能的查询。

2. 关键术语解释

• XoP[r]（r 个置换的异或）
定义：对输入 (x)，输出 (P_1(x) \oplus P_2(x) \oplus \cdots \oplus P_r(x))，其中 (P_1,\dots,P_r) 是相互独立的随机置换。
作用：这是本文研究的核心密码构造。目标是证明它作为伪随机函数，在量子攻击下仍然安全。

• 傅里叶分析的功能方法（Fourier Analysis of Functionals）
定义：把量子算法的接受概率看作定义在“所有函数构成的空间”上的一个函数，然后对这个函数做傅里叶展开。由于量子查询的本质，这个展开的次数不超过 (2q)（(q) 是查询次数）。
作用：这是本文的核心数学工具。它把“量子算法能否区分 XoP 和随机函数”的问题，转化为“XoP 分布在低阶傅里叶分量上的权重有多大”的问题，从而绕开了直接分析量子查询的困难。

• 植入碰撞（Planted Collision）
定义：一种特殊的函数分布——先随机选两个不同的输入 (x_1, x_2)，然后要求函数满足 (f(x_1)=f(x_2))，其余点随机。
作用：在傅里叶分析中，XoP 分布的二阶傅里叶分量恰好可以解释为“植入碰撞分布”与“均匀随机函数分布”之间的密度差。因此，证明 XoP 安全的关键一步，就是证明量子算法很难区分“植入碰撞”和“纯随机函数”。本文用 Zhandry 的小范围分布（small-range distribution）和压缩预言机（compressed oracle）工具来证明这一点。

3. 主要贡献 (Key Contributions)

首次实现量子超越生日界限的安全性
证明了 XoP 构造（(r \ge 2) 个独立置换的异或）在量子攻击下的区分优势上界为
[ 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) 是量子查询次数。这意味着当 (q) 接近 (2^n) 时，优势仍然可忽略。这是第一个从置换构造的量子伪随机函数，其安全性突破了 (2^{n/3}) 的量子生日界限，甚至接近 (2^n)。
提出了“功能傅里叶分析”的量子证明框架
将经典密码学中用于分析 XoP 的傅里叶分析方法，成功推广到量子设置。核心创新是：把量子算法的接受概率表示为定义在函数空间上的低阶傅里叶多项式，从而将量子区分问题转化为对 XoP 分布低阶傅里叶系数的精细组合分析。这为分析其他基于置换的量子密码构造提供了新范式。
建立了植入碰撞问题与压缩预言机的联系，并给出了更紧的界
将 XoP 的二阶傅里叶分量解释为“植入碰撞 vs 随机函数”的区分问题，并利用压缩预言机技术证明其优势上界为 (O(q^{3/2}/N))。这反过来给出了小范围分布（small-range distribution）在大范围参数下的新不可区分性界（Corollary 7.3），这本身也是一个独立有趣的量子密码学结果。
给出了匹配的启发式攻击，表明界是紧的
论文给出了量子碰撞查找攻击和量子计数攻击的启发式分析，其优势分别达到 (\Omega(q^3/Nr)) 和 (\Omega(q^{1.5}/N))，与上界匹配。在 (q \approx 2^n) 时，还给出了基于量子奇偶性算法的攻击，优势达到 (1/2)，说明 (2^{-(r-1.5)n}) 这一项也是紧的。

4. 研究方法 (Methodology)

• 核心理论工具：功能傅里叶分析（Fourier Analysis of Functionals）
作者把量子算法的接受概率 (P_A(f) = \Pr[A^{O_f} \to 1]) 视为定义在函数空间 (\mathcal{F} = {f:{0,1}^n \to {0,1}^n}) 上的“功能”（functional）。利用量子查询的代数性质，证明 (P_A) 的傅里叶展开次数不超过 (2q)。于是，区分优势可以写成
[ \text{Adv} = \langle P_A,\ \mu_{\text{XoP}} - 1\rangle, ]
其中 (\mu_{\text{XoP}}) 是 XoP 分布相对于均匀分布的密度函数。根据傅里叶正交性，只有低阶分量（阶数 (\le 2q)）有贡献。

• 关键技术步骤：

计算 XoP 分布的傅里叶系数：利用随机置换的傅里叶系数公式 (\widehat{\mu_P}(\gamma) = \mathbb{E}{z_1,\dots,z_d \text{ 无放回}}[\prod \chi{\gamma(x_i)}(z_i)])，精确计算低阶（(d=1,2,3,4,6)）分量。
低阶分量的精细处理：对于 (d=2,3,4,6)，纯 (\ell_2) 范数界不够紧。作者将这些分量转化为“植入碰撞”（planted collision）、“植入三重碰撞”、“植入 4-XOR”等辅助分布与随机函数的区分问题，然后用 Zhandry 的小范围分布不可区分性定理和压缩预言机技术来界定这些辅助问题的优势。
高阶分量的统一界定：对于 (d \ge 5) 的其他分量，用组合方法证明其 (\ell_2) 范数足够小（Lemma 5.4–5.6），从而贡献可忽略。
中间查询范围的改进：对于 (q \ge 2^{n/3})，利用压缩预言机重新分析植入碰撞问题，得到 (O(q^{3/2}/N)) 的界，从而给出第二个优势上界 (O(q^{1.5}/2))。

• 与关键术语的呼应：整个方法的核心就是“功能傅里叶分析”；而证明低阶分量界的关键步骤，则是将傅里叶分量转化为“植入碰撞”问题，并用压缩预言机和小范围分布工具来解决。

5. 实验结果与结论 (Results and Conclusion)

• 关键结论：

XoP[(r)]（(r \ge 2) 个独立随机置换的异或）在量子攻击下是安全的，区分优势上界为
[ 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 \le 2^{n/57774}) 成立。特别地，当 (q \approx 2^n) 时，优势仍然可忽略。
这是第一个从置换构造的量子伪随机函数，其安全性超越 (2^{n/3}) 的量子生日界限。在量子理想密码模型下（如 AES-256 用独立密钥实例化），这意味着可以安全地抵抗高达约 (2^{85}) 次量子查询（对于 (n=128)），远优于之前仅 (2^{43}) 次的安全性。
论文给出的启发式攻击表明，上述三个界在相应参数范围内都是紧的。

• 对领域的意义：

解决了量子密码学中一个长期悬而未决的问题：是否存在基于置换的量子伪随机函数能突破生日界限？答案是肯定的，而且安全性几乎达到最优。
为实际部署在量子时代的对称密钥密码学提供了理论保障：即使使用 AES 这样的分组密码，通过简单的异或构造，也能在量子攻击下保持极高的安全性。
提出的“功能傅里叶分析”框架可望用于分析其他基于置换的密码构造（如 Feistel 网络、Even-Mansour 等）的量子安全性。

• 开放性问题与未来启示：

论文的界中隐藏了依赖于 (r) 的常数因子，对于较大的 (r)，这些常数是否实际可行？能否优化？
对于 (r=2) 的 XoP，在 (q) 处于 (2^{n/2}) 到 (2^n) 之间时，第一个界和第二个界哪个更紧？论文并未完全解决这个区间的紧性（表 1 中标注为“?”）。
能否将傅里叶分析方法推广到其他非异或的置换组合构造？能否用于分析量子理想密码模型中的其他模式（如 CBC-MAC、PMAC 等）？
论文中 AI 辅助证明的披露（使用 ChatGPT 5.5 Pro 等）也引发了一个元问题：AI 在复杂数学证明中的角色将如何演变？

6. 论文标签 (Tags)

量子算法, 量子信息, 量子复杂性, 编译与优化

📄 点击此处展开/折叠原文 PDF

原文链接： Quantum Security of XOR of Permutations via Fourier Analysis