【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-llmGitHub 镜像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^203 位把它压到约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 多分量上限深 11comps 深度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。拆开看量值说明n2048环次数q~2^60单个素数的大小B8噪声界CKKS_NOISE_CBD 8中心二项分布eta8σ√(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;区别只在要翻译的目标不同密钥满足的关系用途rkrelinD(rk0_d rk1_d·s) B^d · s²把s²换回s降分量gkGaloisD(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 σ_kk 任意奇数 */为什么σ_{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但它让哪些地方还能接受多分量变成一条需要人工维护的约束。我们还没把它写进任何自动检查。下一篇我们进自举七段流水线以及一个反直觉的实测结论——自举几乎不提高精度。