技术摘要：基于 LWE/LPN/CDH 的 NC1 类伪随机函数

1. 问题陈述

构建具有低并行复杂度（具体而言是在 NC1 类中，即由多项式大小、对数深度的电路计算）的伪随机函数（PRFs）是密码学领域一个长期的开放问题。虽然可以通过 Goldreich-Goldwasser-Micali (GGM) 变换从伪随机生成器 (PRGs) 通用地构造 PRF，但这种方法本质上是顺序性的。即使底层的 PRG 是在对数深度内可计算的，生成的 PRF 也需要 $\omega(\log n)$ 的深度，从而使其脱离了 NC1 类。

在此项工作之前，已知的 NC1 可计算 PRF 非常稀少，且依赖于高度特定的代数结构或强假设：

• Naor-Reingold (1997, 2004)： 从判定型 Diffie-Hellman (DDH) 和分解问题构造了 $TC_0 \subseteq NC1$ 中的 PRFs。
• Banerjee-Peikert-Rosen (2012)： 从 Ring-LWE 构造了 $TC_0$ 中的 PRFs，但要求超多项式的模数与噪声比例（modulus-to-noise ratio）。
• Ding-Jain-Komargodski (2025)： 从结构化变体形式的 Learning Parity with Noise (LPN)，例如 SeededLPN 或 Ring-LPN，构造了 PRFs。

核心挑战在于如何从标准假设（具有多项式模数与噪声比例的标准 LWE、标准 LPN 以及计算型 Diffie-Hellman）实现 NC1 可计算的 PRFs，而不依赖于结构化变体或超多项式参数。

2. 方法论

本文引入了一种双管齐下的方法：一种从弱伪随机函数 (WPRFs) 到强 PRFs 的通用深度保持变换，以及基于标准假设的新型深度高效 WPRF（或合成器）构造。

2.1 Tapering-GGM：一种通用变换

作者提出了一种对 GGM 树构造的新颖改进，称为 Tapering-GGM，它可以在升级 WPRF 到强 PRF 的同时保持评估电路的深度。

• 渐缩机制 (The Tapering Mechanism)： 在标准的 GGM 树中，状态大小保持不变，且深度随树层数 $\ell \cdot d_{WPRF}$ 线性累积。在 Tapering-GGM 中，状态大小在每一层呈几何级数缩小。如果第 $i$ 层的安全参数为 $\lambda^{(i)}$，作者定义 $\lambda^{(i)} = \lambda^{2^{-i+1}}$。因此，第 $i$ 层 WPRF 的调用深度 $d(\lambda^{(i)})$ 呈几何级数递减。
• 深度分析： 如果基础 WPRF 的深度为 $d(\lambda) = \Theta(\log \lambda)$，则 Tapering-GGM 构造的总深度为：
  $$d_{total} = O(\log \lambda) + \sum_{i=1}^{\ell} d(\lambda^{(i)}) \approx O(\log \lambda) + \sum_{i=1}^{\ell} \log(\lambda^{2^{-i+1}}) = O(\log \lambda)$$
  这种几何级数衰减确保了总深度保持为 $O(d(\lambda))$，使得该构造在输入 WPRF 属于 NC1 的情况下仍保持在 NC1 内。
• 安全性挑战与解决方案：
  • 挑战： 随着树的加深，安全参数 $\lambda^{(i)}$ 会变得很小（亚多项式级别），这可能会破坏底层 WPRF 的计算安全性。
  • 解决方案 1（哈希）： 输入首先通过一个两两独立的哈希函数进行哈希处理。这确保了以高概率，攻击者的查询被“粉碎”（映射到不同的路径）在顶部的 $O(\log_\Delta q)$ 层内，此时安全参数仍为多项式级别。
  • 解决方案 2（密钥均匀性）： 对于低于粉碎点的层，构造依赖于信息论安全性。作者要求 WPRF 是密钥均匀的（1-wise independent）。如果粉碎层的状态是伪随机的，那么随后由密钥均匀变换组成的序列会将该状态映射为完全均匀的输出，无论底层 WPRF 的计算难度如何。

2.2 深度高效的 WPRF 构造

作者使用来自标准假设的新型 WPRF 构造来实例化 Tapering-GGM 框架：

• 来自 LWE (Learning With Errors)：

  • 作者构造了第一个来自具有多项式模数与噪声比例 ($\alpha = n^{-\epsilon}$) 的标准 LWE 的 NC1 WPRF。
  • 关键技术工具： 一个可在 $O(\text{poly}(\log \log \lambda))$ 深度内计算的舍入高斯采样器 (Rounded Gaussian Sampler)。他们利用低深度的多项式逼近（针对 $\ln$、$\cos$ 和平方根的牛顿迭代）来近似 Box-Muller 变换。
  • 构造： 他们采用了一种链式范式（受 Kim [Kim20] 启发）。该构造逐层计算掩码 LWE 内积。前一层输出的高位比特决定性地为下一层采样误差分布。误差采样器的有界性确保了稳定性，使得可以通过混合方法（hybrids）进行安全性证明。

• 来自 LPN (Learning Parity with Noise)：

  • 作者利用了 Ding, Jain, 和 Komargodski [DJK25] 最近的一项结果，该结果提供了来自标准 LPN（任意反多项式噪声）的 NC1 WPRFs。
  • 通过将此结果与 Tapering-GGM 结合，他们获得了首个来自标准 LPN 的 NC1 PRFs，消除了先前工作中对结构化变体（如 Ring-LPN）的需求。

• 来自 CDH (Computational Diffie-Hellman)：

  • 作者观察到 Tapering-GGM 实际上需要一种比 WPRF 更弱的原语：合成器 (Synthesizer)（其中输入池对攻击者是隐藏的）。
  • 他们使用 Naor-Reingold 合成器构造 [NR95, NR99] 来实例化该变换，该构造在 CDH 假设下是 NC1 可计算的。这产生了首个来自 CDH 的 NC1 PRFs，优于之前的 DDH 基构造。

3. 核心贡献

1. 通用深度保持变换： 一种黑盒变换，可以将任何在深度 $d(\lambda) = \Omega(\log \lambda)$ 内可计算的 WPRF（或合成器）转换为在深度 $O(d(\lambda))$ 内可计算的强 PRF。这解决了阻碍标准假设实现 NC1 PRFs 的通用障碍。
2. 来自标准 LWE 的 NC1 PRFs： 首次构造了来自具有多项式模数与噪声比例 $\alpha = n^{-\epsilon}$ 的标准 LWE 的 NC1 WPRF，解决了 Vaikuntanathan 讲义中明确提出的开放问题。这依赖于 GapSVP 在多项式逼近因子下的硬度。
3. 来自标准 LPN 的 NC1 PRFs： 首次构造了来自标准 LPN 假设的 NC1 PRFs，不再需要像 Ring-LPN 或 Sparse LPN 这样的结构化变体。
4. 来自 CDH 的 NC1 PRFs： 首次构造了来自计算型 Diffie-Hellman (CDH) 假设的 NC1 PRFs，改进了依赖于更强判定型 Diffie-Hellman (DDH) 的 30 年前的 Naor-Reingold 结果。
5. 低深度高斯采样器： 一个用于在 $O(\text{poly}(\log \log \lambda))$ 深度内采样舍入高斯误差的新型确定性电路，这是基于 LWE 的 WPRF 的关键组成部分。

4. 结果

本文确立了以下具体结果：

• 定理： 如果存在 NC1 中的 WPRFs，那么就存在 NC1 中的 PRFs。
• 推论 (LWE)： 假设 LWE 假设在噪声与模数比例 $\alpha = n^{-\epsilon}$ 下成立，则存在 NC1 中的 PRFs。
• 推论 (LPN)： 假设 LPN 假设在噪声概率 $\mu = n^{-\epsilon}$ 下成立，则存在 NC1 中的 PRFs。
• 推论 (CDH)： 假设 CDH 假设成立，则存在 NC1 中的 PRFs。
• 推论 (GapSVP)： 假设 GapSVP 在 $\tilde{O}(n^{1+\epsilon})$ 因子内难以近似，则存在 NC1 中的 PRFs。

5. 意义

本文声称解决了密码学原语复杂度中的几个长期开放问题。通过将 PRF 评估的深度与 GGM 变换的顺序性质解耦，作者证明了可以从广泛的标准假设构造强 PRF，而不会牺牲并行效率。

具体而言，这项工作：

• 消除了对用于 NC1 PRFs 的 Ring-LWE 和超多项式参数的依赖，转向了具有多项式参数的标准 LWE。
• 消除了对结构化 LPN 变体的依赖，转向了标准 LPN。
• 将基于 CDH 的 PRF 的硬度假设从 DDH 弱化到了 CDH。
• 提供了一个通用框架 (Tapering-GGM)，可以将任何现有的对数深度 WPRF 候选者（例如来自 [ABG+14], [AR16]）升级为对数深度的 PRF，只要底层假设成立。

作者将这项工作定位为理解密码学并行复杂性的重要一步，这对安全计算协议、学习理论（通过 PRF 与学习之间的联系）以及元复杂度（meta-complexity）具有重要意义。