什么是同态加密(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 中,构造加密这只函数的是使用以下的数学难题:

Image for post

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

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

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

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

最后的结果可以看成把

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

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

本文链接地址:https://www.wwsww.cn/jishu/6093.html
郑重声明:本文版权归原作者所有,转载文章仅为传播更多信息之目的,如作者信息标记有误,请第一时间联系我们修改或删除,多谢。