💻 computer science

Multi-Input Ciphertext Multiplication for Homomorphic Encryption

本文提出了一种针对同态加密的优化多输入密文乘法方法，该方法通过重构计算、引入额外评估密钥以及采用多级重缩放技术，将输入扩展至两个以上，从而实现了相比先前设计显著降低逻辑面积和延迟的硬件架构。

原作者： Sajjad Akherati, Xinmiao Zhang

发布于 2026-05-19

📖 1 分钟阅读☕ 轻松阅读

原作者： Sajjad Akherati, Xinmiao Zhang

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一位主厨，试图烤制蛋糕，但有一个限制：你必须戴着厚重、隔热的手套进行所有搅拌和烘烤，这让你无法感知食材或看见碗。这就是同态加密（HE）。它允许计算机在“加密”数据（手套中的蛋糕面糊）上执行数学运算，而无需解密（摘下手套）。这能保护秘密安全，无论是你的医疗记录还是银行余额。

然而，戴着这些“手套”进行数学运算极其缓慢且混乱。最大的瓶颈在于乘法。在标准加密中，你一次只能将两种食材相乘。但许多现代任务，例如训练人工智能识别疾病或分析复杂的金融趋势，需要一次性将许多“食材”（密文）相乘。

本文介绍了一种新的、超高效的加密“食材”相乘方法，专门针对一种流行的加密方法CKKS。以下是他们突破的分解，使用简单的类比：

1. 问题：“混乱的厨房”

当你将加密数字相乘时，“噪声”（由烤箱手套产生的混乱）会变得越来越响。如果你一次性相乘太多数字而不进行清理，噪声就会淹没实际数据，导致结果变成垃圾。

为了解决这个问题，加密系统必须在每次乘法后执行一个称为**重缩放（Rescaling）**的“清理”步骤。这就像停下来擦拭台面并将食材归位。

旧方法：如果你需要相乘 10 种食材，旧方法就像一条传送带：相乘两种，停下来清理，再相乘两种，再停下来清理，以此类推。这种方法缓慢且需要大量清洁用品（硬件资源）。
之前的“三种食材”尝试：作者之前的工作表明，你可以一次性相乘三种食材，这更快。但它仍然包含许多不必要的清理步骤。

2. 解决方案：“智能装配线”

作者提出了两项重大升级，使该过程更快、更紧凑：

A. “一步清理”（改进的三输入乘法）

在他们新的三种食材相乘设计中，他们意识到自己以一种笨拙、绕远的方式执行清理（重缩放）和重新排列（重线性化）。

类比：想象你有三碗面糊。旧方法是混合它们，将混合物倒入新碗，清理旧碗，再次倒入混合物，然后再清理。
改进：他们重新设计了流程，使混合和清理可以在一个流畅的动作中完成。他们找到了合并清理步骤的方法，因此你不必如此频繁地停下来擦拭台面。
结果：与之前的最佳设计相比，他们新的“三碗混合器”速度快了50%（延迟），在芯片上占用的空间减少了15%（面积）。

B. “分组清理”（多输入乘法）

如果你需要一次性相乘四种、五种甚至十二种食材怎么办？

旧方法：你会建立一条长长的“双碗混合器”生产线。混合两种，清理，再混合两种，清理，然后混合结果，再次清理。这会形成一条非常长的生产线（高“乘法深度”），意味着噪声积累过快。
新策略：作者意识到，如果你以不同的方式分组食材，就可以进行**“分组清理”**。
- 他们开发了一种数学技巧（称为多重重缩放 Multi-Rescaling），允许你等待并一次性清理多层混乱，而不是在每一步之后都清理。
- 类比：想象你在洗碗。旧方法是洗一个盘子，擦干，收起来，然后洗一个杯子，擦干，收起来。新方法则是洗一整摞盘子，然后擦干整摞，最后全部收起来。你只为整个组执行一次“擦干”（昂贵且缓慢的部分）。
结果：通过重新安排分组方式（“划分”），他们可以合并这些清理步骤。对于相乘 4 到 12 种食材，与旧的“两两”生产线相比，他们的新方法节省了32%的空间，并将时间缩短了一半（快了45%）。

3. 为什么这很重要（根据论文）

该论文严格专注于硬件架构——即执行这些数学运算的计算机芯片的物理设计。

他们证明，通过改变数学的组织方式（算法）和芯片的构建方式（架构），可以更快地执行复杂的加密数学运算。
他们特别提到，这有助于机器学习、医疗诊断和金融分析等应用，因为这些领域通常需要将许多加密数据点相乘。

总结

将这篇论文想象为为一名无法摘下烤箱手套的主厨发明了一个新的、超高效的厨房。

他们找到了如何一次性混合三种食材而不弄乱的方法。
他们发明了一种同时清理多层混乱的方法，而不是一次清理一层。
结果是一个更小、更快、且能耗更低的厨房，能够在执行复杂数学运算的同时保护秘密安全。

作者在这篇论文中并未在真实患者或真实银行账户上测试此方法；他们仅证明了设计用于执行此项工作的机器显著优于我们之前的机器。

技术摘要：同态加密的多输入密文乘法

问题陈述
同态加密（HE），特别是 RNS-CKKS 方案，支持在加密数据上进行算术运算，这对于机器学习和医疗诊断等隐私保护应用至关重要。然而，标准的同态加密方案仅定义了两个输入之间的密文乘法。许多实际应用，例如用于神经网络激活函数（如 ReLU）的高阶多项式近似、决策树以及基因组测序，都需要对多个密文（ $n > 2$ ）进行乘法运算。

现有的处理多输入乘法的方法通常将多个双输入乘法器以二叉树结构串联。这种方法存在两个主要低效之处：

高延迟与面积开销：使用双输入单元依次对 $n$ 个密文进行乘法运算，会导致显著的硬件开销和延迟。
噪声增长与重缩放开销：每次乘法都会增加噪声水平，因此需要执行重缩放操作以恢复消息尺度。在标准二叉树中，为了防止噪声呈指数级增长，必须在每次乘法步骤后执行重缩放。这导致需要大量的重缩放单元，每个单元都需要昂贵的数论变换（NTT）和逆数论变换（INTT）操作，从而显著增加了计算复杂度和硬件资源占用。

方法论
本文提出了一种直接进行 $n$ 输入密文乘法的框架，旨在最小化乘法深度和硬件复杂度。该方法分为两个主要贡献：

改进的三输入乘法器：
作者首先重构了三输入乘法过程。在前期工作 [26] 中，重线性化和重缩放是分开执行的，这需要多次 ModUp/ModDown 操作和大量的 (I)NTT 模块。新设计：
- 重构重线性化：通过将 $P^{-1}$ 缩放因子移至基转换（BConv）和评估密钥乘法中，消除了独立的缩放步骤。
- 优化重缩放：作者重构了数据路径，在最终 NTT 之前的原始域中执行重缩放，而不是在 NTT 域中执行。这使得能够消除冗余的 (I)NTT 操作。
- 结果：这些变化将数据路径中的 (I)NTT 模块数量从八个减少到四个，有效地将数据路径长度减半。
结合重缩放的多输入扩展：
为了在不增加乘法深度的情况下将乘法扩展到 $n > 3$ 个输入，本文引入了：
- 广义评估密钥：引入新的评估密钥（ $ek_t$ ）以对由 $n$ 个密文相乘生成的更高阶多项式项（ $d_t s^t$ ）进行重线性化，将结果还原为双多项式格式。
- 多重缩放（Multi-RS）算法：理论分析确定了可以延迟并合并多个重缩放操作的条件。作者提出了一种算法，使用与单次重缩放相同数量的 (I)NTT 操作来执行 $\mu$ 次级联的重缩放操作。这是通过将输入转换到 INTT 域，在系数域中执行迭代重缩放，然后转换回来，并利用预计算常数合并操作来实现的。
- 输入划分指南：本文提供了将 $n$ 个输入划分为组（例如 $(n_1, n_2, \dots, n_m)$ ）的指南，以在保持最优乘法深度 $\lceil \log_2 n \rceil$ 的同时，最大化可合并的重缩放操作数量。这涉及尽可能创建不平衡的树结构，以便在重缩放步骤之前对更多输入进行分组。

主要贡献

算法重构：提出了一种新的三输入乘法公式，通过合并中间计算，减少了 (I)NTT 操作的数量并缩短了数据路径。
多输入框架：利用广义评估密钥和树状结构乘法器，将密文乘法扩展至任意 $n$ 个输入。
结合重缩放：一种新颖的多重缩放算法，将执行多次重缩放的复杂度降低至单次重缩放的复杂度，无论合并步骤的数量（ $\mu$ ）是多少。
硬件架构：为所提出的乘法器设计了全流水线硬件架构，包括优化的 ModUp、ModDown 和重缩放单元。

结果
所提出的设计使用 GlobalFoundries 22FDX 工艺进行了综合，参数为 $N=2^{16}$ ， $L=K=24$ ， $w=64$ 。

三输入乘法器：与前期工作 [26] 相比，改进的三输入乘法器实现了逻辑面积减少 15% 和延迟减少 50%。由于 (I)NTT 单元数量减少，内存需求也减少了约 20%。
多输入乘法器（ $n=4$ 到 $12$）：与使用双输入乘法器二叉树的基准实现相比，所提出的方法实现了平均 32% 的总面积减少 和 45% 的延迟减少。
重缩放效率：对于非 2 的幂次输入（例如 $n=17$ ），优化的划分结合多重缩放，与标准二叉树方法相比，将重缩放单元总数（及相关 (I)NTT 操作）减少了约 47%。

意义
本文声称，这些改进解决了同态加密中多输入乘法的瓶颈问题，这对于复杂的隐私保护应用至关重要。通过降低密文乘法的硬件复杂度和延迟，所提出的架构使得在资源受限或高吞吐量环境中部署同态加密变得更加可行。这项工作表明，通过算法重构和仔细的输入划分，可以在不牺牲加密方案安全性或正确性的前提下，显著最小化噪声管理（重缩放）的开销。作者指出，未来的工作将专注于进一步简化针对更大数量输入的乘法器。

1. 问题：“混乱的厨房”

2. 解决方案：“智能装配线”

A. “一步清理”（改进的三输入乘法）

B. “分组清理”（多输入乘法）

3. 为什么这很重要（根据论文）

总结

类似论文