上一篇分析了能够实现同态乘法的ElGamal加密
，有没有什么加密方式可以实现同态加法呢？
Paillier就是其中之一。

准备工作

1. 首先选择两个大质数$p,q$
2. 计算$n=p\ast q$。
3. 令$\mu$为$(p-1,q-1)$的最小公倍数。
4. $g=n+1$。
5. $g,n$为公钥，$\mu$为私钥。

加密消息$m$

1.选择一个随机数$r$。
计算$c=g^m\ast r^n$。

解密密文$c$

1. $m=\frac{(c^{\mu }\mathrm{mod}{n}^2)-1}{(g^{\mu }\mathrm{mod}{n}^2)-1}$

正确性证明

先看分式的上半部分

• $(c^{\mu }\text{mod}{n}^2)-1=(g^{m\mu }{r}^{n\mu }\text{mod}{n}^2)-1$

根据欧拉定理可知，如果$r$与$n$互质，那$r^{\phi (n)}\text{mod}n=1$，$\phi (n)$为欧拉函数：在小于$n$的正整数中，与$n$互质的整数个数。那么

• $\phi (p^2)=p(p-1)$
• $\phi (q^2)=q(q-1)$

此时
$r^{n\mu }\text{mod}{n}^2$
$=r^{p(p-1)q(q-1)}\text{mod}{n}^2$
$=r^{p(p-1)q(q-1)}\text{mod}{p}^2\ast q^2$
$=1$

这个时候分式的上半部分：

• $(c^{\mu }\text{mod}{n}^2)-1=(g^{m\mu }\text{mod}{n}^2)-1$

$g^{m\mu }\text{mod}{n}^2=(n+1{)}^{m\mu }\text{mod}{n}^2$。
可以观察以下规律

• $(n+1)\text{mod}{n}^2=n+1$
• $(n+1{)}^2\text{mod}{n}^2=2n+1$
• $(n+1{)}^3\text{mod}{n}^2=3n+1$
• ……

所以，$(n+1{)}^{m\mu }\text{mod}{n}^2=(1+nm\mu )\text{mod}{n}^2$

分式的上半部分最后的结果为：

• $(c^{\mu }\text{mod}{n}^2)-1=(g^{m\mu }\text{mod}{n}^2)-1=nm\mu$

同理，分式的下半部分：

• $(g^{\mu }\mathrm{mod}{n}^2)-1=n\mu$

所以：

$\frac{(c^{\mu }\mathrm{mod}{n}^2)-1}{(g^{\mu }\mathrm{mod}{n}^2)-1}=\frac{nm\mu }{n\mu }=m$

正确性得证。

安全性分析

• 从公钥$g,n$，想要推测私钥$\mu$，需要知道$p,q$，而分解$p,q$的过程是一个大整数分解难题。

安全性得证。

同态加法

给定明文$m_1$对应的密文$c_1$，$m_2$对应的密文$c_2$。
明文$m=m_1+m_2$对应的密文

• $c=c_1\ast c_2$。

正确性证明

• $c_1=g^{m_1}\ast r_1^n\text{mod}{n}^2$
• $c_2=g^{m_2}\ast r_2^n\text{mod}{n}^2$
• $c=c_1\ast c_2\text{mod}{n}^2=g^{(m_1+m_2)}\ast (r_1\ast r_2{)}^n\text{mod}{n}^2$

解密过程同上。不再赘述。