Paillier加密是一种公钥加密算法，基于复合剩余类的困难问题。其满足于加法同态，即密文相乘等于明文相加，即： $$D(E(m_1)\cdot E(m_2))=m_1+m_2$$

1 加法同态加密定义

在描述具体方案之前，我们先定义加法PHE。首先列举方案具有的所有算法。

KeyGen()：密钥生成算法。用于产生加密数据的公钥PK（Public Key）和私钥SK（Secret Key），以及一些公开常数PP（Public Parameter）； Encrypt()：加密算法。使用PK对用户数据Data进行加密，得到密文CT（Ciphertext）； Decrypt()：解密算法。用于解密得到数据原文PT（Plaintext）。

HE除了加解密以外，还具有在密文上进行处理的能力，所以还应拥有“处理”算法。对于加法PHE，支持的算法有同态加以及同态标量乘（标量乘法可看作多次加法）。

Add()：同态加算法。输入两个CT进行同态加运算。 ScalaMul()：同态标量乘算法。输入一个CT和一个标量PT，计算CT的标量乘结果。

2 Paillier方案描述

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

密钥生成

1. 选两个大素数$$p, q$$ , 保证$$gcd(pq, (p-1)(q-1))=1$$,且满足$$p,q$$长度相等。
2. 计算 $$n = pq, \lambda = lcm(p-1,q-1)$$， 这里lcm表示最小公倍数。
3. 定义$$L(x)=\frac{x-1}{n}$$, 这里分式是除法
4. 随机选取一个小于$$n^2$$的正整数$$g$$，并且存在$$u=(L(g^{\lambda}mod\ n^2))^{-1} mod\ n$$

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

快速生成私钥

$$g=n+1, \lambda = \phi(n), u=(\phi(n)-1）mod\ n, \phi(n) $$为欧拉函数，即$$\phi(n) = (p-1)*(q-1)$$

加密

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

解密

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

加法同态

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$

其中$$r_1$$和$$r2$$都是$$ Z{n^2}^$$中的元素，因此$$r_1r2$$也属于$$ Z{n^2}^$$, 并具有相同的性质，所以 $$c_1c_2$$可以看作是$$m=m_1+m_2$$加密的密文，$$c_1*c_2$$的解密结果为 $$m$$。

总结

常见的同态加密算法中，Paillier算法和Benaloh算法仅满足加法同态，RSA算法和ElGamal算法只满足乘法同态，而Gentry算法则是全同态的。

论文：https://link.springer.com/chapter/10.1007/3-540-48910-X_16