Paillier 加法同态加密：从数学原理到隐私计算的基石

概述

2009 年 Craig Gentry 证明第一个全同态加密方案存在时，他在论文中明确引用了三个"里程碑式"的前驱工作：1978 年 RSA 算法隐含的乘法同态特性、1999 年 Pascal Paillier 提出的加法同态加密、以及 1985 年 ElGamal 的乘法同态特性。其中，Paillier 加密是唯一仍在实际工程中广泛使用的部分同态方案。

与后来的 BFV、CKKS、TFHE 等 FHE 方案不同，Paillier 不涉及复杂的格密码结构或多项式环运算，其安全性基于经典的合数剩余类问题（Decisional Composite Residuosity Assumption, DCRA），这在计算数论中有严格的归约关系。更重要的是，Paillier 支持高效的批量加密（batch encryption）和同态加法操作，使其在电子投票、隐私求和、安全多方计算等场景中具有不可替代的价值。

本文从 DCRA 假设出发，完整推导 Paillier 方案的数学构造，分析其在隐私计算中的应用范式，并与国密 SM9 标识密码中的配对运算进行对比，探讨国密体系在同态加密领域的演进空间。

数学基础：合数剩余类问题

1.1 二次剩余与 Jacobi 符号

设 $n = p \times q$ 是两个安全素数的乘积（即 $p = 2p' + 1$，$q = 2q' + 1$，其中 $p', q'$ 也是素数）。对于任意 $x \in \mathbb{Z}_n^*$，定义：

$$\left(\frac{x}{n}\right) = \left(\frac{x}{p}\right) \cdot \left(\frac{x}{q}\right)$$

其中 $\left(\frac{x}{p}\right)$ 是 Legendre 符号：

$$\left(\frac{x}{p}\right) = x^{(p-1)/2} \bmod p \in \{1, -1\}$$

1.2 二次剩余子群 $QR_n$

$\mathbb{Z}_n^*$ 中的二次剩余定义为：

$$QR_n = \{y \in \mathbb{Z}_n^* \mid \exists x \in \mathbb{Z}_n^*, y \equiv x^2 \pmod{n}\}$$

关键性质：

• $|QR_n| = \phi(n)/4$，即 $\mathbb{Z}_n^*$ 的子群，指数为 4
• 对于 $y \in QR_n$，存在恰好 4 个平方根（由中国剩余定理保证）
• 判定一个元素是否属于 $QR_n$ 需要知道 $n$ 的因子分解

1.3 DCRA 假设

DCRA（合数剩余类判定假设）：给定 $n = pq$ 和随机 $z \in \mathbb{Z}_n^*$，区分 $z \in QR_n$ 与 $z$ 为随机元素的计算困难性，等价于整数分解问题。

形式化定义：

$$\text{Adv}_{\mathcal{A}}^{\text{DCRA}}(\lambda) = \left|\Pr[\mathcal{A}(n, z) = 1 \mid z \xleftarrow{R} \mathbb{Z}_n^*] - \Pr[\mathcal{A}(n, z) = 1 \mid z \xleftarrow{R} QR_n]\right|$$

如果对于所有 PPT 算法 $\mathcal{A}$，$\text{Adv}_{\mathcal{A}}^{\text{DCRA}}(\lambda)$ 可忽略，则 DCRA 成立。

与素性判定的关系：当 $n$ 是素数时，二次剩余判定可由 Euler 准则高效解决；但当 $n$ 是合数时，该问题被认为是困难的——这正是 Paillier 安全性的根基。

Paillier 加密方案

2.1 参数设置

密钥空间：选择两个等长大小的安全素数 $p, q$，计算 $n = pq$，$\lambda = \text{lcm}(p-1, q-1)$。

消息空间：$\mathbb{Z}_n$，即任意整数模 $n$。

密文空间：$\mathbb{Z}_{n^2}^*$，即模 $n^2$ 的可逆元素构成的乘法群。

2.2 密钥生成

KeyGen():
  1. 随机选择安全素数 p, q
  2. 计算 n = p × q, λ = lcm(p-1, q-1)
  3. 计算 g = n + 1（Paillier 原始方案的特定点）
  4. 计算 μ = λ^(-1) mod n
  5. 公钥 pk = (n, g)，私钥 sk = (λ, μ)

为什么选择 g = n + 1？

这是一个精巧的设计选择。当 $g = 1 + n$ 时，有：

$$L(g^x \bmod n^2) = L((1+n)^x \bmod n^2) = L(1 + nx \bmod n^2) = x$$

其中 $L(u) = \frac{u-1}{n} \bmod n$ 是 Paillier 特有的辅助函数。这使得解密过程极其简洁：

$$m = L(c^λ \bmod n^2) \cdot μ \bmod n$$

2.3 加密过程

Encrypt(pk, m; r):
  输入：明文 m ∈ Z_n，随机数 r ∈ Z_n*
  输出：密文 c ∈ Z_{n^2}*
  
  1. 计算 c = g^m · r^n mod n²
  2. 返回 c

为什么需要随机数 r？

这是 Paillier 的概率加密特性——同一个明文 $m$ 多次加密会产生不同的密文。这提供了 IND-CPA 安全（语义安全），防止攻击者通过密文比对推断明文。

数学验证：

$$c = (1+n)^m \cdot r^n \bmod n^2 = (1 + nm) \cdot r^n \bmod n^2$$

由于 $r^n \bmod n^2 \in \mathbb{Z}_{n^2}^*$ 且阶整除 $\lambda$，我们有：

$$c \bmod n = r^n \bmod n \in \mathbb{Z}_n^*$$

因此可以通过 $c \bmod n$ 检查密文的有效性（但不足以恢复 $m$）。

2.4 解密过程

Decrypt(sk, c):
  输入：密文 c ∈ Z_{n²}*
  输出：明文 m ∈ Z_n
  
  1. 计算 u = c^λ mod n²
  2. 计算 m = L(u) · μ mod n
  3. 返回 m

解密正确性证明：

由于 $c = g^m \cdot r^n \bmod n^2$，且 $g = 1 + n$：

$$c^\lambda = (1+n)^{m\lambda} \cdot r^{n\lambda} \bmod n^2$$

注意到 $r^{n\lambda} \equiv 1 \pmod{n^2}$（因为 $r^\lambda \equiv 1 \pmod{n}$），所以：

$$c^\lambda \equiv (1+n)^{m\lambda} \equiv 1 + nm\lambda \pmod{n^2}$$

因此：

$$L(c^\lambda \bmod n^2) = \frac{(1 + nm\lambda) - 1}{n} = m\lambda \bmod n$$

最后：

$$m = L(c^\lambda) \cdot \mu = m\lambda \cdot \lambda^{-1} = m \bmod n$$

$\blacksquare$

同态性质

3.1 加法同态

Paillier 的核心特性是加法同态：给定两个密文 $c_1 = E(m_1)$ 和 $c_2 = E(m_2)$，可以在不解密的情况下计算 $m_1 + m_2$ 的密文。

定理：$E(m_1) \cdot E(m_2) \equiv E(m_1 + m_2) \pmod{n^2}$

证明：

$$c_1 \cdot c_2 = g^{m_1} r_1^n \cdot g^{m_2} r_2^n = g^{m_1+m_2} (r_1 r_2)^n \bmod n^2$$

这正是 $E(m_1 + m_2)$ 的形式，随机数为 $r_1 \cdot r_2 \bmod n$。

$\blacksquare$

3.2 标量乘法

对于明文 $m$ 和标量 $k \in \mathbb{Z}$，有：

$$E(m)^k \equiv E(k \cdot m) \pmod{n^2}$$

应用：服务器可以对加密数据执行标量乘法，而无需知道数据的真实值。

3.3 混合运算示例

假设 $c_1 = E(m_1)$，$c_2 = E(m_2)$：

3.4 安全性证明思路

IND-CPA 安全性（选择明文攻击下的不可区分性）：

假设存在 PPT 算法 $\mathcal{A}$ 可以区分 Paillier 加密的两个明文 $m_0$ 和 $m_1$。我们可以构造算法 $\mathcal{B}$ 解决 DCRA 问题：

• $\mathcal{B}$ 接收挑战 $(n, z)$，其中 $z \in_R \mathbb{Z}_n^*$ 或 $z \in_R QR_n$
• $\mathcal{B}$ 随机选择 $b \in \{0, 1\}$，计算 $c^* = z \cdot g^{m_b} \bmod n^2$
• $\mathcal{A}$ 输出 $b'$
• 如果 $b' = b$，$\mathcal{B}$ 输出 $z \in QR_n$；否则输出 $z \notin QR_n$

性能特征

4.1 计算复杂度

4.2 与 RSA 的对比

4.3 实际应用中的优化

Batch Encryption（Boneh-Goh-Nissim, 2005）：

Paillier 支持使用多项式编码实现批量加密。设 $v = (v_0, v_1, \ldots, v_k) \in \mathbb{Z}_n^{k+1}$，则可以加密 $k+1$ 个明文：

$$c = g^{\sum_{i=0}^{k} v_i m_i} \cdot r^n \bmod n^2$$

通过适当的参数设置，可以在单次加密中处理多个明文的线性组合。

快速解密优化：

使用中国剩余定理（CRT），可以将解密分为两个子问题：

$$m_p = L(c^\lambda \bmod p^2) \bmod p$$ $$m_q = L(c^\lambda \bmod q^2) \bmod q$$ $$m = \text{CRT}(m_p, m_q) \bmod n$$

这可以将解密速度提升约 4 倍。

应用场景

5.1 电子投票系统

Paillier 最著名的应用是电子投票。假设有 $N$ 个选民，每个选民投票 $v_i \in \{0, 1\}$，选举委员会需要计算总票数 $\sum v_i$ 而不泄露任何个人的投票选择。

协议流程：

1. 选举委员会生成 Paillier 密钥对 (pk, sk)
2. 每个选民 i 计算 E(v_i) 并上传
3. 选举委员会计算 C = ∏ E(v_i) = E(∑v_i)
4. 使用私钥解密 C，得到总票数

安全保证：

• 单个选票无法被追踪（概率加密）
• 总票数正确（同态加法）
• 即使所有非目标节点被攻破，只要有一个 honest node 就安全

5.2 隐私求和

在医疗研究中，多家医院需要计算患者的平均血糖值，但不想透露各自的统计数据。

协议：

• 每家医院 $H_i$ 加密其患者数量 $n_i$ 和血糖总和 $S_i$
• 聚合服务器计算 $\sum E(n_i) = E(\sum n_i)$ 和 $\sum E(S_i) = E(\sum S_i)$
• 解密后得到总患者数和总血糖值
• 计算平均值 $\frac{\sum S_i}{\sum n_i}$

5.3 安全多方计算（MPC）

Paillier 是许多 MPC 协议的基础构件：

国密视角：SM9 与同态加密

6.1 SM9 标识密码的结构特点

SM9（GM/T 0044-2016）是基于双线性对的标识密码标准，其核心操作包括：

签名：d_ID = [t2]P1，其中 t2 = s × t1^(-1) mod N
验证：e([l]U, P2) == ω × e(P1, Ppub)^h
加密：C1 = [k]P1, C2 = H2(e(P_pub, Q_ID)^k) ⊕ M, C3 = H3(kM)

SM9 的配对运算 $e: G_1 \times G_2 \rightarrow G_T$ 提供了强大的代数结构，理论上可以构建同态加密方案。

6.2 Paillier vs SM9 的安全性基础对比

6.3 国密体系在同态加密领域的演进方向

目前国密体系中没有原生的同态加密标准，但以下方向值得关注：

• SM9 扩展：利用 SM9 的配对结构，可以构建基于身份的加密方案，但同态特性仍需额外设计
• PQC 迁移：NIST 标准化的 ML-KEM（Kyber）基于格密码，天然支持同态操作，未来可能与国密体系结合
• 混合方案：结合 SM2 签名 + Paillier 加密，兼顾身份认证与隐私计算

实现要点与陷阱

7.1 Python 参考实现

from hashlib import sha256

class Paillier:
    def __init__(self, key_size=2048):
        self.key_size = key_size
        self.p, self.q = self._generate_primes()
        self.n = self.p * self.q
        self.n_sq = self.n * self.n
        self.lambda_val = (self.p - 1) * (self.q - 1)  # 简化版
        self.mu = pow(self.lambda_val, -1, self.n)
        self.g = self.n + 1  # Paillier 原始方案
    
    def _generate_primes(self):
        # 实际实现应使用安全随机数生成器
        from Crypto.PublicKey import RSA
        key = RSA.generate(self.key_size)
        return key.p, key.q
    
    def encrypt(self, m, rand=None):
        if rand is None:
            rand = int.from_bytes(sha256(m.to_bytes(32, 'big')).digest(), 'big') % self.n
        u = pow(self.g, m, self.n_sq)
        v = pow(rand, self.n, self.n_sq)
        return (u * v) % self.n_sq
    
    def decrypt(self, c):
        u = pow(c, self.lambda_val, self.n_sq)
        m = (self._L(u) * self.mu) % self.n
        return m
    
    def _L(self, u):
        return (u - 1) // self.n
    
    def homomorphic_add(self, c1, c2):
        return (c1 * c2) % self.n_sq
    
    def homomorphic_scalar_mul(self, c, k):
        return pow(c, k, self.n_sq)

7.2 常见陷阱

7.3 性能测试（参考）

在 2048-bit 参数下，典型性能数据（Intel Xeon Gold 6248R，2023 年数据）：

注意：以上为参考数据，实际性能取决于硬件平台、库实现和参数大小。生产环境建议实测。

与其他同态方案的对比

8.1 PHE 方案对比

8.2 选择指南

选择 Paillier 当：

• 只需要加法同态（而非全同态）
• 数据规模较大（批量处理需求）
• 需要高效的解密操作
• 不需要乘法同态

• 需要进行复杂的加密计算
• 运算深度可控（< 100 层）
• 接受较低的吞吐量
• 对延迟不敏感

历史与发展

9.1 Paillier 的提出（1999）

Pascal Paillier 在 1999 年的 Eurocrypt 会议上提出了该方案，灵感来源于 Damgård 的近似同态加密思想。Paillier 的关键贡献是将"近似"变为"精确"，并证明了其在 DCRA 假设下的 IND-CPA 安全性。

9.2 后续发展

• 2003：自由等人提出"部分同态数字投票方案"，首次将 Paillier 应用于电子投票
• 2005：Boneh-Goh-Nissim 提出批量加密方案
• 2007：Naccache-Stern 方案的改进版本
• 2010s：在隐私计算、安全多方计算领域广泛应用
• 2020s：成为隐私计算基础设施的标准构件

参考标准与文献

• Paillier, P. (1999). "Public-Key Cryptosystems Based on Composite Degree Residuosity Classes." *Eurocrypt 1999*, LNCS 1592, Springer.
• Damgård, I., & Jurik, M. (2001). "A Generalization, a Simplification and Some Applications of Paillier's Probabilistic Public-Key System." *PKC 2001*, LNCS 2274, Springer.
• Boneh, D., Goh, E. J., & Nissim, K. (2005). "Evaluating 2-DNF Formulas on Ciphertexts." *TCC 2005*, LNCS 3378, Springer.
• GM/T 0044-2016《SM9 标识密码算法》——国密标识密码标准，可作为 Paillier 的国密替代参考
• GB/T 39786-2021《信息安全技术 信息系统密码应用基本要求》——同态加密的合规要求参考

相关实践链接

• SM9 标识密码算法深度解析 —— 国密标识密码的核心技术
• 同态加密基础：从部分同态到全同态加密 —— Paillier 在 HE 体系中的位置