DGHV同态库

DGHV

DGHV全同态方案的实现

这是具有压缩公钥的DGHV的全同态加密方案的实现，参考文章：

[1] J.S. Coron, D. Naccache and M. Tibouchi, "Public-key Compression and Modulus Switching for Fully Homomorphic Encryption over the Integers", Proceedings of Eurocrypt 2012.available at http://eprint.iacr.org/2011/440

实现依靠数学库Sage，具体参考：数学库Sage安装和使用

什么是DGHV方案？

最初在下面的文章中给出：

[2] M. van Dijk, C. Gentry, S. Halevi and V. Vaikuntanathan, "FullyHomomorphic Encryption over the Integers". Proceedings of Eurocrypt 2010.and available at http://eprint.iacr.org/2009/616

加密：c= q*p + 2*r + m

这里p是密钥，m是比特明文（0或1）,q是一个大随机数，r是一个小随机数

解密：m=(c mod p) mod 2，容易看出，若噪音2*r < p，则可以解密成功

例如：

给定两个密文：

c1= q1*p + 2*r1 + m1
c2= q2*p + 2*r2 + m2

加法：c1+c2=(q1+q2)*p+2*(r1+r2)+m1+m2

可以得到：m1+m2=（ c1+c2）mod p mod 2

乘法：c1*c2=q12*p+2*(2*r1*r2+r1*m2+r2*m1)+m1*m2

也可以得到：m1*m2=（ c1*c2）mod p mod 2

这里，密文的噪音比原始密文c1和c2扩大了两倍，由于噪声必须低于p，

因此在密文上进行的乘法次数是有限的，所以方案叫做 Somewhat FHE

为了获得“纯”的FHE，即密文的无限次加法和乘法，必须减少密文中的噪音量，叫做密文刷新。

Gentry的密文刷新的关键思想，是使用密钥位的加密对密文位上的解密电路进行同态计算，这叫做Bootstrapping技术，然而我们得到的不是明文位，而是明文位的加密，即相同明文的新密文，现在若解密电路有足够小的深度，那么新密文中的噪音量实际上小于原始明文中的噪音量，因此叫做密文刷新。

然而，之前的解密算法m=(c mod p) mod 2的深度并不小，因此解密过程必须被“压缩”，以便可以将其表示为低深度电路，在[2]中解释了是如何完成的。

到目前为止，我们只描述了一个私钥加密方案，即加密者必须知道私钥p，然而很容易获得公钥加密方案。为此生成一组公开密文xi，它们都是0的不同的加密，xi=qi*p+2*ri，然后加密1bit的m，c=m+2*r+random_subset_sum(xi)，

c确实是m的加密。

在该库中，我们实现了DGHV的同态加密，即实现了密钥生成，加解密，同态加，同态乘和密文刷新

什么是压缩公钥？

在DGHV算法中我，密文大小必须是很大的，以防止格基约减算法，密文大小至少为10^7 bits，密钥p相对较小，大概为2000bit，大约10^4的密文必须包含在公钥中，所以我们给出公钥的的大小为10^11 bits，即12.5GB

为了减少公钥的大小，我们实现了[1]的技术，而不是生成 xi=qi*p+2*ri ，第一生成相同尺寸的伪随机数X，计算di，使得 xi=Xi-di是小的，模p，那么只有这些小的正确的值被存储在公钥中，（带有PRNG的种子），使用

这种压缩技术，可以减少公钥大小变为 10^4*(2*10^3)=2*10^7 bits，即2.5MB，这是可以接受的。

下载

源码地址

git clone 地址

安装

1、安装sage库

具体参考：数学库Sage安装和使用

2、运行sage

./sage

load("dghv.sage")

testPkRecrypt()函数里面有密钥生成，密文加法、密文乘法和密文刷新

问题：

 各种报错，欢迎交流！

参考

1、dghv code运行笔记