2009年IBM的Gentry提出的全然同态加密(FHE)方案是password学上的一项重大突破，以下就做个小小的总结。

1、 定义

若一个加密方案对密文进行随意深度的操作后解密，结果与对明文做对应操作的结果同样，则该方案为全然同态加密方案。

也可描写叙述为：若一个加密方案同一时候满足加法同态和乘法同态，则称该方案为全然同态加密方案。

(1)同态性：代数系统{A,+}，{B,*}。f为A到B的映射，若f(a+b)=f(a)*f(b)，则A、B同态。

能够列举一个简单的样例，两组对象分别为正实数域和对数域。实数的乘运算和对数的加运算就属于同态运算，即对于不论什么正实数x。y和z，

假设x*y = z。那么log(x)+log(y)=log(z)。正是这样的同态性提供了以不同方式达到同样目的的两种选择，假设给出x和y。我们能够直接将它们相乘。

也能够取它们的对数相加。最后得到的结果是同样的。都是z。

(2)随意深度：进行随意深度的计算是全然同态加密的最重要的特性，之前已经有了一些同态加密方案。这些方案要么是满足加法同态，如Paillier、Benaloh算法，

要么是满足乘法同态的。如RSA、ElGamal算法，另一些可以同一时候满足有限次加法与乘法的同态方案，可是在这些方案中没有一个是全然同态的。

 

2、 关键技术：同态解密

在加密过程加入的随机成分会形成噪音。这些噪音会随着计算的进行而迅速增强（大致来说，密文乘积的噪音是噪音之积，密文和的噪音是噪音之和），一旦超过阈值，就会使得解密结果不可靠。噪音问题是实现全同态加密方案的最大障碍。全同态的关键就是对噪音进行控制，使用的是同态解密技术。

在最早的版本号中。Gentry首先提出一个基于理想格的部分同态加密方案（somwhatFHE或SWHE）,该方案仅仅支持密文上的低阶多项式运算。然后对该方案进行改进，使其成为全然同态加密方案。首先将要运算的函数分解为基本计算：加法和乘法（Gentry使用二进制电路来描写叙述一个函数，这么做有两个优点:一、在电路模型下用电路深度和门电路个数衡量计算复杂度；二、将计算分解为基本步骤：二进制的加和乘）。在进行每一步基本计算前都对密文进行“同态解密”或称为“重加密”操作，得到新密文并能控制新密文噪音在阈值内。相当于 “刷新”了一下密文，然后再进行下一步基本计算。

用电路观点描写叙述的话，就是在基本门电路前加入一个解密电路，形成增强版的基本门电路，例如以下图:    

同态解密是指在密文空间运行解密函数，输入是加密后的解密密钥和加密后的密文，输出是一个新奇密文且该新奇密文具有更低的噪音。听起来有点绕，为了理解这一过程，能够联想到明文空间。若在明文空间运行解密函数。则输入应为解密密钥和密文，输出为明文。

由于明文空间与密文空间存在同态关系，故映射到密文空间后，输入输出都为明文空间中内容的加密。

随之而来的一个问题是：在密文空间是否能运行解密函数。

存在这个问题的解决办法是解密函数也存在计算深度的问题，一旦解密函数的深度超过了SWHE的承受范围，密文空间就不能运行解密函数。不能运行解密函数就不能减少噪音，不能减少噪音就不能进行随意深度的计算。也即不能实现全然同态。非常不幸。依照Gentry思路构造的解密函数被证明不能被SWHE计算。

Gentry的解决方法是压缩解密函数。使其进入SWHE的可以接受的函数集合中去。压缩解密函数的基本思路是“预处理”。即在公钥中加入一部分私钥信息。加密的时候对密文进行预处理。提前计算出一些辅助信息加入到密文中，用来减轻解密函数的负担，减少解密函数的深度。

顺便提一下，这样的预处理的加密方法广泛应用于server辅助加密方案中，计算能力较弱的client将部分解密密钥信息泄露给server。借助server强大的计算能力进行部分解密，仅仅留下少量工作给client运行。

因为同态解密开销很大，所以后面又有人发明了密钥交换技术、模交换技术等来削减密文噪音。

3、 方案描写叙述

(1)    KeyGen算法（密钥生成）

该算法生成加密公钥和解密私钥，还可能生成一个密文计算公钥，用于Evaluate中密文计算。

(2)    Enc算法（加密）

该算法生成密文。另外，通过Enc得到的密文的噪音最低。经过同态计算后的密文噪音将逐渐增强。

(3)    Dec算法（解密）

当密文噪音在阈值内时解密正确。超过阈值后解密不可靠。

(4)    Evaluate算法（密文计算）

这个算法是全然同态加密最重要的部分。通过Evaluate能够对随意功能函数进行计算。输入都是密文。特别重要的是该算法能够计算解密函数，这是形成全然同态加密方案的关键。

4、发展

(1)1978 年Rivest 等人于提出同态加密概念。推出了最早的公钥password体系RSA。此方案满足乘法同态性。

(2)2009年Gentry提出了第一个全然同态加密方案[1]，该方案是基于理想格构造的。困难性基于两个如果：格上的标准难题和稀疏子集和难题。

(3)2009年Dijk、Gentry等人提出了整数上的全然同态加密方案[2]，困难性基于近似GCD难题。该方案主要贡献是将原来基于“理想格”的SWHE替换为一个很easy的整数描写叙述的SWHE。在概念上的进行了极大的化简，但依然是使用Gentry的同态解密技术将SWHE其转化为FHE。

故效率没有提高。

(4)2011年Brakerski、Gentry、Vaikuntanathan提出的全然同态加密方案[3]。简称BGV方案。能够看做第二代FHE。

困难性基于LWE（纠错学习）。利用密钥交换技术、模交换技术来减少密文维数和减弱噪音，使得效率大大提高。

5、案例分析

这里选择一个相对easy理解的方案分析，是2009年Dijk和Gentry等提出的整数上基于模运算的全然同态加密方案。

首先是一个对称的部分同态加密方案：

密钥生成：生成密钥p(奇数)。公开參数q(大整数)

加密：c=m+2r+pq

解密：m=(cmod p )mod 2=(c-「c/p」) mod 2=LSB(c) XOR LSB(「c/p」)

密文计算：基本加法与乘法计算。

当中r是随机小整数；明文m∈{0,1}。密文c；「」：四舍五入方式取整；LSB：最低有效位。

规定a mod p∈(-p/2,p/2)，将m+2r看作“噪音”。明文空间是{0,1}，密文空间是整数域。

正确性验证：若保证噪音m+2r<p/2，则能正确解密，(m+2r+pq) mod 2 =(m+2r) mod 2 =m，在方案的參数选择上能够保证新奇密文的噪音m+2r一定小于p/2,故可解密成功。

同态性验证：如果 c1= m1+2r1+pq1，c2=m2+2r2+pq2。当中c1 是对密文m1 的加密，c2 是对密文m2 的加密。

c1+c2=(m1+m2)+2(r1+r2)+p(q1+q2) 若c1+c2的噪音2(r1+r2)+m1+m2<p/2

则((c1+c2) mod p) mod 2=((m1+m2)+2(r1+r2)) mod2=m1+m2，即加法同态。

c1*c2=(m1+2r1)(m2+2r2)+p(pq1q2+m1q2+m2q1+2r1q2+2r2q1)。若c1*c2 的噪音( m1+2r1)(m2+2r2) <p/2

则(c1*c2 mod p)mod 2=( m1+2r1)(m2+2r2) mod 2=m1*m2。即乘法同态。

从上式还能够看出密文之和的噪音是各自密文的噪音之和。而密文乘积的噪音是噪音之积。

上述描写叙述的方案是对称加密，改成非对称加密（公钥加密）也非常方便。

密钥生成：私钥sk=p，公钥pk={x1,x2,…,xt}。当中xi=pqi+2ri。即 xi是对0的加密。

加密：c=m+2r+sum(S),当中S是{x1,x2,…,xt}的一个随机子集。sum(S)为一些0加密之和，故对解密结果不影响。

解密：m=((cmod p) mod) 2=(c-「c/p」) mod 2=LSB(c) XOR LSB(「c/p」)

密文计算：基本加法与乘法计算。

补充一下。近似GCD难题在此处是指给出部分的xi=pqi+2ri。非常难求出p。

对上述方案进行改进，使之成为全然同态加密方案。

密钥生成：私钥sk’=<s1,s2,…sm>是一个随机二进制向量，且设稀疏子集S={i:si=1}。公钥pk’=<pk,y1,y2,...,ym>,当中有理数yi∈[0,2)且sum(yi)≈(1/p) mod 2,i∈S

加密：c’=<c,z1,z2,…zm>，当中zi=(c*yi)mod 2

解密：m=(c’-「sum(si*zi)」)mod 2=LSB(c’) XOR LSB(「sum(si*zi)」)

密文计算：由基本加法与乘法计算组成。

由上述改进能够看出，密钥与密文体积都增大了，以此为代价换来的是解密函数的化简，即将复杂的除法运算c/p替换为sum(si*zi)，当然若要真正化简解密函数还要利用Hamming Weight的技术来简化二进制加法计算。

6、应用^[4]

全然同态能够解决云计算的安全性问题。托付至云端的数据都是加密的，云端在不解密的前提下能够实现用户请求的操作。

比如，银行有很多交易数据须要进行分析，但若其本身的数据处理能力较弱，能够把交易数据加密后交给云端数据处理中心来进行处理分析。处理中心对数据进行分析，得出结果并返回。

在这个过程中，数据处理中心接触到的都是密文，这样就能够充分保证银行数据的机密性。

再如，医疗机构能够将病人的医疗数据加密后存储至云端，云端对数据进行一些统计分析，能够对病情进行预測和给出治疗建议，这样既保证了病人的隐私有充分利用了云端的强大的计算能力。

同态加密还可用于垃圾邮件过滤。假如你公布了加密公钥。你的好友能够向你发送加密的电子邮件，但垃圾邮件发送者也能够利用公钥加密广告和其它垃圾邮件来填塞你的邮箱。利用全然同态加密技术，垃圾邮件过滤器在无法解密邮件的前提下也能过滤掉垃圾邮件。

參考：

[1] .Fully Homomorphic Encryption Using IdealLattices

[2]. Fully Homomorphic Encryption over theIntegers

[3]. Fully Homomorphic Encryption withoutBootstrapping

[4]. Can Homomorphic Encryption be Practical