第一章 序章：同态性质的三十年

第一章 序章：同态性质的三十年

章节摘要：本章跟着一条线走——从一九七八年 Rivest、Adleman、Dertouzos 那篇"数据银行与隐私同态"的构想出发，看 RSA 与 ElGamal 如何顺带实现了乘法同态、Paillier 如何补上加法同态，最后停在 Gentry 破冰前夜的"噪声之墙"上。读懂这三十年，你才能理解后文每一次技术选择背后的债。

一条主线

故事的主线是一对矛盾的拉锯：人们想要"密文上直接计算"，而当时的公钥密码只肯交出"单一种运算"的同态性。RSA 与 ElGamal 天生会乘法，Paillier 天生会加法，但乘与加无法在同一个密文体系里共存——不是没人试，而是每往"同时支持两种运算"迈一步，解密就会因为误差累积而失效。这道墙后来有了名字：噪声。本章以三个节点串起这段史前史：构想的提出、乘法同态的发现与利用、加法同态的补全与僵局。

沿途站点

第一节"同态性与运算守恒"给全册的公共语言：什么是同态映射，加密方案的同态性怎样形式化，正确性边界在哪里。这一节是地基中的地基，后面所有方案都用这里的记号。第二节"RSA 乘法同态的偶然发现"回到历史现场，用可运行的小数值算例重现那个被忽视的副产物，并解释为什么确定性加密让它难以直接商用。第三节"Paillier 加法同态与噪声之墙"讲加法这一半：合数剩余类问题、概率加密、电子投票里的真实用法，然后引入噪声的概念，把三十年僵局收拢到一个问题上——乘法会让误差平方级膨胀。

拐点与结论

本章关键的认知转折在第三节末尾：部分同态方案的"只会一种运算"不是功能缺陷，而是数学结构使然——支持加法的结构与支持乘法的结构在密文空间里互斥，直到有人想出"让误差本身成为方案的一部分"。读者离开本章时应带上这个悬念：噪声既是敌人，也将是二零零九年那个方案的核心组件。

读完你应该

• 能写出同态加密的形式化定义：解密方对密文运算结果的解密值，等于对明文做对应运算的值
• 能用小素数手推 RSA 乘法同态的完整算例，并说出确定性加密在语义安全上的缺陷
• 能解释 Paillier 密文乘积对应明文相加的推导链条，以及标量乘对应明文数乘
• 能叙述"噪声"如何限制早期方案只能做单运算，以及乘法深度与误差增长的平方关系
• 能列举三个部分同态时代的真实应用：电子投票、聚合统计、密钥托管评测

下一章的接力

主线的下一站是二零零九年。带着"噪声是墙"的结论进入第二章，你会看到 Gentry 做的两件事：把地基从整数环搬到格上（第一节），然后让密文在同态域里给自己解密（第三节）。历史没有跳跃——靴子技术的每个零件，都能在本章的僵局里找到对应的问题。

本章知识点自测清单

支柱页最后给出按节细分的自测条目，读完逐条打勾，不确定的回对应节重读。第一节：能默写同态加密四算法组成与核心正确性等式；能解释为什么加法与乘法构成计算的完备集；能说出求值算法不接触私钥带来的安全衍生问题。第二节：能手推小素数 RSA 的同态算例（密文之积解密回明文之积）；能说明确定性加密为何不满足语义安全、填充为何会摧毁同态性；能把 RSA、ElGamal、Paillier 正确放进部分同态的分类框架。第三节：能手推 Paillier 玩具算例的三条运算规则；能解释明文模数下的回绕现象；能定量描述整数方案中乘法噪声的平方增长（十位比特噪声经三次乘法后的量级）；能把"些许同态"的定义与噪声预算挂钩。

三条线里贯穿本章的通用能力：其一，给出任一部分同态方案，能按"运算种类、次数上限、随机化、困难性基础"四列做结构化描述；其二，能把一个真实业务需求（如联合计数、选票聚合）映射到合适的部分同态工具并指出其能力边界；其三，能向非密码学背景的同事解释"为什么三十年造不出全同态"——这个解释能力比背出年表更能检验理解深度。