Paillier算法简介

  Paillier加密算法是Pascal paillier在1999年发明的概率公钥加密算法，该算法基于复合剩余类的困难问题，是一种满足加法的同态加密算法，已经广泛应用在加密信号处理或第三方数据处理领域。

原论文出处参见：https://link.springer.com/content/pdf/10.1007%2F3-540-48910-X_16.pdf

密钥生成

 秘钥生成主要由如下步骤： $k_{pub}=(n,g),k_{pr}=(\lambda ,\mu )$

1. 随机选择两个大素数$p$和$q$满足$gcd(pq,(p-1)(q-1))=1$,且满足p$和$q$的长度相等。
2. 计算 $n=p\ast q$, $\lambda =lcm(p-1,q-1)$, $lcm$为两个数的最小公倍数。
3. 随机选取$g$, $g\in Z_{n^2}^{\ast }$, 并且满足$gcd(L(g^{\lambda }mod{n}^2),n)=1$。 其中$L(x)=\frac{x-1}{n}$, $\mu =(L(g^{\lambda }mod{n}^2){)}^{-1}modn$
4. 公钥为$k_{pub}=(n,g)$
5. 私钥为$k_{pr}=(\lambda ,\mu )$

明文加密

1. 输入明文信息m, 满足$m\in Z_n$
2. 选择随机数 $0\le r<n$且$r\in Z_n^{\ast }$
3. 计算密文：$$c=g^m{r}^n(mod{n}^2)$$

密文解密

1. 输入密文c, 满足$c\in Z_{n^2}^{\ast }$
2. 计算明文消息：$$m=L(c^{\lambda }mod{n}^2)\ast \mu modn=\frac{L(c^{\lambda }mod{n}^2)}{L(g^{\lambda }mod{n}^2)}modn$$

正确性分析

参见文章：https://zhuanlan.zhihu.com/p/259282416

加法同态的性质

相关代码