Paillier 1999 — 能在密文上直接做加法的公钥加密

待复核

是什么

Paillier 加密是一种别人看不到数字，却还能帮你把数字相加的公钥加密。日常类比：每个人把投票纸放进透明但打不开的盒子，计票员看不到每张票，却能把所有盒子叠起来，最后只让有钥匙的人打开总票数。

普通加密像把文件塞进保险柜：外人只能保存或转发，不能改动内容。Paillier 的特别之处是，外人可以把两个密文相乘，解密后得到的却是两个明文相加。

论文标题里的“复合剩余类”听起来很硬，其实核心直觉是：选两个大素数 p, q，公开 n = p * q，但不公开 p, q。不知道分解的人很难判断某个数是不是“某类 n 次剩余”，知道分解的人可以快速解开。

这篇论文给了三个构造，其中最常被今天系统引用的是 Scheme 1：概率加密 + 加法同态 + 标准模型下基于 DCRA 的语义安全证明。

为什么重要

不理解 Paillier，下面这些事都讲不清：

为什么电子投票可以“单票保密、总票可数”——密文能先相加，最后只解密总和。
为什么 PSI / MPC 协议里经常出现“加法同态加密”这个组件——它让一方在不知道数值时仍能做线性聚合。
为什么全同态加密之前，密码学已经有“半同态”路线——Paillier 是加法同态代表。
为什么隐私计算里“加密”和“可计算”不是天然矛盾——Paillier 展示了有限计算能力可以嵌进加密方案。

核心要点

陷门还是大整数分解：类比门锁，公开的 n 是锁孔，私有的 p, q 是钥匙齿形。知道 p, q 的人能算出解密需要的 λ，不知道的人只能面对一个大整数分解难题。
随机数让同一条消息每次密文不同：类比同一句话可以装进不同颜色的信封。加密公式里有随机 r，所以同一个 m 多次加密会得到不同 c，攻击者不能靠“看起来一样”猜明文。
密文乘法对应明文加法：类比把两个封好的投票箱扣在一起，外面的人看不到里面是什么，但最后打开会得到总票数。公式上就是 Dec(Enc(a) * Enc(b)) = a + b mod n。

这三点合起来，就是 Paillier 的定位：不是万能计算机，而是一个非常好用的“保密加法器”。

实践案例

案例 1：玩具版 Paillier 跑通一次加解密

from math import gcd, lcm
import random

p, q = 17, 19
n = p * q
n2 = n * n
g = n + 1
lam = lcm(p - 1, q - 1)
L = lambda x: (x - 1) // n
mu = pow(L(pow(g, lam, n2)), -1, n)

def enc(m):
    r = random.randrange(1, n)
    while gcd(r, n) != 1:
        r = random.randrange(1, n)
    return (pow(g, m, n2) * pow(r, n, n2)) % n2

def dec(c):
    return (L(pow(c, lam, n2)) * mu) % n

逐部分解释：

n = p * q 是公钥的一部分；p, q 不能泄露。
g = n + 1 是常见简化选法，方便初学者看公式。
r 是每次加密的新随机数，同一条消息不会固定成同一个密文。
dec 里的 lam 和 mu 来自私钥信息，外人没有它们就很难还原明文。

案例 2：密文相乘，明文相加

a = enc(7)
b = enc(5)
total_cipher = (a * b) % n2
print(dec(total_cipher))  # 12

逐部分解释：

操作者只拿到 a 和 b 两个密文，不知道里面是 7 和 5。
他做的动作只是乘法：a * b mod n²。
解密者打开后得到 12，这就是“密文乘法 → 明文加法”。
如果明文和超过 n，结果会按 mod n 回绕，所以生产系统要设计数值范围。

案例 3：加密投票只公开总数

votes = [1, 0, 1, 1, 0]   # 1 表示赞成，0 表示反对
cipher_sum = 1
for vote in votes:
    cipher_sum = (cipher_sum * enc(vote)) % n2

print(dec(cipher_sum))    # 3

逐部分解释：

每张票单独加密，计票服务器看不到单个选民投了什么。
服务器把所有密文乘起来，等价于把明文票数相加。
最后只解密总和 3，不需要暴露每个人的选择。
真实电子投票还要配合身份认证、零知识证明和审计日志，Paillier 只解决“保密计数”这一块。

踩过的坑

把 Paillier 当全同态加密：它主要支持加法和“密文乘常数”，不能任意做密文乘密文的明文乘法。
忘记随机数 r 必须每次新鲜：重复或弱随机会让概率加密退化，攻击者可能关联同一明文。
忽略 mod n 回绕：加法结果超过 n 会取模，计票、求和、统计前必须先给最大值留足空间。
以为语义安全等于抗所有攻击：论文的主方案证明的是 chosen-plaintext 语义安全，不是直接抗 chosen-ciphertext 攻击。

适用 vs 不适用场景

适用：

电子投票、匿名问卷、隐私统计这类只需要求和的场景。
PSI / MPC 中需要线性聚合、盲化或阈值解密的子协议。
小规模隐私计算教学和原型验证，公式比现代 FHE 更容易手写。
需要自盲化的协议，让密文可以公开刷新但明文不变。

不适用：

大文件或实时流量加密；Paillier 密文膨胀明显，速度也不如对称加密。
任意机器学习推理；需要加法和乘法组合时应看 gentry-fhe-2009 或后续 FHE。
抗量子长期保密；它仍依赖大整数分解相关困难假设。
直接裸用到生产协议；还需要 padding、范围证明、CCA 转换和密钥管理。

历史小故事（可跳过）

1976 年：diffie-hellman-1976 提出公钥密码学方向，让“公开加密钥匙、私钥解密”成为研究目标。
1978 年：rsa 给出第一个实用公钥密码，安全直觉来自大整数分解难题。
1980s-1990s：Goldwasser-Micali、Benaloh、Naccache-Stern 等方案探索“剩余类 + 同态”的路线。
1999 年：Pascal Paillier 在 EUROCRYPT 发表本文，把复合剩余类假设、概率加密和加法同态组织成一个清晰方案。
2000 年以后：Paillier 被电子投票、阈值密码、PSI、安全聚合等协议反复拿来当基础积木。

学到什么

半同态已经很有用：只支持加法也足够支撑投票、求和、聚合和很多隐私协议。
安全假设要分层看：DCRA 负责“看不出明文差异”，CCRA 负责“算不出剩余类”，分解 n 则是持钥匙者的陷门。
随机化是公钥加密的生命线：同一明文必须能加密成许多不同密文，才有语义安全的直觉。
理论组件到生产协议还有距离：Paillier 只是组件，完整系统还要处理恶意输入、范围证明、阈值解密和审计。

关联

rsa —— Paillier 和 RSA 都用 n = p * q，但 Paillier 把模数扩到 n² 并获得加法同态。
diffie-hellman-1976 —— 公钥密码学的起点，Paillier 是之后“可计算密文”的一条支线。
gentry-fhe-2009 —— Paillier 是加法同态代表，Gentry 解决的是同时支持加法和乘法的全同态。
brakerski-bgv-2012 —— BGV 是更实用的 FHE 后继，和 Paillier 都服务于密文计算但能力层级不同。
rabin-ot-1981 —— OT 解决“选而不泄露”，Paillier 解决“算而不看”，两者都是 MPC/PSI 积木。
dwork-dp-icalp-2006 —— 差分隐私保护统计输出，Paillier 保护统计计算过程中的输入。
zk-snark —— 零知识证明可证明投票或范围合法，常与 Paillier 这类加密组件组合。

反向链接

freedman-psi-2004 —— Freedman PSI 2004 — 把集合交集算出来但不交出名单

Paillier 1999 — 能在密文上直接做加法的公钥加密

是什么

为什么重要

核心要点

实践案例

案例 1：玩具版 Paillier 跑通一次加解密

案例 2：密文相乘，明文相加

案例 3：加密投票只公开总数

踩过的坑

适用 vs 不适用场景

历史小故事（可跳过）

学到什么

延伸阅读

关联

反向链接