CKKS同态加密数学原理详解：从RLWE到模数链的完整推导

第一次在项目里真正把 CKKS 用起来的时候，我对着源代码里Encoder和Evaluator的接口发了很久的呆。之前我接触的是 BFV/BGV 这类整数同态方案，思路非常直接：把明文变成一个大整数，加密，做运算，再解密。可 CKKS 完全不一样，它处理的不是整数，而是一堆复数（或者实数）组成的向量。最让我困惑的是这几个现象：为什么编码明文的时候要先乘一个大数再做取整？为什么乘法之后密文长度会变长？为什么每做一次乘法，模数就要“切掉”一段？这些问题靠翻文档很难彻底理解，因为文档只会告诉你“要这样调”，不会告诉你“为什么这个数学结构天然要求这样调”。

我在把推导完整走了一遍之后，才把这些问号一个个消掉。这篇文章不打算讲某个具体库的 API，而是把 CKKS 的数学地基从头到尾捋一遍：从多项式环、RLWE、编码缩放，到加密解密、重线性化、重缩放，再到参数选型。目标读者是那种已经知道同态加密大概是什么、但想真正读懂 CKKS 源码或论文的人。

1. 先搞清楚 CKKS 到底在加密什么

1.1 它和 BFV/BGV 的本质差别

BFV 和 BGV 是精确方案：明文空间是一个整数模 t 的环，加密、运算、解密，每一步都是“精确”的。你输入 3 和 4，乘法解密出来就是 12，不会多也不会少。这种性质非常适合做数据库查询、计费等对结果绝对性有要求的场景。

但现实世界里有大量计算本身就不要求绝对精确。神经网络推理、统计分析、科学计算，这些场景的输入是浮点数，中间结果是浮点数，最终结果也是一个允许误差的浮点数。你要是硬用 BFV 去做，就必须把每个浮点数放大成一个大整数，并且要预留足够的位宽防止乘法后溢出。层数一深，位宽瞬间爆炸，性能和噪声都不可控。

CKKS 换了一条路：既然你本来就不需要精确结果，那我把“噪声”直接当作计算误差的一部分来处理。明文可以是复数向量，解密结果允许带误差，只要误差在可接受范围内就行。这个设计哲学的改变，让 CKKS 在实数和复数计算上远比 BFV/BGV 自然。

1.2 近似方案带来的三个直接后果

这个“近似”不是空口说的，它带来了三个具体的工程后果，理解这三点后面看源码会顺畅很多：

• 明文在编码阶段就有误差。复数向量的每个分量是连续值，但多项式系数必须是整数，所以编码时必然要舍入。
• 解密结果 = 真实明文 + 计算噪声。噪声不是 bug，而是方案的一部分。
• 噪声会随着乘法深度增长，因此参数设计必须预留“噪声预算”，就像你出门前要估算油量一样。

CKKS 整套数学推导，本质上就是围绕“如何把噪声控制在可接受范围内”来设计的。

1.3 贯穿全文的两个核心概念

第一个是编码（Encode）：把一个复数向量变成一个整数系数的多项式。第二个是缩放因子（Scale）：编码时乘上的一个大数 Δ，用来把复数映射到整数域，同时决定精度和噪声水位。

我后面会反复提到这两个概念，你可以先把它们理解为：编码负责把数据“塞进”多项式，缩放因子负责控制“塞”进去的时候损失多少精度。

2. 底层代数结构：多项式环与 RLWE

2.1 为什么偏偏选 X^N+1 这个分圆多项式

CKKS 工作在多项式环 R = Z[X]/(X^N+1) 上。这里的 N 必须是 2 的幂，这样 X^N+1 就是分圆多项式。所谓分圆多项式，简单说就是它的根恰好是 2N 次本原单位根。这个性质非常关键，它让环 R 具有丰富的代数结构：我们可以用单位根的幂来构造求值映射，从而把多项式“看成”一组复数点。

你可能要问：为什么不用更简单的多项式环，比如 Z[X]/(X^N-1)？因为 X^N-1 不是不可约的，环里有零因子，很多密码学证明用不了。分圆多项式是既保证环足够“大”、又保证结构可控的最优选择。而且，因为 N 是 2 的幂，X^N+1 的乘法可以用数论变换（NTT）快速实现——这是 CKKS 能实际跑起来的重要前提。

2.2 RLWE 假设：安全性的地基

在环 R_q = R/qR 上，RLWE 问题说的是：给定随机多项式 a 和形如 b = a·s + e 的样本，其中 s 是从一个较窄分布中抽取的秘密多项式，e 是从离散高斯分布中抽取的小噪声，攻击者很难恢复 s。即便他能看到任意多组 (a, b)，也无法区分这些样本和完全均匀随机的一对多项式。

这个假设是整个 CKKS 安全性的源头。私钥 s 通常从三元分布 {-1, 0, 1} 中抽样，有很多实现还会限制非零系数的个数（稀疏私钥）。噪声 e 的分布宽度会直接影响方案的错误率和安全性，这个在选型时很重要。

2.3 后面推导要用的记号，先统一一下

为了避免后续推导看得眼花缭乱，先列一张表：

3. 编码与解码：复数向量如何打包成一个多项式

3.1 为什么用“求值”而不是“系数”来打包

如果你是第一次接触 CKKS，最容易犯的错是想当然地认为：把复数向量的分量直接塞到多项式系数里就行了。比如向量 (1+2i, 3-4i) 就变成多项式 1+2iX + (3-4i)X^2。这样做听起来很自然，但加法还好，乘法就有大问题：两个这样的多项式相乘，系数会互相卷积，根本不是你想要的分量相乘。

CKKS 想要的是 SIMD 风格的操作：两个复数向量做逐分量相乘，对应槽位的值相乘，互不干扰。要达到这个效果，必须用求值点来定义槽位。它利用的是一个数学事实：环 R 通过在一组单位根上求值，同构于 C^N（这里 N 是环的嵌入次数，对应到槽位组合后再考虑共轭约束）。多项式乘法在两个槽位上恰好变成对应复数乘法。

3.2 编码的具体步骤

设 ζ = exp(π i / N) 是一个 2N 次本原单位根，那么对于任意多项式 m ∈ R，我们可以在 ζ 的各个幂次上求值，得到一串复数。如果 m 的系数是实数，这些求值点会满足共轭对称：m(ζ^j) 和 m(ζ^{-j}) 互为共轭。

于是给定一个长度为 N/2 的复数向量 z = (z_0, ..., z_{N/2-1})，编码过程可以这样理解：

1. 把这 N/2 个复数分别放到一组满足共轭对称的求值点位置上。
2. 对整组共轭对称的求值点做逆离散傅里叶变换（IDFT），得到唯一一个实系数多项式 m(X)，满足在那些求值点上的值（近似）等于 z 的对应分量。
3. 由于 m 的系数还不一定是整数，需要乘以缩放因子 Δ，然后逐系数四舍五入取整。

整个过程用公式表达就是：先通过 IDFT 把求值点映射回系数域，再取整。所以编码其实是两步：插值 + 量化。

注意：这里说的 IDFT 在代码里通常是用复数 FFT 或者专门的 NTT 实现的。不同库的索引约定可能略有差异，但数学本质是一样的——利用分圆单位根把“槽位值”翻译成“多项式系数”。

3.3 缩放因子 Δ 的作用

这一步非常关键。如果不乘 Δ，直接把实数系数四舍五入成整数，那么精度损失大概是 0.5 级别的绝对误差。这个误差在编码阶段就够大了，再经过多层乘法放大会彻底不可用。

乘上 Δ 之后再取整，相当于把实数小数点整体左移 p 位（Δ = 2^p 时），量化误差变成约 1/(2Δ)。后面解密之后，再除以 Δ，就能恢复出近似原值。所以 Δ 越大，量化误差越小，但代价是需要的模数空间越大，噪声预算消耗越快。

这就是为什么 CKKS 里始终存在一个“精度与容量”的权衡：你想要更精确，就得用更大的缩放因子，但它会占用更多模数位数，能支持的乘法深度就变浅。

3.4 解码就是编码的逆过程

解码时，先对解密得到的多项式除以 Δ，然后在一组选定的求值点（单位根幂次）上求值，得到复数向量，再取前 N/2 个分量。整个过程跟编码完全互逆，唯一的差异来自取整误差和计算噪声。

需要特别注意的是：编码本身不是加密。编码后的多项式不含任何密钥信息，任何人拿到编码结果都知道这对应什么数据。它的作用纯粹是把数据形状从“向量”翻译成“多项式”，好让环上的同态运算能够作用于它。

4. 加密与解密：密文从哪来、到哪里去

4.1 密钥生成：sk 和 pk

先采集私钥 s，它是一个系数很小的多项式，通常从 {-1, 0, 1} 中抽取且稀疏。再随机抽一个均匀多项式 a ← R_q，和一个小的噪声多项式 e。然后计算：

b = -a·s + e mod q

公钥就是 (b, a)，私钥是 s。注意，想要从 (b, a) 反推出 s，就要解 RLWE 问题，这正是安全性的基础。

4.2 加密算法与随机性

加密时，输入的是编码后的明文多项式 m ∈ R_q。我们需要另外抽三个随机量：v（从三元分布抽）、e0、e1（从高斯分布抽）。密文是一个二元组：

c0 = v·b + m + e0 mod q c1 = v·a + e1 mod q

这里的 v 叫作“临时随机数”，它的作用是把公钥中的信息“打散”。每次加密都用不同的 v，所以同一个明文加密两次会得到完全不同的密文，这就是同态加密里的语义安全性。

4.3 解密正确性推导

解密极其简单：接收方用私钥 s 计算 c0 + c1·s。

把加密公式带进去展开：

c0 + c1·s = (v·b + m + e0) + (v·a + e1)·s = v·(−a·s + e) + m + e0 + v·a·s + e1·s = m + v·e + e0 + e1·s

看到没有，v·a·s 和 v·(−a·s) 抵消了，剩下的就是 m 加上一堆噪声。只要这堆噪声的系数足够小，多项式 c0 + c1·s 在整数意义下就和 m 基本一致，解码时不会出错。

4.4 解密噪声的组成

解密噪声由三部分构成：v·e（公钥噪声被 v 调制）、e0（加密噪声）、e1·s（加密噪声乘私钥）。其中 e1·s 是多项式乘法，系数会发生卷积，所以噪声的界跟 N 有关。这就是为什么私钥 s 要取得稀疏且小——s 越小，e1·s 这个乘积的系数增长就越慢。

从这里你可以得到一个直觉：CKKS 里面的每一个环节都在积累噪声。密钥生成贡献一点，加密贡献一点，后面每做一次运算再贡献一点。整个方案能不能用，取决于最终解密的噪声是否低于可以接受的误差阈值。

5. 同态乘法与重线性化

5.1 密文乘法的自然展开

加法很简单：两个密文对应分量相加，解密后噪声也是相加，几乎不需要额外处理。乘法则需要认真推导。

设两个密文分别是 c_a = (a0, a1)，对应的明文是 φ_s(c_a) = a0 + a1·s；另一个 c_b = (b0, b1)，明文是 φ_s(c_b) = b0 + b1·s。

两个明文相乘：

φ_s(c_a) · φ_s(c_b) = (a0 + a1·s)(b0 + b1·s) = a0·b0 + (a0·b1 + a1·b0)·s + a1·b1·s²

从这个式子可以看出，要表达乘积的密文，就不能再用二元组了，需要三元组：

c_mult = (a0·b0, a0·b1 + a1·b0, a1·b1)

对应的“密钥”变成 (1, s, s²)。也就是说，密文乘法的自然结果是三元组，解密公式变成 c0 + c1·s + c2·s²。

5.2 为什么必须重线性化

如果每次乘法都不处理，密文长度会像这样从 2 变 3，下一轮乘法之后变成 5，再往后指数增长。密文越长，存储和计算开销越大，而且解密公式里会出现 s 的高次幂，噪声快速增长，正确性很快崩掉。

所以必须有一个操作把三元组恢复成二元组，同时不破坏明文的正确性。这个操作就是重线性化（Relinearization）。它的目标非常明确：找一个二元组 (c0', c1')，使得：

c0' + c1'·s ≈ a0·b0 + (a0·b1 + a1·b0)·s + a1·b1·s²

也就是说，把 s² 这项“吸收”掉，让密文重新变成一个与 s 线性相关的表示。

5.3 重线性化的数学：数字分解

核心工具是数字分解。思路是这样的：如果直接把 a1·b1 乘以某个东西再凑出二元组，会引入很大的噪声。所以把 a1·b1（记作 c2）按某个基 B 分解成多个小块：

c2 = ∑_{i=0}^{l-1} c2_i · B^i

其中每个 c2_i 的系数都落在 [-B/2, B/2] 范围内。这样做的意义是，每个小块 c2_i 都非常小，和它相乘的密钥相关项引入的噪声也就被控制住了。

求值密钥 evk 是一组特殊构造的密文，每一块对应一个：

evk_i = (−a_i·s + e_i + B^i·s², a_i) mod q

其中 a_i 是随机多项式，e_i 是小噪声。你可以注意到，evk_i 的形式和公钥很像，只不过“加密”的内容是 B^i·s²。

现在，把每个小块 c2_i 和对应的 evk_i 做内积再求和：

5.4 重线性化的标准公式

relin(c_mult) = (a0·b0 + ∑ c2_i·evk_i[0], a0·b1 + a1·b0 + ∑ c2_i·evk_i[1]) mod q

验证一下解密结果：

c0' + c1'·s = a0·b0 + ∑ c2_i·(evk_i[0] + evk_i[1]·s) = a0·b0 + ∑ c2_i·(−a_i·s + e_i + B^i·s² + a_i·s) = a0·b0 + ∑ c2_i·(B^i·s² + e_i) = a0·b0 + c2·s² + ∑ c2_i·e_i

前面三项正是乘法的目标明文，最后一项就是重线性化引入的额外噪声。只要 ∑ c2_i·e_i 足够小，密文就依然可用。

这里想强调一下：基 B 的选取很重要。B 越小，每个 c2_i 的系数越小，重线性化噪声越低，但分解出来的块数 l 越多，evk 就越长，计算量也越大。这是一个典型的空间/噪声权衡。

5.5 重线性化的代价

重线性化不是免费的，它主要有三个成本：一是求值密钥 evk 占据额外的存储；二是每次乘法后都要额外做 l 次多项式乘法，计算开销明显增加；三是引入了额外噪声。但所有主流 CKKS 实现都会在乘法后自动做重线性化，因为不做的话，密文膨胀带来的代价比重线性化本身更大。

6. 重缩放与模数链：精度和噪声的再平衡

6.1 乘法之后 scale 出问题了

回到缩放因子的视角。编码时，明文多项式 m1、m2 都带有缩放因子 Δ，所以乘法前的两个密文对应的实际明文是 Δ·a 和 Δ·b。密文相乘之后，解密得到的明文多项式实际上是：

Δ²·a·b + 噪声

这个结果的 scale 变成了 Δ²。如果就这样交给下一层乘法，下一层结果 scale 会变成 Δ³，再到后面 scale 越来越大，彻底乱套。更糟的是，明文幅度本身也平方了，噪声也跟着涨。

6.2 重缩放操作的数学定义

重缩放（Rescaling）要解决的问题就是：把 scale 从 Δ² 拉回 Δ，同时把噪声也等比例缩小。做法是：把密文的每个分量都除以 Δ，再做一次四舍五入。

如果当前模数是 q，且 Δ 能整除 q，那么重缩放后模数降到 q' = q/Δ。设 c = (c0, c1)，则：

c' = ( round(c0 / Δ) mod q', round(c1 / Δ) mod q' )

解密验证：

c0' + c1'·s ≈ (c0 + c1·s) / Δ = (Δ²·a·b + 噪声) / Δ = Δ·a·b + 噪声/Δ + 舍入误差

这一步做完，scale 恢复成 Δ，噪声也缩小了。但要注意，四舍五入本身会引入一个小的舍入误差，这个误差大约在 ±0.5 量级，是重缩放操作无法消除的。

6.3 模数链和“吃掉模数”的说法

重缩放一次，模数 q 就缩小一个因子。所以 CKKS 的参数设计通常是选一串模数：

q_L = q_0 · ∏_{i=1}^{L} p_i

其中 p_i 是每次重缩放要除掉的素数（或接近 Δ 的数），q_0 是底层的“基础模数”。方案从 q_L 开始，每做一次乘法加一次重缩放，模数链条就少一截，直到最后剩下 q_0。

为什么要设计成链式而不是一个固定模数？因为 CKKS 的“容量”本质上是模数的总位数。模数越大，能容纳的噪声预算越多，能支撑的乘法深度越深。每次重缩放都在消耗这个预算，就像油表一格一格往下掉。

6.4 噪声预算的粗略估算

一个非常粗略的噪声账本大约是：一次乘法会让噪声增长到原来的约 (2N + 1) 倍，再加上重线性化噪声和重缩放舍入误差。每条模数链到底能支撑几层乘法，最终由这三个因素决定：

• 初始噪声大小（取决于密钥、加密噪声分布）
• 每次乘法引入的噪声增量（取决于 N、私钥分布、缩放因子）
• 最终必须保留的最低精度（取决于应用要求）

工程上，每层乘法大约消耗 30~60 位左右的模数预算，具体要看实现和参数。这就是为什么文档里常说“这个方案能支撑 10 层乘法”而不是“无限层”。

7. 参数怎么选：安全强度、容量和性能三方权衡

7.1 安全性底线

同态加密参数不能自己拍脑袋定。目前社区的通行做法是用 lattice-estimator 这类工具验证，输入 N、log2(q)、噪声分布等参数，它会输出一个安全强度估计。一般来说，要达到 128-bit 安全级别，固定 N 的情况下，log2(q) 不能超过某个上限；反过来，如果你要很深的乘法链，log2(q) 必然很大，那就必须把 N 调大以维持安全性。

一个直觉参考：N=2^15 时，log2(q) 大约在 218 附近还能有接近 128-bit 的安全强度；N=2^16 时可以撑到 400 多位。出了这个范围，一定要跑估计器确认，不要拍脑袋。

7.2 槽位数、深度和容量的换算

槽位数 = N/2，这是因为在一个 2N 次分圆环上，满足共轭对称后可以容纳 N/2 个复平面上的自由分量。所以 N=2^15 时你有 16384 个复数槽位，N=2^16 时有 32768 个。如果数据量小于槽位数，可以把多个样本打包进一个明文，这也是 CKKS 效率优势的重要来源。

容量和深度的换算关系大约是：

容量 ∝ (log2(q) − log2(q_0)) / 每层乘法消耗位数

比如说，log2(q)=400，q_0 占 60 位，每层消耗约 40 位，那可用深度大约是 (400 − 60) / 40 ≈ 8.5 层。

7.3 一个 10 层乘法的参数例子

假设你想跑一个 10 层乘法深度的模型推理，每层缩放因子用约 40 位的素数（大约能保留 12 位十进制精度），那么模数链总位数大约是：

10 × 40 + 60（基础模数） = 460 位

这时 N=2^15 的安全性大概率不够，需要上到 2^16 甚至 2^17。对应的单次密文乘法时间，在普通 CPU 上大约是几毫秒到几十毫秒的级别，内存占用也会明显上升。这就是为什么深度参数对性能影响如此巨大——它是一个跨数量级的差距。

7.4 工程上我会怎么验证参数

我会先在估计器里验证安全强度，然后用小维度参数跑通正确性，最后再放大到实际参数。千万不要一开始就上大参数，否则定位 bug 会非常痛苦。CKKS 的 bug 往往表现为精度突然崩坏，这时候你很难分清是参数问题、缩放因子没对齐还是噪声超预算了。

8. CKKS 推导中容易栽的坑

8.1 把近似方案当成精确方案用

如果你需要判断两个加密值是否相等，CKKS 永远给不了你布尔级的确定答案。解密结果是“近似相等加上噪声”，你只能判断差值是否小于阈值。很多从 BFV 转过来的人在这里栽跟头，一定要在设计协议早期就想清楚你的业务逻辑能不能承受近似误差。

8.2 scale 不对齐就做加法

加法要求两个密文的 scale 一致，否则就是对不同数量级的数做加减，结果毫无意义。底层实现里，编码器通常会让所有明文保持同一个 scale，但经过不同次数的乘法或重缩放后，scale 可能不再一致。执行加法之前，必须检查两边 scale 是否相同，必要时先做一次重缩放或强制改 scale。

8.3 重线性化和重缩放混为一谈

这两个操作经常被放在一起说，但解决的问题完全不同。重线性化解决的是密文“长度”问题（三元组降回二元组），发生在乘法之后；重缩放解决的是“scale 和模数”问题（把 Δ² 拉回 Δ），也发生在乘法之后。一个不管长度会指数膨胀，一个不管 scale 会数值错乱。正确流程是：乘法 → 重线性化 → 重缩放。

8.4 槽位布局和共轭对称

编码时对求值点做了共轭对称处理，所以不是每个槽位都能独立设定任意复数。你在手动构造槽位布局、做旋转或共轭操作时，必须清楚哪些槽位是“自由的”，哪些是“镜像的”。如果用错了，数据不会报错，但解密结果会莫名其妙地错位或者镜像翻转，而且是那种很难察觉的 bug。

8.5 不跑估计器直接定参数

我见过有人直接拿论文里的参数套自己的场景，结果安全强度完全不够，或者容量冗余巨大导致性能浪费。正确做法是：根据深度需求初步估算 log2(q)，结合 N 查估计器，反复迭代。宁可多花半小时跑一次估计器，也不要上线后被人用格攻击打穿。

CKKS 的数学推导其实是一条清晰的逻辑链：从分圆环到 RLWE，从编码缩放到密文运算，每个环节都在做同样一件事——用可控的噪声换取可计算的容量。我回头看那些当初让我困惑的源码接口，它们每一个背后都对应着一个数学操作：编码器在做 IDFT 和缩放，乘法的relinearize在做数字分解，rescale在切模数链。把这条链走通之后，你再去看任何 CKKS 库的文档，都会觉得那些 API 不再是魔法，而是一步一步算出来的必然结果。