如何为全同态加密构造电路特定的解密密钥 part 4

自从去年提出 Diamond iO 论文及其部分实现以来，我们一直致力于从理论和工程角度提高 BGG+ 编码的效率。我们相信这一方向将使 Diamond iO 能够应用于更大规模输入和更复杂电路，如我们的路线图所示。

所有代码均可在我们的 mxx 仓库 中找到。

GPU 实现

我们为 BGG+ 编码和基于格的 iO 的基础操作开发了 GPU 实现。具体包括：

• 多项式的算术运算与数字分解，
• 多项式矩阵的算术运算，以及
• 原像采样。

与 CPU 实现相比，GPU 实现的多项式矩阵乘法获得了约 1000 倍的加速，原像采样获得了约 20 倍的加速。

基于 BGG+ 编码的新型查找表评估

去年，我们引入了一种在编码上评估查找表（LUT）的新技术 [ SB25 ]。然而，对于大型电路而言，这仍然远未达到实用程度。其中一个瓶颈是：设 T 为 LUT 的大小，GL 为评估该 LUT 的门数量，那么由可信方生成的评估密钥（作为混淆电路的一部分）必须包含 O(TM) 个格原像。

为了解决这一瓶颈，我们构建了一种新的 LUT 评估技术，将原像数量减少到 O(T+GL)。我们相信，该构造在 LWE 假设和私密币 evasive LWE 假设下是安全的。

在大参数下评估 BGG+ 编码上的模 q 乘法

利用新的 LUT 评估技术，我们成功地在 BGG+ 编码上评估了模 q 乘法，其中 q 是编码模数 Q 的一个素因子，约为 24 位。评估所使用的参数足够大，足以保证正确性和安全性；特别地，环维度 n=2^14，编码模数大小 log2 Q = 264 位。然而，编码模数大小仅基于正确性进行选择，因此实际模数大小可能需要更大以确保安全性（例如，用于噪声泛洪）。

使用 8 块 GPU（RTXPro 6000）并行运行，预处理（对应于 iO 中的混淆）耗时约 1.5 小时，在线评估（对应于混淆电路评估）在一分钟内完成。预处理输出大小（对应于混淆电路的一部分）为 731 GB。

值得注意的是，我们确认了预处理的瓶颈——所有 LUT 条目（实验中为 23,114 个条目）的原像采样——具有良好的并行性。这意味着通过增加相同 GPU 的数量可以缩短预处理时间。

BGG+ 编码上的槽位操作

为了最终支持 FHE 乘法，我们将 BGG+ 编码上的模 q 乘法扩展到了多项式乘法。为此，BGG+ 编码必须支持单独编码多项式每个评估槽的值，以及跨槽转换值的槽位转移操作。

为了在不增加 LUT 预处理输出大小（随槽位数增长）的情况下实现这些新特性，我们引入了一种 BGG+ 编码变体，其中公钥在所有槽位间共享，而私钥则特定于每个槽位。此外，通过引入跨不同槽位切换私钥的机制，我们实现了该变体编码的槽位转移。槽位转移的预处理数据大小以 O(NGS) 为界，其中 GS 是槽位转移门的数量，N 是槽位数，即环维度。

BGG+ 编码上的 GSW FHE 乘法

通过结合以上所有新技术，我们成功实现了一个可以在 BGG+ 编码上评估的 GSW FHE 评估电路。作为具体示例，我们通过以加密种子的编码为输入计算 Goldreich 的 PRG 来测量基准测试性能。

评估在单块 H200 GPU 上进行，环维度 n=2^16，模数大小 log2 Q = 1120 位。由于电路规模和总计算成本过大，无法完成完整计算，因此我们仅评估了最小的可并行化单元，例如每个电路层中单个门的评估，并通过将这些测量结果乘以相应并行计算单元的数量来估算基准测试结果。

估算的基准测试结果如下：

• 在预处理（对应于 iO 中的混淆）中，当 GPU 数量超过 10^12 时，最小延迟为 10 分钟。
• 在线评估（对应于 iO 中的评估）中，当 GPU 数量超过 10^18 时，最小延迟为 51 分钟。

• 原文链接： machina-io.com/posts/cir...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～