同态加密是基于数学难题的计算复杂性理论的密码学技术。对经过同态加密的数据进行处理得到一个输出,将这一输出进行解密,其结果与用同一方法处理未加密的原始数据得到的输出结果是一样的,下面来看看同态加密技术的发展是怎样的吗?
同态加密思想从提出到现在,在具体实现方案方面,经历了3个重要时期:1978—1999年是部分同态加密的繁荣发展时期;1996—2009年是部分同态加密与浅同态加密的交织发展时期,也是浅同态加密方案的繁荣发展时期;2009年以后是全同态加密的繁荣发展时期。下面将以时间为主线,按照同态加密方案的类型介绍同态加密的发展。
1、部分同态加密方案
部分同态加密方案按照明文空间上能实现的代数或算术运算分为乘法同态、加同态和异或同态3种类型。下面从几个著名的同态加密方案的优缺点入手,总结一下乘法同态、加同态、或同态加密方案的特性。
(1)乘法同态加密方案。乘法同态加密方案的同态性表现为[m1×m2=D(E(m1)×E(m2))]。RSA[5]是最早的具有乘法同态性的加密方案,它是基于因子分解困难问题的,属于确定性加密,不能抵御选择明文攻击;1985年,ElGamal[3]基于有限域上的离散对数困难假设设计了ElGamal加密算法,该加密方案同样具有乘法同态性,并且满足选择明文不可区分(IND-CPA)安全。
(2)加法同态加密方案。加法同态加密方案的同态性表现为[m1+m2=D(E(m1)?E(m2))]([?]为定义在密文空间上的某种代数运算或算术运算)。具有加法同态性的加密方案有很多,应用最为广泛的当属Paillier[5]加密系统,该加密系统基于高阶合数度剩余类困难问题,且具有IND-CPA安全。
(3)异或同态加密方案。乘法同态加密方案的同态性表现为[m1⊕m2=D(E(m1)?E(m2))]([?]为定义在密文空间上的某种代数运算或算术运算)。目前,只有Goldwasser-Micali[15]加密系统属于该类同态加密系统,该加密系统基于二次剩余困难问题,虽具有IND-CPA安全,但每次只能加密单比特,因此加密效率会比较低。
2、浅同态加密方案
浅同态加密方案能同时进行有限次乘法和加法运算的加密。从某种程度上讲,该类型的加密方案是人们在研究解决RSA3个人提出的公开问题(如何设计全同态加密方案)的过程中,出现的“副产品”。1999—2005年间出现了不少浅同态加密方案,例如文献[6]、[16-18]中提到的方案。目前最为著名的浅同态加密方案当属Boneh[5]等基于理想成员判定困难假设设计的加密方案。该方案能执行一次乘法和若干次加法运算,Boneh[5]等虽然用它成功解决了2DNF问题,但是该方案在解密时需要搜索解密,因此基于此方案的2DNF保密计算协议效率很低。
虽然此类加密系统为实现全同态加密方案的设计奠定了一定的基础,但是只能用于解决某些专门的问题,即能够解决的应用问题有限,很难将其拓展并且应用于解决更广泛的问题。
3、全同态加密方案
2009年Gentry[7]设计了首个全同态加密方案,这一里程碑事件激起了全同态研究的热潮。到目前,全同态加密方案按照构造思想大致可以分为以下3代。
(1)以Gentry[7]设计方案为代表的、基于格上困难问题构造的第1代全同态加密方案,这类方案的设计思想大致如下:
设计一个能够执行低次多项式运算的浅同态加密算法。
控制密文噪声增长,即依据稀疏子集和问题对解密电路执行“压缩”操作,然后再执行自己的解密函数实现同态解密,从而能够达到降噪的目的。
依据循环安全假设(即假定用方案的公钥加密自身密钥作为公钥是安全的)实现纯的全同态加密。
(2)以Brakerski-Vaikuntanathan[9]为代表的、基于带误差学习或环上带误差学习困难问题构造的第2代全同态加密方案,该类方案的构造思想大致如下:
归约的基础是误差学习或环上带误差学习困难问题。
用向量表示密钥与密文。
用密钥交换技术来约减密文的膨胀维数,以达到降噪目的。
该类方案的优点是不再需要电路自举技术,突破了Gentry的设计框架,在效率方面实现了很大的提升;其缺点是在使用密钥交换技术时需要增加大量用于密钥交换的矩阵,从而导致公钥长度的增长。
(3)以Gentry-Sahai-Waters[12]为代表的、基于带误差学习或环上带误差学习困难问题构造的第3代全同态加密方案,此类方案的构造思想大致如下:
方案的安全性最终归约到带误差学习或环上带误差学习的困难问题上。
使用近似向量方法表示私钥,即用户的私钥实际就是密文的近似特征向量。
密文的同态计算使用的是矩阵的乘法与加法运算。
这类方案被认为是目前最为理想的方案,它们不再需要密钥交换与模转换技术。
以上是小编介绍同态加密技术的发展是怎样的的内容,本网信息安全知识库中还有很多关于信息泄漏方面的知识,感兴趣的朋友可以继续关注,才能更好的保证我们信息不外泄。