在目前的实务上，最常使用的同态加密是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 中，构造加密这只函数的是使用以下的数学难题：

用个例子让大家理解上面的问题有多困难。假设n=10403 ，z=4。则现在请你找一个y 使得

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

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

从加密的方式可以看到，对于同样的message m，每次产生的结果都会不一样，因为每次的输出都会乘上一个随机乱数r。因此这也呼应前面所说的semantic security。 可观察到这个函数的input 是在范围0 到N 之间。这个暗示了加密函数的input 是跟security level 绑在一起(ie N 越大安全性越强)。这一点之后会导致Paillier cryptosystem 在使用上有其不方便性。 当取得密文，并且已知公钥的所有参数，要能反解出m，那么需要能解决上面所提的数学难题。 以效率来说， N= 2048-bits 长时，以个人电脑来说加解密速度都是大约是28 ms 左右的级距。算是相当的有效率。 最后从加密函式Encryption 的定义，我们可以观察到：

最后的结果可以看成把

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

PS： 这个式子的等号是有问题的，以值来说他们左右两边不相同，因为使用的nonce r 是很大的机率是不一样的。等号的概念可以想成对两边再做解密时，所得到的明文结果是一样的。

小结：我们给了一个同态加密的例子，并且展示它的加密是基于哪一个数学难题去保证它的安全性。同时也解释了为何它有semantic security以及满足homomorphism的形式。

然而…..

Paillier cryptosystem 似乎很棒了，但是其实还藏着一个问题。注意到加密函数Encryption 的input 是0 到N 之间。然而N 是由两个大质数所相乘。但是常常实务上的应用时， message space 是在0 到某个质数P 之间，甚至是更一般的合数( ie 非质数)。这种不一致性，会导致当你明明其实想在message space 内做运算，但是当你使用了同态加密帮你运算，但是随着运算的次数变多，会发生产生了“误差”，也就是说传回给你的密文，根据你提交的公式计算后，你再用私钥解密的产物，不是真正你期待的值。

我们举个例子(ie 里面有些许不严谨的推论)：

假设Paillier 的N = 5 * 7 = 35。

假设你现在的message space 的有效范围是在[0,10] 之间(ie 等价mod 11 的世界)。

此时你选8 在你的message space。你把它作加密变成En(8)。

接下来你希望计算En(8)En(8)En(8)En(8)En(8) “=” En(40)，再做解密后得到5，因为

但是呢，依照你自己在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 的空间可以自由指定。若是如此，这样做任意次数运算，都不会产生误差。我们会在下个系列文章讨论。