💻 computer science

Low-Latency Bootstrapping for CKKS using Roots of Unity

本文介绍了稀疏单位根（SPRU），这是一种针对 CKKS 同态加密方案的新型自举算法，它将模运算嵌入到复数单位根中，以显著降低乘法深度，并实现相比传统方法高达 5 倍的延迟改善。

原作者： Jean-Sebastien Coron, Robin Koestler

发布于 2026-07-31

📖 1 分钟阅读☕ 轻松阅读

原作者： Jean-Sebastien Coron, Robin Koestler

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

想象一下，你正试图给一位朋友发送一条秘密信息，但你不能信任邮局。你把信锁在一个盒子里，但邮局需要对它进行分类、堆叠，甚至可能为了检查地址而打开它，但它永远无法看到里面的内容。这就是**全同态加密（Fully Homomorphic Encryption, FHE）**的魔力。它允许计算机对仍处于加密锁定状态的数据进行计算。这就像一个神奇的厨房，你可以使用仍然装在密封、未开封包装里的食材来烘焙蛋糕；烤箱完成了工作，当你最后打开盒子时，你会得到一个新鲜的蛋糕，但烤箱从未知道这些食材是什么。

然而，这里有一个问题。每当计算机对这些锁定数据进行一次数学运算时，盒子里就会增加一点“噪声”或静电，就像镜头上落下的灰尘。如果你进行太多次计算，噪声就会变得如此大，以至于信息变得模糊且无法读取。为了解决这个问题，科学家们使用了一个叫做**自举（bootstrapping）**的过程。这就像是一个神奇的重置按钮：计算机拿起那个带有噪声的锁定盒子，执行一个复杂的技巧来清除灰尘，然后将信息放回一个全新的、干净的盒子里，以便继续进行计算。问题在于，这个清洁技巧极其缓慢且沉重，就像是用牙刷洗车一样。它消耗了如此多的计算能力，以至于让实际应用显得非常迟缓。

这正是 Jean-Sébastien Coron 和 Robin Köstler 的一篇新论文所切入的点。他们引入了一种巧妙的新方法来执行这种“清洁”过程，称为稀疏单位根（Sparse Roots of Unity, SPRU）自举。与其使用旧的、笨重的近似复杂曲线（比如正弦波）的方法，他们发现了一种直接将数据映射到被称为“单位根”的数字圆环上的方法。想象一下，与其用牙刷刷车，不如直接把车滑到一个巨大的旋转木马上，随着它的转动自然地擦掉灰尘。他们的这种方法更快、更轻量，尤其是当你同时处理少量数据项时。通过使用这种新方法，他们展示了重置加密所需的时间可以比标准方法减少高达 5 倍，这使得秘密计算的魔力看起来更像是一个现实，而非遥远的梦想。

旧的方法：重型搬运工

要理解为什么这个新技巧如此特别，让我们看看旧方法是如何工作的。在标准的 CKKS 加密方案（最流行的用于处理小数的方案）中，自举过程就像是试图通过在山峦之上画一条平滑的线来猜测山的形状。计算机必须评估一个复杂的多项式（一个高级数学公式）来近似一个“模约减（modular reduction）”。你可以把模约减理解为一种将长数轴包裹成一个圆环，使其能放回一个小盒子里的方式。旧方法试图画一条正弦波（一条波浪线）来模仿这个包裹过程。

虽然这行得通，但却是一项繁重的任务。它需要深层的数学运算堆栈，这意味着计算机必须使用一个非常大的“环维度”（衡量数学游乐场大小的指标）。这就像是背着一个沉重的背包跑马拉松；它减慢了速度，并限制了重置后能进行的有用工作量。作者指出，这种高“乘法深度”（你需要经过的数学层数）是主要的瓶颈，使得该过程对于实际用途来说过于缓慢，尤其是在你只需要处理少量数字时。

新的方法：单位根的旋转木马

作者的新想法——SPRU 自举——通过跳过沉重的近似过程改变了游戏规则。他们不再试图通过画一条波浪线来模仿包裹过程，而是意识到他们可以直接将数据嵌入到“单位根”中。

这里有一个简单的类比：想象旧方法是试图通过为每一个字母编写一段冗长复杂的字典条目来翻译秘密代码。这太慢了。而新方法是意识到这个秘密代码实际上只是一组完美契合特定锁具的钥匙。与其进行翻译，你只需转动钥匙。

从技术层面来说，他们直接将加法群（数字相加的方式）映射到复数单位根（复数系统中的圆周点）中。由于 CKKS 加密方案原生就能理解这些复数，计算机可以直接执行“清洁”操作，而无需近似正弦波。这就像是从用单独的砖块搭建桥梁，转变为使用一个完美契合的预制拱门。

秘诀：稀疏性与打包

论文不仅引入了新的映射方式，还引入了两个巧妙的优化，使其在处理少量数据槽位（例如列表中的几个数字）时更加快速。

比特打包（Packing the Bits）： 在过去，如果你有一个包含 1,000 个比特的密钥，计算机必须逐个处理这些比特。作者意识到可以将这些比特“打包”进加密槽位中，就像把 1,000 封信塞进一个单一且高效的超级邮箱里。这减少了所需的重度计算次数，从海量减少到了仅为对数级别（可以理解为将一份长清单缩减为一个简短的摘要）。
稀疏块技巧（The Sparse Block Trick）： 他们还假设密钥具有特殊的结构：密钥不是随机比特，而是被分为若干块，其中每个块中只有一个比特是“1”，其余都是“0”。这就像有一排电灯开关，每组十个开关中只有一个是开启状态。通过使用这种“稀疏”结构，他们可以用简单的加法步骤取代许多困难的乘法步骤。这与从计算一长串数字的乘法变为仅仅加法几个数字的区别。这进一步降低了计算的“深度”，从一座高塔变成了一个小阶梯。

结果：加速魔法

作者使用 OpenFHE 库（一个构建加密软件的流行工具）测试了他们的新方法。他们将 SPRU 自举与原始的笨重方法进行了对比。

结果令人瞩目，特别是在特定场景下。当处理具有少量槽位的密文时（这在许多实际应用中很常见），他们的新方法速度提升了高达 5 倍（延迟降低了 5 倍）。这是一个巨大的进步，因为这意味着“重置按钮”不必等待那么久，从而让计算机能更快地回到有用的工作中。

然而，论文也谨慎地指出，这并不是解决所有问题的万灵药。如果你试图处理海量的槽位（一个巨大的数据集），原始方法可能仍然更有效。但在处理较小批量数据的许多情况下，这种新方法提供了显著的加速。

为什么这很重要

这项工作的精妙之处在于，它不仅仅是微调了数字，而是从根本上改变了我们对自举过程的思考方式。通过放弃沉重的多项式近似，并拥抱加密方案的原生能力，作者们表明我们可以让全同态加密变得更加实用。

他们证明了，通过使用这些“单位根”和智能打包技术，我们可以显著减少保持加密数据可用性所需的计算时间和计算能力。虽然论文侧重于技术细节和背后的数学原理，但其核心结论是明确的：通过这种方式，我们可以让处理秘密数据的梦想离现实更近一步。作者们提供了一种更轻、更快速的方法来保持这份魔力，使得未来你的私人数据可以在云端被处理，而无需被看见，也无需等待永恒的结果，这成为了可能。

技术摘要：基于单位根的低延迟 CKKS 自举技术

问题陈述

CKKS 同态加密方案支持对复数进行近似算术运算，使其适用于安全机器学习和云计算。然而，CKKS 的一个关键瓶颈在于**自举（bootstrapping）**过程，该过程需要刷新密文以实现无限的计算深度。

原始的 CKKS 自举方法 [CHK+18a] 依赖于同态评估模约减函数的多项式近似（具体为缩放的正弦函数）。这种方法存在两个主要缺陷：

高乘法深度： 多项式近似需要一个很深的电路，这导致需要较大的密文模数。
对小槽数（Slot Count）效率低下： 原始方法的复杂度随槽数 ( $n$ ) 和环维度 ( $N$ ) 缩放，通常需要 $O(\log n + \log N)$ 次操作。这种高深度迫使使用更大的环维度以维持安全性，从而导致增加了延迟。

作者指出，需要一种能够降低乘法深度、从而允许使用更小的环维度并显著降低延迟（特别是对于具有少量槽数的密文）的自举算法。

方法论：稀疏单位根 (SPRU)

本文引入了 稀疏单位根 (SPRU) 自举，这是一种全新的算法，从根本上改变了 CKKS 中执行模约减的方式。

核心概念：原生嵌入

SPRU 自举不再通过正弦函数来近似模约减，而是直接将加法群 $\mathbb{Z}_q$ 嵌入到复数单位根的乘法群中。作者利用了同态映射：
$f: \mathbb{Z}_q \to \mathbb{C}, \quad x \mapsto \exp(2i\pi \cdot x/q)$

对于 LWE 风格的解密方程 $m = \langle s, c \rangle \pmod q$ ，作者观察到：
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} \exp(2i\pi \cdot c_k s_k / q)$
由于密钥位 $s_k \in \{0, 1\}$ 起到了选择器的作用，该乘积可以重写为：
$\exp(2i\pi \cdot m/q) = \prod_{k=0}^{N-1} (1 + (\exp(2i\pi \cdot c_k/q) - 1) \cdot s_k)$
通过分离虚部并应用线性缩放因子，可以恢复原始消息 $m$ 。该方程可以在不使用正弦函数多项式近似的情况下，在 CKKS 方案内进行同态评估。

关键优化

为了使该方法具有实用性，作者引入了两个关键优化措施：

打包密钥位 (Packing Secret-Key Bits)：
作者没有单独加密每个密钥位，而是将 $N$ 个比特打包进两个 CKKS 密文的 $N/2$ 个槽中。项 $(\exp(2i\pi \cdot c_k/q) - 1)$ 也进行了类似的打包。这些项的乘积通过乘法算子 ( $Pr_{N/2 \to 1}$ ) 计算，将同态乘法的次数从 $O(N)$ 降低到 $O(\log N)$ 。
稀疏块密钥 (Sparse Block Secret Key)：
作者假设了一种结构化密钥 $s$ ，它被分为 $h$ 个大小为 $B = N/h$ 的块，每个块中恰好包含一个非零位（即“1”）。这种结构允许将块内的乘积替换为求和。
- 块内的求和通过迹算子 ( $Tr_{N/2 \to h}$ ) 计算，该算子仅涉及加法和自同构（不增加乘法深度）。
- 最终的乘积是在这 $h$ 个块的结果之上进行的。
- 结果： 乘法深度从 $\log_2 N + 2$ 降低到 $\log_2 h + 1$ 。由于 $h \ll N$ ，这显著降低了所需的模数大小。

向多槽位的扩展

该方法被推广以处理 $n$ 个槽位（其中 $n \le N/2$ ）。首先提取解密矩阵，然后并行地将自举方程应用于每个 $n$ 个消息分量。其复杂度为 $O(n + \log N)$ ，对于较大的 $n$ ，其渐近复杂度高于原始 CKKS 自举（ $O(\log n + \log N)$ ）。然而，对于较小的 $n$ ，降低的乘法深度带来了更优的实际性能。

核心贡献

SPRU 自举算法： 一种用于 CKKS 的新自举技术，它用单位根的原生评估取代了正弦函数近似。
降低乘法深度： 通过利用稀疏块密钥和迹算子，该算法实现了 $O(\log h)$ 的乘法深度，显著低于原始方法的 $O(\log N)$ 。
优化实现： 作者提供了使用 OpenFHE C++ 库的开源实现，展示了与剩余数系统 (RNS) 算术以及现有线性变换优化（SlotToCoeff）的兼容性。
安全性分析： 对块二进制密钥分布进行了形式化分析，证明只要正确调整参数，该结构不会削弱 RLWE 问题针对已知攻击（混合对偶攻击和中间相遇攻击）的安全性。

结果

作者使用 OpenFHE 库在 128 位安全参数下，将 SPRU 自举与原始 CKKS 自举进行了基准测试。

延迟降低： 对于槽数较少的密文，SPRU 自举实现了高达 5 倍的延迟降低。
效率： 乘法深度的降低允许使用更小的环维度，从而进一步提升了速度。
并行性： 该方法具有高度可并行性；通过 $n$ 个处理器，它可以实现与原始方法相当的 $O(\log N)$ 复杂度。

意义与主张

本文声称 SPRU 自举提供了一种实用的替代方案，专门针对低延迟至关重要且槽数较少的情景。通过避免昂贵的多项式近似并降低乘法深度，该方法使得更高效的密文刷新成为可能。

作者将他们的工作定位为迈向使全同态加密在需要频繁自举的现实应用中更具可行性的重要一步。他们指出，虽然其方法针对小槽数进行了优化，但它通过提供一种侧重于延迟而非大规模并行化的不同权衡，与现有的工作（例如专注于全 $N/2$ -槽自举的 Cheon 等人的独立工作 [CHKS25]）形成了互补。

论文总结道，降低乘法深度是效率提升的主要驱动力，这为自举后的有用操作释放了更多的计算层级，并允许使用更小、更快的环维度。