💻 computer science

Efficient Mod Approximation and Its Applications to CKKS Ciphertexts

本文提出了一种基于多项式插值和切比雪夫级数的新方法，实现了对 CKKS 同态加密方案中模函数在整个输入域上的高精度多项式近似，并据此设计了高效的数据打包方案及同态舍入与秘密份额转换等应用。

原作者： Yufei Zhou

发布于 2026-04-08

📖 1 分钟阅读☕ 轻松阅读

原作者： Yufei Zhou

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

这篇论文主要解决了一个在“隐私计算”领域非常棘手的问题：如何在数据加密的状态下，高效且准确地做“取余数”（Mod）运算，并利用这个能力把更多的小数据塞进同一个加密包里，从而节省上传时间和空间。

为了让你更容易理解，我们可以把这篇论文的内容想象成**“给加密数据搬家和打包”**的故事。

1. 背景：加密的“黑盒子”与“取余数”的难题

想象一下，你有一个魔法黑盒子（这就是 CKKS 同态加密方案）。

它的超能力：你可以把数据（比如图片、基因数据）放进去，别人虽然看不到里面的内容，但可以在盒子上直接做加法或乘法。
它的弱点：这个盒子只能做加减乘除，做不了“取余数”（Mod）。

什么是“取余数”？
就像你有一堆苹果（比如 13 个），每 5 个装一袋，问最后剩下几个？答案是 3。这就是 13 mod 5 = 3。
在数学里，这个“取余数”的操作就像是一个锯齿状的楼梯，它是断断续续的、不连续的。而那个“魔法黑盒子”只擅长处理平滑的曲线（多项式）。

以前的做法：以前的科学家试图用平滑的曲线去模仿这个锯齿楼梯，但只能模仿其中一小段（比如只模仿 0 到 5 这一段）。一旦数据超过这个范围，模仿就完全乱套了，误差巨大。
这篇论文的突破：作者发明了一种新魔法（基于切比雪夫级数和多项式插值），能够在整个范围内（比如从 0 到 100 的所有整数）都非常精准地模仿这个“锯齿楼梯”。哪怕数据很大，它也能算得准，误差极小（小到 $10^{-8}$ ，几乎可以忽略不计）。

2. 核心创新：两个超级打包法（BitStack 和 CRTStack）

既然我们有了精准的“取余数”魔法，作者就利用它来发明了两个**“超级打包法”，专门用来处理那些数值很小**的数据（比如基因里的 0/1/2，或者图片里的像素值 0-255）。

想象你要把很多个小包裹（小数据）寄给远方的服务器，但快递箱（加密后的数据块）很贵，而且每个箱子能装的东西有限。

方法一：BitStack（比特堆叠法）—— 像“俄罗斯套娃”

原理：把每个小数据看作一串二进制代码（比如 101）。作者把这些二进制代码像叠罗汉一样，一个接一个地“塞”进一个大整数里。
- 比如：数据 A 是 1，数据 B 是 2。把它们拼起来变成 1 和 2 的组合。
怎么拆开？ 以前拆开这种堆叠很麻烦，需要一层层剥皮，容易出错。
这篇论文的魔法：利用刚才发明的“取余数”魔法。
- 想取出最底层的 A？直接对大整数做 mod 2^k（取余），剩下的就是 A。
- 想取出 B？把 A 减掉，再除以 2，再做一次 mod。
比喻：就像你有一根很长的糖葫芦，每一颗山楂代表一个数据。以前你想吃第二颗，得把第一颗咬掉，再咬第二颗（串行，慢且容易碎）。现在有了“取余数”魔法，你可以直接变出第二颗，或者同时变出所有山楂（如果配合并行策略）。

方法二：CRTStack（中国剩余定理堆叠法）—— 像“多把锁的保险箱”

原理：利用数学上的“中国剩余定理”。想象你有几个不同的锁（互质的数字，比如 3, 5, 7）。
- 数据 A 是锁 3 的钥匙，数据 B 是锁 5 的钥匙。
- 作者把它们组合成一个超级大数字，这个数字同时满足“除以 3 余 A"、“除以 5 余 B"。
怎么拆开？
- 想取 A？直接对大数字做 mod 3。
- 想取 B？直接对大数字做 mod 5。
优势：可以并行！ 就像你有三个工人，一个人负责开 3 的锁，一个人开 5 的锁，大家同时开工，速度极快。
比喻：BitStack 是像剥洋葱，一层层剥；CRTStack 是像切蛋糕，大家同时切不同的块，互不干扰。

3. 实际应用：不仅仅是打包

除了打包，这个“取余数”魔法还能干别的：

四舍五入（Rounding）：
- 在加密状态下，很难把 3.7 变成 4 或 3。
- 有了取余数，我们可以算出 3.7 除以 1 的余数是 0.7。如果余数大于 0.5，就进位。这样就能在加密状态下精准地做“四舍五入”了。
秘密共享转加密（Secret Shares to HE）：
- 场景：以前，大家把秘密分成几份（秘密共享），各自拿一份，想计算时得大家凑在一起解密再计算，很麻烦。
- 新魔法：现在，每个人拿着自己的那份秘密（加密状态），直接扔进这个“取余数”魔法里，服务器就能把它们自动拼成一个完整的加密数据，不需要任何人解密，也不需要大家互动。这就像把散落在各地的拼图碎片，直接在空中自动拼成了一幅完整的画。

4. 总结：这到底意味着什么？

对普通人：这意味着你的数据（比如手机里的健康数据、基因数据）在上传到云端处理时，更隐私（全程加密），更省钱（上传的数据量变小了，流量费少了），更快（服务器处理效率高了）。
对技术界：这篇论文填补了一个巨大的空白。以前大家觉得在加密数据上做“取余数”太难、太不准，所以很多应用（如神经网络推理、基因分析）没法用。现在，作者不仅解决了“准不准”的问题，还解决了“快不快”的问题，让隐私计算真正变得实用起来。

一句话总结：
作者发明了一种**“万能取余数魔法”，把它用来把无数个小数据像叠积木一样塞进一个加密盒子里，不仅塞得更多**，而且拆得更快、更准，让隐私计算在云端跑得飞起。

这是一份关于论文《Efficient Mod Approximation and Its Applications to CKKS Ciphertexts》（高效模运算近似及其在 CKKS 密文中的应用）的详细技术总结。

1. 研究背景与问题 (Problem)

背景：
同态加密（HE）允许在加密数据上直接进行计算，从而保护隐私。CKKS 方案因其支持近似实数运算和 SIMD（单指令多数据）并行处理，在隐私保护计算中应用广泛。然而，CKKS 原生仅支持加法和乘法运算，缺乏对非线性或不连续运算（如模运算 mod）的直接支持。

核心问题：

模函数近似难题： 模函数（ $x \mod p$ ）具有周期性和不连续性（跳跃间断点）。现有的近似方法（如基于正弦函数的级数展开）通常只能在输入域的有限子区间内保持高精度，而在整个输入区间（特别是模数倍数附近）误差较大，无法满足全区间精确计算的需求。
数据打包效率低： 在 CKKS 中，为了利用 SIMD 特性，需要将多个明文值打包到一个密文中。然而，现有的打包方案在处理小整数输入时，往往导致明文空间利用率低，或者在服务器端解包（Unpacking）时需要极高的计算开销（如多次引导 Bootstrapping 或复杂的比较操作），且通信成本高昂。
秘密共享到 HE 的转换缺失： 现有的方案缺乏一种仅基于 CKKS 操作、无需修改底层秘密共享方案即可将加法秘密共享（Additive Secret Shares）转换为 CKKS 密文的完整方案。

2. 方法论 (Methodology)

本文提出了一套完整的解决方案，核心在于全区间模函数近似及其在数据打包和协议转换中的应用。

2.1 基于多项式插值与切比雪夫级数的模函数近似

离散采样与切比雪夫展开： 针对输入区间 $[0, B]$ 内的所有整数点，将模函数视为离散采样点 $(i, i \mod p)$ 。利用**第一类切比雪夫级数（Chebyshev series）**进行拟合。
解决数值不稳定： 直接拉格朗日插值会导致系数巨大且数值不稳定。切比雪夫多项式具有极小极大（Minimax）性质，系数衰减快，能有效避免龙格现象（Runge phenomenon）。
最小二乘法求解： 构建线性方程组求解切比雪夫系数。当方程数少于未知数（欠定系统）时，选择 $\ell_2$ 范数最小的解，以减小 CKKS 计算中的噪声放大。
缩放因子 $\delta$ ： 为了防止中间计算结果溢出导致误差爆炸，引入缩放因子 $\delta$ 将系数压缩至 1 以下，并在最终结果中还原。
Paterson-Stockmeyer 算法： 采用该算法高效计算高次切比雪夫多项式，优化同态评估的乘法深度。

2.2 高效数据打包方案

利用上述模运算，设计了两种针对小整数输入的打包方案：

BitStack（位堆叠）：
- 原理： 将多个小整数按二进制位拼接成一个大整数。
- 解包： 利用模运算 $x \mod 2^{l_i}$ 提取低位数据，然后除以 $2^{l_i}$ 提取高位数据，递归进行。
- 特点： 结构紧凑，但解包是串行的，乘法深度消耗较大。
CRTStack（中国剩余定理堆叠）：
- 原理： 基于中国剩余定理（CRT），选择一组两两互质的模数 $\{P_1, ..., P_d\}$ ，将数据 $a_i$ 编码为同余方程组 $x \equiv a_i \pmod{P_i}$ 的解。
- 解包： 利用 $x \mod P_i$ 并行提取各层数据。
- 特点： 支持并行解包，各层误差独立，精度更高，但需要更大的近似范围。

2.3 辅助应用

同态取整（Rounding）： 利用 $Floor(x, p) = (x - (x \mod p)) / p$ 等公式，实现了高精度的同态取整、向上取整和四舍五入。
秘密共享转 HE 密文： 提出了一种通用转换方案。重构者收集所有参与者的加密秘密份额 $[[s_i]]$ ，计算 $\sum [[s_i]]$ ，然后利用同态模运算 $ModP(\sum [[s_i]], p)$ 直接得到原始秘密 $x$ 的 CKKS 密文，无需中间解密或复杂的密钥管理。

3. 关键贡献 (Key Contributions)

全区间高精度模近似： 提出了一种基于切比雪夫级数的新方法，克服了现有方法仅适用于子区间的局限，实现了在 $[0, B]$ 全整数区间上的高精度近似（误差低至 $10^{-8}$ ）。
新型数据打包机制： 设计了 BitStack 和 CRTStack 两种方案，显著提高了 CKKS 明文空间的利用率，大幅降低了小整数数据的加密和上传开销。
同态取整实现： 基于模近似实现了高精度的同态取整操作，误差低至 $10^{-10}$ 。
秘密共享到 CKKS 的完整转换： 首次实现了仅基于 CKKS 操作将加法秘密共享转换为 CKKS 密文的完整方案，填补了该领域的空白。

4. 实验结果 (Results)

实验在 Intel Xeon Gold 6145 CPU 上进行，使用 OpenFHE 库实现。

模近似精度：
- 在多项式次数为 45-50 时，平均绝对误差达到 $10^{-8}$ 级别。
- 相比之下，现有最佳方法（Lee et al. [LLL+21]）在部分区间误差高达 2.0，且无法随次数增加而显著降低；OpenFHE 原生切比雪夫近似误差也较大（约 0.7-0.8）。
数据打包性能：
- 解包速度： 提出的 ModP 方法解包时间仅需 15.39 秒（处理 $2^{15}$ 个 4 位整数），远快于基于比较的 Extract 方法（~932 秒）和基于方案切换的 Switch 方法。
- 通信开销： 与纯 CKKS 加密相比，Combine 2 方案（VecConcat + CRTStack + ImgConcat）将上传数据量减少了近 两个数量级（从 2492 MB 降至 26 MB）。
- 与 Transcipher 对比： 与 Rubato（代表性 Transcipher 方案）相比，本文方案在用户端加密时间更短，解包速度快 1.6 倍（156.70s vs 407.03s），且解包后的误差小一个数量级。
取整与转换：
- 同态取整误差可达 $10^{-10}$ 。
- 秘密共享转换在 8 个参与方下，重建时间约 12 秒，误差保持在 $10^{-8}$ 级别。

5. 意义与影响 (Significance)

扩展 CKKS 功能边界： 证明了 CKKS 不仅能处理近似实数，通过精心设计的近似算法，也能高效处理离散的小整数运算（如模运算），极大地丰富了 CKKS 的适用场景。
提升隐私计算实用性： 通过 BitStack 和 CRTStack，解决了小整数数据（如基因数据、图像像素、分类标签）在 HE 中传输和存储成本过高的问题，使得在资源受限设备（如 IoT、智能手机）上部署隐私保护计算成为可能。
协议互操作性： 提出的秘密共享到 HE 的转换方案，打通了安全多方计算（MPC）与同态加密之间的壁垒，为混合架构的隐私计算系统提供了新的构建模块。
未来方向： 虽然目前受限于输入范围（通常 $B$ 为几十到几百），无法直接用于 CKKS 的 Bootstrapping（需要大范围模运算），但该方法为处理小整数密集型应用（如神经网络推理中的量化参数、基因分析等）提供了高效、精确的解决方案。

总结： 该论文通过数学上的创新（切比雪夫级数近似）和系统上的优化（数据打包与转换协议），解决了 CKKS 中模运算难、数据打包效率低的关键瓶颈，显著提升了同态加密在实际应用中的性能和可用性。