【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 分量。
int ckks_mult(ckks_ct_t *ct, const ckks_ct_t *a, const ckks_ct_t *b); /* tensor, 3 分量 */
int ckks_relin(ckks_ct_t *ct, const ckks_ct_t *in, const ckks_rk_t *rk); /* 3->2 分量 */
如果不做处理，分量数会随深度线性增长。头文件里留了这条上限：
#define CKKS_MAX_COMP 13 /* 无 relin 多分量上限（深 11：comps = 深度+2） */
也就是说：不做 relin 的话，深度 11 就需要 13 个分量。每个分量都是 nprimes × n 个 uint64——密文尺寸和乘法代价一起爆炸。
所以 relin 不是优化，是为了让深链在物理上存在。
顺带说明：这正是 BFV 那代"不做 relin"的取舍为什么只能撑到深度 2（本系列第 4 篇）。同一个问题，两代实现的答案不同。
2. 数字分解：一对密钥变成 3×2 个
relin 密钥的结构定义得很直白：
#define CKKS_RELIN_DIGITS 3
#define CKKS_RELIN_BASE_BITS 20
typedef struct {
uint32_t n;
int digits;
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² 项用 base 2^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^45 vs 2^60）就是"留有余量"。
注意：这里的参数是机制验证级。真实部署下 n 和 q 都要大得多，噪声尺度与安全尺度会一起变化，但"用数字分解换取噪声数量级"这个结构不变。
4. Galois 密钥：同一个结构，换一个映射
旋转也需要 key-switch，而且结构完全相同：
typedef struct {
uint32_t n;
int digits;
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 自同构作用在槽位上。两个接口：
int ckks_rotate(ckks_ct_t *ct, ..., int t); /* 槽位旋转 σ_{5^t}（支持多分量，输出 2 分量） */
int ckks_rotate_k(ckks_ct_t *ct, ..., uint64_t k); /* 一般 Galois σ_k（k 任意奇数） */
为什么 σ_{5^t} 能当"循环移位"用？因为 5 是 Z_{2n}* 的生成元——用 5 的幂依次作用，槽位索引就被"按序推动"，这正是 t 步循环移位。而 ckks_rotate_k 允许任意奇数 k，用于需要非连续置换的场合。
σ_k 的生成接口也分成两个，对应两种密钥：
int ckks_gk_gen(ckks_gk_t *gk, const ckks_sk_t *sk, const ckks_ctx_t *ctx, int t);
int ckks_gk_gen_k(ckks_gk_t *gk, const ckks_sk_t *sk, const ckks_ctx_t *ctx, uint64_t k);
这里有一个把本系列第 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），但它让"哪些地方还能接受多分量"变成一条需要人工维护的约束。我们还没把它写进任何自动检查。
下一篇我们进自举：七段流水线，以及一个反直觉的实测结论——自举几乎不提高精度。
