企业官网建设流程全解析

如果你调过 SEAL、OpenFHE 或者 HEAAN 的接口，大概已经用 CKKS 跑过密文加法和乘法了。但把一批数字喂给 Encoder，再调 Evaluator.Multiply，和真正理解它每一步在做什么数学变换，完全是两码事。我最初做密文推理时，就是死磕 rescale 和 key switching 才勉强把自己从“调包侠”里捞出来——API 用起来很顺手，真到自己设计协议、算噪声预算的时候，对内部机制的理解就决定了方案能走多远。

这是 CKKS 数学基础推导的第二篇。上一篇我们把 LWE/RLWE 的底子打好了，这一篇不再重复格问题为什么安全，直接进入 CKKS 自己的核心机制：编码解码的嵌入原理、乘法后为什么要 rescale、重线性化的数学本质、Rotation 背后的自同构，最后给一些我在实际做密文神经网络时的参数估算和踩坑经验。即便你没看过上一篇，只要能接受形如 ct = (c0, c1) 的密文、知道解密式 ⟨ct, sk⟩ ≈ m (mod q)，也足够跟上这里的全部推导。

1. 从 RLWE 到 CKKS：它到底在加密什么

先看清楚 CKKS 和经典同态方案的本质差异。BFV/BGV 这类方案做的是精确整数运算，密文里藏的是一个“严格正确”的整数值，所有噪声处理都是为了在解密时还能精确恢复。CKKS 不一样，它一开始就承认计算是近似的——密文里藏的是“带误差的消息”，解密出来的结果和真实结果差一点没关系，只要误差控制在可接受范围。这个设计换来的是更高效的实数运算，正好对上机器学习、统计分析这类容错场景的胃口。

我个人理解 CKKS 的三个核心设计支柱：

1. 编码嵌入：把 N/2 个复数打包进一个 N 阶多项式，让一次同态运算同时处理一批数据（SIMD 风格）。
2. 缩放因子与 rescale：用 Δ 把浮点数放大成整数，再做模数切换把放大的尺度压回来，等价于“手动管理小数点位置”。
3. 密钥切换/重线性化：乘法之后密文会变胖，需要一种机制让它变回原来的形状，同时保持解密正确性。

后续所有推导都围绕这三个支柱展开。先把符号约定放在这里，后文不再重复解释：

在 CKKS 里，加密的真实流程是：先把浮点向量 z 编码成多项式 m，再放大 Δ 倍，然后用标准的 RLWE 加密方式把 m 藏进密文。也就是说，密文直接对应的“明文”并不是 z，而是 Δ·Ecd(z) 加上噪声。这一层“放大”是整个方案能支持实数近似计算的起点。

2. 编码与解码：把复数向量装进多项式

2.1 为什么要费劲做编码

RLWE 加密天然只能处理“环元素”，也就是多项式。但实际数据是向量、矩阵、浮点数。编码要解决的核心问题是：把 N/2 长度的复数向量 z，映射到一个实系数多项式 m(X) 上，并且让“多项式乘法对应向量的逐项乘法”。逐项乘法的性质来自分圆环的 canonical embedding，而不是简单的系数乘法。

直觉上可以这样理解：N 阶多项式有 N 个系数，本来应该有 N 个“自由度”，但因为明文是实系数多项式，它在复数单位根上的取值必须满足共轭对称性——实数的傅里叶变换也是共轭对称的。所以 N 个系数里真正能独立携带信息的坐标只有 N/2 个复数位置。这就是为什么 CKKS 一个明文槽位只能装 N/2 个复数的根本原因。

2.2 canonical embedding 与共轭对称子空间

设 ζ = exp(2πi / 2N) 是一个 2N 次本原单位根，canonical embedding 定义为：

σ: R → C^{2N} σ(f) = (f(ζ), f(ζ³), f(ζ⁵), ..., f(ζ^{2N-1}))

因为分圆多项式 X^N+1 的根正好是 ζ 的奇数次幂，所以这个映射是环同构的“嵌入版本”。关键性质是：对于实系数多项式 f，有 σ(f)j = conj(σ(f){-j})（下标按 2N 取模）。也就是说，嵌入后的向量落在一个共轭对称子空间 H 里，自由度为 N/2。

反过来，给定 H 里的一个向量 v，就可以通过 σ 的逆映射还原出多项式。编码过程就是：

1. 输入 z ∈ C^{N/2}
2. 构造 v ∈ H ⊂ C^{2N}：v_j = z_j（j = 1..N/2），v_{-j} = conj(z_j)，其余位置补 0 或按协议填充
3. 计算 m(X) = σ^{-1}(Δ·v)
4. 因为 m(X) 的系数通常不是整数，做四舍五入取整，得到 R 中的明文多项式

解码过程正好反过来：

z_j = π(σ(m(X))) / Δ

其中 π 是取前 N/2 个坐标的投影。注意解码时不存在取整步骤，因为解密后我们本来就允许浮点误差存在。

2.3 实现时容易被忽略的误差来源

编码噪声有两个来源。第一个是取整噪声：σ^{-1}(Δ·v) 的系数是实数，R 里的系数必须是整数，四舍五入会引入误差，这个误差大概在 O(√N) 量级，对应精度损失约几十 bit 中的几个 bit。第二个是在实际库实现里，σ^{-1} 不是直接做高维矩阵求逆，而是利用 X^N+1 的特殊结构映射成离散傅里叶变换（DFT）。如果你在代码里直接对 Vandermonde 矩阵求逆再乘，复杂度是 O(N²)，而 DFT 是 O(N log N)。

也是因为这个特性，很多人误以为 CKKS 的“槽位编码”和“多项式系数”是一回事——其实槽位是 embedding 后频域坐标上的位置，不是系数位置。后面讲 Rotation 时这个区分会变得更关键。

3. 同态乘法与 Rescale：CKKS 的小数点管理

3.1 加法：线性运算很简单

加法是平凡的：

ct_add = (c0_1 + c0_2, c1_1 + c1_2)

解密验证：

⟨ct_add, sk⟩ = (c0_1 + c0_2) + (c1_1 + c1_2)·s = m_1 + m_2 + (e_1 + e_2)

噪声线性相加。加法不需要 rescale，这也是加法消耗的“预算”几乎可以忽略的原因。

3.2 乘法：张量积与密文膨胀

两个密文 ct1 = (c0, c1)、ct2 = (d0, d1)，解密后分别近似 m1、m2。为了让乘积密文满足 ⟨ct_mult, sk⟩ ≈ m1·m2，直接计算张量积：

ct_mult = (c0·d0, c0·d1 + c1·d0, c1·d1)

验证：

⟨ct_mult, (1, s, s²)⟩ = c0d0 + (c0d1 + c1d0)s + c1d1·s² = (c0 + c1s)(d0 + d1s) ≈ m1·m2

问题来了：乘法后的密文从二元组变成了三元组，解密需要 (1, s, s²)。如果连续做乘法，密文会继续膨胀成四元组、五元组，没法收敛。所以必须引入“重线性化”把三元组压缩回二元组，这个放到下一章重点讲。

但在压缩之前，还有另一个更隐蔽的问题：尺度膨胀。

3.3 Scale 膨胀与 rescale 推导

回顾编码过程：明文 m1 ≈ Δ·v1，m2 ≈ Δ·v2。乘法后：

m1·m2 ≈ Δ²·v1·v2

也就是说，乘积明文的尺度从 Δ 变成了 Δ²。如果 Δ 取 2^40，那乘积尺度就是 2^80，这已经超过了当前模数 q_l 所预留的精度空间。直接这样继续算下去，有效小数位会被噪声挤掉，最后解密出来全是噪声。

CKKS 的处理方式是 rescale。设当前模数为 q_l，下一层模数为 q_{l-1}，且构造模数链时保证 q_l / q_{l-1} ≈ Δ。对乘法后的密文做：

ct' = ⌊(q_{l-1} / q_l) · ct_mult⌉ (mod q_{l-1})

因为 q_{l-1}/q_l ≈ 1/Δ，所以等价于把密文整体除以 Δ，同时把模数从 q_l 降到 q_{l-1}。解密效果：

⟨ct', sk⟩ ≈ (m1·m2) / Δ ≈ Δ·v1·v2

这就把尺度从 Δ² 拉回到了 Δ。整个过程相当于在密文上做了一次“右移小数点”的操作，这也是把 rescale 类比成浮点数指数调整的原因。

3.4 模数链的本质

模数链的设计是 CKKS 工程实现的基石。初始化密文时用的模数是 q_L，每做一次乘法后 rescale，模数就降一级，直到降到 q_0 附近就不能再做乘法了。每一级 q_i / q_{i-1} ≈ Δ，所以模数链的总位宽大约就是“scale 位宽 × 最大乘法深度”。这也解释了为什么 CKKS 的参数选择如此依赖模数链长度——深度每增加一层，q 的总位宽就要加约 scale 那么多位，而安全约束对 q 位宽有硬上限。

有一个细节值得注意：rescale 操作同时做了两件事——缩小密文系数（除以 Δ）和缩小模数（q_l → q_{l-1}）。很多人初学时会漏掉第二个作用，导致对噪声预算的计算完全对不上。在 SEAL 里 rescale 后密文的 level 会自动减 1，这个 level 就是模数链上的位置。

4. 重线性化的数学推导：乘法之后密文为什么是三元组

4.1 问题本质：把高次项“降下来”

乘法后的三元组 (c0, c1, c2) 在扩展密钥 (1, s, s²) 下解密。为了把它变回二元组，需要找到两个新多项式 c0'、c1'，使得：

c0' + c1'·s ≈ c0 + c1·s + c2·s²

关键在于把 c2·s² 这一项“翻译”成关于 s 的表达式，同时噪声可控。这就是密钥切换（key switching）要做的事，重线性化只是它的一个特例。

4.2 基分解与重线性化钥生成

直接对 c2 做高精度乘法并不明智，因为 c2 本身是模 q_l 的大系数多项式，和 s² 相乘噪声会被放大。标准做法是先把 c2 做基分解：

c2 = Σ_{i=0}^{d-1} c2^{(i)} · T^i

其中 T 是分解基数（通常取 2 的幂或某个素数），d 是分解个数。然后把“T^i·s²”预先打包成一个公钥，叫做重线性化钥 evk^{(i)}。生成方式与 RLWE 公钥几乎一样：

evk^{(i)} = (b_i, a_i) ∈ R_{P·q}^2 b_i = -a_i·s + e_i + T^i·s² (mod P·q)

这里 P 是一个额外的辅助模数，作用我马上解释。注意 evk 的模数是 P·q，比普通密文的模数更大，这是为了降低密钥切换过程中的噪声。

4.3 重线性化过程与正确性验证

有了 evk 后，重线性化就是一个线性求和：

ct' = (c0, c1) + Σ_{i=0}^{d-1} c2^{(i)} · evk^{(i)}

验证解密：

⟨ct', (1, s)⟩ = c0 + c1·s + Σ c2^{(i)} · (b_i + a_i·s) = c0 + c1·s + Σ c2^{(i)} · (e_i + T^i·s²) ≈ c0 + c1·s + (Σ c2^{(i)} T^i)·s² = c0 + c1·s + c2·s²

这就是乘法后的解密结果。重线性化之后，密文重新变成二元组，可以继续参与下一次乘法了。

4.4 辅助模数 P 的作用

为什么不直接在模 q 下构造 evk，即 b_i = -a_i·s + e_i + T^i·s² (mod q)？问题在于：这样 e_i 和 s² 都在模 q 的范围内，重线性化时 c2^{(i)} 与 (b_i, a_i) 相乘的结果会被 q 截断，导致噪声与密文系数规模相关，精度损失严重。引入 P 之后，等式在更大的模 P·q 下成立，最后再通过一次模切换把噪声中与 P 相关的部分消掉。这个过程在 RNS（余数系统）实现里对应额外模数的管理。

我自己早期手写实现时，一度想省掉 P，结果每次重线性化后噪声预算直接掉十几位，后来才彻底理解这个辅助模数不是可选项，而是 CKKS 保证精度的核心设计。

4.5 基 T 的选择：速度与噪声的权衡

分解基数 T 的选择直接影响性能。T 越大，d 越小，evk 的存储和计算量越小；但每次重线性化引入的噪声也越大。T 越小，d 越大，evk 越大，噪声越小。实际库的默认值通常针对安全性做过标定，比如 SEAL 在 CKKS 模式下使用比特分解（T = 2^16 之类的参数），OpenFHE 在 RNS 实现里则用多个素数直接做分解，d 通常只有 1 到 2，速度优势非常明显。

5. Rotation 与自同构：槽位操作不只是“换个位置”

5.1 槽位不是在系数上

前面说过，明文向量 z 的每个分量对应 canonical embedding 坐标上的一个位置，而不是多项式系数位置。所以要把 z 循环移动一位，不能直接对多项式系数做左移或右移，必须使用分圆环上的自同构。

5.2 自同构的定义

对满足 gcd(k, 2N) = 1 的奇数 k，定义环自同构：

θ_k: R → R θ_k(f(X)) = f(X^k)

它保持环结构，即 θ_k(a+b) = θ_k(a) + θ_k(b)，θ_k(ab) = θ_k(a)·θ_k(b)。作用在 canonical embedding 坐标上，θ_k 会把原本在位置 j 的值搬到 k·j 的位置，从而在槽位上产生一个循环排列。这就是 CKKS 支持 slot rotation 的数学基础。

5.3 密文上的作用

对于一个普通密文 ct = (c0, c1)，定义：

ct' = (θ_k(c0), θ_k(c1))

注意直接作用并不保持密钥。验证：

⟨ct', θ_k(s)⟩ = θ_k(c0) + θ_k(c1)·θ_k(s) = θ_k(c0 + c1·s) ≈ θ_k(m)

所以 ct' 是在密钥 θ_k(s) = s(X^k) 下解密的。要换回原来的私钥 s，就需要一次密钥切换，把 θ_k(s) 转换回 s。这个密钥切换钥就是通常说的“旋转密钥” rk_k = KS(θ_k(s) → s)，它的数学结构与重线性化钥完全一致，只是把 T^i·s² 换成了 T^i·θ_k(s)。

这也解释了为什么 Rotation 不会消耗 scale 预算，但会消耗一次密钥切换的噪声预算——它本质上就是一次带噪声的线性变换。

5.4 实际应用：矩阵向量乘法的槽位打包

旋转最常见的使用场景是打包向量后做矩阵乘法。假设密文 ct 里存的是一个向量 v = (v0, v1, ..., v_{k-1})，要做对角线提取式矩阵乘法，需要把 v 旋转若干个位置再逐项乘权重、累加。一次 matmul 往往需要 log k 次旋转/乘法/加法的组合，旋转噪声会层层叠加。所以真正的工程经验是：尽量把旋转安排在同态乘法的低 level 阶段，或者尽量多复制明文，用明文乘法代替密文旋转，往往更快。

6. 噪声预算与参数选择：纸上推导之外的实战心得

6.1 噪声的四个来源

如果只记住一件事，那就是 CKKS 的精度完全由噪声预算决定。噪声来源可以分成四类：

1. 编码取整噪声：把浮点明文四舍五入到整数环时产生，约 O(√N)。
2. 加密噪声：RLWE 采样时引入的离散高斯噪声。
3. 乘法与重线性化噪声：乘法本身噪声乘积，加上重线性化引入的 T 相关噪声。
4. 旋转噪声：每次旋转使用旋转钥时引入的密钥切换噪声。

这些噪声相互叠加，直到超过模数允许的容错空间，解密就是纯噪声了。

6.2 深度与 q 位宽的估算方法

做参数选择时，我习惯用一个简化公式来反推模数链位宽：

log q ≈ L·s + noise_budget + λ

其中 L 是最大乘法深度，s 是 scale 位宽（比如 40 bit），noise_budget 是留给各类噪声的余量（实践中大约 20~50 bit 取决于旋转和重线性化次数），λ 是安全余量（通常约几十 bit）。

举个实际例子。假设目标 scale 为 2^40，深度 L = 6，noise_budget = 40 bit，安全余量按约 10 bit 估算：

log q ≈ 6 × 40 + 40 + 10 = 290 bit

那么 N 要选多大？安全要求限制了 N 与 q 的关系。工程经验上，N=8192 时 q 的总位宽上限约 218 bit 量级，N=16384 时约 438 bit。上面这个 290 bit 的需求，N=8192 已经不够安全，至少得选 N=16384。密文大小估算：

2 × N × log q / 8 bytes ≈ 2 × 16384 × 290 / 8 ≈ 1.19 MB

这个数字在真实部署中是比较“重”的。也是为什么很多隐私计算项目用 CKKS 时都尽量压深度、降 scale，而不是无脑加高层级。

6.3 我踩过的几个具体坑

第一个坑是 scale 不一致。两个密文相乘前必须保证它们的 scale 相同，否则乘积的“小数点位置”是错的。库的 API 虽然会自动插入 rescale，但如果你自己拼协议，最容易出的问题就是其中一个密文已经 rescaled，另一个还没 rescale，乘出来结果变成垃圾数据。

第二个坑是低估旋转成本。很多初版方案只算乘法深度和 level，忘了旋转也要消耗噪声。密文深度小的阶段旋转还行，深度大的阶段旋转一次可能直接把仅剩的预算打穿。我后来养成的习惯是：先画计算图，标出所有乘法和旋转的位置，估算每一层的噪声消耗，再决定模数链总长度。

第三个坑是拿 CKKS 当精确计算用。CKKS 是近似方案，结果的相对误差大致和 scale 位宽及噪声水平相关。做神经网络推理时误差累积到 1e-2 都能接受；但如果你拿它跑需要精确相等的逻辑判断（比如比较两个数是否相等），那 CKKS 基本不适合。选型一开始就要想清楚这个边界。

最后分享一个我自己总结的小技巧：调试参数时，先跑一个只含“明文编码 + 加密 → 乘法若干次 → 解密解码”的最小脚本，打印每一步解密后的明文和真实明文之间的误差，这样可以快速定位噪声是来自编码、乘法还是重线性化。这一步看起来笨，但比抱着论文推噪声界要有效得多。毕竟真实系统里的噪声行为，只有实测数据才靠得住。