Paillier 算法

Paillier 是 Pascal Paillier 在 1999 年提出的概率型公钥密码体制。它最重要的工程价值是加法同态：不解密也能在密文域完成明文加法和明文标量乘。

在联邦学习、安全聚合、电子投票和安全多方计算中，Paillier 常被用来保护中间统计量或梯度。它不是全同态加密，不能直接完成两个密文对应明文的乘法。

一句话概括

Paillier 把明文放在模 $n$ 的加法群里，把密文放在模 $n^2$ 的乘法群里：

$$m\in {\mathbb{Z}}_n,c\in {\mathbb{Z}}_{n^2}^{\ast }$$

密文相乘会对应到明文相加：

$$D(E(m_1)E(m_2))\equiv m_1+m_2(\mathrm{mod}n)$$

这也是 Paillier 适合做密文聚合的根本原因。

数学基础

明文、随机数和密文空间

设 $p$、$q$ 是两个大素数：

$$n=pq$$

明文空间通常取为：

$$\mathcal{M}={\mathbb{Z}}_n$$

随机数从可逆剩余类中选取：

$$r\in {\mathbb{Z}}_n^{\ast }$$

密文在模 $n^2$ 下计算：

$$\mathcal{C}\subseteq {\mathbb{Z}}_{n^2}^{\ast }$$

Paillier 的加密形式为：

$$c=g^m{r}^n\mathrm{mod}{n}^2$$

其中 $g$ 是公钥中的生成元，$r$ 提供概率性。即使同一个 $m$ 被重复加密，只要 $r$ 不同，得到的 $c$ 也会不同。

困难假设

Paillier 的语义安全性通常建立在判定性复合剩余类假设上。直观地说，给定 $z\in {\mathbb{Z}}_{n^2}^{\ast }$，判断它是否存在某个 $y$ 使得：

$$z\equiv y^n(\mathrm{mod}{n}^2)$$

在不知道 $p$、$q$ 的情况下被认为是困难的。这个问题称为判定性复合剩余类问题，常记为 DCR 问题。

标准算法流程

密钥生成

1. 选择两个大素数 $p$、$q$，并计算：

$$n=pq$$

2. 计算 Carmichael 函数：

$$\lambda =\mathrm{lcm}(p-1,q-1)$$

3. 选择 $g\in {\mathbb{Z}}_{n^2}^{\ast }$，要求下式在模 $n$ 下存在逆元：

$$L(g^{\lambda }\mathrm{mod}{n}^2)$$

其中辅助函数定义为：

$$L(u)=\frac{u-1}{n}$$

4. 计算：

$$\mu ={\left(L(g^{\lambda }\mathrm{mod}{n}^2)\right)}^{-1}\mathrm{mod}n$$

公钥和私钥分别为：

$$\mathrm{pk}=(n,g)$$

$$\mathrm{sk}=(\lambda ,\mu )$$

加密

给定明文：

$$0\le m<n$$

随机选择：

$$r\in {\mathbb{Z}}_n^{\ast }$$

计算密文：

$$c=E(m;r)=g^m{r}^n\mathrm{mod}{n}^2$$

解密

给定密文 $c$，先计算：

$$u=c^{\lambda }\mathrm{mod}{n}^2$$

再恢复明文：

$$m=L(u)\mu \mathrm{mod}n$$

也就是：

$$m=L(c^{\lambda }\mathrm{mod}{n}^2)\mu \mathrm{mod}n$$

常用优化：取 $g=n+1$

工程实现里经常直接选：

$$g=n+1$$

这时由二项式定理可得：

$$(n+1{)}^m\equiv 1+mn(\mathrm{mod}{n}^2)$$

因此加密公式可以化简为：

$$c=(1+mn)r^n\mathrm{mod}{n}^2$$

私钥参数也可以化简。因为：

$$L((n+1{)}^{\lambda }\mathrm{mod}{n}^2)\equiv \lambda (\mathrm{mod}n)$$

所以：

$$\mu ={\lambda }^{-1}\mathrm{mod}n$$

这个优化把 $g^m\mathrm{mod}{n}^2$ 的大模幂变成一次乘加，对加密端非常友好。它成立的前提是：

$$\gcd (\lambda ,n)=1$$

实践中通常会在选取 $p$、$q$ 时检查：

$$\gcd (n,(p-1)(q-1))=1$$

同态性质

密文乘法对应明文加法

设：

$$c_1=g^{m_1}{r}_1^n\mathrm{mod}{n}^2$$

$$c_2=g^{m_2}{r}_2^n\mathrm{mod}{n}^2$$

则：

$$c_1{c}_2\equiv g^{m_1+m_2}(r_1{r}_2{)}^n(\mathrm{mod}{n}^2)$$

所以：

$$D(c_1{c}_2)\equiv m_1+m_2(\mathrm{mod}n)$$

也就是：

$$D(E(m_1)E(m_2))\equiv m_1+m_2(\mathrm{mod}n)$$

密文幂对应明文标量乘

对任意整数 $k$：

$$c^k\equiv g^{km}(r^k{)}^n(\mathrm{mod}{n}^2)$$

因此：

$$D(E(m{)}^k)\equiv km(\mathrm{mod}n)$$

在联邦学习聚合中，密文加法和标量乘足以表达许多求和型统计量。

负数和定点数编码

Paillier 原生明文是模 $n$ 的非负整数。实际系统要处理负数和浮点数时，通常先做编码。

负数可以用模空间高位表示。例如把整数 $x$ 编码为：

$$\mathrm{EncInt}(x)=x\mathrm{mod}n$$

解码时可设阈值：

$$\mathrm{DecInt}(y)=\{\begin{array}{ll}y,& 0\le y<\frac{n}{2}\\ y-n,& \frac{n}{2}\le y<n\end{array}$$

浮点数一般用定点数缩放。给定缩放因子 $S$：

$$\tilde{x}=\lfloor Sx\rceil$$

密文域完成加法后再除以 $S$ 还原近似值。

解密正确性证明

Paillier 解密里最容易绕的地方是：密文里明明混入了随机数 $r$，为什么做一次 $c^{\lambda }\mathrm{mod}{n}^2$ 再套 $L$ 函数，就能把明文 $m$ 取出来。

先把密文写成：

$$c=g^m{r}^n\mathrm{mod}{n}^2$$

设：

$$a=L(g^{\lambda }\mathrm{mod}{n}^2)$$

密钥生成要求 $a$ 在模 $n$ 下存在逆元，并令：

$$\mu =a^{-1}\mathrm{mod}n$$

随机因子会消失

因为 $r\in {\mathbb{Z}}_n^{\ast }$，而 $\lambda =\mathrm{lcm}(p-1,q-1)$ 是 ${\mathbb{Z}}_n^{\ast }$ 的 Carmichael 指数，所以：

$$r^{\lambda }\equiv 1(\mathrm{mod}n)$$

于是存在整数 $k$，使得：

$$r^{\lambda }=1+kn$$

再利用 [[02-Area/07-算法/00-基本算法/01-二项式定理|二项式定理]]：

$$r^{n\lambda }=(r^{\lambda }{)}^n=(1+kn{)}^n\equiv 1(\mathrm{mod}{n}^2)$$

也就是说，随机因子 $r^n$ 在提升到 $\lambda$ 次方之后，会在模 $n^2$ 下变成 $1$。

明文因子会线性化

因为 $g\in {\mathbb{Z}}_{n^2}^{\ast }$，所以 $g\mathrm{mod}n\in {\mathbb{Z}}_n^{\ast }$，同样有：

$$g^{\lambda }\equiv 1(\mathrm{mod}n)$$

因此 $g^{\lambda }\mathrm{mod}{n}^2$ 一定可以写成：

$$g^{\lambda }\mathrm{mod}{n}^2=1+an$$

其中 $a=L(g^{\lambda }\mathrm{mod}{n}^2)$。于是：

$$(g^{\lambda }{)}^m\equiv (1+an{)}^m\equiv 1+man(\mathrm{mod}{n}^2)$$

套用 $L$ 函数恢复明文

把两部分合起来：

$$c^{\lambda }\equiv (g^m{r}^n{)}^{\lambda }\equiv (g^{\lambda }{)}^m{r}^{n\lambda }\equiv 1+man(\mathrm{mod}{n}^2)$$

所以：

$$L(c^{\lambda }\mathrm{mod}{n}^2)=\frac{(1+man)-1}{n}\equiv ma(\mathrm{mod}n)$$

最后乘上 $\mu =a^{-1}\mathrm{mod}n$：

$$L(c^{\lambda }\mathrm{mod}{n}^2)\mu \equiv ma\cdot a^{-1}\equiv m(\mathrm{mod}n)$$

这就证明了解密公式：

$$D(c)=L(c^{\lambda }\mathrm{mod}{n}^2)\mu \mathrm{mod}n$$

确实能恢复明文 $m$。如果采用 $g=n+1$，则 $a\equiv \lambda (\mathrm{mod}n)$，所以前面常用优化里的 $\mu ={\lambda }^{-1}\mathrm{mod}n$ 只是这个证明的一个特例。

硬件实现视角

Paillier 的主要开销集中在模幂和大整数模乘。标准加密需要计算：

$$r^n\mathrm{mod}{n}^2$$

解密需要计算：

$$c^{\lambda }\mathrm{mod}{n}^2$$

如果 $n$ 是 $2048$ 位，则 $n^2$ 对应约 $4096$ 位模数。也就是说，Paillier 的底层模乘位宽通常是同安全级 RSA 的两倍左右。

采用 $g=n+1$ 后，加密端仍然要做一次 $r^n\mathrm{mod}{n}^2$，但省掉了 $g^m\mathrm{mod}{n}^2$。解密端仍然是大模幂，是硬件加速的重点。

常见优化包括：

• 用 Montgomery 模乘实现连续模乘。
• 用滑动窗口或固定窗口方法减少模乘次数。
• 对解密端利用 CRT，把模 $n^2$ 运算拆到与 $p^2$、$q^2$ 相关的更小模数上。
• 对批量加密场景预计算 $r^n\mathrm{mod}{n}^2$。

优缺点

优点：

• 支持天然的加法同态，适合安全求和与梯度聚合。
• 加密具有概率性，相同明文多次加密会得到不同密文。
• 数学结构简洁，工程实现和安全分析都比较成熟。

缺点：

• 只支持加法同态，不能直接完成密文之间的乘法。
• 密文模数是 $n^2$，带来明显的存储和带宽膨胀。
• 大整数模幂开销高，尤其在批量联邦学习场景中容易成为瓶颈。