Paillier Cryptosystem (Additive Homomorphic Cryptosystem)
Table of Contents
1. Paillier Cryptosystem 简介
Paillier 密码系统是 Pascal Paillier 于 1999 年发明的，它是一种公钥密码算法。除此外，Paillier 具备“加同态”性质。
Paillier 背后的数学难题是“已知合数 \(n\) 和整数 \(z\) ，很难知道是否存在 \(y\) 会满足 \(z = y^n \pmod {n^2}\) ”（DCRA）。
1.1. 生成密钥对
Paillier 密钥对的生成过程：
- 随机选择两个大素数 \(p,q\) ，需要满足条件 \(p \cdot q\) 和 \((p-1)(q-1)\) 互素，不满足就重新选择随机数；
- 计算 \(n=p \cdot q\) ，\(\lambda= \operatorname {lcm}(p-1, q-1)\) ，其中 \(\operatorname {lcm}\) 表示最小公倍数（Least Common Multiple）；
- 定义 \(L(x) = \lfloor{\frac{x-1}{n}} \rfloor\) ，这里是除法后向下取整；
- 随机选择一个小于 \(n^2\) 的正整数 \(g\) ，并且存在 \(\mu =(L(g^{\lambda }{\bmod {n}}^{2}))^{-1}{\bmod {n}}\) ，如果不存在这样的 \(\mu\) ，则要重新选择 \(g\) ，或者从第 1 步重新开始；
得到的 公钥是 \((n, g)\) ；私钥是 \((\lambda, \mu)\) 。 或者说私钥就是 \((p,q)\) ，因为由 \((p,q)\) 可以推导出 \((\lambda, \mu)\) 来。
1.1.1. 生成密钥对的简化方式
如果素数 \(p,q\) 长度相等，则可以采用一种简化的方式来生成 Paillier 的公钥和私钥，第 3/4 步改为： \[\begin{aligned} g &= n + 1 \\ \lambda &=\varphi (n) \\ \mu &= \varphi (n)^{-1} \bmod n \end{aligned}\] 其中 \(\varphi (n)=(p-1)(q-1)\) 。
1.2. 加密和解密过程
设 \(m\) 是需要被加密的数据，它需要满足 \(0 \le m \le n\) ，加密过程如下：
- 随机选择一个 \(r\) 满足 \(0 < r < n\) ，且还满足 \(r\) 和 \(n\) 互素；
- 计算密文： \(c = g^m \cdot r^n \bmod n^2\) 。注：前面介绍过生成密钥对时往往会设置 \(g=n+1\) ，这时计算密文的公式就是 \[c = (1+n)^m \cdot r^n \bmod n^2\]
设密文为 \(c\) ，则解密过程为： \[\begin{aligned} m &= L(c^\lambda \bmod n^2) \cdot \mu \bmod n \\ &= \lfloor \frac{(c^{\varphi (n)} \bmod n^2) - 1}{n} \rfloor \cdot \mu \bmod n \end{aligned}\]
2. Paillier 加解密实例
生成密钥对生成：
p=13, q=17 # 随机选择的素数
n=13*17=221 # n = p * q
\lambda=lcm(12, 16) = 48 # \lambda=lcm(p-1, q-1) = 48
g=4886 # 从小于 221^2 的数中随机选择的
\mu=159 # (L(4886^{48} mod 48841))^{-1} mod 221 = 159
公钥为 \((n,g)=(221, 4886)\) ，私钥为 \((\lambda, \mu) = (48, 159)\) 。
设要对消息 \(m=123\) 进行加密，则加密过程：
m=123
r=666 # 随机选择的，且 r 和 n 互素
c=4886^{123} * 666^{221} mod 48841 = 25889 # c=g^m r^n mod n^2
\__/ \_/
公钥 公钥
解密过程：
m=L(25889^{48} mod 48841) * 159 mod 221 = 123 # m=L(c^{\lambda} mod n^2) * \mu mod n
\_/ \_/
私钥 私钥
可见把消息 \(m=123\) 加密后再解密，得到了原来的消息。
3. Paillier 的设计思路
下面介绍一下 Paillier 加密方案的设计思路。
根据 Binomial theorem ，有： \[(1+n)^x = \sum_{k=0}^x {x \choose k} n^k = 1 + nx + {x \choose 2}n^2 + {\text{higher powers of }}n\]
这意味着： \[(1+n)^x = 1 + nx \pmod {n^2}\] 如果定义： \[y = (1+n)^x \pmod {n^2} \] 那么： \[x = \frac{y-1}{n} \pmod {n^2}\] 从而有： \[L((1+n)^x \bmod n^2) = x \pmod n\] 这里 \(L(u)=\lfloor \frac{u-1}{n} \rfloor\)
4. Paillier 具备“加同态”性质
Paillier 具备“加同态”性质，这句话的意思是： ① 仅已知公钥和两个加密后的消息 \(E(m_1)\) 和 \(E(m_2)\) ，不接触私钥（也就是说不解密）情况下，可以计算出两个明文 \(m_1\) 和 \(m_2\) 相加后再加密的结果，即 \(E(m_1 + m_2)\) 。
\[D(E(m_{1})\cdot E(m_{2}){\bmod {n}}^{2})=m_{1}+m_{2}{\bmod {n}}\] 这个式子表明，在密文上计算 \(E(m_{1})\cdot E(m_{2}){\bmod {n}}^{2}\) 得到的就是 \(m_1+m_2 \bmod n\) 加密后的值。
除了上面性质外，Paillier 加密方案还可实现： ② 仅已知公钥和密文 \(E(m_1)\) 情况下，可以计算出 \(k \cdot m_1\) 的密文（这里 \(k\) 是常量），即 \(E(k \cdot m_1)\) ： \[D(E(m_1)^k \bmod n^2) = k \cdot m_1 \bmod n\] 这个式子表明，在密文上计算 \(E(m_1)^k \bmod n^2\) 得到的就是 \(k \cdot m_1 \bmod n\) 加密后的值。
需要说明的是，对于 Paillier 加密方案，给出公钥和两个加密后的消息 \(E(m_1)\) 和 \(E(m_2)\) ，无法计算出 \(m_1 \cdot m_2\) 的密文。也就是说 Paillier 没有“乘同态”性质。
4.1. 具备“乘同态”性质的加密方案（Unpadded RSA，ElGamal）
我们知道 Paillier 加密方案，不具备“乘同态”性质。那么存在具备“乘同态”性质的加密方案吗？答案是肯定的，如 Unpadded RSA，ElGamal 加密方案都具备“乘同态”性质。
下面以 RSA 为例，介绍一下它的“乘同态”性质。我们知道对于 RSA，加密算法为 \(E(m) = m^e \bmod n\) ，从而可以推出它的“乘同态”性质：
5. Paillier 加解密性能较差
Paillier 算法的加解密性能都较差。主要原因是加密和解密时，都有 non-fixed-base（即底数不是固定的）的模指数（Modular Exponentiation）运算。 我们知道，计算模指数时，如果底数是提前知道的数字，则我们可以提前通过预计算底数的指数来加快模指数运算。但如果底数不能提前知道，则无法使用这些优化措施。
Paillier 在论文 Public-Key Cryptosystems Based on Composite Degree Residuosity Classes 中提出了两种方案 Paillier Schema 1（这就是前文介绍的 Paillier 基本方案）和 Paillier Schema 3（这是一种优化方案），分别如图 1 和 2 所示。
Figure 1: Paillier Schema 1（加解密性能较差，加密时底数 \(r\) 不能提前知道，解密时密文 \(c\) 也不能提前知道）
Figure 2: Paillier Schema 3（加密时底数 \(g\) 是提前知道的；解密时尽管 \(c\) 不能提前知道，但 \(\alpha < \lambda\) ，所以比 Schema 1 性能好些）
关于其它的性能更好的 Paillier 变种，可以参考：Optimized Paillier's Cryptosystem with Fast Encryption and Decryption