什么是同态加密(Paillier cryptosystem)_链圈子

在目前的实务上，最常使用的同态加密是Paillier cryptosystem。是一种非对称式加密：会有一组公钥用来加密，一组私钥用来解密。并且在这情况使用的是RSA模组。更具体的说就是公钥有两个参数决定：

1. N 决定了安全性满足

这里的p ,q 是两个相异质数。

2. 另一个参数是可随意选取的乱数g in [2, N²] 并且g 和N 互质。

如同RSA 的状况，在Paillier 的系统中，如果N 被人家分解出是哪两个质数，那这个加密法基本上就宣告被破解。因此对于实务上的应用至少N 的长度至少要2048-bits 以上。

基本功能

基本上大多数的同态加密都一定有以下这三个functions ： KeyGeneration, Encryption, Decryption。在Paillier 中，构造加密这只函数的是使用以下的数学难题：

除了暴力解让y 从0 到108222409 带入验证以外，似乎是觉得毫无头绪。不用意外，对数学家们，这个问题也没有有效的办法去解它(ie 这里称的有效指的是多项式时间的演算法)。

这边我们特别的去看Paillier 的Encyption 这支函式的定义可观察出下列的特性：

当作Encryption 的input 后​​得到的结果。(ie 后面的两个r 值相乘依然是个乱数)。因此”大体”上我们可以相信Paillier 的Encryption 是一个homomorphism 满足：

但是呢，依照你自己在message space 的世界的计算是得到7，因为

因此导致结果的不一致性。也是常常有人提到的使用同态加密超过一定运算量就会产生“误差”。

小结：在Paillier cryptosystem， 加密函数的message space 是跟系统的security level 绑在一起的，使得在实务应用上因为是要用另一个message space。这种不一致性导致Paillier cryptosystem 在使用上要注意运算次数过多产生的误差。

再去搜索大多数的同态加密(ie 比方说Goldwasser–Micali cryptosystem, Benaloh cryptosystem, )会发现几乎都是基于RSA model 建立的，也就是会有上面所提的缺点，input 的空间大小被security level绑定。因此必定会产生误差。因此是否存在一个同态加密是可以将两着拆开，使得加密函数的input 的空间可以自由指定。若是如此，这样做任意次数运算，都不会产生误差。我们会在下个系列文章讨论。