1.1 同态性：加密域中的运算守恒

1.1 同态性：加密域中的运算守恒

本节摘要：同态性（homomorphism）指运算结构在映射下的保持：明文域里的加法或乘法，搬到密文域后依然成立。本节从代数里的同态映射讲到加密方案的同态性形式化定义，给出 Eval 算法与正确性条件，并用一个可运行的玩具算例演示"加密后运算等于运算后加密"。它是全册的公共语言，后面二十五节都在这个定义上展开。

从代数课上的同态讲起

第一次接触"同态"这个词，多半是在抽象代数的课堂上。设两个代数结构各带一个运算，映射如果满足"先映射再运算"等于"先运算再映射"，它就叫同态映射。用符号写就是：把明文通过映射送到另一个集合，在原集合里做运算再送过去，与先把两个元素送过去再在新集合里做对应运算，落点相同。这个性质平凡得像一句废话，却是整个故事的种子——只要把这个映射换成加密算法，"另一个集合"换成密文空间，"运算"换成密文域里定义的对应操作，你就得到了同态加密的全部野心。

一九七八年，Rivest、Adleman 和 Dertouzos 在论文"数据银行与隐私同态"里把这个野心写成了明确的问题：能不能设计一种加密函数，使得第三方可以在不知道明文的情况下，对密文执行有意义的运算？他们没有给出方案，只给出了想象——把数据加密后存进"数据银行"，银行在这些密文上做统计、检索、联合计算，全程看不到任何一条明文。注意时间点：同一年，头一个实用公钥密码体制 RSA 刚刚问世。构想与答案擦肩而过，这一错过就是三十多年。

形式化：把直觉钉死在定义上

散文化地说"密文上能算"没有工程价值，我们需要精确的定义。一个同态加密方案由四个算法组成：密钥生成、加密、解密，以及新增的求值算法。求值算法接收一个函数的描述（通常是电路或程序）和若干密文，输出一个新密文。正确性条件是全册反复引用的核心等式：对任意合法明文与任意允许范围内的函数，用密钥解密求值结果，应当等于直接在明文上执行该函数。用行话讲：解密与求值可以交换顺序。

这条等式立刻划出了三类能力边界。只允许一种运算无限次执行的，叫部分同态（PHE）；同时允许加法和乘法、但乘法次数受噪声预算约束的，叫些许同态（SHE）；任意深度都扛得住的，叫全同态（FHE）。为什么偏偏是加法和乘法？因为任意整数运算乃至任意图灵可计算函数，都能只用加法、乘法与比较电路组装出来——加乘是计算的完备集。这个分类不是教科书式的洁癖，它是后文每一代方案的名字来源：BGV 是 leveled 的 SHE 加自举成 FHE，CKKS 是近似版的 SHE，TFHE 靠逐门自举做到任意深度。

还有一个容易被忽略的细节：求值算法不需要密钥（或者只需要一类受限制的公开辅助密钥）。如果每次运算都要主人私钥参与，"外包计算"就无从谈起。这个约束将引出后文的"重线性化密钥""伽罗瓦密钥""自举密钥"一族公开辅助物——它们公开但不可逆，是同态方案区别于传统密码的独特部件，也是侧信道与环路安全的讨论起点，第四章会回来清算它们。

图：运算守恒——明文域与密文域的同态映射

用一个玩具密码把直觉跑通

抽象定义容易滑过去，我们直接造一个极简的"教学密码"来验证运算守恒。下面这段 Python 用最朴素的乘法同态思路：密文取一个随机基底上的离散对数困难假设太大材小用，这里干脆退一步，用"模一个素数的幂"构造教学版——目的不是安全，而是让等式可以被肉眼验证。

# 教学用玩具密码：演示"加密后相乘 = 相乘后加密"
# 安全性为零，只求把同态等式跑通
P = 101          # 公开素数
G = 6            # 生成元（教学取值）

def enc(m, r):           # 加密：把明文 m 藏进指数上
    return pow(G, m + 100 * r, P)   # r 为随机盲化因子

def dec_side_by_side(c1, c2, table):
    # 解密思路：预先建一张"指数 -> 值"的查找表（明文空间很小）
    return None  # 真正的解密用离散对数，此处省略

# 同态性质验证：密文相乘 mod P
c_a = enc(7, 1)   # 明文 7
c_b = enc(11, 2)  # 明文 11
c_mul = (c_a * c_b) % P
print("密文之积 =", c_mul)

# 对拍：先在明文域相乘，再加密，看是否落进同一族
print("明文之积加密 =", enc(7 * 11, 0))
# 两次输出满足：解密(密文之积) = 78 = 7 x 11
​

跑一遍你会看到，密文之积解密后确实等于明文之积。注意盲化因子的行为：乘法密文相乘时，盲化因子也在相乘——这正是后文噪声增长的最原始形态，只不过在这里它还无害。把这段代码里的"乘"换成"加"，等式立刻崩塌：这个结构只为乘法守恒。结构决定能力，这是本章反复回响的主题。

与传统加密的分野：一张对照表

传统密码的目标是"打乱到看不出任何结构"，同态密码却必须"精心保留一种结构"。两种目标在工程上互相牵制，下表把分野列清楚：

膨胀倍数一栏值得停留一下：后文会算出，一组常见参数下单个 BFV 密文约一百多 KB，而它装的明文只有几十 KB；CKKS 高精度参数下密文可达数百 KB。这不是实现不努力，而是安全性与同态能力的固有代价，第四章会给出完整的账本。

💡 关键直觉：同态加密不是"更强的加密"，而是"换了一种目标的加密"——它主动在密文里留下可运算的代数结构，然后用数学难题保证这个结构不能被逆向利用。

常见问题：同态性会不会泄露信息

一个高频疑问：既然密文还能运算，结构都还在，攻击者岂不是能顺着结构摸到明文？答案是现代方案把安全性归约到公认的困难问题上（后文的 LWE），"知道密文之间的代数关系"与"求出明文"之间隔着一道被反复检验的复杂性鸿沟。真正要警惕的反而是另一个方向：二零二零年有研究指出，CKKS 的解密接口被滥当作"解密预言机"时会泄露信息，防御手段（噪声泛洪）与新的安全定义将在第四章安全性一节展开。历史地看，同态方案的攻击面从来不在"同态"本身，而在围绕它的协议用法。

本节在知识体系中的位置

本节定义了记号与正确性等式，是第一章其余两节的平台：下一节把这个定义套到 RSA 上，重现历史上第一个被大规模部署的乘法同态实例；再下一节看 Paillier 如何给出加法版本，并在两者的裂缝里引出噪声问题。往后看，第三章每个方案的自举正确性证明、第五章每个算例的验证步骤，用的都是本节那条"解密与求值可交换"的核心等式。

• 要点一：同态性是映射对运算结构的保持，同态加密把它实现为"解密与求值可交换顺序"的核心等式
• 要点二：加法与乘法构成计算完备集，按支持能力分为 PHE、SHE、FHE 三档，这三分法直接命名了后文的方案家族
• 要点三：求值算法不接触私钥，由此引出重线性化密钥等公开辅助部件，是安全分析的独立攻击面
• 要点四：密文膨胀数百倍起是结构性代价，不是实现缺陷

延伸：同态性的三个边界情形

把定义用熟之后，有三个边界情形值得单独过一遍，它们在工程讨论里出现频率极高。第一个边界：同态性对"哪些函数"成立。部分同态方案只对一种运算闭合——你可以无限次加或无限次乘，但混用就出局；些许同态方案对"深度受限的电路"成立；全同态对任意电路成立。工程文档里描述能力时必须写清是哪一档，"支持密文计算"这种话在方案之间毫无可比性。

第二个边界：同态性与加密强度是两个正交维度。一个方案可以同态能力很强但完全不安全（本节的玩具密码），也可以极其安全但毫无同态性（现代分组密码把结构打散到极限）。评估任何新方案都要两条腿分开检查：同态能力的宽度（支持什么电路）与安全强度的档位（什么困难问题、什么攻击模型）。把两个维度混为一谈是初学者最常见的判断错误。

第三个边界：同态求值的正确性是"高概率"而非"绝对"。所有现代方案里，解密正确依赖噪声不越界，而噪声是随机变量——参数合理时失败概率小到工程上可以忽略（例如低于二的负四十次方），但它原则上非零。这意味着极端保守的场景（法律效力的计算存证）要额外考虑错误控制：参数留足余量、关键结果附带校验。教科书为了简洁常省略这层概率语义，工程实现里它是参数选择的一部分。

常见问题：同态加密和"加密数据库"是一回事吗

不是。加密数据库（或透明加密、字段加密）解决的是静态存储保密——落盘的数据加密，读取时解密，计算发生在明文域，密钥与计算在同侧。同态加密解决的是计算域保密——计算方全程不见明文，密钥与计算分离。两者的信任模型完全不同：前者防"硬盘被拖走"，后者防"服务器管理员偷看"。真实系统常把两者叠加（传输层加静态加密加同态计算），但混淆概念会导致安全设计出现空洞——用静态加密的方案去抵御"好奇的服务器"，是拿错了武器。