第3章 部分同态加密：Paillier、ElGamal等

部分同态加密，说白了就是只支持一种同态运算的加密方案。

要么只能做加法，要么只能做乘法。

不能同时支持两种，这也是它跟全同态加密最大的区别。

我早年做隐私计算项目时，经常被客户追问：“你们能不能既算加法又算乘法？”

结果我只能说：“部分同态，咱得选一个方向。”

这一章就聊聊两个最具代表性的方案——ElGamal（乘法同态）和Paillier（加法同态）。

3.1 ElGamal：乘法同态的经典

ElGamal加密系统基于Diffie-Hellman密钥交换，安全性依赖离散对数困难问题。

密文由两部分组成：(c₁, c₂)，其中 c₁ = gʳ，c₂ = m · yʳ。

这个结构天然支持乘法同态。你想想看：

• 加密 m₁ 得 (c₁₁, c₁₂)
• 加密 m₂ 得 (c₂₁, c₂₂)
• 密文对应相乘：(c₁₁·c₂₁, c₁₂·c₂₂) 正好对应 m₁·m₂ 的加密结果

3.2 Paillier：加法同态的主力

Paillier算法基于复合剩余类问题，它的同态特性正好跟ElGamal互补。

加密公式：c = gᵐ · rⁿ mod n²。

它的加法同态很简单：

• 密文相乘 = 明文相加
• 还可以做标量乘法：cᵏ 对应 k·m

我最早接触Paillier是在一个医疗数据统计项目里。医院想统计病患平均年龄，但又不想泄露单个患者的年龄。

密文加一加，最后解密得到总和，再除以人数就搞定了。

整个过程不需要看到任何原始年龄。

3.3 两种方案的对比

特性	ElGamal	Paillier
安全基础	离散对数（DDH假设）	复合剩余类问题
同态类型	乘法同态	加法同态
密文长度	2倍明文长度	2倍n²长度（约2048位）
适用场景	乘积聚合、阈值签名	求和统计、均值计算
是否可重随机化	是	是

说起重随机化这个特性，我记得有个同事想把ElGamal用在一个匿名投票系统里。他一开始没做重随机化，结果同一选票的密文特征太明显，直接暴露了投票模式。加上重随机化之后，同样内容的选票每次看起来都不一样。

3.4 代码实战：同态操作

下面我直接用Python演示一下两种方案的核心同态操作。注意这只是教学示意，实际生产环境得用标准库（比如python-paillier或cryptography框架）。

# ElGamal 乘法同态示意（忽略密钥生成细节）
# 假设已经有公钥 (g, y) 和私钥 x
def elgamal_encrypt(m, g, y, r):
    c1 = pow(g, r, p)
    c2 = (m * pow(y, r, p)) % p
    return (c1, c2)

def elgamal_mul_homomorphic(ct1, ct2):
    # 密文分量分别相乘
    c1 = (ct1[0] * ct2[0]) % p
    c2 = (ct1[1] * ct2[1]) % p
    return (c1, c2)

# Paillier 加法同态示意
def paillier_encrypt(m, g, n, r):
    # c = g^m * r^n mod n^2
    c = (pow(g, m, n*n) * pow(r, n, n*n)) % (n*n)
    return c

def paillier_add_homomorphic(c1, c2):
    return (c1 * c2) % (n*n)

# 标量乘法
def paillier_scalar_mult(c, k):
    return pow(c, k, n*n)

3.5 知识结构图

我把两种部分同态加密的逻辑画在一张图上，方便你对照理解。

3.6 选型避坑指南

我做了几年工程，每次给团队选型时都会按这个思路推一遍：

1. 先问业务到底需要什么运算 —— 统计求和用Paillier，乘法聚合用ElGamal。
2. 再看数值范围 —— ElGamal的乘法结果增长很快，Paillier的加法则好控制得多。
3. 别忽视计算开销 —— Paillier的模指数运算比ElGamal重不少，遇到高并发场景要提前压测。
4. 重随机化能力有没有用？ 做匿名投票、交易混淆时，ElGamal的重随机化特别方便。