同态密码理论与应用进展

杨亚涛 赵 阳 张卷美 黄洁润 高 原

①(北京电子科技学院电子与通信工程系 北京 100070)

②(北京电子科技学院密码科学与技术系 北京 100070)

③(西安电子科技大学通信工程学院 西安 710071)

1 前言

近年来云计算技术以及由云计算技术延伸和扩展而来的云存储技术始终热度不减，各类提供云服务的云平台也如雨后春笋般涌现。通过云计算和云存储技术，可以将海量数据的存储和复杂运算等工作外包给提供云服务的各大运营商，这实现了资源共享，减少了运算开支。然而，提供云服务的第三方无法保障用户数据的隐私安全，网络环境下的各种不可控因素对云上的用户数据隐私保护提出了挑战。使用传统加密手段可以保障数据外包时的存储安全，却难以保障其计算安全。在此背景下，同态加密(Homomorphic Encryption, HE)技术成为解决云环境下隐私保护问题的重要手段。使用同态加密技术，用户对密文进行运算后再解密得到的结果与直接对明文进行运算得到的结果一致，这一特性允许不可信第三方在没有私钥的情况下直接对密文进行运算，避免了第三方在运算过程中需要解密密文而导致的用户敏感信息泄露。

1978年Rivest等人[1]首次提出了隐私同态的概念，旨在构造一种支持密文检索的加密机制，后来发展为这样一种理念：在不解密的情况下对密文进行任意的函数变换，对变换的输出解密，所得结果与对相应的明文进行同样的函数变换所得结果一样。如何实现全同态加密(Fully Homomorphic Encryption, FHE)由此成为密码学界的开放性问题，终于在2009年Gentry[2]首次利用理想格给出了FHE方案的构造，该方案基于理想格上的有界编码问题与稀疏子集和问题，其思路如下：明文空间为{0, 1}，首先构造一个对“新鲜”密文支持有限次多项式运算的类同态加密(SomeWhat Homomorphic Encryption, SWHE)方案；然后基于稀疏子集和问题困难性假设变换私钥的形式，压缩解密电路，将其表示成关于私钥的次数足够低的多项式；最后在公钥中添加私钥的密文等辅助信息，用于对“新鲜”密文同态运算后生成的密文进行同态解密，降低其中包含的噪声，实现“自举”功能，达到对密文进行任意函数变换的目的，这一技术称为Bootstrapping(自举)技术。Gentry提出的这种构造模式被称为Gentry体制，此后全同态加密技术发展迅速，分为两条研究主线，一种是按照Gentry的思路设计的FHE方案，另一种则为基于错误学习(Learning With Errors, LWE)问题或环上错误学习(Ring-LWE, RLWE)问题实现的FHE方案[3,4]。下面，本文主要分析近年来同态加密技术的一些新进展并提出未来值得关注的几个发展方向。

2 相关概念及理论基础

电路观点是指用电路模型来理解同态加密方案的密文计算(Ciphertext computation)算法，电路模型必须接触到所有的输入数据，不会泄露任何信息，因此可以将一个函数或功能 f等效为一个电路模型C (c1,c2,···,ck)∈Cλ， 其中Cλ为 电路集合，λ 为安全系数。电路模型下可以通过门电路数量、乘法电路深度等来衡量算法的计算复杂度。

通常一个公钥加密方案包含3个算法：密钥生成算法( KeyGen )、加密算法(E nc)和解密算法(D ec)。但是在同态加密中，除了上述3个算法之外，还包含第4个算法即密文计算算法( E val)。密文计算是指在密文域上进行的运算，它通常需要满足正确性以及可验证性。

(1) 密钥生成算法 KeyGen(λ)是一个随机化的算法，输入安全系数 λ，输出解密私钥s k、加密公钥p k 以及用于密文计算的公开密钥e k；

(2) 加密算法 Enc(pk,m)是一个随机化的算法，输入公钥 pk 和明文m ，输出密文c，对于相同的明文每次加密得到的密文都是不同的；

(3) 解密算法 Dec(sk,c)是一个确定性的算法，输入私钥s k 以及密文c ，输出明文m 。

(4)密文计算算法E val(ek,(c1,c2,···,ck),C)输入密文计算密钥 ek ，电路C (c1,c2,···,ck)∈Cλ和密文(c1,c2,···,ck) ，输出为密文计算结果c∗；

以上4个算法都是概率多项式时间(Probabilistic Polynomial Time, PPT)算法。

定义1同态性：对于加密方案 α及其明文域M上的运算◦ ， 若对于∀ m1,m2,··· ,mk∈M都满足式(1)，则表明该加密方案对于运算◦ 满足同态性

定义2正确性：对于K eyGen(λ)生成的公私钥对 (pk,sk) ，电路集合Cλ中的任意电路C ，明文域M中的任意明文m1,m2,···,mk以及加密得到的密文(c1,c2,···,ck) ，其中E nc(pk,mi)→ci，如果对输出的c∗=Eval(ek,(c1,c2,···,ck),C)， 都 有Dec(pk,c∗)=C(m1,m2,···,mk)，则 认 为同态加密方案α 关于电路集合Cλ中的电路是正确的。

定义3紧凑性：对于任意的安全参数λ，假如存在一个多项式 f ，使得α 的解密算法能够用一个规模至多为f (λ)的 电路 D来表示，那么，同态加密方案α 便是紧凑的。

通俗来讲，满足紧凑性意味着算法的解密电路不依赖于密文或密文运算函数。

定义4安全性：通过选择明文攻击(Chosen Plaintext Attacks, CPA)来定义同态加密的安全性。若敌手 A为多项式时间的，且式(2)对任意敌手A 在λ 上都是可忽略的，则该同态加密方案为不可区分选择明文攻击安全的(也称为IND-CPA安全的)

其中，( pk,sk)←KeyGen(1λ)。

3 同态加密类型及研究动态

3.1 同态加密算法的分类

同态加密技术虽然还没有统一的分类标准，但是其发展历史仍是具有阶段性特征的。按照各同态加密方案允许密文计算的种类和次数，可以将其分为3类：部分同态加密(Partial Homomorphic Encryption, PHE)方案、类同态加密方案和全同态加密方案。PHE仅满足加法或乘法的密文同态运算；SWHE可同时满足加法和乘法有限次的密文同态运算；FHE可同时满足加法和乘法无限次的密文同态运算。

定义5部分同态加密：若加密方案α 仅对于加法( +)满 足同态性或者仅对于乘法( ×)满足同态性，则称该方案为部分同态加密方案。即仅满足式(3)或式(4)

定义6类同态加密：若加密方案 α对于加法(+)和 乘法( ×)都满足同态性，但是由于噪声限制只能进行有限次的同态运算，则称该方案为类同态加密方案。即同时满足式(3)和式(4)，但只能进行有限次运算。

定义7全同态加密：若加密方案 α对于加法(+)和 乘法( ×)都满足同态性，且能在无限次运算后依然保持同态性，则称该方案为全同态加密方案。即同时满足式(3)和式(4)，且能进行无限次运算。或者可以说对于任意电路C ∈Cλ都满足正确性和紧凑性的同态加密方案为全同态加密方案。

目前很多PHE方案已经取得了比较可观的加解密效率，并且已经被切实应用到了现实生活中(例如Paillier[5]加法同态加密方案被频繁应用在电子投票、医疗计量等场景下，其加解密耗时仅为毫秒级)，但是FHE方案由于管理密文计算中持续增长的噪声需要投入大量的计算资源，效率仍然较低，还不能满足实际应用的需求，此外由于同态性与延展性之间的相互矛盾，全同态加密无法实现INDCCA2安全。因此，对全同态加密的研究仍然任重道远，且相应的主要聚焦于两个方面：一是提高FHE方案的效率；二是提高FHE方案的安全性。全同态加密近十年来的研究进程可大致划分为3个阶段[6]：第1阶段是以Gentry的突破性工作为基础构造的各类FHE方案，首先构造一个SWHE方案，然后通过Bootstrapping技术控制噪声增长实现全同态；第2阶段是以Brakerski和Vaikuntanathan的工作为基础构造的基于LWE和RLWE的FHE方案，通过密钥交换(key switching)技术来解决维数膨胀的问题，通过模交换(Modulus Switching)技术来控制噪声，一定程度上摆脱了对Bootstrapping技术的依赖；第3阶段是由Gentry等人[7]构造的基于近似特征向量的GSW方案，该方案的同态运算全部为简单的矩阵运算，故不会出现维数膨胀的问题，该方案提供了一种构造FHE方案的新思路，将原先复杂的密文运算过程简化为了较为单纯的代数运算，更加便于理解。宋新霞等人[8]对密文矩阵的本质及构造方法进行了研究，提出抽象解密结构的概念，并以此为基础揭示了密文矩阵FHE与其它FHE之间的包含关系。总而言之，近年来对全同态加密技术的研究进展迅速，但是其实现效率问题仍是亟需解决的主要难题。

除了上述按照发展阶段进行划分以外，FHE还可以依照所基于的困难问题来分类[9]，主要有两种，一种是基于传统数论中的困难问题，如整数上近似最大公约数(Approximate Greatest Common Divisor, AGCD)问题，另一种是基于格密码学中的困难问题，如格上LWE问题和RLWE问题。另外，近年还出现了基于NTRU(Number Theory Research Unit)的FHE方案、基于身份和属性的FHE方案以及无噪声的FHE方案等诸多其他类型的FHE方案，李子臣等人[10]通过格上的高斯抽象算法生成密钥对，然后利用Flattening技术构造了基于NTRU选择明文攻击可证明安全的全同态加密方案。为了解决NTRU在实现过程中的侧信道攻击安全隐患，杨亚涛等人[11]对NTRU算法所有系数执行掩码操作，构造了能够有效防御差分能量攻击及相关能量攻击的NTRU全同态掩码防御方案。可以发现，近十年来建立在格密码学基础之上的FHE方案大量涌现，格密码作为后量子密码中颇具潜力的密码体制，使全同态加密技术在量子计算时代仍具有重要的应用价值。

3.2 全同态加密

全同态加密支持密文域上无限次的加法和乘法运算。Gentry提出了一种基于理想格的FHE方案，为FHE的研究奠定了基础，在Gentry的方案中Bootstrapping(自举)技术是实现全同态的关键，下面简要介绍Bootstrapping技术的原理。首先在使用Bootstrapping之前，我们已经可以进行有限次的密文同态运算，但是每进行一次同态运算后密文噪声都会相应增加，尤其是在进行同态乘运算时，密文噪声随运算次数呈指数形式增长，因此必须采取措施进行噪声控制。

如图1所示，对密文进行若干次同态运算后得到的密文 c 对应于明文m ，且该密文噪声很大。Dc为解密电路且满足Dc(sk)=Decsk(c)=m , Encpk(sk)是用公钥直接对私钥进行加密得到的，将Encpk(sk)作为解密电路 Dc的 输入，其输出为密文c′且c′对应的明文仍为 m 。因为E ncpk(sk)的噪声很小(low noise)，因此 c′的噪声也很小，从而达到了降噪的目的。

图1 Bootstrapping原理

由于反复调用解密电路使FHE方案效率过低，因此很多人随后针对Bootstrapping进行了优化，Ducas等人[12]在EUROCRYPT2015上将Helib库中Bootstrapping操作的运行时间从6 min缩短至1 s以内，并相应提出了FHEW方案。Chillotti等人[13]随后在ASIACRYPT2016上对FHEW方案进一步优化，将Bootstrapping的运行时间从1 s以内缩短至0.1 s以内，并将其密钥大小从1 GB减小至24 MB。在EUROCRYPT2018上，Chen等人[14]通过应用“低位删除”多项式优化了开方运算，此举对下文要提到的FV和BGV方案中的Bootstrapping都有重要作用。若令密钥的1-范数为h =//s//1，明文模数为t =pr，则优化算法可以将FV方案的自举深度降至l og2h+log2(logp(ht))，将BGV方案的自举深度从 log2h+2log2t 降至l og2h+log2t。除了优化Bootstrapping以外，另一种为全同态“提速”的有效手段是批处理(batch)技术，也可称为封装(Pack)技术，即允许将多个数据值加密为一个密文，并能够同态执行单指令多数据操作(Single Instruction Multiple Data, SIMD)。2014年，Smart等人[15]通过中国剩余定理分解明文空间，构造了支持SIMD操作的FHE方案。在EUROCRYPT2018上，Castryck等人[16]通过引入劳伦多项式编码技术对Smart的方案进行了改进，极大提高了明文封装容量以及在效率或安全性方面优化系统参数的灵活性。虽然通过不断优化Bootstrapping技术和引入Batching技术大幅提高了FHE方案的实现效率，但是离实际应用的要求还有一定距离，因此构造无噪声的FHE方案成为当前全同态加密研究的一个重要思路[17]。噪声的加入是为了保证FHE方案的安全性，但也带来了噪声控制的困扰，虽然无噪声的FHE方案被认为是不安全的，但该结论也并没有被严格证明，因此研究无噪声的FHE方案仍具有现实意义。2012年Kipnis等人[18]分别基于矩阵和多项式构造了无噪声FHE方案。2014年Nuida[19]在IACR Cryptology ePrint上提出了一个构造无噪声FHE方案的框架。同年，Gentry[20]基于完备群概念提出了一个无噪声FHE框架。除上述方案以外，近年来还出现了基于向量空间[21]，基于八元数环[22]，基于非交换环[23]等的无噪声FHE方案。但是目前现有无噪声FHE方案还并不能在可证明安全框架下严格做到安全可行。此外，GPU和FPGA等硬件架构的特点具有大幅度提高同态加密方案效率的潜力，大整数乘法是FHE算法中最为核心的计算环节，施佺等人[24]采用Verilog HDL语言完成了一个16×24 bit有限域FFT算法的FPGA设计，谢星等人[25]提出一种基于Schönhage-Strassen算法的768 kbit大整数乘法器FPGA设计，均较CPU平台的运算效率有大幅提速。表1总结了提高全同态加密效率的各类解决方案。

在Gentry体制之后，基于整数的FHE方案迅速成型。基于整数的FHE方案完全遵循Gentry的设计思路，其安全性基于AGCD困难问题。2010年Smart等人[26]基于整数与多项式设计了FHE方案，缩短了密钥和密文尺寸。同年，Dijk等人[27]提出了基于整数环上的FHE方案DGHV方案，这某种意义上是第1个基于整数的FHE方案，并且提出能够同时加密多个bit位数据的思路，但其缺点是计算过程比较复杂。此后很多人从DGHV方案入手，对整数上的FHE方案进行了优化。在EUROCRYPT 2013上，Cheon等人[28]引入批处理技术，允许并行处理多比特数据(以向量形式存储)，在EUROCRYPT 2015上Nuida等人[29]将方案的明文空间从 Z2扩展至ZQ， 其中Q 为任意素数，同时当Q =2时，同态乘的算法复杂度从 O(λ(log2λ)2) 降为O (λ)，该方案同样可以扩展为批处理FHE方案。目前FHE方案所基于的困难问题主要有两类，分别是Regev提出的RLWE问题和Howgrave-Graham[30]提出的AGCD问题。Cheon等人[31]在EUROCRYPT2015上将LWE问题归约为AGCD问题的一个变体，并在此基础上提出了一种新的基于AGCD的FHE方案，该方案的安全性不再依赖稀疏子集和的问题假设，且其性能优于此前所有的基于AGCD的FHE方案。现有的基于整数的FHE方案是针对两个参与者“一方加密，一方解密”(一对一)设计的，王彩芬等人[32]提出一种“多方加密，一方解密”(多对一)的FHE方案，与已有方案相比扩展了数据传输量，且提高了效率。除了基于整数的FHE方案以外，大量研究开始关注在实数域上的密文计算，Jaschke等人[33]提出一个有理数通过与2的幂迭代相乘可以近似表示为整数，不过相应也带来了额外的计算负担。另一方面，Dowlin等人[34]提出一种更高效的表示定点小数的方法，即将定点小数编码为整系数多项式，然而要想进行精确的小数运算，明文模需随电路深度的增加呈指数增大。在ASIACRYPT2017上，Cheon等人[35]构造了一种实数域上的FHE方案CKKS方案，可以对浮点数进行近似计算，方案加密时对明文进行舍入，解密时输出满足精度要求的近似值，通过使用Rescaling技术，在保证计算精度的同时将密文模数增长从指数增长变为线性增长，并通过使用批处理技术提高算法的计算效率。方案分别给出了在乘法逆、指数函数、逻辑运算和离散傅里叶变换这4种运算电路下的效率分析，效率都较为可观，但是该方案为层次型同态加密方案，不能通过Bootstrapping转化为全同态加密方案。随后在EUROCRYPT2018上，Cheon等人[36]基于Bootstrapping提出了一种更新低层级密文的新技术，将上述的层次型同态加密方案扩展为了全同态加密方案，该技术使用正弦函数近似代替模数约减操作，每次迭代操作仅包含1次同态乘运算，若对加密后的128个数字(精度为12 bit)进行密文更新，共耗时139.8 s。表2总结了利用全同态加密技术在处理整数和实数域上的研究进展。

表1 提高全同态加密效率的解决方案

基于对称密码体制的FHE算法，近年来多次出现在人们视野中。目前基于对称密码体制的同态加密算法主要有基于序列密码的和基于分组密码的两类，由于在循环迭代过程中噪声会迅速增大，基于分组密码的同态加密方案只能满足微弱的同态性，而基于序列密码的同态加密方案仅在第1次密文计算时满足较强的同态性，在EUROCRYPT2016上，Méaux等人[37]结合了这两类方案的优点，通过在序列密码中加入滤波置换(filter permutator)，使得每轮输出的噪声恒定不变，理论上讲，这种设计架构也适用于其他的FHE方案。随着量子计算理论的发展，未来必将迎来量子计算机应用的热潮，量子同态加密的概念也被随之提出。在CRYPTO2015中，Broadbent等人[38]正式给出了量子同态加密(Quantum homomorphic encryption)的定义，即实现量子信息的加密以及密文的量子同态运算，此外作者还相应给出了量子信息中IND-CPA的定义。随后在CRYPTO2016中，Dulek等人[39]基于文献[38]中所提出的架构，构造了第1个量子全同态加密(Quantum FHE, QFHE)方案，可以实现任意多项式级量子电路的密文运算。

表2 全同态加密在整数域和实数域上的研究进展

3.3 可验证同态加密

可验证计算是在分布式计算和云计算环境下，保障数据外包时计算结果可靠性的重要手段[40]，构造可验证的同态加密方案成为保证数据完整性以及计算过程可靠可信的关键。在2002年Johnson等人首次在文献[41]中提出了同态签名(Homomorphic Signature, HS)的概念，此后相继出现了很多支持线性函数计算的同态签名方案。2011年Boneh等人[42]构造了首个能够执行确定阶数的多项式运算的同态签名方案。2013年Gneearo等人[43]形式化定义了同态消息认证(HomMAC)的概念，指出同态MAC可以看作同态签名方案的对称密钥版本。至此，同态签名和同态MAC都可以作为保护外包数据完整性和可靠性的有效手段，简言之，同态签名可实现公开验证(Public verification)，同态MAC可实现私人验证(Private verification)。目前，同态MAC方案的相关研究已取得了很多重要进展，在EUROCRYPT2013上，Catalano等人[44]提出了两个同态MAC的具体实现，均支持低次多项式运算且效率较高，但不能同时满足标签的简洁性(Succinctness)和方案的复合性(Composability)。随后他们在PKC-2014上对先前的工作进行了总结，抽象出了有限延展性编码的思想，允许同态MAC在满足简洁性的前提下，一定程度上同时满足复合性。2018年，白平等人[45]运用有限延展性编码的思想构造了基于默克尔哈希树的同态认证方案，虽然在复合度上有所不足，但可以在不同云服务器之间的数据传输过程中实现数据完整性和删除操作的可验证。

在ASIACRYPT2014上，Catalano等人[46]提出了适用于Paillier加密体制的可验证同态加密方案。Catalano等人针对同态加密方案的可验证问题引入了一个新的密码学原语LAEPuV(Linearly homomorphic Authenticated Encryption with Public Verifiability), 即支持公开验证的线性同态认证加密。线性同态签名是一种特殊的数字签名，它对消息和签名都具有同态性，其概念最早由Boneh等人[47]在2009年提出。LAEPuV方案即为在标准模型下的多项式同态签名方案，它在保护数据隐私安全和计算结果正确性的基础上，支持对计算结果的公开验证，即在仅有密文情况下，验证者依然可以进行验签。Catalano等人给出了LAEPuV在Paillier加密体制中的具体形式，证明了其适用性。在ASIACRYPT 2014上，Joo等人[48]对同态认证加密(Homomorphic Authenticated Encryption, HAE)进行了系统的研究，并首次给出了在HAE中IND-CPA和INDCCA等安全概念的定义以及UF-CPA和UF-CCA等认证概念的定义。Joo等人指出当前现有的同态签名方案和同态MAC方案还存在很多局限性(比如仅支持次数较低的多项式函数，仅能进行有限次的验证查询[49])，并基于EF-GCD(Error-Free approximate GCD)假设构造了一种HAE方案，虽然该方案是类同态而不是全同态的，但是它同时满足作者所定义的IND-CPA和SUF-CCA安全性。

在上面提到的所有方案中，注意到方案中带标签的程序(Labeled-program)能够计算不同用户在不同时刻认证过的数据，前提条件是这些数据都是用同一个密钥进行认证加密的。Fiore等人[50]在ASIACRYPT2016上定义了多密钥同态签名(Multi-key Homomorphic Signature, M-HS)，适用于需要多方参与的场景，增强了同态签名的实用性，并在此基础上构造了确定阶数多项式深度的同态签名方案。然而现有M-HS方案签名的不可伪造性依赖于假设所有的签名者都是可信的，这一假设在MHS的实际应用(如可验证多方计算)中并不符合实际，因此Lai等人[51]在ASIACRYPT2018中对存在任意数量不可信签名者的情形进行了研究，基于零知识证明中的ZK-SNARK技术提出了一种M-HS的通用结构，但是并没有分析该结构的认证安全性和实用性。在ASIACRYPT2017中Alagic等人[52]指出量子同态计算也可以通过无交互的方式进行验证，通过在密文计算算法的输出结果中增加密文计算日志可实现其可验证性，由此构造了一个可验证的量子全同态加密方案，并证明了该方案的正确性和安全性。如何能够既保证用户数据的私密性又保证计算结果的正确性，是云环境下执行运算的难题之一。表3总结了可验证同态加密的研究进展。

4 同态密码知识产权分析

随着同态加密技术的深入研究，一些基于同态加密的具体应用已被逐步推广，然而目前还不能满足对云中海量数据进行复杂运算的需求，因此针对同态加密算法的改进以及针对其实际应用的探索仍有一段很长的路要走。下面通过分析近几年与同态密码相关的知识产权，透视该技术目前的应用现状。

表3 可验证同态加密研究进展

文献[53]基于CO-ACD(CO-Approximate Common Divisor)问题构造并实现了一个加法部分同态加密方案。文献[54]公开了一种基于同态加密的签名方案，具体可以应用于匿名证书、电子投票和群签名中。文献[55]公开了一种可验证计算正确性的全同态加密方案及其实现。文献[56]公开了一种有效提高同态乘效率全同态密码系统。文献[57]公开了一种支持有理数运算的同态加密方案。文献[58]公开了一个包含密钥交换、模交换和噪声动态管理的同态加密库。文献[59]公开了一种片上系统(System on Chip, SoC)的隐私保护验证方法，在验证时，参与验证的各方可以通过被加密的测试向量来验证IP核，以避免泄露不必要的信息。文献[60]发明了用于读取同态运算指令的计算机可读存储器，实现了两个终端之间的同态加密通信。

文献[61]公开了一种基于同态加密算法的个人图像安全检索方法，在不泄露用户检索信息和数据的前提下，实现图像的安全检索。文献[62]公开了一种云存储中基于同态加密的密文检索方法，保障了数据的隐私安全，同时使用树形结构来存储提高密文检索效率。文献[63,64]分别公开了一种基于同态加密的密文检索技术。文献[65]公开了一种基于同态加密的线性SVM(Support Vector Machine)模型训练算法，得以在云上训练密文SVM模型，从而避免泄露训练数据等隐私信息。文献[66]公开了一种基于全同态加密的生物特征认证技术，允许在密文状态下认证生物特征，从而避免用户信息泄露。当前，同态加密已被应用在机器学习隐私保护领域，较有代表性的是Gilad-bachrach等人[67]基于SEAL库提出的隐私保护神经网络模型Cryptonets，已较好地适用于小型神经网络。

文献[68]公开了一种基于加法同态的隐藏分散贷款额获取贷款总和的方法，这是多方安全计算的一个应用场景。文献[69]公开了一种基于同态加密的多值打包方案。文献[70]公开了一种基于全同态加密的双方不经意传输方案。文献[71]公开了一种使用同态加密技术计算DNA编辑距离的方法，首先将DNA序列编码为字符串，然后在密文域实现两字符串间编辑距离的计算。文献[72]公开了一种基于同态加密的智能电网用户售电方法，使用同态加密技术加密用户的真实购电需求，结合身份认证保护用户的购电信息不被电力公司等获取。文献[73]基于同态加密技术公开了一种用于计算各分布式设备所贡献计算量的方法。文献[74]公开了一种基于同态加密技术生成条形码的技术，可以在密文域中根据从服务器接收到的生成请求来生成对应的标识码。文献[75]公开了一种基于同态加密算法保护程序代码的方案及其实现，以增加程序代码安全性。文献[76]公开了一种基于同态加密的通信技术，保障在通信过程中数据的计算安全和存储安全。表4总结了近年来同态加密相关的知识产权所聚焦的不同领域。

表4 同态加密相关的知识产权聚焦的不同应用领域

5 全同态加密库对比分析

目前已经有一些团队对FHE方案进行了软件实现，例如基于BGV方案的Helib、基于BFV方案的SEAL、基于GSW方案的TFHE等。下面分别分析Helib, SEAL和TFHE全同态加密库的运行效率。

2014年Brakerski等人[77]提出了BGV同态方案，使用模交换技术进行噪声管理，在不使用Bootstrapping的情况下构造出了层次性全同态加密方案；2013年Halevi等人[78]公开了实现BGV方案的函数库Helib，Helib是使用C++编写的同态加密函数库，着重聚焦使用SV密文封装技术和GHS优化算法[79]，2018年3月，IBM发布了新版本Helib同态加密库，通过重线性化，使效率提升了15～75倍。使用i5-1.6 GHz处理器，内存8 GB的Dell笔记本电脑进行效率测试，表5为level=2时Helib的运行效率，m表示模数。

表5 Test_Timing效率测试结果(μs)

Fan等人[80]于2012年提出了BFV同态方案，该方案可视为对Brakerski所提方案[81]的优化，随后微软公开了基于BFV方案的同态加密库SEAL。2016年Bajard等人[82]提出了一个BFV方案的RNS变体(Residue number systems)。2017年微软发布SEAL2.3.0，使其可以支持Bajard等人的方案。2018年微软发布SEAL3.0，使其支持Cheon等人提出的CKKS方案，可以实现实数域上的密文近似计算。2019年发布SEAL3.2，增加了对.NET开发的完整支持，使.NET开发人员编写同态加密应用程序更为便捷。目前SEAL最新的版本为SEAL3.4。使用英特尔i5, 1.6 GHz处理器，8 GB内存的Dell笔记本电脑分别测试SEAL3.4中BFV方案和CKKS方案在默认参数下的运行效率。BFV方案在默认参数下的效率测试结果如表6所示，CKKS方案在默认参数下的效率测试结果如表7所示。其中Poly,Coeff和Plain为方案的3个主要参数，不同参数会影响方案的安全性、效率以及可进行同态运算的次数。

Gentry等人[7]于2013年提出了GSW同态方案，旨在基于LWE问题构造一个便于理解的、同态运算形式更为纯粹的FHE方案。基于GSW方案的同态加密库TFHE在2017年公布。TFHE使用C++语言编写，它可以运算由逻辑门电路组成的任意布尔电路，函数库支持对10种逻辑门电路的同态运算，包括与门、或门、非门、异或门、与非门、或非门和多路选择器等，每个门电路的单核运算时间约为13 ms，每个选择器花费大约26 ms，TFHE库与其他库的区别是其Bootstrapping不受门电路数量和结构的限制，这就意味着即使在运算电路未提前得知的情况下，它也能够实现对任意电路的密文同态运算。在ASIACRYPT2017中，Chillotti等人[83]针对TFHE提出了新的改进思路，通过使用垂直和水平两种密文封装技术大幅提升了其运行效率，并解决了门电路不可复合的问题。

表6 SEAL中BFV方案效率测试(μs)

表7 SEAL中CKKS方案效率测试(μs)

6 结束语

综上可知，全同态加密技术历经十余年的发展，正逐步由理论层面步入应用阶段，阻碍全同态加密投入应用的效率问题也在一定程度上得到解决，电子投票、密文数据库、区块链隐私保护以及机器学习隐私保护等多元化的应用场景被相继开发，同态加密技术在未来仍具有重要的研究和应用价值。

同态加密技术未来的研究方向可以归纳为提高效率、提高安全性和应用研究3个方面。在效率方面，目前的同态加密方案大部分都是基于公钥密码体制而构建的，存在密钥尺寸大、密文尺寸大的问题，不能满足云上对海量数据进行密文操作的要求，要实现云环境中密文的快速稳定存储、计算等应用，一是可以进一步提高非对称FHE方案的效率，二是可以研究对称同态加密算法。相比非对称同态加密方案，对称同态加密方案的计算复杂度要低得多，然而现行对称同态加密方案仍存在实现效率低、密钥管理复杂、在实际应用中部署困难、存在安全漏洞等种种未解决的问题，仍需做进一步的深入研究。在安全性方面，可验证同态加密可以保障使用同态加密技术时的数据完整性和可认证性，目前实现同态加密可验证的同态签名与同态MAC两种均还处在起步阶段。基于格上困难问题或其他困难问题设计的抗量子计算攻击的、高效的FHE方案目前是研究的主流，现有的大部分方案未考虑侧信道攻击(Side Channel Attacks, SCA)的影响，设计能够有效抵抗SCA的FHE方案是研究的重要方向之一。在应用方面，目前同态加密技术在安全多方计算、电子投票、机器学习和区块链隐私保护等领域都得到了重要应用，同态加密技术可以实现对数值型数据的同态运算，然而对于逻辑运算的处理有些无力，例如比较两个密文的大小，而这类运算在加密机器学习、密文检索等应用中都比较常见，尤其是随着大数据的快速发展，密文检索问题成为一个亟待解决的难题，设计基于同态加密的高效密文检索方案、利用同态加密技术实现加密机器学习都具有重要的现实意义。