Pailliar加密算法1999年被提出，是基于DCRT（Decisional Composite Residuosity Assumption）的加法同态加密方案。

DCRT

DCRT问题是说，判断一个数是否是模$n^2$的$n$次剩余是困难的，也就是没有多项式时间算法可以解决。

密钥生成

Pailliar算法是一个非对称加密算法，有公钥和私钥。
选择两个素数$p$和$q$，计算$n=pq$.
在区间$(0,n^2)$随机选择一个数$g$，满足$L(g^{\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)$与 $n$互素，其中 $\lambda$是$p-1$与$q-1$的最小公倍数（也就是n的欧拉函数值，即小于n与n互素的元素个数）。$L(x)$是一个函数，$L(x)=\frac{x-1}{n}$，这里使用的是一般的除法，不是模除法。
通常需要选择$g=1\mathrm{m}\mathrm{o}\mathrm{d}n$，使得$L(g^x\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)=kx\mathrm{m}\mathrm{o}\mathrm{d}n$，k是整数.
证明如下：
由$g=1\mathrm{m}\mathrm{o}\mathrm{d}n$，知道$g=1+kn$，k是一个整数。
所以，$g^x=(1+kn{)}^x=1+kn+c_2{n}^2+c_3{n}^3+\cdots +c_x{n}^x=1+kn\mathrm{m}\mathrm{o}\mathrm{d}{n}^2$.
所以，$g=1\mathrm{m}\mathrm{o}\mathrm{d}n$，使得$L(g^x\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)=kx\mathrm{m}\mathrm{o}\mathrm{d}n$.

最后产生的公钥$pk=(n,g)$，私钥$sk=\lambda$.

加密

设要加密的明文为$m\in [0,n)$；
在$(0,n)$之间选择一个随机数$r$；
密文$c=g^m{r}^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^2$.

解密

$m=L(c^{\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)\cdot L^{-1}(g^{\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)\mathrm{m}\mathrm{o}\mathrm{d}n$，其中$L^{-1}(g^{\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)$是$L(g^{\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2）$关于n的模逆元。

解密正确性验证

首先，我们知道$n\lambda$就是$n^2$的欧拉函数值，所以，$r^{n\lambda }=1\mathrm{m}\mathrm{o}\mathrm{d}{n}^2$.
$$\begin{array}{rl}m& =L(c^{\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)\cdot L^{-1}(g^{\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)\mathrm{m}\mathrm{o}\mathrm{d}n\\ & =L(g^{m\lambda }{r}^{n\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)\cdot (k\lambda {)}^{-1}\mathrm{m}\mathrm{o}\mathrm{d}n\\ & =L(g^{m\lambda }\mathrm{m}\mathrm{o}\mathrm{d}{n}^2)\cdot (k\lambda {)}^{-1}\mathrm{m}\mathrm{o}\mathrm{d}n\\ & =km\lambda \cdot (k\lambda {)}^{-1}\mathrm{m}\mathrm{o}\mathrm{d}n\\ & =m\mathrm{m}\mathrm{o}\mathrm{d}n\end{array}$$

同态加法

假设 $C_1=g^{m_1}{r}_1^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^2,C_2=g^{m_2}{r}_2^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^2$分别是 $m_1$和$m_2$的两个有效密文。
$C_1+C_2=g^{m_1}{r}_1^n\cdot g^{m_2}{r}_2^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^2=g^{m_1+m_2}(r_1{r}_2{)}^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^2$是$m_1+m_2$的一个有效密文。

标量乘法

设$C=g^m{r}^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^2$是$m$的密文。
则$C^a=(g^m{r}^n{)}^a\mathrm{m}\mathrm{o}\mathrm{d}{n}^2=g^{am}(r^a{)}^n\mathrm{m}\mathrm{o}\mathrm{d}{n}^2$显然是$am$的一个有效密文。