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。