Paillier 加法同态加密

形式陈述

Paillier 是一种加法同态公钥加密：密文相乘，解密得到明文相加。这里给出常用的 $g=1+n$ 版本。[1]

生成不同的大奇素数 $p,q$ ，令

n=pq,\qquad \lambda_n=\operatorname{lcm}(p-1,q-1), \qquad \gcd(n,\lambda_n)=1.

最后一个条件保证 $\lambda_n$ 在模 $n$ 下可逆。公开 $n$ 和 $g=1+n$ ，保留 $\lambda_n$ 及 $\nu=\lambda_n^{-1}\bmod n$ 。这里 $\lambda_n$ 是数论指数，不是一般记号中的密码学安全参数。

明文为 $m\in\mathbb Z_n$ 。每次独立均匀抽取 $r\in\mathbb Z_n^*$ ，输出

\operatorname{Enc}(m;r)=(1+n)^m r^n\pmod{n^2}. \tag{1}

对合法密文，先算 $u=c^{\lambda_n}\bmod n^2$ 。它满足 $u\equiv1\pmod n$ ，所以整数函数

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

有定义。解密为

\operatorname{Dec}(c)=L(c^{\lambda_n}\bmod n^2)\,\nu\pmod n. \tag{2}

所有等式的模数都很重要：加密和密文运算在模 $n^2$ 中，消息和最后解密结果在模 $n$ 中。相关记号见同余与模运算。

保密性依赖判定合数剩余类假设（DCRA）：对合法生成的大模数 $n$ ，高效算法不能区分均匀 $n$ 次剩余 $r^n\bmod n^2$ 与均匀的 $\mathbb Z_{n^2}^*$ 元素。此处的随机化与假设是计算安全条件，不能由式 (2) 的正确性推出。

直觉

$(1+n)^m$ 负责携带消息。二项式展开模 $n^2$ 后，二次及以上项都消失，只留下 $1+mn$ ，所以这里藏着一个很简单的线性编码。

$r^n$ 则把编码藏到一个随机陪集里。知道分解的人能用 $\lambda_n$ 消去随机因子，再用 $L$ 把“偏离1的多少个 $n$ ”读出来。外部观察者看到的是陪集中的随机元素，而不是直接可读的 $1+mn$ 。

明文2与4在模15下相加得到6；对应密文158与223在模225下相乘得到134，解密回到6。

例子与边界

模225的完整计算

取教学参数 $p=3,q=5$ ，于是 $n=15$ 、 $\lambda_n=4$ 、 $\nu=4$ ，因为 $4\cdot4\equiv1\pmod{15}$ 。这两个素数太小，完全不提供保密性。

加密2时选 $r_1=2$ ，加密4时选 $r_2=7$ 。模225计算给出

c_1=16^2\,2^{15}\bmod225=158, \qquad c_2=16^4\,7^{15}\bmod225=223.

先分别检查： $158^4\bmod225=121$ ，故 $L(121)=8$ ，再乘4模15得到2； $223^4\bmod225=16$ ，故 $L(16)=1$ ，解密得到4。

服务器无须私钥，直接相乘：

c_+=158\cdot223\bmod225=134.

现在 $134^4\bmod225=136$ ，所以

L(136)=9,\qquad9\cdot4\bmod15=6.

随机因子也有具体含义： $r_1r_2\bmod15=14$ ，因而134正是采用随机因子14的一份加密6。

为什么解密会消去随机性

中国剩余定理允许分别在 $p^2,q^2$ 上验证。因为 $n\lambda_n$ 都是 $p(p-1)$ 与 $q(q-1)$ 的倍数，对单位元 $r$ 有

r^{n\lambda_n}\equiv1\pmod{p^2},\qquad r^{n\lambda_n}\equiv1\pmod{q^2},

于是也模 $n^2$ 等于1。另一因子满足

(1+n)^{m\lambda_n}\equiv1+m\lambda_n n\pmod{n^2}.

故 $L(c^{\lambda_n})\equiv m\lambda_n\pmod n$ ，再乘逆元 $\nu$ 就恢复 $m$ 。 $L$ 只应用在已确认模 $n$ 等于1的结果上，不是对任意整数随意整除。

加法、常数倍与回绕

由式 (1) 直接相乘，

\operatorname{Enc}(m_1;r_1)\operatorname{Enc}(m_2;r_2) =\operatorname{Enc}(m_1+m_2\bmod n;r_1r_2\bmod n).

同样，密文的已知整数次幂对应明文的已知倍数。这里没有给出“两个未知明文相乘”的接口，因此 Paillier 本身不是通用 FHE。

在模15的例子中，12加7解出4，而非19。要把结果解释为普通非负整数和，必须预先证明总和小于 $n$ ；有符号编码则应保证不越过所选代表区间。加密不会替应用消除整数溢出。

若固定 $r=1$ ，式 (1) 退化为 $1+mn\bmod n^2$ ，任何人都可应用 $L$ 直接读出消息。即使固定了一个未知的 $r$ ，重复使用也使两份密文的比值消掉随机因子，从而泄漏明文差。

推论与应用

DCRA 为什么对应消息隐私？ $n$ 次剩余构成子群 $H$ ， $\operatorname{Enc}(m)$ 在陪集 $(1+n)^mH$ 上均匀。在 DCRA 下， $H$ 的均匀分布与全体单位元的均匀分布计算不可区分；乘上公开可逆元素 $(1+n)^m$ 保持这一性质。于是每个消息的密文都不可区分于同一个全群均匀分布，两条消息之间再用三角不等式衔接。这给出 CPA 的归约机制，而非仅说“分解大数很难”。

已算出的密文可乘一份独立的加密零 $\rho^n$ 来重随机化。固定原随机因子 $r$ 后， $r\rho$ 仍在 $\mathbb Z_n^*$ 上均匀，所以对合法密文，这一步确实恢复相同消息的新鲜加密分布；它也不能使错误明文变正确。

若用平方—乘模幂算法，加密的 $r^n$ 与解密的 $c^{\lambda_n}$ 各需要 $O(\log n)$ 次模 $n^2$ 乘法； $(1+n)^m$ 可直接用 $1+mn$ 计算。若 $M(k)$ 表示 $k$ 位乘法的成本，并采用相应量级的模约简，每次加密或解密的位成本为 $O(M(\log n)\log n)$ ，密文用约 $2\log_2n$ 位。生成与检验素数、求最小公倍数及逆元属于另计的密钥生成成本。

这种结构适合加密计数、线性加权和与需要隐藏操作痕迹的线性子协议。其公开可塑性同时意味着原方案不具普通 CCA2 安全，协议不能把任意相关密文的解密结果反馈给攻击者。它与ElGamal的群乘法同态在明文语义和困难假设上都不同。

参考资料

[1] Pascal Paillier, Public-Key Cryptosystems Based on Composite Degree Residuosity Classes, EUROCRYPT 1999，§§2–4：DCRA、剩余类映射、 $L$ 函数与 Scheme 1；正式出版 DOI：10.1007/3-540-48910-X_16。

形式陈述 ​

模225的完整计算 ​

为什么解密会消去随机性 ​

加法、常数倍与回绕 ​

反向链接

形式陈述

模225的完整计算

为什么解密会消去随机性

加法、常数倍与回绕