3.1 BGV 与模交换：噪声的汇率折算

3.1 BGV 与模交换：噪声的汇率折算

本节摘要：BGV 方案（二零一一年）用两个互相配合的技术把第一代的账单撕掉大半：密钥交换（重线性化）把乘法产生的"平方密钥"密文拉回标准形态；模交换在每次乘法后把密文与系数模数同步除以二，用极小的附加误差换回成片的噪声余量。分层同态的"分层"二字就来自这条递减的模数链。本节拆解两项技术的机制、代价与配合方式，并给出噪声增长的定量框架。

密钥交换：先解决乘法留下的变形

要理解 BGV 动了什么手术，先看乘法在同态方案里留下的烂摊子。线性密文解密时与私钥做一次内积；两个密文相乘后，解密式里的私钥以平方形式出现——密文结构从"对一次私钥线性"变成"对二次项开口"。放着不管，下一次乘法就是三次项、四次项，密文形态逐层失控，尺寸与噪声双双爆炸。

密钥交换的标准解法后来成为所有方案的通用件：预先发布一份"重线性化密钥"（也叫求值密钥），它本质上把"私钥的平方"用对新私钥加密的方式交代出来。乘法后，用位分解技术把新密文按比特拆开，逐位查表重组，得到一个对新私钥线性的标准密文。位分解这一步不是多余的礼仪：直接用大系数乘会引入与系数同量级的噪声，按比特拆开后每次只乘零或一，噪声被压在很小的一位增量内。这套流程的概念骨架如下：

# 密钥交换（重线性化）概念骨架
def key_switch(square_ct, evk):
    digits = bit_decompose(square_ct)   # 按比特拆分，压低每次乘的系数
    # evk 中每一条都是"平方私钥分量的加密"
    # 逐位求和：新密文对新私钥 s 线性，噪声仅增加一个小的常数因子
    return sum(d * e for d, e in zip(digits, evk))

def eval_mul(ct1, ct2, evk):
    raw = tensor(ct1, ct2)      # 张量积：密文相乘，解密式中出现 sxs
    return key_switch(raw, evk) # 拉回标准形态，密文尺寸复原
​

付出的代价有两笔：一份公开的重线性化密钥（尺寸按维度与分解位数增长，典型在兆字节级，对比第一代的千兆字节已是天壤），以及每次乘法多一遍分解与重组的计算。收益是密文尺寸恒定——不管理论上乘多少层，密文始终是两条多项式，这个"尺寸不变"性质是后文一切打包与摊销的前提。

模交换：噪声的汇率折算

第二项技术更精妙，也更需要直觉。设定如下：密文的系数活在一个大模数的环里，噪声占其中低位，明文信息经编码后占特定位置。乘法让噪声翻倍膨胀，很快顶到模数天花板。朴素思路是"把模数加大"，但模数越大安全性越差（上一章讲过维度与模数之比定安全），这条路有尽头。

BGV 的思路反过来：乘完之后，主动把密文所有系数连同模数一起除以二。奇迹在于几何关系：噪声是与模数成比例缩小的，而由加密结构保证的"明文编码位置"在折算中保持对齐；折算过程只引入一位新的小误差。等式两端一起变小，相对空间反而变宽裕。用汇率比喻：把资产从大额钞票换成小额硬币，面值缩水一半，但你的储蓄占钱包的比例没有变化，而后续消费的"找零损耗"却按小面值计。每做一次模交换，系数模数的比特长度下降一档，同时噪声回到接近上一档的初始水平——一条从大到小逐级递减的模数链，就是"分层"的实体。

图：模交换的噪声折算机制

两项技术的配合与噪声账本

模交换与密钥交换按固定节拍配合：乘法（张量积）之后立刻做密钥交换复原尺寸，随后按层级折算模数。完整的一次同态乘法在概念层面就是这三拍。把节奏写成账本，噪声演化近似遵循以下规则：加法后噪声取两噪声的较大者加一；乘法后噪声约为两噪声之和加上明文幅度贡献；折算后噪声减半再加常数。定几组数字方便记忆：初始噪声二十比特量级，一次乘法翻到四十比特上下，折算后回到二十出头——因此每层需要预留约三十比特模数；一条二百一十八比特的模数链大约支撑四到六层乘法，这与实用配置的经验值吻合。

表格最后一列暗示了 BGV 留给后世的接口：所有辅助密钥（重线性化、后文的旋转、再后的自举密钥）构成方案的公开运行时，它们的尺寸与生成成本在第四章的账单里统一清算。

💡 关键直觉：模交换的本质是"承认噪声是相对量而非绝对量"。安全强度只关心模数与噪声的比值，那么在比值不变的前提下主动缩小两者，等于免费腾出了后续运算的空间——这是同态密码里罕见的"没有代价的午餐"，代价其实被转嫁到了"深度必须预先知道"这个约束上。

本节要点回顾

• 要点一：密钥交换解决乘法密文的形态失控——张量积后密文对新私钥线性化，尺寸恒定，是打包与摊销的前提
• 要点二：位分解把交换噪声压到常数级，直接用大系数乘会引入与系数量级相同的噪声
• 要点三：模交换让噪声与模数同步折半，相对余量恢复；每层约消耗三十比特模数，二百一十八比特链支撑四到六层乘法
• 要点四：分层的隐含契约是"加密前知道电路深度"；深度未知或无限循环负载必须回到自举路线，两条路线的分野由此确立

一个完整的预算推演算例

纸面规则要落到数字上才算掌握。设定一个小型任务：密文上计算多项式式的评分（两次乘法加若干加法），参数档取四千零九十六维度、系数模数一百零九比特、明文模数二十比特。推演过程分四步。第一步定初始噪声：新密文噪声约二十比特量级（由噪声分布与维度决定）。第二步算乘法消耗：两次乘法，每次约二十到二十五比特（乘积噪声相加，加明文幅度贡献二十比特上下），总计约四十五比特。第三步算折算消耗：两次折算各约三十比特模数，链上消耗六十比特——加上首尾的安全余量，一百零九比特的链刚好容纳这条两乘电路，且余量不多。第四步验证：解密条件要求最终噪声小于缩放因子的半（约三十七比特），推演末端噪声约二十出头，通过。把这套四步推演用在任何电路设计前，就得到了第四章"预算分配表"的最小版本。

同样的推演还能解释两个常见现象。现象一：明明只加了一层乘法，系统却报预算不足——因为电路里藏着隐式乘法（求逆级数、多项式逼近的展开项），四步推演把它们全数计入后深度跃升。现象二：换大维度档后同样的电路"能跑了"——大维度档配套更大的系数模数（八千一百九十二维度配二百一十八比特），链长翻倍，容纳同样深度后仍有富余。参数档的"能跑与否"从来不是玄学，就是这条链的加法。

密钥交换的尺寸账与生成成本

重线性化密钥的尺寸值得单独算一次，它经常成为系统设计的意外瓶颈。条数等于分解位数（典型三四十位到六十位），每条尺寸与一个密文同档（四千零九十六维度下约一百一十千字节），合计数兆字节；如果为不同层级分别生成（分层方案的常见做法），还要乘以层级数。生成成本同样可观：每条是一次完整的加密操作，批量生成以秒到分钟计——这就是第四章说的"密钥包初始化计入冷启动"的具体来源。工程上的对策有三：密钥复用（同一套密钥服务多个会话，权衡是暴露面累积）、按需生成（用到哪层生成哪层，权衡是首请求延迟）、密钥压缩（特殊的编码技巧，权衡是解压计算）。

旋转密钥的账更夸张：全量旋转需要覆盖所有二的幂次步长，每步长一套分解密钥，总量可达数十兆字节。实用系统用"复合旋转"压缩——任意步长分解为二的幂次之和，旋转次数翻倍但密钥总量降为对数规模。第五章推理算例里对角线法的旋转调度，正是在这套密钥预算下做的设计权衡。密钥尺寸、生成时间、使用时延三角的权衡，是同态系统运维手册里必备的一页。

常见问题：分层方案最后还要自举吗

取决于电路深度是否超出链容量。链容量由参数档决定（可推演、可加档），电路深度由负载决定（可改造、可切分）。深度小于容量，全程零自举，这是分层路线的舒适区；深度略超，先试负载改造（降次逼近、合并运算），再试加档（换更大维度）；深度远超或本未知（迭代训练、流式计算），回到自举路线或混合调度。这个决策顺序是第三章与第四章知识的交汇点，也是实践中最高频的架构决策之一。