技术摘要：基于置换的类 Shearer 不等式的非自适应密码分析时空下界

1. 问题陈述与动机

本文研究了在预处理（非均匀）模型中，适应性在密码分析时空权衡中的威力。在该模型中，攻击者由两个阶段组成：预处理阶段根据问题实例生成一个长度为 $S$ 比特的建议字符串，随后是在线阶段，利用 $T$ 次预言机查询和建议字符串解决特定挑战。

尽管许多最先进的密码分析算法（例如用于离散对数的 Pollard Rho 算法、针对 Even-Mansour 的适应性攻击）严重依赖适应性（即查询依赖于先前的预言机响应），但非自适应算法（即查询预先固定，可能仅依赖于建议字符串）是否能达到类似的效率尚不清楚。针对这些问题的先前下界技术通常无法区分自适应和非自适应算法，往往得出的界限过于薄弱，无法证明适应性提供了显著优势。

作者解决了 Corrigan-Gibbs 和 Kogan [CK19] 提出的问题：非均匀密码分析算法中适应性的威力有多大？ 具体而言，他们的目标是证明精确的下界，表明在预处理设置下，针对基础密码学问题，非自适应算法无法匹敌自适应算法的效率。

2. 方法论与技术框架

2.1 置换挑战 (PC) 模型

为了统一分析各种问题（离散对数、DDH、sqDDH 以及 Even-Mansour 密钥恢复），作者引入了置换挑战 (PC) 模型。

• 结构：该模型涉及一个“内部置换” $\sigma: [N] \to [N]$ 和一个秘密值 $d$。
• 查询：攻击者进行两种类型的查询：
  1. 内部查询：直接访问 $\sigma$（或 $\sigma^{-1}$）。
  2. 外部查询：访问由翻译函数 $tr(d, m)$和后处理函数$post(d, \cdot)$定义的“外部函数”。查询$m$通过$tr$被转换为$\sigma$ 的输入，输出随后被后处理。
• 非适应性定义：如果一个算法的预翻译查询（即 $m$ 值和内部查询索引）是基于建议字符串 $z$ 预先固定的，而不依赖于特定挑战 $d$ 或 $\sigma$ 的输出，则该算法是非自适应的。关键在于，由于翻译函数的存在，对 $\sigma$ 的实际预言机查询可能依赖于 $d$，这使得该模型能够捕捉经典的非自适应算法（如大步小步法）。

2.2 信息论工具

证明的核心依赖于应用于置换空间 $S_N$ 上分布（而非乘积空间）的信息论工具。

• 置换的 Shearer 引理：作者利用了一种针对随机双射的 Shearer 引理变体（源自 Barthe 等人 [BCELM11] 以及 Caputo 和 Salez [CS24]）。该不等式将置换上分布的 Kullback-Leibler (KL) 散度与其在索引子集上的边际分布的 KL 散度联系起来。
• 读-$k$ 族的集中不等式：他们推导了针对置换上函数族的集中界，其中每个函数依赖于一个“读-$k$"变量集（每个坐标最多被 $k$ 个函数访问）。这将 Gavinsky 等人 [GLSS15] 的结果从乘积空间扩展到了双射空间。
• 翻译的均匀性：一个关键的技术条件是翻译函数 $tr$必须是**$u$-均匀**的。这意味着对于任何固定的外部查询，当秘密$d$均匀选择时，生成的置换输入在$[N]$ 上近似均匀分布。

2.3 证明策略

主定理（定理 4.1）通过将非自适应预处理攻击者的成功概率与非预处理攻击者的成功概率联系起来，对其进行了界定。

1. 混合论证：证明引入了一个“中间博弈”，攻击者可以固定有限数量的置换值（模拟内部查询），但其余部分均匀采样。
2. KL 散度分析：通过对建议字符串进行条件化，作者分析了预处理设置中置换分布与均匀分布之间的 KL 散度。
3. 类 Shearer 界限的应用：利用翻译函数的 $u$-均匀性，他们证明了翻译后的外部查询集合构成了一个读-$k$ 族。集中不等式（定理 1.9）随后界定了从建议字符串中获得的优势，表明除非建议字符串足够大（$S \gg \sqrt{N}$），否则成功概率无法显著超过非预处理算法的成功概率。

3. 主要贡献与结果

本文确立了精确下界，证明了在预处理模型中，适应性为多种密码学问题提供了显著优势。

3.1 离散对数 (DLOG)

• 结果：对于素数阶 $N$ 的通用群，任何带有预处理的非自适应 $(S, T)$-算法的成功概率被界定为：
  $$\text{Success} \le 2 \cdot \text{Max}_{S}^{\text{DLOG}}(T) + \frac{4 \log(2) ST}{N} + \frac{T^2}{N}$$
  其中 $\text{Max}_{S}^{\text{DLOG}}(T) \le T^2/N$ 是非预处理算法的界限（Shoup [Sho97]）。
• 推论：非自适应大步小步算法的在线时间复杂度 $T = O(\sqrt{N})$ 无法通过预处理得到改进，除非建议字符串大小 $S$ 超过 $\Omega(\sqrt{N})$。这与自适应算法（例如 Mihalcik [Mih10]、Bernstein 和 Lange [BL13]、Corrigan-Gibbs 和 Kogan [CK18]）形成鲜明对比，后者实现了 $ST^2 = \tilde{O}(N)$ 的权衡，允许在 $S = \tilde{O}(N^{1/3})$ 时达到 $T = O(N^{1/3})$。

3.2 判定性 Diffie-Hellman (DDH) 和 sqDDH

• 结果：针对 DDH 和 sqDDH 推导出了类似的界限。对于 sqDDH，该界限是精确的，并且与自适应算法的一个简单非自适应变体相匹配。对于 DDH，作者推测该界限并不紧，并提出最优界限为 $1/2 + \tilde{O}(T^2/N + ST/N)$。
• 推论：对于这些判定性问题，非自适应预处理并未提供像自适应预处理那样的权衡改进。

3.3 Even-Mansour (EM) 密码系统

• 结果：针对 Even-Mansour 密码的密钥恢复攻击，无界预处理并不能加速非自适应攻击（除非 $S \ge \tilde{\Omega}(\sqrt{N})$）。
• 推论：这与自适应攻击（例如 Fouque、Joux 和 Mavromati [FJM14]）形成鲜明对比，后者可以在 $S = \tilde{O}(2^{n/3})$ 时实现 $T = \tilde{O}(2^{n/3})$ 的在线复杂度。非自适应下界证实，自适应攻击中的内存减少根本上依赖于适应性。

4. 意义与局限性

意义

• 适应性的形式化证明：本文提供了首个形式化证明，表明在预处理模型中，为了实现 DLOG 中的次 $\sqrt{N}$ 时间复杂度和 Even-Mansour 密钥恢复中的次 $2^{n/3}$ 复杂度，适应性是不可或缺的。
• 新技术工具：在算法背景下应用置换的类 Shearer 不等式（定理 1.8）是一项新颖的贡献。作者指出，这是此类变体首次被用于该领域的下界论证。
• 统一模型：置换挑战模型成功抽象了广泛的搜索和判定问题，允许对其非自适应时空权衡进行集体分析。

局限性与开放问题

• 依赖挑战的查询：证明策略依赖于预翻译查询与挑战的独立性。若要扩展这些结果以允许依赖于挑战的预翻译查询（例如 $f(d + f(d))$），则需要新的集中不等式，因为当前的类 Shearer 界限无法有效处理此类组合输入。
• 自适应轮次：本文留下了刻画具有特定适应性轮次 $r$ 的自适应算法的时空权衡问题。作者推测界限为 $\tilde{O}(T^2/N + rST/N)$。
• DDH 的紧性：非自适应 DDH 的下界被推测为松散，作者认为真实界限可能比证明的界限更紧。

本文结论指出，之前的通用技术（压缩论证、预采样、标准集中不等式）在区分自适应和非自适应算法方面存在固有局限，对自适应界限的改进最多仅为多对数因子。本文提出的新信息论方法克服了这一障碍，适用于所分析的非自适应算法特定类别。