技术摘要：带密钥预言机的不可区分性提升、压缩理想密码以及更多应用

1. 问题陈述

在密码学安全性证明中，通常使用带密钥的预言机（keyed oracles）来对方案进行建模。这些预言机由大量独立的基底预言机实例组成（例如，理想密码中每个密钥选择一个独立的随机置换，或者随机预言机中每个输入选择一个独立的随机字符串）。从经典到量子安全模型的过渡过程中，出现了一个根本性的挑战：

• 量子叠加问题： 量子对手可以对以密钥叠加态形式存在的带密钥预言机进行查询。这种单次查询实际上同时触及了所有基底预言机的实例。
• 经典技术的失效： 标准的经典证明技术（如混合论证/hybrid argument）在这种设定下会失效。在经典情况下，可以逐一替换基底预言机的实例（这会引入与查询次数 $q$ 成线性关系的损失）。但在量子情况下，由于单次查询跨越了所有实例，直接的混合论证无法奏效。
• 现有工作的局限性： 现有的处理方法要么在量化效率上存在缺陷（引入了超多项式或平方根级别的优势损失），要么在适用范围上受到限制（仅适用于无状态预言机）。许多有用的预言机，例如压缩预言机（如 Zhandry 的压缩预言机、Unruh 和 Carolan 的压缩置换预言机），是有状态的（stateful），即它们的内部存储器会随每次查询而演变。目前尚不存在针对量子环境下有状态预言机的通用提升定理。

本文旨在解决这样一个通用问题：如果两个基底预言机 $O_0$ 和 $O_1$ 在 $q$ 次量子查询下是不可区分的，那么它们对应的带密钥预言机 $O_0^{\mathcal{K}}$ 和 $O_1^{\mathcal{K}}$ 是否也是不可区分的？其安全性损失是多少？

2. 研究方法

作者采用了一种结合了**多项式方法（polynomial method）与马尔可夫兄弟不等式（Markov brothers' inequality）**的新颖应用，以建立一个通用的不可区分性提升定理。

提升定理

其核心贡献是一个定理，该定理指出：如果基底预言机 $O_0$ 和 $O_1$ 在 $q$ 次量子查询下的不可区分优势为 $\epsilon$，那么它们的带密钥版本之间的不可区分优势最多为 $8q^2 \epsilon$。

关键技术步骤：

1. 参数化归约： 证明过程构建了一个归约算法 $\mathcal{B}$，用于区分基底预后 $O_0$ 和 $O_1$。$\mathcal{B}$ 通过基于两个独立采样的函数 $H$ 和 $G$ 来模拟对抗者的带密钥预言机，这两个函数将密钥映射到服从参数为 $p$ 和 $z$ 的伯努利分布的比特。
2. 多项式表述： 对抗者的区分优势被表示为 $|f(1) - f(0)|$，其中 $f(p)$ 是当基底预言机为 $O_1$ 且路由参数为 $p$ 时，$\mathcal{A}$ 输出 1 的概率。
3. 导数联系： 作者表明导数 $f'(p)$ 与另一个函数 $g_p(z)$ 在 $z=0$ 处的导数相关。至关重要的是，$g_p(z)$ 被证明是一个次数至多为 $2q$ 的关于 $z$ 的多项式。
4. 通过不等式进行界定： 利用马尔可夫兄弟不等式（以及涉及拉格朗日插值的特定变体），作者界定了该多项式的导数。这使得他们能够将连续的差值 $|f(1) - f(0)|$ 与归约算法 $\mathcal{B}$ 的离散区分优势联系起来，从而引入了 $O(q^2)$ 的乘性因子。

这种方法既适用于统计也适用于计算环境，并且至关重要地，它适用于有状态预言机，因为多项式方法分析的是量子态的振幅，而不要求预言机是静态的。

3. 核心贡献与结果

A. 通用不可区分性提升定理

本文建立了一个定理：对于任何（可能是有状态的）两个预言机 $O_0$ 和 $O_1$，如果它们在 $q$ 次量子查询下的不可区分优势为 $\epsilon$，则它们的带密钥版本之间的不可区分优势至多为 $8q^2 \epsilon$。

• 最优性： 作者通过一个特定的构造性预言机选择，证明了 $O(q^2)$ 的损失是优化的，这与标准 Grover 搜索攻击所能达到的优势相匹配。
• 支持有状态性： 与以往的工作不同，该定理适用于有状态预言机，从而能够分析像压缩预言机这样复杂的模拟器。

B. 压缩理想密码

作为直接应用，作者将 Carolan 的压缩置换预言机扩展到了理想密码模型，创建了一个高效可实现的压缩理想密码 (cIC)。

• 构造： 他们定义了一个有状态模拟器，为每个密钥维护一个部分置换数据库。
• 安全界限： 利用提升定理，他们证明了 cIC 与真实理想密码是不可区分的。如果单实例界限为 $\Delta_{cpO}(n, q)$，则 cIC 的界限为 $8q^2 \cdot \Delta_{cpO}(n, q)$。
• 模块化： 作者强调，未来任何对压缩置换预言机单实例界限的改进（例如 Kim [Kim26] 以及 Carolan & Majenz [CM26] 的最新改进）都会自动提升压缩理想密码的界限，而无需重新证明提升过程。

C. Davies-Meyer 的原像抗性

利用压缩理想密码，本文证明了 Davies-Meyer 压缩函数在量子理想密码模型下的原像抗性。

• 结果： 对抗者找到原像的概率被限制在涉及 $q^2/2^n$ 以及压缩理想密码区分优势的项中。
• 技术： 该证明模仿了量子随机预言机模型中的技术，通过逐次查询来界定包含原像查询的压缩数据库的量级。

D. 量子 PRP 的域扩展

本文提出了一个模块化构造，可以将任何量子安全的强伪随机置换 (PRP) 的消息长度从 $n$ 比特扩展到 $2n$ 比特。

• 第一步（PRP 到可调控密码）： 将 PRP 通过 PRF（通过 PRP-PRF 转换引理从 PRP 导出）转换为可调控密码，以生成每个调控值 (tweak) 对应的密钥。提升定理确保了该构造与理想密码是不可区分的。
• 第二步（可调控密码到 $2n$ 比特 PRP）： 使用两轮类 Feistel 构造（使用上述可调控密码）来构建最终的 PRP。
• 分析： 两轮构造的安全性是通过专门的多项式方法论证（独立于提升定理）来证明的，以展示其在量子双向查询下与随机置换的不可区分性。最终的优势界限包含诸如 $O(q^4/2^n)$ 之类的项。

4. 重要性与主张

本文声称其重要性在于为涉及带密钥预言机的量子安全证明提供了一个通用、最优且支持有状态的工具。

• 解决通用障碍： 它解决了在量子环境下将不可区分性从基底预言机提升到带密钥预言机的困难，这一障碍此前要么需要专门的证明，要么会导致松散的界限。
• 最优性： 作者展示了 $O(q^2)$ 的损失在特定情况下是紧致的，与 Grover 搜索下界相匹配，这与以往计算设置中松散的 $O(q^{1.5})$ 或平方根损失形成了对比。
• 赋能有状态分析： 通过支持有状态预言机，这项工作使得对依赖于压缩模拟技术的现代密码原语进行严谨分析成为可能，而这些技术此前难以提升到理想密码模型中。
• 模块化： 提升定理作为一个“黑盒”工具发挥作用。底层基底预言机（例如压缩置换）界限的任何改进，都会立即转化为提升后的带密钥预言机的改进界限，从而简化了未来的研究。

作者认为其方法是对直接分析（如 Carolan 和 Majenz 对理想密码的分析）的补充。虽然直接分析可能会为特定结构提供更紧凑的常数，但提升定理提供了一个适用于任意（且可能是有状态的）基底预言机的通用框架。