Paillier同态加密算法

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

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

1. Paillier方案描述

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

1.1 密钥生成

1. 选两个大素数 , 需要满足条件, 不满足就重新选择随机数；
2. 计算 ， 这里表示最小公倍数（Least Common Multiple）；
3. 定义, 这里除法后向下取整；
4. 随机选取一个小于的正整数，并且存在，如果不存在这样的，则要重新选择，或者从第1步重新开始。

得到的公钥为, 私钥为

快速生成私钥

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

其中为欧拉函数，即。

1.2 加密

1. 明文为;
2. 随机选择, 满足 且, 和 互质；
3. 计算密文：

1.3 解密

1. 计算明文

2. Paillier加解密实例

生成密钥对：

1. 随机选择素数
2. 计算
3. 
4. 随机选择小于的正整数
5. 计算

则公钥为 ，私钥为。

假设要对消息进行加密，则加密过程：

1. 随机选择，且和互素
2. 计算加密结果

解密过程：

3. Paillier的设计思路

下面介绍一下 Paillier 加密方案的设计思路。

根据 Binomial theorem ，有：

这意味着：

如果定义：

那么：

从而有：

这里

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

加法同态

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

对于两个密文

其中和都是中的元素，因此也属于, 并具有相同的性质，所以 可以看作是加密的密文，的解密结果为 。

同态标量乘法

对于密文和标量，计算

需要说明的是，对于 Paillier 加密方案，给出公钥和两个加密后的消息 和 ，无法计算出的密文。也就是说 Paillier 没有“乘同态”性质。

4.1 具备“乘同态”性质的加密方案（Unpadded RSA，ElGamal）

Unpadded RSA，ElGamal 加密方案都具备“乘同态”性质。

下面以 RSA 为例，介绍一下它的“乘同态”性质。我们知道对于 RSA，加密算法为 ，从而可以推出它的“乘同态”性质:

总结

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

参考

1. https://link.springer.com/chapter/10.1007/3-540-48910-X_16
2. https://mp.weixin.qq.com/s/zF-0KAAtaiNDB6TAa6t89Q
3. https://snowolf0620.xyz/index.php/crypto/459.html
4. https://docs.chainmaker.org.cn/v1.2.4/html/tech/Paillier%E5%8D%8A%E5%90%8C%E6%80%81%E5%8A%A0%E5%AF%86%E7%AE%97%E6%B3%95%E6%96%B9%E6%A1%88%E4%BB%8B%E7%BB%8D.html
5. http://aandds.com/blog/paillier-crypto.html