Paillier同态加密算法

Paillier加密是一种公钥加密算法，基于复合剩余类的困难问题。其满足于加法同态，即密文相乘等于明文相加，即：

$D(E(m_1)\cdot E(m_2))=m_1+m_2$

标量乘法同态，即标量k乘以

$D(k*E(m1)) = k*m1$

1. Paillier方案描述

原版Paillier方案于论文[1]中提出，下面对方案进行描述：

1.1 密钥生成

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

得到的公钥为 $(n, g)$ , 私钥为 $(\lambda, u)$

快速生成私钥

如果素数 $p, q$ 长度相等，则可以采用一种简化的方式来生成Paillier的公钥和私钥，第3、4步改为：

$g=n+1, \ \lambda = \phi(n), \ u=(\phi(n)-1）mod\ n$

其中 $\phi(n)$ 为欧拉函数，即 $\phi(n) = (p-1)*(q-1)$ 。

1.2 加密

明文为 $m, 0 < m < n$ ;
随机选择 $r$ , 满足 $0<r<n$ 且 $r \in Z_{n^2}^*$ , $r$ 和 $n$ 互质；
计算密文： $c=g^mr^n \ mod \ n^2$

1.3 解密

计算明文 $m=L(c^{\lambda} \ mod \ n^2)*u \ mod \ n$

2. Paillier加解密实例

生成密钥对：

随机选择素数 $p=13, q=17$
计算 $n=13*17=221$
$\lambda = lcm(p-1, q-1) = lcm(12, 16) = 48$
随机选择小于 $n^2 = 221^2$ 的正整数 $g=4886$
计算 $u=(L(g^{\lambda}mod\ n^2))^{-1} mod\ n = (L(4886^{48}mod\ 48841))^{-1} \ mod\ 221 =159$

则公钥为 $(n,g)=(221, 4886)$ ，私钥为 $(\lambda , u)=(48, 159)$ 。

假设要对消息 $m=123$ 进行加密，则加密过程：

随机选择 $r=666$ ，且 $r$ 和 $n$ 互素
计算加密结果 $c=g^m r^n mod n^2 = 4886^{123} * 666^{221} \ mod \ 48841 = 25889$

解密过程：

$m = L(c^{ \lambda } mod n^2) * u \ mod \ n=L(25889^{48} \ mod \ 48841) * 159 \ mod \ 221 = 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(x)= \left \lfloor \frac{x-1}{n} \right \rfloor$

4. Paillier具备“加同态”性质

加法同态

Paillier加密的两个密文消息相乘的结果解密后得到两个消息相加的结果。

对于两个密文 $c_1 \equiv g^{m_1}.r_1^n \bmod n^2 和 c_2 \equiv g^{m_2}.r_2^n \bmod n^2$

$c_1c_2 \equiv g^{m_1}.g^{m_2}.r_1^n.r_2^n \bmod n^2 \\ \Rightarrow c_1c_2 \equiv g^{m_1}.g^{m_2}.r_1^n.r_2^n \equiv g^{m_1+m_2}.(r_1.r_2)^n \bmod n^2$