Paillier同态加密的注解

Paillier加密是加法同态加密,在密文空间计算中有较好的应用,在数字货币中也有应用。Paillier加密和零知识证明是一个标准的交易隐私保护方法。在Wiki中,https://en.wikipedia.org/wiki/Paillier_cryptosystem,有算法的详细描述。在CSDN的博客中,https://blog.csdn.net/jason_cuijiahui/article/details/79121702,有Java实现代码的描述。

理解这个算法,需要从欧拉函数说起。有一篇CSDN的博客,https://blog.csdn.net/paxhujing/article/details/51353672,里面有几个公式,说明了欧拉函数的计算方法。欧拉函数的意义是求跟某个数互素,且小于这个数的元素的个数。设数n,那么phi(n)=|Z_n^*|。

然后就要看卡迈克尔函数。同样有一个WiKi的链接,https://en.wikipedia.org/wiki/Carmichael_function,是专门在讲这个函数。这个函数求得是与n互素且小于n的任意一个数,在计算模n的幂次的时候,等于1的那个最小的幂次。欧拉同学已经证明gcd(a,n)=1,那么a^phi(n)=1 mod n。这是可以通过数数证明的。卡迈克尔同学则说明,phi(n)不一定最小,最小的那个数得用卡迈克尔函数可以算。在WiKi上有例子:

里面粗体的那些,就是说明卡迈克尔函数很牛的例证。

卡迈克尔函数计算上跟最小公倍数相关,用lcm(a,b)表示a,b的最小公倍数,用lambda(n)表示卡迈克尔函数,那么lambda(lcm(a,b))=lcm(lambda(a),lambda(b))。对于不能继续分解的数,所有的奇素数和2,4这两个数,卡迈克尔数和欧拉数是一样的,对于2的幂次,且大于4的那些数,卡迈克尔函数的计算结果是欧拉函数的一半。

所以在wiki表格中,8=2^3,是欧拉的一半;12=lcm(3,4), lambda(12) = lcm(2,2) = 2;15=lcm(3,5),lambda(15) = lcm(2,4)=4;16=2^4,是欧拉的一半。以此类推,可以验证每一个表项。

接下来就是关于一个一一映射的关系。在2008年的一个文献《The Paillier Cryptosystem》中(链接:http://www.tcnj.edu/~hagedorn/papers/CapstonePapers/OKeeffe/CapstoneOKeeffeCryptography.pdf),有这个映射:

epsilon_g: Z_n times Z_N^* rightarrow Z_^*

epsilon_g( x , y ) rightarrow g^xy^n mod n^2

这个映射可以证明为一一映射,即Z_^*中的任意元素都与数对x,y通过表达式epsilon_g一一对应。这里面的一个特殊要求是g mod n^2的阶必须是n的非零的倍数。

在有了这样一个映射之后,找到Z_^*中的一个特殊元素n+1,这个元素在mod n^2下,模幂计算简单,例如,(1+n)^x = 1+xn mod n^2。同时因为(1+n)^n = 1+ n^2 =1 mod n^2,所以n+1是映射epsilon_g中g的一个有效的表达。所以,(n+1)^xy^n 可以表示Z_^*的任意元素。

现在我们回到Paillier加密,c = g^mr^n,其中g是一个阶为n的非零倍数的元素。那么c^ mod n^2= g^r^ mod n^2。对于r in Z_n^*,因为n=p*q是奇素数的乘积,卡迈克尔函数的计算与欧拉函数相同,lambda(n^2) = n*lambda(n),所以r^ = 1 mod n^2。g替换为(1+n)^xy^n,得到

c^ = (1+n)^y^ mod n^2

后半部分的y^ mod n^2 又是1,所以

c^ = (1+n)^ mod n^2

即1+(x*m*lambda(n))n mod n^2。应用L函数之后,得到的就是x*m*lambda(n)。

对于g^lambda(n) mod n^2,g替换为(1+n)^xy^n,得到

(1+n)^y^ mod n^2,即

(1+n)^ = 1+x*lambda(n)*n mod n^2,应用L函数之后得到

x*lambda(n)。

现在,整个解密的过程就是 在模n下,计算x*m*lambda(n)*(x*lambda(n))^{-1} mod n。所以预先计算出来mu=(x*lambda(n))^{-1},可以直接解密得到m。

  • 发表于:
  • 原文链接http://kuaibao.qq.com/s/20180505G0SO5700?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券