文章目录
  1. Paillier同态加密系统
    1. 符号说明
    2. 密钥生成
    3. 加密
    4. 解密
  2. 解密的正确性

Paillier同态加密系统

符号说明

  • p,q为大素数，$p\neq q$；
  • $n=p\cdot q$；
  • $\lambda =(p-1)\cdot (q-1)$；
  • $B_{\alpha}=\{e\in Z_{n^{2}}^{\ast}|ord(e)=\alpha\cdot n\}$；
  • $B=\bigcup_{\alpha=1}^{\lambda}B_{\alpha}$；
  • 函数$L(x,n)=[(x-1)/n]$；

密钥生成

  • 随机选择指定长度的大素数p,q；(p,q)为私钥；
  • $n=p\cdot q$；随机选择$g\in B$；(g,n)为公钥；

加密

  • 明文m<n，随机选择r<n；
  • 密文$c=g^{m}\cdot r^{n}\ \textrm{mod}\ n^{2}$；

解密

  • 密文$c<n^{2}$；
  • 明文$m=L(c^{\lambda}\ \textrm{mod}\ n^{2}, n)\cdot L(g^{\lambda}\ \textrm{mod}\ n^{2}, n)^{-1}\ \textrm{mod}\ n$；

解密的正确性

对于$g=1+n$的情形，网上已有很多证明解密正确性的推导，而我在这里是希望给出更一般的情形下解密正确性的证明；推导参考提出Paillier同态加密系统的这篇论文：《Public-Key Cryptosystems Based on Composite Degree Residuosity Classes》。

定义1：定义映射$\varepsilon_{g}: Z_{n}\times Z_{n}^{\ast}\mapsto Z_{n^{2}}^{\ast}$，$\varepsilon_{g}(x,y)=g^{x}\cdot y^{n}\ \textrm{mod}\ n^{2}$。

引理1：若$g$的阶$ord(g)$是$n$的非零整数倍，则$\varepsilon_{g}$是双射。

证明：由于$Z_{n}\times Z_{n}^{\ast}$与$Z_{n^{2}}^{\ast}$的元素个数均为$n\phi(n)$(参考《近世代数》(第三版)杨子胥 第149页 定理1)，因此只需证明$\varepsilon_{g}$是单射；

假设$\varepsilon_{g}(x_{1},y_{1})=\varepsilon_{g}(x_{2},y_{2})$；

则$g^{x_{1}-x_{2}}\cdot (y_{1}\cdot y_{2}^{-1})^{n}\equiv 1\ \textrm{mod}\ n^{2}$；

因此$g^{\lambda(x_{1}-x_{2})}\cdot (y_{1}\cdot y_{2}^{-1})^{\lambda\cdot n}\equiv g^{\lambda(x_{1}-x_{2})}\equiv 1\ \textrm{mod}\ n^{2}$；

从而$ord(g)|\lambda(x_{1}-x_{2})$；

又$n|ord(g)\Rightarrow n|\lambda(x_{1}-x_{2}) , (n,\lambda)=1\Rightarrow n|(x_{1}-x_{2})$；

因此在$x_{1},x_{2}\in Z_{n}$的意义下，$x_{1}=x_{2}$；

那么$(y_{1}\cdot y_{2}^{-1})^{n}\equiv 1\ \textrm{mod}\ n^{2}$，则$y_{1}\cdot y_{2}^{-1}\equiv 1\ \textrm{mod}\ n$，理由如下：

假设$x^{n}\equiv 1\ \textrm{mod}\ n^{2}$，则：

即：

又$(p,q-1)=1$，$(q,p-1)=1$，从而存在$s,t\in Z$，使得$p\cdot s\equiv 1\ \textrm{mod}\ q-1 , q\cdot t\equiv 1\ \textrm{mod}\ p-1$，同理可得：

由中国剩余定理，$x$在模$n$意义下有唯一解，又1满足上述同余方程组，因此$x\equiv 1\ \textrm{mod}\ n$
回到本引理的证明，则有$y_{1}\cdot y_{2}^{-1}\equiv 1\ \textrm{mod}\ n$，即$y_{1}\equiv y_{2}\ \textrm{mod}\ n$；
综上，$\varepsilon_{g}$是单射，也是双射。

解密的正确性

由引理1，存在$(a,b)\in Z_{n}\times Z_{n}^{\ast}$使得$g=(1+n)^{a}\cdot b^{n}\ \textrm{mod}\ n^{2}$，则：

$g^{\lambda}\equiv (1+n)^{a\cdot\lambda}\cdot b^{n\cdot\lambda}\equiv (1+n)^{a\cdot\lambda}\equiv 1+na\lambda\ \textrm{mod}\ n^{2}$

同理，$c^{\lambda}\equiv (g^{m}\cdot r^{n})^{\lambda}\equiv [(1+n)^{a}\cdot b^{n}]^{m\lambda}\cdot r^{n\lambda}\equiv (1+n)^{a\cdot m\lambda}\cdot b^{n\cdot m\lambda}\cdot r^{n\lambda}\equiv (1+n)^{a\cdot m\lambda}\equiv 1+mna\lambda\ \textrm{mod}\ n^{2}$

因此，$L(c^{\lambda})\cdot [L(g^{\lambda})]^{-1}\equiv ma\lambda\cdot (a\lambda)^{-1}\equiv m\ \textrm{mod}\ n$。