同態(tài)密碼理論與應(yīng)用進(jìn)展

楊亞濤 趙 陽 張卷美 黃潔潤(rùn) 高 原

①(北京電子科技學(xué)院電子與通信工程系 北京 100070)

②(北京電子科技學(xué)院密碼科學(xué)與技術(shù)系 北京 100070)

③(西安電子科技大學(xué)通信工程學(xué)院 西安 710071)

1 前言

近年來云計(jì)算技術(shù)以及由云計(jì)算技術(shù)延伸和擴(kuò)展而來的云存儲(chǔ)技術(shù)始終熱度不減，各類提供云服務(wù)的云平臺(tái)也如雨后春筍般涌現(xiàn)。通過云計(jì)算和云存儲(chǔ)技術(shù)，可以將海量數(shù)據(jù)的存儲(chǔ)和復(fù)雜運(yùn)算等工作外包給提供云服務(wù)的各大運(yùn)營(yíng)商，這實(shí)現(xiàn)了資源共享，減少了運(yùn)算開支。然而，提供云服務(wù)的第三方無法保障用戶數(shù)據(jù)的隱私安全，網(wǎng)絡(luò)環(huán)境下的各種不可控因素對(duì)云上的用戶數(shù)據(jù)隱私保護(hù)提出了挑戰(zhàn)。使用傳統(tǒng)加密手段可以保障數(shù)據(jù)外包時(shí)的存儲(chǔ)安全，卻難以保障其計(jì)算安全。在此背景下，同態(tài)加密(Homomorphic Encryption, HE)技術(shù)成為解決云環(huán)境下隱私保護(hù)問題的重要手段。使用同態(tài)加密技術(shù)，用戶對(duì)密文進(jìn)行運(yùn)算后再解密得到的結(jié)果與直接對(duì)明文進(jìn)行運(yùn)算得到的結(jié)果一致，這一特性允許不可信第三方在沒有私鑰的情況下直接對(duì)密文進(jìn)行運(yùn)算，避免了第三方在運(yùn)算過程中需要解密密文而導(dǎo)致的用戶敏感信息泄露。

1978年Rivest等人[1]首次提出了隱私同態(tài)的概念，旨在構(gòu)造一種支持密文檢索的加密機(jī)制，后來發(fā)展為這樣一種理念：在不解密的情況下對(duì)密文進(jìn)行任意的函數(shù)變換，對(duì)變換的輸出解密，所得結(jié)果與對(duì)相應(yīng)的明文進(jìn)行同樣的函數(shù)變換所得結(jié)果一樣。如何實(shí)現(xiàn)全同態(tài)加密(Fully Homomorphic Encryption, FHE)由此成為密碼學(xué)界的開放性問題，終于在2009年Gentry[2]首次利用理想格給出了FHE方案的構(gòu)造，該方案基于理想格上的有界編碼問題與稀疏子集和問題，其思路如下：明文空間為{0, 1}，首先構(gòu)造一個(gè)對(duì)“新鮮”密文支持有限次多項(xiàng)式運(yùn)算的類同態(tài)加密(SomeWhat Homomorphic Encryption, SWHE)方案；然后基于稀疏子集和問題困難性假設(shè)變換私鑰的形式，壓縮解密電路，將其表示成關(guān)于私鑰的次數(shù)足夠低的多項(xiàng)式；最后在公鑰中添加私鑰的密文等輔助信息，用于對(duì)“新鮮”密文同態(tài)運(yùn)算后生成的密文進(jìn)行同態(tài)解密，降低其中包含的噪聲，實(shí)現(xiàn)“自舉”功能，達(dá)到對(duì)密文進(jìn)行任意函數(shù)變換的目的，這一技術(shù)稱為Bootstrapping(自舉)技術(shù)。Gentry提出的這種構(gòu)造模式被稱為Gentry體制，此后全同態(tài)加密技術(shù)發(fā)展迅速，分為兩條研究主線，一種是按照Gentry的思路設(shè)計(jì)的FHE方案，另一種則為基于錯(cuò)誤學(xué)習(xí)(Learning With Errors, LWE)問題或環(huán)上錯(cuò)誤學(xué)習(xí)(Ring-LWE, RLWE)問題實(shí)現(xiàn)的FHE方案[3,4]。下面，本文主要分析近年來同態(tài)加密技術(shù)的一些新進(jìn)展并提出未來值得關(guān)注的幾個(gè)發(fā)展方向。

2 相關(guān)概念及理論基礎(chǔ)

電路觀點(diǎn)是指用電路模型來理解同態(tài)加密方案的密文計(jì)算(Ciphertext computation)算法，電路模型必須接觸到所有的輸入數(shù)據(jù)，不會(huì)泄露任何信息，因此可以將一個(gè)函數(shù)或功能 f等效為一個(gè)電路模型C (c1,c2,···,ck)∈Cλ， 其中Cλ為 電路集合，λ 為安全系數(shù)。電路模型下可以通過門電路數(shù)量、乘法電路深度等來衡量算法的計(jì)算復(fù)雜度。

通常一個(gè)公鑰加密方案包含3個(gè)算法：密鑰生成算法( KeyGen )、加密算法(E nc)和解密算法(D ec)。但是在同態(tài)加密中，除了上述3個(gè)算法之外，還包含第4個(gè)算法即密文計(jì)算算法( E val)。密文計(jì)算是指在密文域上進(jìn)行的運(yùn)算，它通常需要滿足正確性以及可驗(yàn)證性。

(1) 密鑰生成算法 KeyGen(λ)是一個(gè)隨機(jī)化的算法，輸入安全系數(shù) λ，輸出解密私鑰s k、加密公鑰p k 以及用于密文計(jì)算的公開密鑰e k；

(2) 加密算法 Enc(pk,m)是一個(gè)隨機(jī)化的算法，輸入公鑰 pk 和明文m ，輸出密文c，對(duì)于相同的明文每次加密得到的密文都是不同的；

(3) 解密算法 Dec(sk,c)是一個(gè)確定性的算法，輸入私鑰s k 以及密文c ，輸出明文m 。

(4)密文計(jì)算算法E val(ek,(c1,c2,···,ck),C)輸入密文計(jì)算密鑰 ek ，電路C (c1,c2,···,ck)∈Cλ和密文(c1,c2,···,ck) ，輸出為密文計(jì)算結(jié)果c?；

以上4個(gè)算法都是概率多項(xiàng)式時(shí)間(Probabilistic Polynomial Time, PPT)算法。

定義1同態(tài)性：對(duì)于加密方案 α及其明文域M上的運(yùn)算? ， 若對(duì)于? m1,m2,··· ,mk∈M都滿足式(1)，則表明該加密方案對(duì)于運(yùn)算? 滿足同態(tài)性

定義2正確性：對(duì)于K eyGen(λ)生成的公私鑰對(duì) (pk,sk) ，電路集合Cλ中的任意電路C ，明文域M中的任意明文m1,m2,···,mk以及加密得到的密文(c1,c2,···,ck) ，其中E nc(pk,mi)→ci，如果對(duì)輸出的c?=Eval(ek,(c1,c2,···,ck),C)， 都 有Dec(pk,c?)=C(m1,m2,···,mk)，則 認(rèn) 為同態(tài)加密方案α 關(guān)于電路集合Cλ中的電路是正確的。

定義3緊湊性：對(duì)于任意的安全參數(shù)λ，假如存在一個(gè)多項(xiàng)式 f ，使得α 的解密算法能夠用一個(gè)規(guī)模至多為f (λ)的 電路 D來表示，那么，同態(tài)加密方案α 便是緊湊的。

通俗來講，滿足緊湊性意味著算法的解密電路不依賴于密文或密文運(yùn)算函數(shù)。

定義4安全性：通過選擇明文攻擊(Chosen Plaintext Attacks, CPA)來定義同態(tài)加密的安全性。若敵手 A為多項(xiàng)式時(shí)間的，且式(2)對(duì)任意敵手A 在λ 上都是可忽略的，則該同態(tài)加密方案為不可區(qū)分選擇明文攻擊安全的(也稱為IND-CPA安全的)

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

3 同態(tài)加密類型及研究動(dòng)態(tài)

3.1 同態(tài)加密算法的分類

同態(tài)加密技術(shù)雖然還沒有統(tǒng)一的分類標(biāo)準(zhǔn)，但是其發(fā)展歷史仍是具有階段性特征的。按照各同態(tài)加密方案允許密文計(jì)算的種類和次數(shù)，可以將其分為3類：部分同態(tài)加密(Partial Homomorphic Encryption, PHE)方案、類同態(tài)加密方案和全同態(tài)加密方案。PHE僅滿足加法或乘法的密文同態(tài)運(yùn)算；SWHE可同時(shí)滿足加法和乘法有限次的密文同態(tài)運(yùn)算；FHE可同時(shí)滿足加法和乘法無限次的密文同態(tài)運(yùn)算。

定義5部分同態(tài)加密：若加密方案α 僅對(duì)于加法( +)滿 足同態(tài)性或者僅對(duì)于乘法( ×)滿足同態(tài)性，則稱該方案為部分同態(tài)加密方案。即僅滿足式(3)或式(4)

定義6類同態(tài)加密：若加密方案 α對(duì)于加法(+)和 乘法( ×)都滿足同態(tài)性，但是由于噪聲限制只能進(jìn)行有限次的同態(tài)運(yùn)算，則稱該方案為類同態(tài)加密方案。即同時(shí)滿足式(3)和式(4)，但只能進(jìn)行有限次運(yùn)算。

定義7全同態(tài)加密：若加密方案 α對(duì)于加法(+)和 乘法( ×)都滿足同態(tài)性，且能在無限次運(yùn)算后依然保持同態(tài)性，則稱該方案為全同態(tài)加密方案。即同時(shí)滿足式(3)和式(4)，且能進(jìn)行無限次運(yùn)算?；蛘呖梢哉f對(duì)于任意電路C ∈Cλ都滿足正確性和緊湊性的同態(tài)加密方案為全同態(tài)加密方案。

目前很多PHE方案已經(jīng)取得了比較可觀的加解密效率，并且已經(jīng)被切實(shí)應(yīng)用到了現(xiàn)實(shí)生活中(例如Paillier[5]加法同態(tài)加密方案被頻繁應(yīng)用在電子投票、醫(yī)療計(jì)量等場(chǎng)景下，其加解密耗時(shí)僅為毫秒級(jí))，但是FHE方案由于管理密文計(jì)算中持續(xù)增長(zhǎng)的噪聲需要投入大量的計(jì)算資源，效率仍然較低，還不能滿足實(shí)際應(yīng)用的需求，此外由于同態(tài)性與延展性之間的相互矛盾，全同態(tài)加密無法實(shí)現(xiàn)INDCCA2安全。因此，對(duì)全同態(tài)加密的研究仍然任重道遠(yuǎn)，且相應(yīng)的主要聚焦于兩個(gè)方面：一是提高FHE方案的效率；二是提高FHE方案的安全性。全同態(tài)加密近十年來的研究進(jìn)程可大致劃分為3個(gè)階段[6]：第1階段是以Gentry的突破性工作為基礎(chǔ)構(gòu)造的各類FHE方案，首先構(gòu)造一個(gè)SWHE方案，然后通過Bootstrapping技術(shù)控制噪聲增長(zhǎng)實(shí)現(xiàn)全同態(tài)；第2階段是以Brakerski和Vaikuntanathan的工作為基礎(chǔ)構(gòu)造的基于LWE和RLWE的FHE方案，通過密鑰交換(key switching)技術(shù)來解決維數(shù)膨脹的問題，通過模交換(Modulus Switching)技術(shù)來控制噪聲，一定程度上擺脫了對(duì)Bootstrapping技術(shù)的依賴；第3階段是由Gentry等人[7]構(gòu)造的基于近似特征向量的GSW方案，該方案的同態(tài)運(yùn)算全部為簡(jiǎn)單的矩陣運(yùn)算，故不會(huì)出現(xiàn)維數(shù)膨脹的問題，該方案提供了一種構(gòu)造FHE方案的新思路，將原先復(fù)雜的密文運(yùn)算過程簡(jiǎn)化為了較為單純的代數(shù)運(yùn)算，更加便于理解。宋新霞等人[8]對(duì)密文矩陣的本質(zhì)及構(gòu)造方法進(jìn)行了研究，提出抽象解密結(jié)構(gòu)的概念，并以此為基礎(chǔ)揭示了密文矩陣FHE與其它FHE之間的包含關(guān)系?？偠灾?，近年來對(duì)全同態(tài)加密技術(shù)的研究進(jìn)展迅速，但是其實(shí)現(xiàn)效率問題仍是亟需解決的主要難題。

除了上述按照發(fā)展階段進(jìn)行劃分以外，F(xiàn)HE還可以依照所基于的困難問題來分類[9]，主要有兩種，一種是基于傳統(tǒng)數(shù)論中的困難問題，如整數(shù)上近似最大公約數(shù)(Approximate Greatest Common Divisor, AGCD)問題，另一種是基于格密碼學(xué)中的困難問題，如格上LWE問題和RLWE問題。另外，近年還出現(xiàn)了基于NTRU(Number Theory Research Unit)的FHE方案、基于身份和屬性的FHE方案以及無噪聲的FHE方案等諸多其他類型的FHE方案，李子臣等人[10]通過格上的高斯抽象算法生成密鑰對(duì)，然后利用Flattening技術(shù)構(gòu)造了基于NTRU選擇明文攻擊可證明安全的全同態(tài)加密方案。為了解決NTRU在實(shí)現(xiàn)過程中的側(cè)信道攻擊安全隱患，楊亞濤等人[11]對(duì)NTRU算法所有系數(shù)執(zhí)行掩碼操作，構(gòu)造了能夠有效防御差分能量攻擊及相關(guān)能量攻擊的NTRU全同態(tài)掩碼防御方案。可以發(fā)現(xiàn)，近十年來建立在格密碼學(xué)基礎(chǔ)之上的FHE方案大量涌現(xiàn)，格密碼作為后量子密碼中頗具潛力的密碼體制，使全同態(tài)加密技術(shù)在量子計(jì)算時(shí)代仍具有重要的應(yīng)用價(jià)值。

3.2 全同態(tài)加密

全同態(tài)加密支持密文域上無限次的加法和乘法運(yùn)算。Gentry提出了一種基于理想格的FHE方案，為FHE的研究奠定了基礎(chǔ)，在Gentry的方案中Bootstrapping(自舉)技術(shù)是實(shí)現(xiàn)全同態(tài)的關(guān)鍵，下面簡(jiǎn)要介紹Bootstrapping技術(shù)的原理。首先在使用Bootstrapping之前，我們已經(jīng)可以進(jìn)行有限次的密文同態(tài)運(yùn)算，但是每進(jìn)行一次同態(tài)運(yùn)算后密文噪聲都會(huì)相應(yīng)增加，尤其是在進(jìn)行同態(tài)乘運(yùn)算時(shí)，密文噪聲隨運(yùn)算次數(shù)呈指數(shù)形式增長(zhǎng)，因此必須采取措施進(jìn)行噪聲控制。

如圖1所示，對(duì)密文進(jìn)行若干次同態(tài)運(yùn)算后得到的密文 c 對(duì)應(yīng)于明文m ，且該密文噪聲很大。Dc為解密電路且滿足Dc(sk)=Decsk(c)=m , Encpk(sk)是用公鑰直接對(duì)私鑰進(jìn)行加密得到的，將Encpk(sk)作為解密電路 Dc的 輸入，其輸出為密文c′且c′對(duì)應(yīng)的明文仍為 m 。因?yàn)镋 ncpk(sk)的噪聲很小(low noise)，因此 c′的噪聲也很小，從而達(dá)到了降噪的目的。

圖1 Bootstrapping原理

由于反復(fù)調(diào)用解密電路使FHE方案效率過低，因此很多人隨后針對(duì)Bootstrapping進(jìn)行了優(yōu)化，Ducas等人[12]在EUROCRYPT2015上將Helib庫中Bootstrapping操作的運(yùn)行時(shí)間從6 min縮短至1 s以內(nèi)，并相應(yīng)提出了FHEW方案。Chillotti等人[13]隨后在ASIACRYPT2016上對(duì)FHEW方案進(jìn)一步優(yōu)化，將Bootstrapping的運(yùn)行時(shí)間從1 s以內(nèi)縮短至0.1 s以內(nèi)，并將其密鑰大小從1 GB減小至24 MB。在EUROCRYPT2018上，Chen等人[14]通過應(yīng)用“低位刪除”多項(xiàng)式優(yōu)化了開方運(yùn)算，此舉對(duì)下文要提到的FV和BGV方案中的Bootstrapping都有重要作用。若令密鑰的1-范數(shù)為h =//s//1，明文模數(shù)為t =pr，則優(yōu)化算法可以將FV方案的自舉深度降至l og2h+log2(logp(ht))，將BGV方案的自舉深度從 log2h+2log2t 降至l og2h+log2t。除了優(yōu)化Bootstrapping以外，另一種為全同態(tài)“提速”的有效手段是批處理(batch)技術(shù)，也可稱為封裝(Pack)技術(shù)，即允許將多個(gè)數(shù)據(jù)值加密為一個(gè)密文，并能夠同態(tài)執(zhí)行單指令多數(shù)據(jù)操作(Single Instruction Multiple Data, SIMD)。2014年，Smart等人[15]通過中國(guó)剩余定理分解明文空間，構(gòu)造了支持SIMD操作的FHE方案。在EUROCRYPT2018上，Castryck等人[16]通過引入勞倫多項(xiàng)式編碼技術(shù)對(duì)Smart的方案進(jìn)行了改進(jìn)，極大提高了明文封裝容量以及在效率或安全性方面優(yōu)化系統(tǒng)參數(shù)的靈活性。雖然通過不斷優(yōu)化Bootstrapping技術(shù)和引入Batching技術(shù)大幅提高了FHE方案的實(shí)現(xiàn)效率，但是離實(shí)際應(yīng)用的要求還有一定距離，因此構(gòu)造無噪聲的FHE方案成為當(dāng)前全同態(tài)加密研究的一個(gè)重要思路[17]。噪聲的加入是為了保證FHE方案的安全性，但也帶來了噪聲控制的困擾，雖然無噪聲的FHE方案被認(rèn)為是不安全的，但該結(jié)論也并沒有被嚴(yán)格證明，因此研究無噪聲的FHE方案仍具有現(xiàn)實(shí)意義。2012年Kipnis等人[18]分別基于矩陣和多項(xiàng)式構(gòu)造了無噪聲FHE方案。2014年Nuida[19]在IACR Cryptology ePrint上提出了一個(gè)構(gòu)造無噪聲FHE方案的框架。同年，Gentry[20]基于完備群概念提出了一個(gè)無噪聲FHE框架。除上述方案以外，近年來還出現(xiàn)了基于向量空間[21]，基于八元數(shù)環(huán)[22]，基于非交換環(huán)[23]等的無噪聲FHE方案。但是目前現(xiàn)有無噪聲FHE方案還并不能在可證明安全框架下嚴(yán)格做到安全可行。此外，GPU和FPGA等硬件架構(gòu)的特點(diǎn)具有大幅度提高同態(tài)加密方案效率的潛力，大整數(shù)乘法是FHE算法中最為核心的計(jì)算環(huán)節(jié)，施佺等人[24]采用Verilog HDL語言完成了一個(gè)16×24 bit有限域FFT算法的FPGA設(shè)計(jì)，謝星等人[25]提出一種基于Sch?nhage-Strassen算法的768 kbit大整數(shù)乘法器FPGA設(shè)計(jì)，均較CPU平臺(tái)的運(yùn)算效率有大幅提速。表1總結(jié)了提高全同態(tài)加密效率的各類解決方案。

在Gentry體制之后，基于整數(shù)的FHE方案迅速成型?；谡麛?shù)的FHE方案完全遵循Gentry的設(shè)計(jì)思路，其安全性基于AGCD困難問題。2010年Smart等人[26]基于整數(shù)與多項(xiàng)式設(shè)計(jì)了FHE方案，縮短了密鑰和密文尺寸。同年，Dijk等人[27]提出了基于整數(shù)環(huán)上的FHE方案DGHV方案，這某種意義上是第1個(gè)基于整數(shù)的FHE方案，并且提出能夠同時(shí)加密多個(gè)bit位數(shù)據(jù)的思路，但其缺點(diǎn)是計(jì)算過程比較復(fù)雜。此后很多人從DGHV方案入手，對(duì)整數(shù)上的FHE方案進(jìn)行了優(yōu)化。在EUROCRYPT 2013上，Cheon等人[28]引入批處理技術(shù)，允許并行處理多比特?cái)?shù)據(jù)(以向量形式存儲(chǔ))，在EUROCRYPT 2015上Nuida等人[29]將方案的明文空間從 Z2擴(kuò)展至ZQ， 其中Q 為任意素?cái)?shù)，同時(shí)當(dāng)Q =2時(shí)，同態(tài)乘的算法復(fù)雜度從 O(λ(log2λ)2) 降為O (λ)，該方案同樣可以擴(kuò)展為批處理FHE方案。目前FHE方案所基于的困難問題主要有兩類，分別是Regev提出的RLWE問題和Howgrave-Graham[30]提出的AGCD問題。Cheon等人[31]在EUROCRYPT2015上將LWE問題歸約為AGCD問題的一個(gè)變體，并在此基礎(chǔ)上提出了一種新的基于AGCD的FHE方案，該方案的安全性不再依賴稀疏子集和的問題假設(shè)，且其性能優(yōu)于此前所有的基于AGCD的FHE方案?，F(xiàn)有的基于整數(shù)的FHE方案是針對(duì)兩個(gè)參與者“一方加密，一方解密”(一對(duì)一)設(shè)計(jì)的，王彩芬等人[32]提出一種“多方加密，一方解密”(多對(duì)一)的FHE方案，與已有方案相比擴(kuò)展了數(shù)據(jù)傳輸量，且提高了效率。除了基于整數(shù)的FHE方案以外，大量研究開始關(guān)注在實(shí)數(shù)域上的密文計(jì)算，Jaschke等人[33]提出一個(gè)有理數(shù)通過與2的冪迭代相乘可以近似表示為整數(shù)，不過相應(yīng)也帶來了額外的計(jì)算負(fù)擔(dān)。另一方面，Dowlin等人[34]提出一種更高效的表示定點(diǎn)小數(shù)的方法，即將定點(diǎn)小數(shù)編碼為整系數(shù)多項(xiàng)式，然而要想進(jìn)行精確的小數(shù)運(yùn)算，明文模需隨電路深度的增加呈指數(shù)增大。在ASIACRYPT2017上，Cheon等人[35]構(gòu)造了一種實(shí)數(shù)域上的FHE方案CKKS方案，可以對(duì)浮點(diǎn)數(shù)進(jìn)行近似計(jì)算，方案加密時(shí)對(duì)明文進(jìn)行舍入，解密時(shí)輸出滿足精度要求的近似值，通過使用Rescaling技術(shù)，在保證計(jì)算精度的同時(shí)將密文模數(shù)增長(zhǎng)從指數(shù)增長(zhǎng)變?yōu)榫€性增長(zhǎng)，并通過使用批處理技術(shù)提高算法的計(jì)算效率。方案分別給出了在乘法逆、指數(shù)函數(shù)、邏輯運(yùn)算和離散傅里葉變換這4種運(yùn)算電路下的效率分析，效率都較為可觀，但是該方案為層次型同態(tài)加密方案，不能通過Bootstrapping轉(zhuǎn)化為全同態(tài)加密方案。隨后在EUROCRYPT2018上，Cheon等人[36]基于Bootstrapping提出了一種更新低層級(jí)密文的新技術(shù)，將上述的層次型同態(tài)加密方案擴(kuò)展為了全同態(tài)加密方案，該技術(shù)使用正弦函數(shù)近似代替模數(shù)約減操作，每次迭代操作僅包含1次同態(tài)乘運(yùn)算，若對(duì)加密后的128個(gè)數(shù)字(精度為12 bit)進(jìn)行密文更新，共耗時(shí)139.8 s。表2總結(jié)了利用全同態(tài)加密技術(shù)在處理整數(shù)和實(shí)數(shù)域上的研究進(jìn)展。

表1 提高全同態(tài)加密效率的解決方案

基于對(duì)稱密碼體制的FHE算法，近年來多次出現(xiàn)在人們視野中。目前基于對(duì)稱密碼體制的同態(tài)加密算法主要有基于序列密碼的和基于分組密碼的兩類，由于在循環(huán)迭代過程中噪聲會(huì)迅速增大，基于分組密碼的同態(tài)加密方案只能滿足微弱的同態(tài)性，而基于序列密碼的同態(tài)加密方案僅在第1次密文計(jì)算時(shí)滿足較強(qiáng)的同態(tài)性，在EUROCRYPT2016上，Méaux等人[37]結(jié)合了這兩類方案的優(yōu)點(diǎn)，通過在序列密碼中加入濾波置換(filter permutator)，使得每輪輸出的噪聲恒定不變，理論上講，這種設(shè)計(jì)架構(gòu)也適用于其他的FHE方案。隨著量子計(jì)算理論的發(fā)展，未來必將迎來量子計(jì)算機(jī)應(yīng)用的熱潮，量子同態(tài)加密的概念也被隨之提出。在CRYPTO2015中，Broadbent等人[38]正式給出了量子同態(tài)加密(Quantum homomorphic encryption)的定義，即實(shí)現(xiàn)量子信息的加密以及密文的量子同態(tài)運(yùn)算，此外作者還相應(yīng)給出了量子信息中IND-CPA的定義。隨后在CRYPTO2016中，Dulek等人[39]基于文獻(xiàn)[38]中所提出的架構(gòu)，構(gòu)造了第1個(gè)量子全同態(tài)加密(Quantum FHE, QFHE)方案，可以實(shí)現(xiàn)任意多項(xiàng)式級(jí)量子電路的密文運(yùn)算。

表2 全同態(tài)加密在整數(shù)域和實(shí)數(shù)域上的研究進(jìn)展

3.3 可驗(yàn)證同態(tài)加密

可驗(yàn)證計(jì)算是在分布式計(jì)算和云計(jì)算環(huán)境下，保障數(shù)據(jù)外包時(shí)計(jì)算結(jié)果可靠性的重要手段[40]，構(gòu)造可驗(yàn)證的同態(tài)加密方案成為保證數(shù)據(jù)完整性以及計(jì)算過程可靠可信的關(guān)鍵。在2002年Johnson等人首次在文獻(xiàn)[41]中提出了同態(tài)簽名(Homomorphic Signature, HS)的概念，此后相繼出現(xiàn)了很多支持線性函數(shù)計(jì)算的同態(tài)簽名方案。2011年Boneh等人[42]構(gòu)造了首個(gè)能夠執(zhí)行確定階數(shù)的多項(xiàng)式運(yùn)算的同態(tài)簽名方案。2013年Gneearo等人[43]形式化定義了同態(tài)消息認(rèn)證(HomMAC)的概念，指出同態(tài)MAC可以看作同態(tài)簽名方案的對(duì)稱密鑰版本。至此，同態(tài)簽名和同態(tài)MAC都可以作為保護(hù)外包數(shù)據(jù)完整性和可靠性的有效手段，簡(jiǎn)言之，同態(tài)簽名可實(shí)現(xiàn)公開驗(yàn)證(Public verification)，同態(tài)MAC可實(shí)現(xiàn)私人驗(yàn)證(Private verification)。目前，同態(tài)MAC方案的相關(guān)研究已取得了很多重要進(jìn)展，在EUROCRYPT2013上，Catalano等人[44]提出了兩個(gè)同態(tài)MAC的具體實(shí)現(xiàn)，均支持低次多項(xiàng)式運(yùn)算且效率較高，但不能同時(shí)滿足標(biāo)簽的簡(jiǎn)潔性(Succinctness)和方案的復(fù)合性(Composability)。隨后他們?cè)赑KC-2014上對(duì)先前的工作進(jìn)行了總結(jié)，抽象出了有限延展性編碼的思想，允許同態(tài)MAC在滿足簡(jiǎn)潔性的前提下，一定程度上同時(shí)滿足復(fù)合性。2018年，白平等人[45]運(yùn)用有限延展性編碼的思想構(gòu)造了基于默克爾哈希樹的同態(tài)認(rèn)證方案，雖然在復(fù)合度上有所不足，但可以在不同云服務(wù)器之間的數(shù)據(jù)傳輸過程中實(shí)現(xiàn)數(shù)據(jù)完整性和刪除操作的可驗(yàn)證。

在ASIACRYPT2014上，Catalano等人[46]提出了適用于Paillier加密體制的可驗(yàn)證同態(tài)加密方案。Catalano等人針對(duì)同態(tài)加密方案的可驗(yàn)證問題引入了一個(gè)新的密碼學(xué)原語LAEPuV(Linearly homomorphic Authenticated Encryption with Public Verifiability), 即支持公開驗(yàn)證的線性同態(tài)認(rèn)證加密。線性同態(tài)簽名是一種特殊的數(shù)字簽名，它對(duì)消息和簽名都具有同態(tài)性，其概念最早由Boneh等人[47]在2009年提出。LAEPuV方案即為在標(biāo)準(zhǔn)模型下的多項(xiàng)式同態(tài)簽名方案，它在保護(hù)數(shù)據(jù)隱私安全和計(jì)算結(jié)果正確性的基礎(chǔ)上，支持對(duì)計(jì)算結(jié)果的公開驗(yàn)證，即在僅有密文情況下，驗(yàn)證者依然可以進(jìn)行驗(yàn)簽。Catalano等人給出了LAEPuV在Paillier加密體制中的具體形式，證明了其適用性。在ASIACRYPT 2014上，Joo等人[48]對(duì)同態(tài)認(rèn)證加密(Homomorphic Authenticated Encryption, HAE)進(jìn)行了系統(tǒng)的研究，并首次給出了在HAE中IND-CPA和INDCCA等安全概念的定義以及UF-CPA和UF-CCA等認(rèn)證概念的定義。Joo等人指出當(dāng)前現(xiàn)有的同態(tài)簽名方案和同態(tài)MAC方案還存在很多局限性(比如僅支持次數(shù)較低的多項(xiàng)式函數(shù)，僅能進(jìn)行有限次的驗(yàn)證查詢[49])，并基于EF-GCD(Error-Free approximate GCD)假設(shè)構(gòu)造了一種HAE方案，雖然該方案是類同態(tài)而不是全同態(tài)的，但是它同時(shí)滿足作者所定義的IND-CPA和SUF-CCA安全性。

在上面提到的所有方案中，注意到方案中帶標(biāo)簽的程序(Labeled-program)能夠計(jì)算不同用戶在不同時(shí)刻認(rèn)證過的數(shù)據(jù)，前提條件是這些數(shù)據(jù)都是用同一個(gè)密鑰進(jìn)行認(rèn)證加密的。Fiore等人[50]在ASIACRYPT2016上定義了多密鑰同態(tài)簽名(Multi-key Homomorphic Signature, M-HS)，適用于需要多方參與的場(chǎng)景，增強(qiáng)了同態(tài)簽名的實(shí)用性，并在此基礎(chǔ)上構(gòu)造了確定階數(shù)多項(xiàng)式深度的同態(tài)簽名方案。然而現(xiàn)有M-HS方案簽名的不可偽造性依賴于假設(shè)所有的簽名者都是可信的，這一假設(shè)在MHS的實(shí)際應(yīng)用(如可驗(yàn)證多方計(jì)算)中并不符合實(shí)際，因此Lai等人[51]在ASIACRYPT2018中對(duì)存在任意數(shù)量不可信簽名者的情形進(jìn)行了研究，基于零知識(shí)證明中的ZK-SNARK技術(shù)提出了一種M-HS的通用結(jié)構(gòu)，但是并沒有分析該結(jié)構(gòu)的認(rèn)證安全性和實(shí)用性。在ASIACRYPT2017中Alagic等人[52]指出量子同態(tài)計(jì)算也可以通過無交互的方式進(jìn)行驗(yàn)證，通過在密文計(jì)算算法的輸出結(jié)果中增加密文計(jì)算日志可實(shí)現(xiàn)其可驗(yàn)證性，由此構(gòu)造了一個(gè)可驗(yàn)證的量子全同態(tài)加密方案，并證明了該方案的正確性和安全性。如何能夠既保證用戶數(shù)據(jù)的私密性又保證計(jì)算結(jié)果的正確性，是云環(huán)境下執(zhí)行運(yùn)算的難題之一。表3總結(jié)了可驗(yàn)證同態(tài)加密的研究進(jìn)展。

4 同態(tài)密碼知識(shí)產(chǎn)權(quán)分析

隨著同態(tài)加密技術(shù)的深入研究，一些基于同態(tài)加密的具體應(yīng)用已被逐步推廣，然而目前還不能滿足對(duì)云中海量數(shù)據(jù)進(jìn)行復(fù)雜運(yùn)算的需求，因此針對(duì)同態(tài)加密算法的改進(jìn)以及針對(duì)其實(shí)際應(yīng)用的探索仍有一段很長(zhǎng)的路要走。下面通過分析近幾年與同態(tài)密碼相關(guān)的知識(shí)產(chǎn)權(quán)，透視該技術(shù)目前的應(yīng)用現(xiàn)狀。

表3 可驗(yàn)證同態(tài)加密研究進(jìn)展

文獻(xiàn)[53]基于CO-ACD(CO-Approximate Common Divisor)問題構(gòu)造并實(shí)現(xiàn)了一個(gè)加法部分同態(tài)加密方案。文獻(xiàn)[54]公開了一種基于同態(tài)加密的簽名方案，具體可以應(yīng)用于匿名證書、電子投票和群簽名中。文獻(xiàn)[55]公開了一種可驗(yàn)證計(jì)算正確性的全同態(tài)加密方案及其實(shí)現(xiàn)。文獻(xiàn)[56]公開了一種有效提高同態(tài)乘效率全同態(tài)密碼系統(tǒng)。文獻(xiàn)[57]公開了一種支持有理數(shù)運(yùn)算的同態(tài)加密方案。文獻(xiàn)[58]公開了一個(gè)包含密鑰交換、模交換和噪聲動(dòng)態(tài)管理的同態(tài)加密庫。文獻(xiàn)[59]公開了一種片上系統(tǒng)(System on Chip, SoC)的隱私保護(hù)驗(yàn)證方法，在驗(yàn)證時(shí)，參與驗(yàn)證的各方可以通過被加密的測(cè)試向量來驗(yàn)證IP核，以避免泄露不必要的信息。文獻(xiàn)[60]發(fā)明了用于讀取同態(tài)運(yùn)算指令的計(jì)算機(jī)可讀存儲(chǔ)器，實(shí)現(xiàn)了兩個(gè)終端之間的同態(tài)加密通信。

文獻(xiàn)[61]公開了一種基于同態(tài)加密算法的個(gè)人圖像安全檢索方法，在不泄露用戶檢索信息和數(shù)據(jù)的前提下，實(shí)現(xiàn)圖像的安全檢索。文獻(xiàn)[62]公開了一種云存儲(chǔ)中基于同態(tài)加密的密文檢索方法，保障了數(shù)據(jù)的隱私安全，同時(shí)使用樹形結(jié)構(gòu)來存儲(chǔ)提高密文檢索效率。文獻(xiàn)[63,64]分別公開了一種基于同態(tài)加密的密文檢索技術(shù)。文獻(xiàn)[65]公開了一種基于同態(tài)加密的線性SVM(Support Vector Machine)模型訓(xùn)練算法，得以在云上訓(xùn)練密文SVM模型，從而避免泄露訓(xùn)練數(shù)據(jù)等隱私信息。文獻(xiàn)[66]公開了一種基于全同態(tài)加密的生物特征認(rèn)證技術(shù)，允許在密文狀態(tài)下認(rèn)證生物特征，從而避免用戶信息泄露。當(dāng)前，同態(tài)加密已被應(yīng)用在機(jī)器學(xué)習(xí)隱私保護(hù)領(lǐng)域，較有代表性的是Gilad-bachrach等人[67]基于SEAL庫提出的隱私保護(hù)神經(jīng)網(wǎng)絡(luò)模型Cryptonets，已較好地適用于小型神經(jīng)網(wǎng)絡(luò)。

文獻(xiàn)[68]公開了一種基于加法同態(tài)的隱藏分散貸款額獲取貸款總和的方法，這是多方安全計(jì)算的一個(gè)應(yīng)用場(chǎng)景。文獻(xiàn)[69]公開了一種基于同態(tài)加密的多值打包方案。文獻(xiàn)[70]公開了一種基于全同態(tài)加密的雙方不經(jīng)意傳輸方案。文獻(xiàn)[71]公開了一種使用同態(tài)加密技術(shù)計(jì)算DNA編輯距離的方法，首先將DNA序列編碼為字符串，然后在密文域?qū)崿F(xiàn)兩字符串間編輯距離的計(jì)算。文獻(xiàn)[72]公開了一種基于同態(tài)加密的智能電網(wǎng)用戶售電方法，使用同態(tài)加密技術(shù)加密用戶的真實(shí)購電需求，結(jié)合身份認(rèn)證保護(hù)用戶的購電信息不被電力公司等獲取。文獻(xiàn)[73]基于同態(tài)加密技術(shù)公開了一種用于計(jì)算各分布式設(shè)備所貢獻(xiàn)計(jì)算量的方法。文獻(xiàn)[74]公開了一種基于同態(tài)加密技術(shù)生成條形碼的技術(shù)，可以在密文域中根據(jù)從服務(wù)器接收到的生成請(qǐng)求來生成對(duì)應(yīng)的標(biāo)識(shí)碼。文獻(xiàn)[75]公開了一種基于同態(tài)加密算法保護(hù)程序代碼的方案及其實(shí)現(xiàn)，以增加程序代碼安全性。文獻(xiàn)[76]公開了一種基于同態(tài)加密的通信技術(shù)，保障在通信過程中數(shù)據(jù)的計(jì)算安全和存儲(chǔ)安全。表4總結(jié)了近年來同態(tài)加密相關(guān)的知識(shí)產(chǎn)權(quán)所聚焦的不同領(lǐng)域。

表4 同態(tài)加密相關(guān)的知識(shí)產(chǎn)權(quán)聚焦的不同應(yīng)用領(lǐng)域

5 全同態(tài)加密庫對(duì)比分析

目前已經(jīng)有一些團(tuán)隊(duì)對(duì)FHE方案進(jìn)行了軟件實(shí)現(xiàn)，例如基于BGV方案的Helib、基于BFV方案的SEAL、基于GSW方案的TFHE等。下面分別分析Helib, SEAL和TFHE全同態(tài)加密庫的運(yùn)行效率。

2014年Brakerski等人[77]提出了BGV同態(tài)方案，使用模交換技術(shù)進(jìn)行噪聲管理，在不使用Bootstrapping的情況下構(gòu)造出了層次性全同態(tài)加密方案；2013年Halevi等人[78]公開了實(shí)現(xiàn)BGV方案的函數(shù)庫Helib，Helib是使用C++編寫的同態(tài)加密函數(shù)庫，著重聚焦使用SV密文封裝技術(shù)和GHS優(yōu)化算法[79]，2018年3月，IBM發(fā)布了新版本Helib同態(tài)加密庫，通過重線性化，使效率提升了15～75倍。使用i5-1.6 GHz處理器，內(nèi)存8 GB的Dell筆記本電腦進(jìn)行效率測(cè)試，表5為level=2時(shí)Helib的運(yùn)行效率，m表示模數(shù)。

表5 Test_Timing效率測(cè)試結(jié)果(μs)

Fan等人[80]于2012年提出了BFV同態(tài)方案，該方案可視為對(duì)Brakerski所提方案[81]的優(yōu)化，隨后微軟公開了基于BFV方案的同態(tài)加密庫SEAL。2016年Bajard等人[82]提出了一個(gè)BFV方案的RNS變體(Residue number systems)。2017年微軟發(fā)布SEAL2.3.0，使其可以支持Bajard等人的方案。2018年微軟發(fā)布SEAL3.0，使其支持Cheon等人提出的CKKS方案，可以實(shí)現(xiàn)實(shí)數(shù)域上的密文近似計(jì)算。2019年發(fā)布SEAL3.2，增加了對(duì).NET開發(fā)的完整支持，使.NET開發(fā)人員編寫同態(tài)加密應(yīng)用程序更為便捷。目前SEAL最新的版本為SEAL3.4。使用英特爾i5, 1.6 GHz處理器，8 GB內(nèi)存的Dell筆記本電腦分別測(cè)試SEAL3.4中BFV方案和CKKS方案在默認(rèn)參數(shù)下的運(yùn)行效率。BFV方案在默認(rèn)參數(shù)下的效率測(cè)試結(jié)果如表6所示，CKKS方案在默認(rèn)參數(shù)下的效率測(cè)試結(jié)果如表7所示。其中Poly,Coeff和Plain為方案的3個(gè)主要參數(shù)，不同參數(shù)會(huì)影響方案的安全性、效率以及可進(jìn)行同態(tài)運(yùn)算的次數(shù)。

Gentry等人[7]于2013年提出了GSW同態(tài)方案，旨在基于LWE問題構(gòu)造一個(gè)便于理解的、同態(tài)運(yùn)算形式更為純粹的FHE方案。基于GSW方案的同態(tài)加密庫TFHE在2017年公布。TFHE使用C++語言編寫，它可以運(yùn)算由邏輯門電路組成的任意布爾電路，函數(shù)庫支持對(duì)10種邏輯門電路的同態(tài)運(yùn)算，包括與門、或門、非門、異或門、與非門、或非門和多路選擇器等，每個(gè)門電路的單核運(yùn)算時(shí)間約為13 ms，每個(gè)選擇器花費(fèi)大約26 ms，TFHE庫與其他庫的區(qū)別是其Bootstrapping不受門電路數(shù)量和結(jié)構(gòu)的限制，這就意味著即使在運(yùn)算電路未提前得知的情況下，它也能夠?qū)崿F(xiàn)對(duì)任意電路的密文同態(tài)運(yùn)算。在ASIACRYPT2017中，Chillotti等人[83]針對(duì)TFHE提出了新的改進(jìn)思路，通過使用垂直和水平兩種密文封裝技術(shù)大幅提升了其運(yùn)行效率，并解決了門電路不可復(fù)合的問題。

表6 SEAL中BFV方案效率測(cè)試(μs)

表7 SEAL中CKKS方案效率測(cè)試(μs)

6 結(jié)束語

綜上可知，全同態(tài)加密技術(shù)歷經(jīng)十余年的發(fā)展，正逐步由理論層面步入應(yīng)用階段，阻礙全同態(tài)加密投入應(yīng)用的效率問題也在一定程度上得到解決，電子投票、密文數(shù)據(jù)庫、區(qū)塊鏈隱私保護(hù)以及機(jī)器學(xué)習(xí)隱私保護(hù)等多元化的應(yīng)用場(chǎng)景被相繼開發(fā)，同態(tài)加密技術(shù)在未來仍具有重要的研究和應(yīng)用價(jià)值。

同態(tài)加密技術(shù)未來的研究方向可以歸納為提高效率、提高安全性和應(yīng)用研究3個(gè)方面。在效率方面，目前的同態(tài)加密方案大部分都是基于公鑰密碼體制而構(gòu)建的，存在密鑰尺寸大、密文尺寸大的問題，不能滿足云上對(duì)海量數(shù)據(jù)進(jìn)行密文操作的要求，要實(shí)現(xiàn)云環(huán)境中密文的快速穩(wěn)定存儲(chǔ)、計(jì)算等應(yīng)用，一是可以進(jìn)一步提高非對(duì)稱FHE方案的效率，二是可以研究對(duì)稱同態(tài)加密算法。相比非對(duì)稱同態(tài)加密方案，對(duì)稱同態(tài)加密方案的計(jì)算復(fù)雜度要低得多，然而現(xiàn)行對(duì)稱同態(tài)加密方案仍存在實(shí)現(xiàn)效率低、密鑰管理復(fù)雜、在實(shí)際應(yīng)用中部署困難、存在安全漏洞等種種未解決的問題，仍需做進(jìn)一步的深入研究。在安全性方面，可驗(yàn)證同態(tài)加密可以保障使用同態(tài)加密技術(shù)時(shí)的數(shù)據(jù)完整性和可認(rèn)證性，目前實(shí)現(xiàn)同態(tài)加密可驗(yàn)證的同態(tài)簽名與同態(tài)MAC兩種均還處在起步階段?；诟裆侠щy問題或其他困難問題設(shè)計(jì)的抗量子計(jì)算攻擊的、高效的FHE方案目前是研究的主流，現(xiàn)有的大部分方案未考慮側(cè)信道攻擊(Side Channel Attacks, SCA)的影響，設(shè)計(jì)能夠有效抵抗SCA的FHE方案是研究的重要方向之一。在應(yīng)用方面，目前同態(tài)加密技術(shù)在安全多方計(jì)算、電子投票、機(jī)器學(xué)習(xí)和區(qū)塊鏈隱私保護(hù)等領(lǐng)域都得到了重要應(yīng)用，同態(tài)加密技術(shù)可以實(shí)現(xiàn)對(duì)數(shù)值型數(shù)據(jù)的同態(tài)運(yùn)算，然而對(duì)于邏輯運(yùn)算的處理有些無力，例如比較兩個(gè)密文的大小，而這類運(yùn)算在加密機(jī)器學(xué)習(xí)、密文檢索等應(yīng)用中都比較常見，尤其是隨著大數(shù)據(jù)的快速發(fā)展，密文檢索問題成為一個(gè)亟待解決的難題，設(shè)計(jì)基于同態(tài)加密的高效密文檢索方案、利用同態(tài)加密技術(shù)實(shí)現(xiàn)加密機(jī)器學(xué)習(xí)都具有重要的現(xiàn)實(shí)意義。