做同态加密的人十有八九是从CKKS开始入坑的原因也很简单——它支持浮点数的近似运算跟机器学习、统计分析里的场景天然匹配。但说实话CKKS的数学门槛不算低光“编码/解码”和“重缩放”这两件事就能劝退不少刚接触的人。这篇博文我想把CKKS的核心数学基础从头捋一遍从环结构、误差分布到编解码、密钥生成、加解密、同态乘法再到重缩放和模数链尽量做到每个公式都解释清楚“为什么要这么算”。适合正在做隐私计算、联邦学习相关项目的同学也适合刚入门同态加密、想搞明白库里面“黑盒操作”背后原理的开发者和研究者。CKKS全称是Cheon-Kim-Kim-Song2017年由首尔大学团队提出属于层次型同态加密方案Leveled HE。它跟BFV、BGV最大的区别在于后两者处理的是整数多项式上的精确运算而CKKS允许浮点数的近似计算换句话说就是把“误差”当作方案的一部分直接接受。这个设计一出来直接让同态加密从“玩具级别的整数加法”往前迈了一大步也让它真正有机会落到实际业务里。下面我就按自己的理解把CKKS从底层到应用层一层层拆开讲。1. 为什么要啃CKKS的数学一个总览很多人学CKKS只看库的API调一调参数跑通加解密就觉得自己会了。但真到业务场景里十有八九会碰壁要么编码精度不够要么乘法深度超了要么错误地估计了噪声预算最后解出来的数据一团糟。要搞明白这些就得回到数学层面去看——CKKS的每一步设计都是数学在背后决定的。1.1 同态加密家族里CKKS到底解决什么问题同态加密这个概念其实很直接允许你在密文上做运算运算结果解密后等于明文做同样运算的结果。理想情况下你希望云端只看到密文却能在密文上完成全部计算。这在数据安全、隐私计算、联邦学习里都是硬需求。在CKKS之前主流方案是BGV和BFV它们能处理的是整数环上的精确运算适合做数据库查询、统计计数这类整数值业务。可机器学习和大部分科学计算几乎全是浮点数你要是用BFV去算一个线性回归得先做定点化缩放每乘一次就得截断一次运算深度稍微大一点精度立刻崩掉。CKKS的出现就是为了解决这个问题它本身就在密文里模拟浮点运算的舍入效应把“误差”变成方案内在的一部分而不像BFV那样力求精确。业界经常会说BFV是“整数同态”CKKS是“近似同态”这个“近似”就是它最大的卖点也是它最难理解的地方。1.2 这套方案适合谁怎么学才算真正吃透如果你只是用现成的库SEAL、OpenFHE、HEAAN都封装得不错那看这篇推导的意义更多在于理解参数为什么这么配、为什么某些操作那么贵。如果你是做底层开发或者想做性能优化那这部分基础就是必修课了。我的建议是学CKKS不要一上来就追源码先把五件事搞明白一是底层的RLWE安全假设二是多项式环里的编码解码三是加密解密的数学形态四是同态乘法和重线性化五是重缩放和模数链。这五件事每一个都会在后续实操里反复出现。当你把这几环真正串起来再回头看文档里的参数配置就会有一种“原来如此”的通透感。2. 环、高斯误差与RLWE假设CKKS的地基CKKS的所有操作都在一个特定的代数结构上完成那就是分圆多项式对应的剩余环。理解这个环为什么存在、为什么长这样比背几个公式重要得多。2.1 多项式环与分圆结构CKKS最常用的环是 R Z[X] / (X^N 1)其中N是2的幂。为什么偏偏要用X^N 1而不是别的多项式原因是它满足两个关键性质第一X^N 1是分圆多项式它的根是2N次本原单位根这保证了环里可以做高效的数论变换NTT密文乘法能加速到接近线性级别第二这个多项式是“完全分裂”的在很多模数下都能分裂成一次因式这让背后的明文槽plaintext slot编码成为可能。你可以把R想象成一个N维的整数格点空间每个环元素就是一个系数向量。明文多项式、密文多项式、密钥多项式都生活在这个环里。不同之处是明文多项式的系数通常很小密文多项式的系数则被取模到q密钥多项式则是从特殊分布里采样的。这里有一个容易忽略的点CKKS的明文空间并不直接被定义为这个环而是先用实数向量编码成多项式再进入环进行运算。编码前后的映射关系才是CKKS数学基础和BFV拉开差距的地方。2.2 离散高斯采样与误差分布同态加密的安全性来自于一个叫“带误差学习”Learning With ErrorsLWE的困难问题CKKS使用的是它的环版本也就是RLWE。简单说给定一个环上的随机元素a和另一个元素b a·s e其中s是密钥e是服从窄高斯分布的误差从(b, a)里反推s是非常困难的。这个“困难”不是单纯的计算量大而是目前学术界公认的最坏情况格问题困难性可以归约到它身上。实操里采样e的时候要特别小心我用过一个库默认高斯参数太宽导致密文噪声增长比预期快得多。一般来说高斯分布的标准差σ需要根据安全强度选定常见取σ在3.2到8之间具体的还要配合安全参数评估工具来算。误差分布越大越安全但噪声预算越小加密后能做的乘法次数越少所以安全性和可用性在这里是一对天生的矛盾。2.3 RLWE问题的“困难性”如何变成安全性RLWE的安全论证链条是这样的如果攻击者能通过公钥破解密文那他就能解决RLWE问题而RLWE问题在参数正确选取时难度等价于某个格问题的最坏情况。这段归约听起来很美好但实际落地时参数选取的稍微不合理安全性就大打折扣。我自己见过不少人为了压低噪声把q调得很小结果安全强度直接从128比特掉到80比特以下。所以这里必须提醒一句不要自己凭感觉乱选q和N建议用官方安全参数表或者用LWE估计器lattice-estimator去验证。你省下来的那点噪声预算换来的可能是整个系统的安全塌方。3. 编码与解码把实数塞进多项式的艺术BFV、BGV这些方案处理整数时直接对待加密数字做进制分解就行。CKKS不行因为它要处理的是复数向量而底层环的加法和乘法都是多项式运算。于是问题来了怎么把N/2个复数放到一个N次多项式里并且保证多项式乘法对应到向量分量乘法答案就是正则嵌入。3.1 正则嵌入与明文槽设N2^k分圆多项式X^N 1的根是ξ, ξ^3, ξ^5, ..., ξ^(2N-1)其中ξ是2N次本原单位根。CKKS利用这些根的前N/2个在某种排序下构成一个同构把环R映射到C^(N/2)上。这个映射就是正则嵌入σσ(m) (m(ξ), m(ξ^3), ..., m(ξ^(N-1)))m是明文多项式σ(m)就是它在这N/2个根上的求值。反过来给定一个复数向量z想找到对应的多项式m需要对z做逆映射。这个逆映射本质上是解一个范德蒙德线性方程组复杂度是O(N log N)可以用高效的逆NTT变体完成。这里的关键是“明文槽”概念向量z的第i个分量会被独立地编码到多项式里两个明文多项式做乘法对应的明文槽就各自独立相乘互不干扰。换句话说一次密文乘法同时完成了N/2个复数的乘法这就是CKKS能做SIMD风格批处理运算的数学原理。3.2 缩放、取整与泰勒近似误差从哪里来仅仅把复数向量逆嵌入到多项式里还不够因为正则嵌入的输入必须是共轭对称的实数系数产生的复数值而实际业务里的向量可能不满足这个条件。CKKS论文给出的处理方式分两步第一步是把复数向量z扩展成共轭对称向量z即对后半部分取共轭。这是因为多项式在共轭根上的取值必然共轭所以天然满足对称性。 第二步是做缩放。原始向量里的每个分量可能是任意实数多项式系数却是整数直接舍入会带来很大的相对误差。CKKS在编码前先乘一个缩放因子Δ通常取2^p把向量放大到整数范围再取整得到整数系数这样精度就能围绕2^p来分配。这里就是近似性的第一层来源缩放取整本身引入了舍入误差误差幅度大约在0.5以内相对误差大约1/Δ。实际使用中Δ的选取要结合后续乘法深度来定。比如计划做L层乘法那么初始缩放因子至少要取Δ 2^(p / L)级别的约束否则到后期精度会跌破可用阈值。我在项目里经常先按目标精度倒推Δ再往前推出模数大小这个顺序几乎不会错。3.3 一个N8的编码实例理论说多了容易绕我拿一个极小的例子演示。假设N8分圆多项式是X^8 1明文槽数量是N/24。假设要编码向量z (12i, -34i, 5i, 6-2i)。第一步把z扩展成共轭对称的8维向量即保证σ解码时后半部分能被自动共轭匹配。 第二步乘上缩放因子Δ16得到(1632i, -4864i, 8016i, 96-32i)以及对应的共轭项。 第三步对这8个值做逆范德蒙德插值得到整数系数多项式m(x)。 第四步实际存储的是m的整数系数因为缩放后已经取整。解码时把m代入4个根上求值得到(1632i, -4864i, ...)然后除以16得到近似z。由于取整引入误差解码值通常带有约0.03~0.05的扰动这个扰动在密文运算里还会被后续计算放大。很多初学者在这个地方容易犯一个错误直接拿不满足共轭对称的向量去编码。库通常不会报错但解密后结果会错得莫名其妙查半天才发现是编解码映射不匹配。4. 密钥生成、加密与解密的形式化推导理解了环和编码之后加解密本身其实就顺理成章了。CKKS的密钥体系由三个部分组成私钥、公钥和重线性化密钥。后者的作用我放到乘法那一节再展开。4.1 密钥生成密钥生成过程如下采样一个私钥多项式 s ← R系数通常从{ -1, 0, 1 }里抽取所以s是一个稀疏且系数极小的多项式。采样一个随机多项式 a ← R_q并从离散高斯分布采样一个误差多项式 e ← χ。计算公钥 pk (b, a)其中 b -a·s e mod q。注意这个形式b和a都在模q的环里取值。攻击者面对的是“找s”的RLWE问题已知(a, b)找一个短的s和小的e使得b ≈ -a·s。由于RLWE困难性攻击者拿不到有效信息。而拥有s的接收方可以很容易算出b a·s e虽然不知道e的精确值但能确定它就是一个小误差。除此之外还要生成重线性化密钥evk用于乘法后的密钥切换。它的形式类似于对s²做某种“加密”具体生成方式是选择随机a计算evk (b, a)其中b -a·s e p·s²。这里p是一个特殊的基通常取模数q的一个“缩放因子”用来在分解密文时平衡精度和开销。evk的作用在乘法那一节会看得更清楚。4.2 加密解密的数学形态加密一个明文多项式m的过程是采样随机多项式 v ← R通常系数从{ -1, 0, 1 }里均匀采样。采样误差多项式 e0, e1 ← χ。计算密文对 (c0, c1) (v·b m e0, v·a e1)。密文长度是2。解密的时候用私钥s计算c0 c1·s v·b m e0 v·a·s 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之外只有v·e、e0、e1·s这三项噪声。只要这三项足够小m就能被正确恢复出来。我们在工程里常说的“噪声预算”就是指明文m的振幅预期值和噪声项振幅预期值之间的差距。这个差距是有限的而每次同态操作都会消耗它。4.3 为什么会带误差在RLWE语义下的安全论证有人可能会问为什么解密非要差个e而不是精确相等因为在RLWE安全模型里公钥里必须包含噪声否则攻击者可以通过解线性方程组直接恢复私钥。CKKS的“近似”就是把这个噪声作为方案的一部分刻意让解密结果带一个可控的误差。用户拿到误差范围内的数值就能继续使用。这里我要补充一个容易被忽略的细节v的采样方式直接关系到安全性。很多框架默认v的系数从{ -1, 0, 1 }采样但少数实现为了减少密文大小会把v设成稀疏分布这其实暗藏风险。之前有研究发现v过稀可能导致密钥恢复攻击所以建议用标准实现里的安全默认值别为一点性能去动v的分布。5. 同态运算加法、乘法和重线性化到了最核心的部分。CKKS能在密文上做加法和乘法靠的是环本身的代数结构。加法好理解乘法则牵扯到密文维数膨胀和密钥切换这也是整个方案里最容易让人卡壳的地方。5.1 加法为什么简单如果两个密文分别是(c0, c1)和(d0, d1)它们的明文噪声分别是e1和e2那么逐分量相加 c_add_0 c0 d0 c_add_1 c1 d1解密时 c_add_0 c_add_1·s (m1 noise1) (m2 noise2)噪声是线性叠加的误差增幅大约是两倍非常温和。这也是同态加密里最廉价的运算几乎不消耗多少噪声预算。但注意如果连续做很多次加法噪声也会累积到不可忽略的程度只是相比乘法来说小得多。5.2 乘法的张量积展开与三项密文密文乘法就没有那么简单了。给定两个密文c (c0, c1)和d (d0, d1)我们想要一个密文能解出m1·m2。先看解密过程的乘积 (c0 c1·s) · (d0 d1·s) c0·d0 (c0·d1 c1·d0)·s c1·d1·s²所以理论上可以把三元组(c0·d0, c0·d1 c1·d0, c1·d1)作为“三维密文”。任何持有私钥s的人都能解出m1·m2c0·d0 (c0·d1 c1·d0)·s c1·d1·s² ≈ m1·m2问题来了这个密文从2项变成了3项。如果接下来继续做乘法密文项数会指数级膨胀完全无法控制。标准的解决方案是“重线性化”也称密钥交换。5.3 重线性化用密钥交换把密文拉回两项重线性化的目标很明确把三元组(c0, c1, c2)重新变成两元组(c0, c1)使得c0 c1·s ≈ c0 c1·s c2·s²做法是利用之前生成的evk密钥。把c2做基分解分解成若干个小数字 c2 ∑_i c2_i · p^i 这里的p是重线性化基数通常取2的幂用来控制分解精度和性能。然后 c0 c0 ∑_i c2_i · evk0_i c1 c1 ∑_i c2_i · evk1_i其中evk0_i和evk1_i来自evk的分解块。由于evk本身编码的是s²这个交换在解密时正好把s²项“降回”s同时只引入一个很小的额外噪声。这一段我第一次看的时候绕了很久后来总结了一个直观理解重线性化其实就是“用公钥式的工具把s²的贡献折算到s上”相当于把三维投影回二维代价是加了一点点噪声。在工程实现里这一步也是密文乘法最贵的一环很多性能优化都围绕它展开比如用NTT加速、用RNS分解减少乘法开销等。6. 重缩放与模数链控制精度的核心做同态乘法时明文本身还会伴随缩放因子的膨胀。第一次编码时我们乘了Δ乘法运算后明文值会近似变成Δ²·m1·m2。如果继续做乘法数值会指数级爆炸。重缩放就是为了把这个Δ²重新拉回Δ量级同时控制噪声增长。6.1 为什么乘法后必须做重缩放假设初始明文编码为Δ·m1和Δ·m2乘法后得到的明文是Δ²·m1·m2。如果此时不处理下一次乘法就会变成Δ⁴级别的缩放到最后系数数量级远超模数q解密时直接溢出。重缩放的操作就是让密文整体除以Δ并做系数取整c_rescale round( (1/Δ) · c ) mod q这样解密后得到的大约是Δ·m1·m2缩放因子又回到Δ。同时除以Δ会连带把部分噪声也缩小相当于一定程度“清理”了噪声。不过要注意噪声的实际相对水平并不会因此降低它只是被按比例缩放所以归根结底噪声预算还是每次乘法都会消耗。在具体实现里重缩放并不是简单除以一个数而是利用模数链结构预先选择一系列模数q_L q_{L-1} ... q_0每次重缩放就把密文从模q_l切换到模q_{l-1}。这么做的好处是取整过程可以通过RNS基的切换高效完成不需要做大整数除法。6.2 模数链与RNS表示下的实现真相CKKS的参数设计里模数链的长度直接决定能做多少次乘法。如果每层乘法都伴随一次重缩放那模数从q_L降到q_0之间有多少个“台阶”就能支持多少次带重缩放的乘法。具体关系是log q_L ≈ log q_0 L · log Δ。所以你的乘法深度L越大初始模数就要越大密文也就越大运算开销也越高。工程里的优化思路通常是在保证安全强度的前提下尽量选择小的q和合适的Δ合理规划乘法深度。有些任务只需要两层乘法你却配置了一个能支持十几层乘法的参数那纯粹是浪费内存和算力。另外必须提RNS表示。CKKS里的多项式系数动辄上千比特不可能直接存成一个大整数数组。RNS表示把它拆成多个互素模数下的余数每个余数可以放进64位机器字。所有加法和乘法都可以在各个余数通道上并行完成。重缩放时只需要丢弃一个余数通道再对剩余通道做基数变换校正开销远小于直接做高精度除法。理解了RNS再看库里的“重新线性化密钥数量”和“特殊模数”概念思路会清晰很多。6.3 噪声预算和参数选择经验说到参数选择我踩过的坑值得拿出来分享。第一Δ不是越大越好。Δ决定精度但同时也决定模数大小。同样的乘法深度下Δ翻倍log q就要增加约1比特密文变大运算变慢。第二明文槽数量N/2越大能批处理的数据越多但N越大安全强度在同等q下会下降所以需要更大的N才能撑住同等安全强度。N、q、L、Δ这四个量是相互制约的调任何一个都要考虑其他三个。我一般是这样做的先定业务需要的乘法深度L和精度位数p然后根据L和p算出Δ和初始模数大小的约束再用这个约束对照安全参数表选一个满足128比特安全性的N最后在真实数据上跑一遍端到端测试看最终误差是否达标。这样走一圈虽然前面要算几步但能大幅减少“调了半天参数最后精度崩了”的情况。7. 踩坑与调参心得这里我把实操中遇到的典型问题整理成一个速查表方便大家对照排查。现象可能原因处理建议解密结果完全不对编码时未满足共轭对称扩展检查明文的slot维度是否为N/2确认库的编码API是否自动做共轭扩展单次乘法后精度损失过大缩放因子Δ太小增大Δ重新计算模数链长度确认q_0还有余量多次乘法后噪声爆炸重缩放时机不对或者模数链不够长确认每层乘法后调用重缩放重新估算L性能比预期慢很多N选得过大或者重线性化密钥数量过多检查安全强度是否过高适当降低N和q到目标强度使用RNS时结果偶发错误模数链里互素模数选择不当确认模数都是互素的且特殊模数足够大以支持基数变换还有一个特别容易踩的坑不同库对缩放因子的处理不一致。比如SEAL里的CKKS默认用固定缩放因子但有些版本在乘法后会自动重缩放而OpenFHE里缩放因子可以在每一层动态调整。这意味着同一组参数在不同库里跑出来的误差可能完全不一样切换库的时候一定要重新做参数标定不能直接沿用。最后再分享一个小技巧调试CKKS项目时千万不要只在整数上测试。CKKS的近似特性在遇到特殊数据时会放大误差比如数据范围横跨好几个数量级、或者存在极大的异常值。我是习惯写一个自动化的错误评估脚本在每次密文运算的中间节点都插入解密验证看噪声是怎么一步步累积的这比到最后再找原因高效得多。CKKS的数学基础说难确实难但真正理解了环、RLWE、编解码、重缩放这条主线之后再看任何同态加密库的文档都会觉得清爽很多。希望这篇推导能帮你把最模糊的几块拼图补上少走点我当初走过的弯路。别急着一口气背下所有公式先拿一个小参数例子自己手算一遍加解密和乘法体会会完全不一样。