如果你调过 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 的三个核心设计支柱编码嵌入把 N/2 个复数打包进一个 N 阶多项式让一次同态运算同时处理一批数据SIMD 风格。缩放因子与 rescale用 Δ 把浮点数放大成整数再做模数切换把放大的尺度压回来等价于“手动管理小数点位置”。密钥切换/重线性化乘法之后密文会变胖需要一种机制让它变回原来的形状同时保持解密正确性。后续所有推导都围绕这三个支柱展开。先把符号约定放在这里后文不再重复解释符号含义N2 的幂对应分圆多项式 X^N 1 的次数R多项式环 Z[X]/(X^N1)R_q模 q 的多项式环 R/qRsk s私钥从 R 中按小系数分布采样ct (c0, c1)RLWE 密文c0, c1 ∈ R_qΔ缩放因子scale通常取 2^pq_l第 l 层模数满足 q_i / q_{i-1} ≈ Δm / v编码后的多项式明文 / 原始复数向量在 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^N1 的根正好是 ζ 的奇数次幂所以这个映射是环同构的“嵌入版本”。关键性质是对于实系数多项式 f有 σ(f)j conj(σ(f){-j})下标按 2N 取模。也就是说嵌入后的向量落在一个共轭对称子空间 H 里自由度为 N/2。反过来给定 H 里的一个向量 v就可以通过 σ 的逆映射还原出多项式。编码过程就是输入 z ∈ C^{N/2}构造 v ∈ H ⊂ C^{2N}v_j z_jj 1..N/2v_{-j} conj(z_j)其余位置补 0 或按协议填充计算 m(X) σ^{-1}(Δ·v)因为 m(X) 的系数通常不是整数做四舍五入取整得到 R 中的明文多项式解码过程正好反过来z_j π(σ(m(X))) / Δ其中 π 是取前 N/2 个坐标的投影。注意解码时不存在取整步骤因为解密后我们本来就允许浮点误差存在。2.3 实现时容易被忽略的误差来源编码噪声有两个来源。第一个是取整噪声σ^{-1}(Δ·v) 的系数是实数R 里的系数必须是整数四舍五入会引入误差这个误差大概在 O(√N) 量级对应精度损失约几十 bit 中的几个 bit。第二个是在实际库实现里σ^{-1} 不是直接做高维矩阵求逆而是利用 X^N1 的特殊结构映射成离散傅里叶变换DFT。如果你在代码里直接对 Vandermonde 矩阵求逆再乘复杂度是 O(N²)而 DFT 是 O(N log N)。也是因为这个特性很多人误以为 CKKS 的“槽位编码”和“多项式系数”是一回事——其实槽位是 embedding 后频域坐标上的位置不是系数位置。后面讲 Rotation 时这个区分会变得更关键。3. 同态乘法与 RescaleCKKS 的小数点管理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 ≈ Δ·v1m2 ≈ Δ·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 Σ_{i0}^{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) Σ_{i0}^{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(ab) θ_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 的精度完全由噪声预算决定。噪声来源可以分成四类编码取整噪声把浮点明文四舍五入到整数环时产生约 O(√N)。加密噪声RLWE 采样时引入的离散高斯噪声。乘法与重线性化噪声乘法本身噪声乘积加上重线性化引入的 T 相关噪声。旋转噪声每次旋转使用旋转钥时引入的密钥切换噪声。这些噪声相互叠加直到超过模数允许的容错空间解密就是纯噪声了。6.2 深度与 q 位宽的估算方法做参数选择时我习惯用一个简化公式来反推模数链位宽log q ≈ L·s noise_budget λ其中 L 是最大乘法深度s 是 scale 位宽比如 40 bitnoise_budget 是留给各类噪声的余量实践中大约 20~50 bit 取决于旋转和重线性化次数λ 是安全余量通常约几十 bit。举个实际例子。假设目标 scale 为 2^40深度 L 6noise_budget 40 bit安全余量按约 10 bit 估算log q ≈ 6 × 40 40 10 290 bit那么 N 要选多大安全要求限制了 N 与 q 的关系。工程经验上N8192 时 q 的总位宽上限约 218 bit 量级N16384 时约 438 bit。上面这个 290 bit 的需求N8192 已经不够安全至少得选 N16384。密文大小估算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 基本不适合。选型一开始就要想清楚这个边界。最后分享一个我自己总结的小技巧调试参数时先跑一个只含“明文编码 加密 → 乘法若干次 → 解密解码”的最小脚本打印每一步解密后的明文和真实明文之间的误差这样可以快速定位噪声是来自编码、乘法还是重线性化。这一步看起来笨但比抱着论文推噪声界要有效得多。毕竟真实系统里的噪声行为只有实测数据才靠得住。
