Paillier Cryptosystem (Additive Homomorphic Cryptosystem)

1. Paillier Cryptosystem 简介
- 1.1. 生成密钥对
  - 1.1.1. 生成密钥对的简化方式
- 1.2. 加密和解密过程
2. Paillier 加解密实例
3. Paillier 的设计思路
4. Paillier 具备“加同态”性质
- 4.1. 具备“乘同态”性质的加密方案（Unpadded RSA，ElGamal）
5. Paillier 加解密性能较差
6. 参考

1. Paillier Cryptosystem 简介

Paillier 密码系统是 Pascal Paillier 于 1999 年发明的，它是一种公钥密码算法。除此外，Paillier 具备“加同态”性质。

Paillier 背后的数学难题是“已知合数 $n$ 和整数 $z$ ，很难知道是否存在 $y$ 会满足 $z = y^{n} (\mod n^{2})$ ”（DCRA）。

1.1. 生成密钥对

Paillier 密钥对的生成过程：

随机选择两个大素数 $p, q$ ，需要满足条件 $p \cdot q$ 和 $(p - 1) (q - 1)$ 互素，不满足就重新选择随机数；
计算 $n = p \cdot q$ ， $λ = lcm (p - 1, q - 1)$ ，其中 $lcm$ 表示最小公倍数（Least Common Multiple）；
定义 $L (x) = ⌊ \frac{x - 1}{n} ⌋$ ，这里是除法后向下取整；
随机选择一个小于 $n^{2}$ 的正整数 $g$ ，并且存在 $μ = (L (g^{λ} {mod n}^{2}))^{- 1} mod n$ ，如果不存在这样的 $μ$ ，则要重新选择 $g$ ，或者从第 1 步重新开始；

得到的 公钥是 $(n, g)$ ；私钥是 $(λ, μ)$ 。 或者说私钥就是 $(p, q)$ ，因为由 $(p, q)$ 可以推导出 $(λ, μ)$ 来。

1.1.1. 生成密钥对的简化方式

如果素数 $p, q$ 长度相等，则可以采用一种简化的方式来生成 Paillier 的公钥和私钥，第 3/4 步改为： $\begin{aligned} g & = n + 1 \\ λ & = φ (n) \\ μ & = φ (n)^{- 1} mod n \end{aligned}$ 其中 $φ (n) = (p - 1) (q - 1)$ 。

1.2. 加密和解密过程

设 $m$ 是需要被加密的数据，它需要满足 $0 \leq m \leq n$ ，加密过程如下：

随机选择一个 $r$ 满足 $0 < r < n$ ，且还满足 $r$ 和 $n$ 互素；
计算密文： $c = g^{m} \cdot r^{n} mod n^{2}$ 。注：前面介绍过生成密钥对时往往会设置 $g = n + 1$ ，这时计算密文的公式就是 $c = (1 + n)^{m} \cdot r^{n} mod n^{2}$

设密文为 $c$ ，则解密过程为： $\begin{aligned} m & = L (c^{λ} mod n^{2}) \cdot μ mod n \\ = ⌊ \frac{(c^{φ (n)} mod n^{2}) - 1}{n} ⌋ \cdot μ mod 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)$ ，私钥为 $(λ, μ) = (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} (\binom{x}{k}) n^{k} = 1 + n x + (\binom{x}{2}) n^{2} + higher powers of n$

这意味着： $(1 + n)^{x} = 1 + n x (\mod n^{2})$ 如果定义： $y = (1 + n)^{x} (\mod n^{2})$ 那么： $x = \frac{y - 1}{n} (\mod n^{2})$ 从而有： $L ((1 + n)^{x} mod n^{2}) = x (\mod n)$ 这里 $L (u) = ⌊ \frac{u - 1}{n} ⌋$

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}) {mod n}^{2}) = m_{1} + m_{2} mod n$ 这个式子表明，在密文上计算 $E (m_{1}) \cdot E (m_{2}) {mod n}^{2}$ 得到的就是 $m_{1} + m_{2} mod n$ 加密后的值。

除了上面性质外，Paillier 加密方案还可实现： ② 仅已知公钥和密文 $E (m_{1})$ 情况下，可以计算出 $k \cdot m_{1}$ 的密文（这里 $k$ 是常量），即 $E (k \cdot m_{1})$ ： $D (E (m_{1})^{k} mod n^{2}) = k \cdot m_{1} mod n$ 这个式子表明，在密文上计算 $E (m_{1})^{k} mod n^{2}$ 得到的就是 $k \cdot m_{1} mod 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} mod n$ ，从而可以推出它的“乘同态”性质：

\begin{aligned} E (m_{1}) \cdot E (m_{2}) & = m_{1}^{e} \cdot m_{2}^{e} mod n \\ = (m_{1} \cdot m_{2})^{e} mod n \\ = E (m_{1} \cdot m_{2}) \end{aligned}

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 所示。