1.3 Paillier 加法同态与噪声之墙

1.3 Paillier 加法同态与噪声之墙

本节摘要：Paillier 于一九九九年提出的概率加密方案让"密文相乘等于明文相加"，同时满足语义安全，成为聚合统计与电子投票的标准工具。本节给出其代数结构、可复算的玩具算例与三类典型用法，随后引入整数方案中的"噪声"概念，说明加法与乘法为何无法在旧结构中并存，把三十年的僵局收敛为一道待解的题。

历史现场：从乘法世界换到加法世界

上一节结尾留了悬念：同一个"密文相乘"动作无法同时表达"明文相乘"与"明文相加"。一九九九年，Paillier 的做法是干脆换地基——把运算从模数的群搬到模数平方的群上，利用一个精巧的代数事实：在模平方剩余类结构里，基的指数相加、随机部分的指数相乘，两个动作可以叠加在一个乘法里完成。于是密文之积恰好对应明文之和，而随机数仍然各自独立，语义安全得以保全。

具体结构如下。取两个大素数之积作为模数，加密时明文放在一个特殊基的指数上，随机数放在另一个基的指数上，两者相乘后对模数的平方取余。解密利用模数结构的知识（两个素数减一的公倍数）把指数还原出来。推导细节对本册不是必需品，你需要记住的是三条运算规则：两个密文相乘，解密得明文之和；密文自乘整数次幂，解密得明文的整数倍；明文乘常数可以不加密直接乘到密文上（明文系数留在模数群里同样守恒）。这三条规则合起来，就是一个完整的"密文线性代数"工具箱。

玩具算例：把加法同态跑通

下面用小素数把整个流程跑一遍。取素数十三与十七，模数为二百二十一，模数平方为四万八千八百四十一，特殊基取模数加一。这组参数小到可以手算复核，又大到足以展示全部行为。

# Paillier 加法同态：小素数完整算例（python 任意精度整数，无需第三方库）
def modpow(base, exp, mod):
    result, base = 1, base % mod
    while exp > 0:
        if exp & 1:
            result = result * base % mod
        base = base * base % mod
        exp >>= 1
    return result

def modinv(a, m):  # 扩展欧几里得求逆元
    def eg(a, b):
        if b == 0:
            return a, 1, 0
        g, x, y = eg(b, a % b)
        return g, y, x - (a // b) * y
    g, x, _ = eg(a % m, m)
    return x % m

p, q = 13, 17
n, n2 = p * q, (p * q) ** 2          # n = 221, n2 = 48841
lam = 48                              # 素数减一的最小公倍数 lcm(12, 16)
g = n + 1                             # 特殊基取 n+1
mu = modinv((g ** lam % n2 - 1) // n, n)   # 解密辅助量 = 198

def encrypt(m, r):                    # r 为每次加密的随机数
    return modpow(g, m, n2) * modpow(r, n, n2) % n2

def decrypt(c):
    return ((c ** lam % n2 - 1) // n * mu) % n

c1, c2 = encrypt(20, 5), encrypt(9, 7)
print("E(20) =", c1)                  # 44985
print("E(9)  =", c2)                  # 41741
print("密文之积解密 =", decrypt(c1 * c2 % n2))   # 29 = 20 + 9
print("密文立方解密 =", decrypt(modpow(c1, 3, n2)))  # 60 = 3 x 20
print("常数十三次幂 =", decrypt(modpow(c1, 13, n2))) # 39 = 260 mod 221
​

三个输出各讲一件事。密文之积解密回二十九——加法同态成立。密文立方解密回六十——标量乘（明文数乘）也成立，注意它与乘法同态的差别：这里是"明文乘一个常数"，不是"两个明文相乘"。第三个输出是本节的第一个警钟：明文二十乘十三本应是二百六十，但明文空间本身是模二百二十一的，于是回绕成三十九——密文上的线性运算永远活在模数划定的世界里，忘记这一点会在真实系统里制造安静的错误。

它在真实世界里干了什么

加法同态的应用清单比乘法长得多，因为统计学的第一课就是"求和"。三个有代表性的用法值得展开。

第一个是电子投票。每张选票把"投给某候选人"编码为该候选人槽位上的一、其他槽位上的零，各自加密后混入票池；计票员把全部密文相乘，得到一张记录总票数的密文，最后协同解密一次。全程没有任何单张选票以明文出现过，选民的匿名性由密文随机性保证。这个范式自二零零零年代初起被多国选举协议研究采纳，Paillier 家族长期是其中的主力部件。

第二个是聚合统计。一群数据持有方各自加密自己的计数，中心把密文加总后只解密总量——医院联合统计发病率、设备群上报使用指标、广告主合并转化计数，都是同一形状的问题。它的隐私性质干净：中心除了总和什么都学不到。局限同样干净：只解密总和意味着你只回答"总量"类问题，任何更复杂的统计量都超出线性工具箱。

第三个是联邦学习早期的梯度聚合（第五章会展开完整算例）：参与方加密本地梯度，服务器做密文加法得到全局梯度。线性层用 Paillier 刚好够用，这也是它至今仍在生产系统里活跃的原因——不是每个场景都需要全同态，"够用的同态"往往在性能上便宜两三个数量级。

噪声之墙：僵局的解剖

时间来到二零零零年代，两张拼图各有一半：RSA 给了乘法，Paillier 给了加法，但没有任何一个密文能同时享受两种运算。要理解墙在哪里，最好的入口是后来 Dijk、Gentry、Halevi、Vaikuntanathan 在二零一零年提出的整数方案雏形——它把"为什么难"展示得最裸露。

那个方案把密文写成三部分之和：明文，加上一个小的偶数随机项（这就是噪声），再加上模数与一个辅助大整数的乘积。解密时对密文取模二，噪声与模数项自动消失，明文落出来。加法是仁慈的：两个密文相加，噪声不过相加，慢悠悠地线性增长。乘法是残酷的：两个三项式相乘，噪声项近似相乘——从"小"直接跳到"小乘小还是不小"，更糟的是两个密文再乘，噪声以平方速度膨胀，几个深度之后就淹没明文位。用数字说话：若初始噪声占十位比特，一次密文乘法后约二十位，两次后约四十位，三次后约八十位——而模数总共只有百余位，三到四层乘法深度就是天花板。

这就是"些许同态"的准确含义：支持加法与乘法，但乘法深度受噪声预算约束。它也解释了分类的深层逻辑——不是工程师没做完，而是这个结构里"能算多少"是一个耗尽型资源。从二十世纪八十年代到本世纪初的众多尝试（椭圆曲线上的配对方案、双线性映射构造等）都撞在同一面墙上：能给一点深度，但深度与安全性此消彼长，无法做到任意。

破冰需要的不是修补，而是视角反转：既然噪声必然增长，能不能在密文还健康的时候，把它"洗"一遍？这个问题在二零零九年之前没有人知道答案，因为洗噪声意味着"在不解密的前提下对密文执行解密函数"——自相矛盾的要求。Gentry 的博士论文证明了这件事可以不自相矛盾，但前提是把整个方案搬到一块新地基上。下一章，我们先看那块地基。

💡 关键直觉：把噪声预算想象成一组建筑地基的承重余量——每加一层楼（乘法）余量平方级消耗，加法只线性占用；"全同态"的目标不是让余量无穷大，而是发明一种在余量耗尽前加固地基的工艺。

本节要点回顾

• 要点一：Paillier 的结构让密文相乘对应明文相加、密文取幂对应明文数乘，且自带随机性满足语义安全，是聚合统计与电子投票的主力
• 要点二：算例验证三条线性规则；明文运算活在模数世界里，超出模数的回绕（二百六十变三十九）是真实系统的安静错误来源
• 要点三：整数方案雏形把噪声展示得最清楚——加法线性增长、乘法平方增长，乘法深度是耗尽型资源，"些许同态"由此得名
• 要点四：三十年的僵局在于"同时支持加乘"与"噪声可控"不可兼得，破题需要让密文在不解密的前提下自我清洗噪声

走深一步：电子投票协议的完整骨架

把 Paillier 的加法同态装配成一份可运行的投票协议，能看清线性工具箱的能力与边界。设定一场三名候选人的选举：选民把选票编码成三元组，投给谁的槽位放一、其余放零；每人用联合公钥加密自己的选票（随机数保证两张相同的选票密文也不同，防比对）。票池聚合：计票员把全部密文相乘，得到一张密文，它解密后是三元组形式的总票数。正确性由加法同态直接保证——这正是 Paillier 在无数选举协议研究里担任主角的原因。

安全与隐私的补丁要打四层。第一层，选票合法性：计票员怎么知道密文里真的是"恰好一个一、其余零"，而不是"某槽位放了九十九"的作弊票？标准做法是选民附一份零知识证明，证明密文里的三元组合法——不泄露投给谁，只证明格式正确。第二层，防重复投票：身份层（选票之外的凭证系统）负责一人一票，与加密层解耦。第三层，门限解密：解密私钥由多名信托人分持，凑不够门限人数谁也开不了票箱——计票的"权威"被拆散。第四层，可验证性：公告板上全部密文留档，任何人可以重放乘法聚合核对总票数。四层补丁合起来，就是"加密聚合、零知识合规、门限权威、公开可审计"的完整骨架——把这个骨架里的 Paillier 换成第三章的整数线方案、把聚合对象从选票换成梯度，它就是第五章联邦学习的加密聚合；换成交易金额，它就是区块链场景的保密结算。同一个协议骨架在不同时代反复重生，这是演化史视角给的额外馈赠。

Paillier 本身的工程参数也值得记录，为第五章的性能对比留锚点：密钥生成需要生成两个大素数（与同级 RSA 相当），加密一次模乘加一次模幂（约为 RSA 加密的两倍工作量），密文是模数平方级别的数（约为同级 RSA 密文的两倍长）。在千万级密文的聚合任务里，这些常数因子会累积成可感知的成本，但对比全同态方案仍然便宜两个数量级——"够用的同态"这句选型格言的量化依据就在这里。

常见问题：Paillier 今天还有竞争力吗

在纯加法聚合的场景里，有，而且常常是最优选。它的安全基于合数剩余类问题（与大整数分解密切相关，注意这意味着它不像格方案那样天然抗量子），实现简单、审计容易、常数因子小。生产系统里"是否升级到格方案"的决策通常由两个问题驱动：负载是否会超出线性运算（会则必须升级），合规是否要求后量子水位（是则建议升级，参见第六章）。只做求和、生命周期短、量子威胁窗口外的内部系统，用 Paillier 是理性的工程决策而非保守。