Paillier半同态加密算法和优化加速

Paillier 算法是一种经典的半同态加密算法，其密文具有加法同态性。本文介绍Paillier算法的密钥生成、加解密、同态加、同态乘以及算法的优化加速。

Pailler 算法具体内容

密钥生成

1. 随机选取两个大素数和，取，，满足（和长度相等），且（最大公约数为1）；

2. 计算以及（最小公倍数）；

3. 随机选取整数，满足存在，其中；

4. 公钥为：，私钥为：。

加密

1. 输入明文，满足；

2. 选择随机数，且；

3. 计算密文；

   若，则。

解密

1. 输入密文c，满足；

2. 计算明文。

密文-密文同态加法

返回 。

密文-明文同态乘法

返回 。

加解密正确性

密文-密文同态加正确性

密文-明文同态乘正确性

安全性

方案安全性可以归约到判定性合数剩余假设（Decisional Composite Residuosity Assumption, DCRA），即给定一个合数和整数，很难判定 在模下是否是次剩余（目前为止还没有多项式时间的算法可以攻破），即是否存在满足。

Paillier 算法优化

快速密钥生成

1. 令，，；

2. 其余和密钥生成内容相同。

加密优化

若，则

解密优化

若有素数和，，计算模指数时，可采用中国剩余定理（Chinese remainder theorem， CRT）优化，即先把映射到、上计算，再将结果聚合到，可得最终结果。

1. （映射到）令，其中，通过欧拉定理，，故

2. （映射到）令，其中，

3. 使用通项公式：，根据裴蜀定理，由于、互素，则，故：

应用到解密中，令，，计算：

1. ，

2. ，