第二章 破冰：Gentry 与靴子技术

第二章 破冰：Gentry 与靴子技术

章节摘要：本章跟着二零零九年的那篇博士论文走。为了讲清自举为什么可能，先铺格与误差学习问题这块新地基，再沿时间线回顾构想到破冰的完整脉络，然后进入全章的核心——靴子技术如何在同态域里执行解密函数、给密文"洗噪声"，最后给第一代方案开一张工程账单，看清它慢在哪里、贵在哪里。

一条主线

上一章的僵局可以压缩成一句话：噪声是耗尽型资源，乘法深度有天花板。Gentry 的破冰分两步。第一步是换地基：把密文放进格上的代数结构（后成熟为误差学习问题），让"加乘并存"与"安全性可证明"同时成立，得到一个深度有限的些许同态方案。第二步是神来之笔：观察到只要"解密函数本身足够浅"，就能用同态能力去执行解密——对加密后的密钥加密的密文做一次同态解密，输出的新密文携带全新的小噪声。噪声像被拉靴带一样把自己提了上去，方案由此获得任意深度的计算能力。这条主线贯串本章四节，也定义了此后所有方案的通用骨架：要么自举，要么分层。

沿途站点

第一节"格与误差学习：新地基"回答"为什么必须是格"：从最短向量与最近向量问题讲到误差学习及其环上版本，给出维度、模数、噪声分布这些贯穿全册的参数记号。第二节"三十年演化时间线"把第一章与本章的人物事件排进一张全景时间线，它是整册演化主线的坐标系。第三节"靴子技术：在同态域里给自己解密"是核心节，从自举的电路视角讲到现代实现的毫秒级门自举与可编程查找表。第四节"第一代方案的账单"回头看：公钥以千兆字节计、单门运算以分钟计的往事，说明为什么第二代方案的第一个动作是"逃离自举"。

拐点与结论

本章的认知转折在于重新理解"解密"：它不再只是主人的特权操作，而是一个可以被加密后执行的普通函数。一旦接受这个视角，"噪声不可消除"的教条就崩塌了——消除噪声与读取明文是两件事。第二个转折是工程视角的清醒：第一代方案证明的是可能性，交付的不是可用性，历史随即转向以效率为纲的第二代。

读完你应该

• 能叙述误差学习问题的采样形式，解释它为何被当作平均情况下的困难假设，以及环上版本带来的性能红利
• 能画出全同态方案的时间线骨架，标出构想、破冰、三代方案与标准化四个阶段
• 能分步讲清靴子技术的流程：压缩解密、加密密钥、同态执行解密、噪声上限的递推控制
• 能背出第一代实现的数量级账单：公钥千兆字节级、单门分钟级、一比特明文
• 能说明"自举路线"与"分层路线"的分野，以及它如何决定了第三章两个家族的命运

下一章的接力

主线的下一站是二零一一年之后的方案大爆发。带着本章的两个结论进入第三章：其一，自举很贵但可控，能否少做甚至不做？模交换技术给出第一种答案。其二，格上结构的参数（维度、模数、明文模数）是性能的旋钮，第二代的每一步优化都是在拧这些旋钮。

本章知识点自测清单

按节列出可考核条目。第一节：能叙述误差学习问题的采样形式与区分版本；能解释最坏情况到平均情况归约对同态场景的意义；能背出参数三旋钮（维度、系数模数、明文模数）各自的职能与社区标准档的组合。第二节：不查资料能画出时间线五阶段的框架并说出每阶段清算的债；能解释"代际是叙述便利"的两个理由。第三节：能分步走通自举流程（压缩解密、加密密钥、同态执行、噪声归位）；能写出不动点不等式的工程含义；能报出自举成本从分钟级到毫秒级的三条演化线。第四节：能背出第一代账单的四个数字（公钥二点三千兆字节、单门约三十分钟、每密文一比特、加密一字节八个密文）；能把四大开销对应到第二代的四项对策。

本章还有两个容易混淆的概念对，自测时值得口头复述一遍：其一，"压缩解密电路"与"自举"是两步——前者是后者的前置条件（把解密电路变浅），两者常被混称为靴子技术，严格说只有第二步配这个名字；其二，"些许同态"与"分层"不是同义词——前者描述能力（深度受限），后者描述实现策略（按深度预设参数链），一个些许同态方案既可以用分层策略跑完，也可以靠自举续展成全同态。概念的分寸感来自这种精确的区分。