【FHE 同态加密】我们如何实现同态加密推理（六）：Key-Switch 重线性化——一个数量级（2^73 噪声）决定整个设计
关键词：同态加密 ｜ FHE ｜ CKKS ｜ Key-Switch ｜ 重线性化 ｜ Relinearization ｜ Galois 旋转 ｜ 噪声预算 ｜ 密文乘法 ｜ 大模型推理
导读：Key-Switch（重线性化）是同态加密里"不做就完全跑不起来"的操作，它的设计几乎完全由一个数量级决定：不做数字分解时，它引入的噪声约 2^73，而我们的素数只有 60-bit。本篇讲清这个数量级论证、Galois 旋转，以及"为什么 key-switch 密钥不是一对多项式，而是 3×2 个"。
项目仓库
Gitee 主仓：https://gitee.com/pei-xiaoguang/kestrel-llm
GitHub 镜像：https://github.com/m13253246268-ship-it/kestrel-llm相关文档
术语与数据口径 ｜
性能与基准 ｜
构建与复现 ｜
快速上手 ｜
架构总览
0. 一句话结论
Key-Switch 是 CKKS 里"不做就完全跑不起来"的操作。它的设计几乎完全由一个数量级决定：
不做数字分解时，key-switch 引入的噪声约n·q·B ≈ 2^73。
而我们的素数只有60-bit。2^73比它大 13 个数量级——噪声会直接淹没整个模数，结果全废。
数字分解（base 2^20，3 位）把它压到约2^45，这才落回安全区。
这就是为什么 key-switch 密钥不是一对多项式，而是3 × 2个。
1. 为什么必须做重线性化
密文乘法是"张量积"：两个 2 分量密文相乘，得到3 分量。
intckks_mult(ckks_ct_t*ct,constckks_ct_t*a,constckks_ct_t*b);/* tensor, 3 分量 */intckks_relin(ckks_ct_t*ct,constckks_ct_t*in,constckks_rk_t*rk);/* 3->2 分量 */如果不做处理，分量数会随深度线性增长。头文件里留了这条上限：
#defineCKKS_MAX_COMP13/* 无 relin 多分量上限（深 11：comps = 深度+2） */也就是说：不做 relin 的话，深度 11 就需要 13 个分量。每个分量都是nprimes × n个uint64——密文尺寸和乘法代价一起爆炸。
所以relin不是优化，是为了让深链在物理上存在。
顺带说明：这正是 BFV 那代"不做 relin"的取舍为什么只能撑到深度 2（本系列第 4 篇）。同一个问题，两代实现的答案不同。
2. 数字分解：一对密钥变成 3×2 个
relin密钥的结构定义得很直白：
#defineCKKS_RELIN_DIGITS3#defineCKKS_RELIN_BASE_BITS20typedefstruct{uint32_tn;intdigits;uint64_t*rk0[CKKS_RELIN_DIGITS];/* [digits][nprimes*n] */uint64_t*rk1[CKKS_RELIN_DIGITS];}ckks_rk_t;它要满足的关系是（头注释原文）：
D(rk0_d + rk1_d·s) = B^d · s²把密文里那个多出来的s²项用 base2^20拆成 3 位，每一位配一对密钥(rk0_d, rk1_d)，于是s²被"翻译"回可以用s表示的形式——这就是 key-switch 的本质。
3 位 × 2 个 =6 个多项式（每个都是nprimes × n），这就是 relin 密钥的体积。
3. 数量级论证（本文核心）
头注释把这条论证写得很干净，值得逐字引用（原文）：
无分解时 key-switch 噪声
~ n·q·B ~ 2^73会爆 60-bit 素数；
digit 分解把噪声降到~ Σ_d n·2^20·B ~ 2^45。
拆开看：
| 量 | 值 | 说明 |
|---|---|---|
n | 2048 | 环次数 |
q | ~2^60 | 单个素数的大小 |
B | 8 | 噪声界（CKKS_NOISE_CBD 8，中心二项分布eta=8，σ=√(eta/2)=2） |
| 无分解 | n·q·B ≈ 2^11 · 2^60 · 2^3 = 2^74 | 头注释写2^73，量级一致 |
| 有分解 | Σ_d n·2^20·B ≈ 3 · 2^11 · 2^20 · 2^3 = 2^37 | 头注释写2^45，同为安全区 |
关键对比：2^60是我们要对抗的尺度。2^73输，2^45赢。
这个论证之所以值得单独写一篇，是因为它展示了密码学工程里最常见的决策方式：不是"能不能做"，而是"噪声是几个数量级"。差 13 个数量级就是"完全不可用"，差 15 个数量级（2^45vs2^60）就是"留有余量"。
注意：这里的参数是机制验证级。真实部署下n和q都要大得多，噪声尺度与安全尺度会一起变化，但"用数字分解换取噪声数量级"这个结构不变。
4. Galois 密钥：同一个结构，换一个映射
旋转也需要 key-switch，而且结构完全相同：
typedefstruct{uint32_tn;intdigits;uint64_t*gk0[CKKS_RELIN_DIGITS];/* [digits][nprimes*n] */uint64_t*gk1[CKKS_RELIN_DIGITS];}ckks_gk_t;区别只在要"翻译"的目标不同：
| 密钥 | 满足的关系 | 用途 |
|---|---|---|
rk（relin） | D(rk0_d + rk1_d·s) = B^d · s² | 把s²换回s（降分量） |
gk（Galois） | D(gk0_d + gk1_d·s) = B^d · σ_k(s) | 把s换成自同构下的像（做旋转） |
而"旋转"在槽位视角下就是Galois 自同构作用在槽位上。两个接口：
intckks_rotate(ckks_ct_t*ct,...,intt);/* 槽位旋转 σ_{5^t}（支持多分量，输出 2 分量） */intckks_rotate_k(ckks_ct_t*ct,...,uint64_tk);/* 一般 Galois σ_k（k 任意奇数） */为什么σ_{5^t}能当"循环移位"用？因为5是Z_{2n}*的生成元——用 5 的幂依次作用，槽位索引就被"按序推动"，这正是t步循环移位。而ckks_rotate_k允许任意奇数k，用于需要非连续置换的场合。
σ_k的生成接口也分成两个，对应两种密钥：
intckks_gk_gen(ckks_gk_t*gk,constckks_sk_t*sk,constckks_ctx_t*ctx,intt);intckks_gk_gen_k(ckks_gk_t*gk,constckks_sk_t*sk,constckks_ctx_t*ctx,uint64_tk);这里有一个把本系列第 13 篇的问题提前埋下的细节：gk_gen_k是按k生成密钥的——也就是说，"按自同构指数k播种 RNG"这个修复方案之所以自然，是因为代码里本来就有按k组织的入口。修复的难度不在改架构，而在改播种点。
5. 安全边界（务请读完）
本文所述参数为机制验证级，远低于 HE 参数标准的 128-bit 水平，不得用于保护真实数据。 本文主张的是：key-switch 的设计约束与噪声量级。 本文不主张：安全强度、性能优越性。特别提示：本文引用的噪声量级（2^73、2^45）是针对我们这组验证级参数的估算，不能外推到其他参数集。
6. 这一篇的未解问题
- 数字分解的位数没有做优化。
base 2^20、3 位，意味着"20 × 3 = 60"刚好覆盖一个素数。这个选择是对的，但"3 位是不是最优"（vs 2 位 × 30、或 4 位 × 15）我们没有做搜索——位数越少密钥越小但噪声越大，这是个可以量化的取舍。 - Galois 密钥的数量没有收敛。我们为每个需要的
k生成一份密钥，链一长、层一多，密钥总数会膨胀。目前没有做"用哪些k的最小集合"的规划。 rotate支持多分量输入但输出 2 分量——这个不对称是有意的（省一次 relin），但它让"哪些地方还能接受多分量"变成一条需要人工维护的约束。我们还没把它写进任何自动检查。
下一篇我们进自举：七段流水线，以及一个反直觉的实测结论——自举几乎不提高精度。
函数的用法与替代方案)
