全同态加密自举技术的研究现状及发展趋势*

刘钦菊,路献辉,李 杰,王鲲鹏

1.中国科学院 信息工程研究所 信息安全国家重点实验室,北京 100093

2.中国科学院大学 网络空间安全学院,北京 100049

1 引言

目前,在大数据和云计算等应用的驱动下,数据的隐私保护问题越来越受到人们的重视.全同态加密(fully homomorphic encryption,FHE)是目前用来解决数据隐私保护的主要技术手段之一.

全同态加密最早可以追溯到1978年,Rivest等人[1]针对“保密数据库”(private data banks)的应用场景提出了全同态加密的概念(当时被称之为“隐私同态,privacy homomorphic”).在此后的三十年里,密码学家们对同态加密进行了非常深入的研究,相继提出了单同态加密方案(partial homomorphic encryption,PHE)和部分同态加密方案(somewhat homomorphic encryption,SHE).单同态加密方案的特点是只能够支持同态加法或者同态乘法中的单一同态运算,代表方案有支持乘法同态的GM82方案[2]和ElGamal[3]方案以及支持加法同态的Paillier[4]方案.部分同态加密方案的特点是能够支持有限次数的同态加法和同态乘法,其代表方案为BGN05[5],该方案是基于双线性映射中的困难问题构造出来的,它除了能够支持任意多次的同态加法之外,还能够支持一次同态乘法,而且不会增加密文的尺寸.第一个可行的全同态加密方案是由Gentry于2009年基于理想格上的困难问题构造出来的[6].具有代表性的单同态加密方案,部分同态加密方案以及全同态加密方案在图1中给出.

图1 同态加密发展的时间线Figure 1 Timeline of homomorphic encryption

2009年,Gentry除了给出第一个可行的全同态加密方案之外,还给出了构造全同态加密方案的理论框架.该理论框架首先构造一个部分同态加密方案,之后再通过自举(bootstrapping)来实现全同态加密.目前,在部分同态加密方案的构造中,出于对方案的安全性考虑,加密过程需要引入噪音.随着同态运算的进行,噪音不断地累积,一旦噪音的尺寸超出某个阈值,就会出现解密错误.因此,我们必须采取消减噪音的操作来保证正确解密.自举是目前最有效的消减密文噪音的操作,也是迄今为止实现全同态加密的唯一途径.但是,自举计算代价昂贵,成为全同态加密算法计算性能的瓶颈.

具体地,自举是指当同态操作进行至噪音达到阈值而无法再进行操作时,将此时的密文与对应私钥的密文进行同态解密的操作.自举后可以得到支持继续同态操作的低噪音密文.根据全同态加密方案的设计思想1http://people.csail.mit.edu/vinodv/FHE/FHE-refs.html,自举技术大致可以划分为三代.

第一代全同态加密自举技术主要用于文献[6,7]中的方案.该类方案的特点是其中使用的部分同态加密方案是不可自举的,即可同态计算电路的深度有限,无法支持方案本身的解密电路.为了解决这一问题,Gentry等人利用稀疏子集和假设,将解密电路中复杂的运算进行预处理,压缩解密电路,使得同态计算电路能够支持解密操作,从而实现自举.该类方案使用的是布尔电路对密钥信息逐比特加密,自举一个比特信息的时间需要30 min左右[8].

第二代全同态加密自举技术针对的是基于格上带错误学习((R)LWE)问题构造的全同态加密方案.该类技术的代表方案主要有BGV[9,10]、BFV[11,12]、CKKS[13].该类方案中使用的部分同态加密方案通过引入噪音消减技术(模切换和rescale技术),使得该类方案在不需要自举的情况下,就能够实现“层次型”全同态加密(leveled-FHE),即在以电路深度为参数作为辅助输入的前提下,能够同态地执行任意有界深度的电路.因此,在自举的过程中,不再依赖于稀疏子集和的安全性假设来压缩解密电路.这样,该类方案的安全性就可以归约到格上的标准困难问题.由于该类方案的密文是向量形式,所以在进行同态计算的过程中需要引入计算密钥.并且这类方案支持打包和并行操作[14],因此能够对多个明文比特同时进行处理,具有很强的应用潜力.目前,分别基于BGV、BFV、CKKS方案设计的开源库HElib、SEAL、HEAAN得到了广泛的应用.

第三代全同态加密自举技术主要针对的是GSW[15]类型的全同态加密方案,以AP14[16]、FHEW[17]以及TFHE[18,19]方案为代表.与第二代全同态加密方案相比较,该类方案的密文是矩阵形式,因此在同态计算的过程中,不再需要引入计算密钥.此外,该类方案在同态计算的过程中噪音的增长是非对称的(即C1⊗C2与C2⊗C1产生的噪音是不相同的,其中C1,C2是密文).这使得之前的噪音消减技术不再适用.因此,Gentry等人提出了Flatten技术,实现了“层次型”全同态加密.并且根据噪音增长的特点,Alperin-Sheriff等人设计了一个快速自举的算法[16].目前基于该类方案设计的开源库主要有FHEW和TFHE.其中,TFHE自举一个比特信息仅需要13 ms的时间,从公开发表的文献来看,这是目前自举效率最高的方案之一.

目前,自举是实现全同态加密的唯一途径,同时也是造成全同态加密效率低下的主要原因.因此,自举是整个全同态加密方案中的核心和关键.本文将着重介绍三代全同态加密方案中自举方案的主要思想和具体实现方法.

2 基本概念

本节主要介绍同态加密中的一些相关的基本概念.

一个同态的公钥加密方案2虽然同态加密方案可以使用相同的密钥进行加解密(对称加密),但它也可以被设计为使用不同的密钥进行加密和解密(非对称,即公钥加密).文献[20]给出了一种将对称和非对称方案相互转换的通用方法.这里主要介绍公钥加密的方案的概念.(假设明文空间M={0,1})通常包含有4个PPT时间的算法:HE.KeyGen,HE.Enc,HE.Dec,HE.Eval.其中,HE.Eval能够完成对加密数据的同态计算.

定义1若公钥加密方案E满足:

•(sk,pk,evk)←HE.KeyGen(1λ,1τ):输入安全参数λ和参数τ,输出私钥sk、公钥pk和公开的计算密钥evk.

•c←HE.Enc(pk,m):给定公钥pk和明文比特m,输出相应的密文c.

•m←HE.Dec(c,sk):给定私钥sk和密文c,输出相应的明文比特m.

•c f←HE.Eval(evk,f,c1,c2,···,c l):输入计算密钥evk、函数f:{0,1}l■−→{0,1}以及密文c1,c2,···,c l,输出相应的计算密文c f.则称E=(HE.KeyGen,HE.Enc,HE.Dec,HE.Eval)是一个同态的公钥加密方案.

从语义上,定义1可以自然地拓展到明文向量(m= (m1,m2,···,m t))和密文向量 (c=(c1,c2,···,c t)=HE.Enc(pk,m)).一个同态加密方案,应至少满足下面几个属性.

•(正确性)通常情况下,HE.Enc输出的密文可称为“新鲜密文”,HE.Eval输出的密文可称为“计算密文”.下面的正确性定义针对的是这两种密文.让E=(HE.KeyGen,HE.Enc,HE.Dec,HE.Eval)表示一个同态加密方案,F={f i}i∈Z表示某个函数族.如果E能够正确解密“新鲜密文”和“计算密文”,那么同态加密方案E对于F是正确的.即对于任意的λ和i∈Z,下面两个条件成立:-对于任意的m∈{0,1},

-对于任意的f∈F以及明文向量m=(m1,m2,···,m t)∈{0,1}t,

•(同态性)如果一个加密方案E支持下面的等式:

E(m1)∗E(m2)=E(m1∗m2),∀m1,m2∈M,

其中M表示的是明文空间,那么该加密方案关于该运算∗是同态的.由于乘法和加法在有限集合上面是功能完备的[21],因此为了构造一个能够允许对任意函数进行同态操作的加密方案,该加密方案只需要满足加法和乘法同态就足够了.特别的,对于布尔电路来说,任意的电路都可以用XOR(加法)门和AND(乘法)门来表示.

•(语义安全性)同态方案的语义安全性是使用选择明文攻击(chosen plaintext attacks,CPA)安全性的标准概念来定义的.在这种定义下,任意一个PPT的敌手,即使是在知道公钥的情况下,也不能够区分0和1的加密.令E=(HE.KeyGen,HE.Enc,HE.Dec,HE.Eval)表示一个同态加密方案,A表示某个敌手.那么A对于E算法的优势定义为:

•(紧致性)对于一个同态加密方案E=(HE.KeyGen,HE.Enc,HE.Dec,HE.Eval),如果存在一个确定多项式函数B(·),对于所有的λ,τ,任意函数f和明文比特向量m=(m1,m2,···,m t)∈{0,1}t,满足

那么该方案E是紧致的.

紧致性能够充分体现同态计算的能力,它要求密文尺寸不随着计算电路的复杂性增加而增加.需要指出,在这里B(·)是一个只依赖于λ的多项式函数.这意味着即使方案中的某些部分(比如公钥的尺寸)依赖于方案中除去λ以外的其他因素,而计算密文是不依赖于这些参数的.换句话说,密文的尺寸与t和f无关.

3 自举的发展与研究现状

目前,在基于格的同态加密方案中,明文在加密成为密文的过程需要引入噪音,其目的是为了保证安全性.然而引入的噪音尺寸会随着同态运算的进行而不断的增长,一旦噪音的尺寸超出了某个阈值,就会出现解密错误.自举技术是目前实现全同态加密的唯一途径.因此,自举在同态地计算较深的电路或者没有限制次数的同态运算中起着至关重要的作用.

3.1 自举的计算任务

粗略地说,在某个给定的方案中自举一个“原始密文”意味着使用该方案中密钥的加密,以同态计算的方式运行该方案自己的解密算法.自举的结果是产生一个新的密文,该密文加密的明文跟“原始密文”相同,并且与“原始密文”相比较,自举之后产生的新的密文的噪音尺寸更小.因此,在同态计算的过程中,在适当的节点进行自举操作,能够保证密文在解密正确的情况下,同态运算可以持续进行下去.

3.2 自举的实现

根据全同态加密方案的划分方式,自举的实现主要划分为三条技术路线.第一条技术路线以第一代全同态加密方案中的自举为代表.他们研究的是在基于整数上稀疏子集和假设下构造的部分同态加密方案的自举,主要的技术手段是通过压缩解密电路和逐比特加密来实现全同态加密.第二条技术路线主要是以第二代的全同态加密方案中的自举为代表.他们研究的是基于环上带错误学习(RLWE)的困难问题构造的层次型全同态加密方案中的自举.这部分的工作主要是针对BGV、BFV和CKKS三个方案自举的设计和改进,与第一代全同态加密方案不同,这类方案利用SIMD技术能够做到同时对多个比特进行处理.特别地,与BGV和BFV方案不同,CKKS方案可以对加密数据进行近似的算术运算.正是由于这个特性,CKKS方案的自举过程有别于BGV和BFV方案.在CKKS的自举过程中,没有选择特殊的模数,而是找到一个代替该方案的解密函数的逼近函数-正弦函数来完成自举.第三条技术路线以第三代全同态加密方案中的自举为代表.他们针对的是对单个比特加密的自举.他们的实验结果表明,对于任意的布尔电路,自举一个比特仅需要13 ms的时间.目前,该方案是自举单个比特效率最高的方案之一.接下来,我们将依次对这三条技术路线中自举的过程和发展进行介绍.

3.2.1 第一代全同态加密方案中自举的实现

以Gentry等人为代表实现的第一代全同态加密方案的主要思想是,首先构造一个部分同态加密方案,该类方案的特点是可同态计算的电路深度比解密电路深度小,因此该类方案无法正确地执行自举操作.因此,该类方案需要通过压缩解密电路,使得解密电路的深度小于同态计算的电路深度,再借助自举技术来实现全同态[6,7].以vDGHV10方案为例,该方案的具体解密操作如下:

Decsk(c)=cmodpmod 2=m,

vDGHV10方案简化解密的具体过程如下:

Step-1(密钥生成):生成集合y={y1,y2,···,yβ}(其中y i∈[0,2)是一个实数),满足:存在一个稀

由于该类方案的实现采用的是布尔电路对密钥信息进行逐比特加密,所以使得整个方案的计算效率不高(自举一个比特需要花费大约30 min的时间)[8],不具备实用化的潜力.但是,尽管如此,其对后来自举方案的实现具有非常重要的理论指导意义.

3.2.2 第二代全同态加密方案中自举的实现

在第二代全同态加密方案中,我们主要介绍自举实现的两个代表方案:BGV方案和CKKS方案.

BGV方案的具体解密操作如下:

Decsk(c)=〈c,sk〉modqmod 2=m,

通过表2可以看出,w i的最低位比特就是z〈i〉.因此,我们可以利用公式(1)来进行比特提取.

表2 2i w i的位置比特信息Table 2 Bits position of 2i w i

表1 的位置比特信息Table 1 Bits position of

表1 的位置比特信息Table 1 Bits position of

比特位置 0 1 2 ··· r−1 z= z〈0〉 z〈1〉 z〈2〉 ··· z〈r−1〉z2= z〈0〉 0 * ··· *z22= z〈0〉 0 0 ··· *::::::z2r−1= z〈0〉 0 0 ··· 0

同态的比特提取无论是从时间还是电路深度上来说,都是复杂度最高的一个操作.并且它的时间和电路深度是随着提取的最高位有效比特(也就是r)增加的.从这一方面入手,直观上可以有两种改进方案.第一种方法,由于˜q=2r+1,因此可以选取较小的˜q来降低同态的比特提取的复杂度.但是,由于受解密正确的条件限制,˜q的选择不能太小,所以这一方法可行性不大.第二种方法,找到一种可以减小最高位有效比特(也就是r),但是不减小˜q的方法.该方法具体过程如下:

“拓展”BGV方案的自举.基础的BGV方案中的明文空间mod2可以拓展到modp e,接下来我们将介绍如何对拓展之后的BGV同态加密方案进行自举[23-25].将明文空间拓展之后的BGV同态加密方案的解密操作如下:

Decsk(c)=〈c,sk〉modqmodp e=m.

拓展的BGV同态加密方案的自举过程与基础方案类似.在基础BGV方案的比特提取过程中,X2在其中发挥了重要的作用.那么在拓展的BGV的同态数字提取过程中,也需要有这种性质的多项式,我们称之为“提升多项式”[26].

定义2(提升多项式)对于任意的e,存在一个次数为p的多项式F(·),满足:若z=z0modp e,则F(z)=z0modp e+1.我们称具有这种性质的多项式为“提升多项式”

拓展的BGV方案的自举过程可以类比基础方案的自举过程得到,我们在这里就不再赘述.

CKKS方案的具体解密操作如下:

Decsk(c)=〈c,sk〉modq=m+e,

图2 模约化和正弦函数[27]Figure 2 Modular reduction and scaled sine functions[27]

CKKS加密方案的自举过程如下:

Step-1(模提升):输入原始密文c,此时其对应的模数为q,则有m(x)=〈c,sk〉modq.我们可以观察到,如果只进行内积操作而不进行模约化,那么t(x)=〈c,sk〉(modX N+1)=m(x)+q I(x),其中I(x)∈R.因此,我们可以将c看作是在一个大的模数Q>q下,对t(x)=t0+t1x+···+t N−1x N−1的加密,即〈c,sk〉modQ=t(x).这时,同态解密过程(自举过程)转换为同态地对t(x)执行modq的操作(m(x)=t(x)modq).

Step-2(线性变换):由于我们是需要对多项式t(x)的系数t0,t1,···,t N−1进行运算操作,因此线性变换的目的是将明文t(x)的系数转换到明文槽中.

Step-3(模约化的近似同态操作):这一步过程主要是进行对t(x)进行modq的同态操作.由于我们可以求得modq的近似多项式函数P(·),所以我们只需要对相应的密文执行多项式P(·)的同态操作即可.

Step-4(逆线性变换):输入上一步得到的密文,这一步工作的目的是将明文m(x)的系数m0,m1,···,m N−1从明文槽中变换到明文系数的位置.这一步实际上是第三步的逆过程.之后,我们就能够得到在新的模数Q′(Q′>q)下对原始明文m(x)加密的新密文,自举过程结束.

3.2.3 第三代全同态加密方案中自举的实现

在第三代全同态加密方案中,主要的代表方案是GSW方案,这部分我们主要介绍针对GSW方案的自举.

GSW方案的特点是只针对单个比特的加解密,并且其同态计算的过程中无需计算密钥的辅助,该方案的解密函数如下:

Decsk(c)=[〈c,sk〉modq]2=m.

我们可以将该方案的解密函数分解成为三个基本的操作:内积(〈·,·〉),模约化(modq)以及舍入操作([·]2).显然内积操作的同态运算是简单的,并且我们可以观察到,〈c,sk〉modq=∑s i c imodq∈Zq.Alperin-Sheriff和Peikert等人[16]观察到这一点,通过构造(Zq,+)与(S q,×)之间的同构映射,将Zq中的元素编码成为S q的元素,之后只需要借助算数电路就能够完成GSW类型的同态加密方案的自举.具体的编码方式是,对于任意的i∈Zq,π(i)=(0,···,0,1,0,···,0)∈S q,其中π(i)的第i个位置为1,其余位置均为0.这种编码方式的好处在于可以自动的实现模约化操作.此外,还能够使得同态的舍入操作变得简单.事实上,我们可以把舍入操作理解为区间判定.因此,要判断一个属于Zq的数字是否属于某个区间,我们只需要将该区间的所有数字与该数字作比较.若相等,则返回1;否则,返回0.例如,判断m1是否与m2相等.给定m1,m2∈Zq,π(m1),π(m2)∈S q,那么m1=m2当且仅当π(m1)·π(m2)=1.

据此,我们可以将GSW类型的方案的解密过程分为两步:累加和最高位比特提取过程[18,19].其解密算法如算法2.

相应地,我们也可以将GSW类型的同态加密方案的自举过程分为两步:

Step-1(同态累加,homomorphic accumulator):这一步的主要目的是解决同态的内积和模约化操作.具体的算法过程如算法3.

算法3 Homomorphic accumulator ACC←b;for i=1 to n do ACC←ACC−Enc inter(a i·s i mod q);end Return ACC

其中,Encinter(·)指得是自举过程中的“中间同态加密方案”.尽管不同的自举方案有不同的中间方案,但是同态累加的过程大致一样,因此在这里就不再一一赘述.

Ducas和Micciancio等人[17]则利用的是Zq与Z[X]/〈X N+1〉,q=2N之间的同构映射σ.即对于任意的i∈Zq,σ(i)=X imodX N+1.具体的映射内容为:

3.3 自举的实现效率

自从2009年Gentry提出自举框架以来,自举技术作为全同态加密中的核心和计算代价最高的操作,得到了非常广泛深入的研究.从最开始自举一个比特需要30分钟开始,关于自举方案的实现主要发展成为两条路线.第一条主要是以第二代的全同态加密方案为代表,这类方案支持打包和并行,所以能够做到对多个明文同时进行自举,代表的开源库有HElib、SEAL、Palisade和HEAAN等.第二条主要是以第三代的全同态加密方案为代表,其针对的是对单个明文比特进行自举,代表的开源库有FHEW和TFHE等(图3).

图3 全同态加密方案中自举实现的效率Figure 3 Efficiency of bootstrapping in FHE

3.4 技术总结以及发展方向

从自举技术的实现来看,解密函数中涉及到的非线性部分是整个自举过程的最大困难点(见表3).而这一部分往往会导致方案本身的解密电路深度要大于方案可同态计算的电路深度.为了实现自举,通常会采取两种方式:一种是通过压缩解密电路的方式来减小解密电路深度(以第一代全同态加密方案为代表);一种是借助削减噪音的技术(模切换等技术)来增大方案可同态计算的电路深度(以第二、三代全同态加密方案为代表).

表3 三代全同态加密方案中自举的技术总结Table 3 Summary of three generations of bootstrapping in FHE

第一代的全同态加密方案中,将私钥信息借助稀疏子集和假设嵌入到公开密钥中,降低解密电路的复杂度.但是这一做法导致方案依赖于非标准的安全性假设.第二代的全同态加密方案的自举过程的主要计算开销来源于比特提取过程.若能找到一种能够对明文多项式的多个系数甚至是所有系数进行比特提取的方法,将会对第二代全同态加密方案中自举效率有很大提升.第三代的全同态加密方案中,恒等测试是自举方案设计的难点,也是决定整个自举计算开销的关键点.而恒等测试的设计依赖于(Zq,+)同构映射的构造.因此,如何构造一个紧致高效的同构映射将成为第三代全同态加密自举方案的设计中重点研究的内容.

4 总结

现如今,在大数据和云计算的推动下,数据隐私保护扮演着越来越重要的角色.全同态加密能够允许任何第三方在不事先解密的情况下对加密的数据执行任意的运算操作.正是由于全同态加密这一优良特性,让其能够自然地解决云计算中遇到的数据隐私保护的问题.因此,利用全同态加密来保护数据隐私成为了一个非常有潜力的发展方向.自举作为目前实现全同态加密的唯一途径,成为全同态加密中的关键和核心.事实上,自从2009年Gentry提出了自举框架开始,该框架已经存在有十多年的历史.随着全同态加密方案设计上的理论和实践创新,自举也得到了深入广泛的研究.具体来说,这篇文章从自举的困难点入手,围绕着自举技术,介绍了近年来全同态加密的发展与研究现状.之后,重点针对三代全同态加密方案的自举技术,逐一展开进行详细的介绍,并进行了效率方面的比较以及对未来发展方向的思考,以供感兴趣的研究学者参考.