2.3 靴子技术：在同态域里给自己解密

2.3 靴子技术：在同态域里给自己解密

本节摘要：靴子技术（bootstrapping，自举）是全同态的命名性发明：在噪声耗尽之前，把密钥加密后，对密文同态地执行解密函数，输出同明文、低噪声的新密文。本节拆解它的两步构造（压缩解密电路、同态执行解密）、正确性递推、以及代价模型，并追踪它从分钟级到毫秒级、再到"可编程查找表"的现代演化。

一个自相矛盾的要求

把上一章的僵局重新表述一遍：密文做乘法，噪声平方级膨胀；噪声一旦超过明文位，解密开始输出垃圾。所有修补思路都撞在同一句禁令上——"想消除噪声就得解密，想解密就得看明文"。Gentry 的洞见是把这句禁令拆开：解密是一个函数，函数可以在任何数据上执行，包括加密的数据。把密钥本身加密，连同待刷新的密文一起喂给同态求值算法，让它"闭着眼睛"执行解密电路：求值算法不知道密钥是什么，也不知道明文是什么，但电路跑完之后，输出端出现一个新密文——它加密的还是原来那个明文，噪声却回到接近新生的水平。

术语"靴子技术"源自西方谚语"提着靴带把自己拉起来"，描述的正是这种自指结构：方案用自己尚存的计算能力，为自己续命。理解它要抓住三件套：待刷新密文（噪声偏大）、加密后的密钥（自举密钥，公开辅助物）、解密电路（要在密文上同态跑的函数）。三者输入求值算法，产出一个噪声被置换的等价密文。

两步构造：先让解密变浅，再同态执行

有个细节必须先处理：解密电路本身有多深？如果解密电路的乘法深度比方案当前剩余的评估能力还深，"同态地执行解密"就是空话——刷新还没做完，刷新过程自己先淹死在噪声里。Gentry 的第一招因此是"压缩解密电路"。原理解释：初代方案的解密包含一次与私钥的大规模内积，深度不低；压缩技巧把私钥信息转写成一堆稀疏向量与提示比特，解密简化为"从少量提示比特里做一次浅层选择求和"，乘法深度骤降。代价是公钥体积膨胀（那些提示比特都要发布），这正是第一代实现公钥以千兆字节计的直接原因。

第二招才是自举本身，流程可以逐步走一遍：

# 自举的概念伪代码：深度管理器视角
def run_circuit(program, ciphertexts, bootstrap_key, budget):
    depth_used = 0
    for op in program:                    # 程序是一串加乘指令
        for c in op.inputs:
            if noise_of(c) > budget - SAFETY:     # 噪声逼近红线
                c = bootstrap(c, bootstrap_key)   # 刷新
        out = op.evaluate()               # 正常的同态运算
        depth_used += 1
    return out

def bootstrap(c, bsk):
    # 在密文域里执行解密函数：
    # 输入 = 加密后的私钥 + 待刷新密文
    # 输出 = 新密文，加密同一明文，噪声接近新生水平
    c_enc_key = encrypt_secret_key(bsk)    # 公开的自举密钥
    return evaluate(decryption_circuit, [c_enc_key, c])
​

正确性论证是一个漂亮的不等式链。设方案能评估深度至多为某上限的电路；只要解密电路（压缩后）的深度小于这个上限，自举就能完成；自举输出密文的噪声量级由解密电路的深度决定，与输入密文的旧噪声无关（旧噪声只参与低深度运算，不主导输出）。于是存在一个不动点：只要"新生噪声加上解密电路贡献的噪声"仍低于危险线，每次自举都把密文拉回同一起跑线，计算可以无限续展。全同态的"全"字，数学上就落在这个不动点不等式上。

图：层次全同态流水线——运算与刷新的交替

代价模型：自举是奢侈品

自举要同态地执行整个解密电路，这意味着它的成本天然是"一次普通运算的许多倍"。第一代实现里，单次自举对应的基本门运算以分钟计——历史上首个工程实现的公开数字是单个比特门约需数十分钟量级，公钥体积二点三千兆字节。这些数字不是为了嘲笑先驱，而是为了校准你的直觉：从论文到可用，中间隔着四到五个数量级。

后续演化把这个成本一路往下压，轨迹值得完整记录。第二代方案的答案是"少做"：预先知道电路深度就定好参数链，全程不自举（分层路线，第三章主线）。第三代方案反其道而行：FHEW 在二零一四年把自举压到一秒以内（约零点七秒），TFHE 在二零一六年进一步压到十几毫秒一次门自举——代价是明文退回比特级，靠打包与摊销找补。CKKS 阵营在二零一八年补上了浮点世界的自举（此前的近似方案只能分层），单次自举数百毫秒到秒级，摊销到数千个槽位后每槽成本可接受。到今天，"要不要自举、多久自举一次"已经成为方案选型的第一分岔，第三章第五节会把这张决策图画全。

⚠️ 常见坑：自举密钥是"加密后的私钥"，它的发布依赖一个独立的安全假设——环路安全（攻击者拿到加密私钥仍无法破解原方案）。所有现代实现都默认接受该假设，但合规审计场景需要把它单独列条目，不能与标准语义安全混为一谈。

现代变奏：自举不只是洗噪声

沿着演化线再多走一步会发现，自举在第三代方案里升格成了计算原语。TFHE 的门自举过程天然可以内嵌一张查找表：刷新的同时顺便把任意函数作用在明文上，这叫可编程自举。它把"非线性函数怎么办"（同态世界最头疼的问题之一，乘加电路只能笨拙地逼近指数、比较等运算）转化为"一次刷新加一次查表"，比较、取整、激活函数都因此变得便宜。这个设计哲学的延伸——用自举算函数而不是用电路逼近函数——已经成为低延迟布尔负载的标准做法，第五章隐私推理算例里它会再次出场。

• 要点一：自举等于"对加密的密钥同态执行解密电路"，输出同明文低噪声的新密文；正确性落在"解密电路深度小于剩余评估能力"的不动点不等式上
• 要点二：两步构造——先压缩解密电路降低深度（代价是公钥膨胀），再同态执行解密
• 要点三：成本从分钟级到毫秒级的演化分三条线：分层路线少做、FHEW/TFHE 做快、CKKS 补上浮点自举
• 要点四：自举密钥依赖环路安全假设，是独立的审计条目；可编程自举已把刷新升格为计算原语

自举的成本解剖与调度策略

把自举的代价再拆细一层，为第四章与第五章的账本做铺垫。一次自举的工作量由三部分构成：同态执行整个解密电路（主体，占总成本七成上下）、自举前的密文格式准备（把密文"摆好"进解密电路期望的输入形态，需要若干次旋转与基转换）、自举后的尺度修复（把输出密文的编码尺度拉回与链上其他密文一致，否则后续运算尺度错配）。三部分里最后一段最容易被忽略——它解释了为什么实际系统里自举的耗时常常比论文标称值高出一截：论文标的是核心电路，工程要算全程。

调度策略上，工程实践分三种。定期自举（每若干层乘法后统一刷新一次）实现简单、延迟可预测，适合批处理流水线。按需自举（预算监控器发现逼近红线才触发）节省自举次数但延迟抖动大，适合离线任务。混合调度（线性段分层算、只在方案切换或非线性处自举）是当代推理系统的主流，它把自举的次数压到电路结构决定的下限。三种策略的选择依据又是那句话：看负载形状，不看方案名字。

历史注记：一个博士论文如何震动整个领域

破冰时刻的史料值得多写两笔，因为它展示了基础研究传播的完整链路。Gentry 的博士论文在二零零八年夏天的密码学年会初步亮相、二零零九年正式定稿，学界最初反应混合着兴奋与怀疑——构造的新颖之处（在加密域里执行解密）超出同行的直觉预期。随后的验证链路走了一年多：其他团队逐步复现与简化（次年整数方案的出现证明思路可迁移），首个工程实现给出真实的性能数字（贵得惊人但确实能跑），安全性归约被独立审视与补强。到二零一一年，"全同态存在"从争议命题变成教科书章节，研究重心整体转向效率。这条"亮相、复现、实现、归入教材"的链路，是判别任何颠覆性密码学声明的可靠模板——今天评估任何"突破"时，看它走到链路第几站即可校准预期。

同样值得记录的是博士论文这个载体本身：破冰成果不是出自大型实验室的集体项目，而是一篇博士论文——导师给了方向与自由，学生用数年时间专注啃一块硬骨头。密码学史上这不是孤例（环上误差学习的关键归约同样来自博士阶段的工作）。这个观察对科研管理的含义由读者自行得出，本册只负责把史实记下。

常见问题：自举会不会泄露信息

标准答案是"在既定假设下不会"：自举过程全程在密文域，中间产物都是密文；解密函数的同态执行不暴露私钥（私钥以加密形态参与）；输出密文的噪声被"规范化"到接近新生水平，反而抹掉了输入密文的运算历史——这最后一点有个专门的名字叫电路隐私的副产品，对"服务器不该知道算过什么"的场景（第四章安全节的电路隐私条目）是加分项。真正要单独声明的是自举密钥的环路安全假设（本节正文已述）与自举实现自身的侧信道（刷新过程的耗时模式理论上可观测）。把这两条写进安全文档，比一句"自举是安全的"专业得多。