同態(tài)加密的發(fā)展及應(yīng)用

鞏林明　李順東　郭奕

摘要：認(rèn)為密碼學(xué)中的同態(tài)加密技術(shù)可以為分布式計算環(huán)境的用戶隱私保護(hù)提供強有力的技術(shù)支撐。同態(tài)加密方案被分成3種類型：部分同態(tài)加密、淺同態(tài)加密和全同態(tài)加密。同態(tài)加密方案在分布式計算環(huán)境下的密文數(shù)據(jù)計算方面有著重要的應(yīng)用，包括：安全云計算與委托計算、遠(yuǎn)程文件存儲、密文檢索等。指出目前全同態(tài)加密方案的構(gòu)造還處于理論階段，尚不能用于實際的密態(tài)數(shù)據(jù)計算問題，如何設(shè)計基于代數(shù)系統(tǒng)的（自然）全同態(tài)加密方案依然是未來研究的重點。

關(guān)鍵詞：同態(tài)加密；密態(tài)計算；安全多方計算；安全云計算；分布式計算

Rivest、Adleman和Dertouzos[1]于1978年提出了秘密同態(tài)的思想：對幾個數(shù)據(jù)的加密結(jié)果進(jìn)行運算后再解密，得到的結(jié)果與這些數(shù)據(jù)未加密時執(zhí)行某一運算所得的結(jié)果一致。此后，研究人員在同態(tài)加密方案設(shè)計方面做了大量的工作并取得了大量的研究成果。例如，1978年由Rivest、Adleman和Dertouzos[2]提出的RSA加密系統(tǒng)、1985年由ElGmal提出的ElGmal加密方案[3]、1998年由Okamoto和Uchiyama[4] 提出的《A new public-key cryptosystem as secure as factoring》、1999年由Paillier[5]提出的Paillier加密方案、2002年由Domingo-Ferrer提出的《A provably secure additive and multiplicative privacy homomorphism》、2005年由Boneh [6]等提出的用于保密計算2-析取范式（2DNF）的加密方案、2009年由Gentry等[7]首次提出的全同態(tài)加密 （FHE）方案、2010年Dijk[8]等提出的整數(shù)域上的FHE方案、2011年由Brakerski、Vaikuntanathan[9]兩人提出的基于誤差學(xué)習(xí)的FHE方案、2012年由Brakerski和 Gentry[10]等提出的無需電路自舉的分層FHE方案、同年由Brakerski[11]提出的無需模轉(zhuǎn)換的FHE方案、2013年由Gentry[12]等提出的環(huán)上的FHE方案、2014年由Brakerski[13]等提出的基于標(biāo)準(zhǔn)誤差學(xué)習(xí)的FHE方案、2015年由Cheon[14]等提出的基于中國剩余定理的整數(shù)域上的FHE方案等都是比較著名的同態(tài)加密成果。

目前出現(xiàn)的同態(tài)加密方案可被分成3種類型：部分同態(tài)加密、淺同態(tài)加密和全同態(tài)加密。部分同態(tài)只能實現(xiàn)某一種代數(shù)運算（或、乘、加）；淺同態(tài)能同時實現(xiàn)有限次的加運算和乘運算；全同態(tài)能實現(xiàn)任意次的加運算和乘運算。

同態(tài)加密方案，除了可以實現(xiàn)加密功能外，還可以用于密文數(shù)據(jù)的計算。近些年來隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，以同態(tài)加密技術(shù)為支撐的密文數(shù)據(jù)計算越來越多地被應(yīng)用于各種分布式計算中，例如，安全云計算與安全云存儲中有關(guān)用戶隱私的保護(hù)和高效的安全多方計算協(xié)議，都需要同態(tài)加密技術(shù)支持；其他應(yīng)用如電子選舉、遠(yuǎn)程文件存儲、密文檢索、版權(quán)保護(hù)等也都需要同態(tài)技術(shù)的支持。

1 同態(tài)加密系統(tǒng)中的一些定義

（1）同態(tài)性

假設(shè)一個加密系統(tǒng)的加密函數(shù)與解密函數(shù)分別為[E：?→C]與[D：C→?]，其中[?]與[C]分別為明文空間與密文空間；令[?]和[?]分別為定義在明文空間和密文空間上的代數(shù)運算或算術(shù)運算。則加密方案的同態(tài)性定義為：給定任意的兩個[m1，m2∈?]，如果一個加密系統(tǒng)的加密函數(shù)與解密函數(shù)滿足代數(shù)關(guān)系[m1?m2=D（E（m1）?E（m2））]（或[E（m1?m2）=E（m1）?E（m2）]），則稱該加密系統(tǒng)具有同態(tài)性。

（2）加法、乘法、異或同態(tài)

一個具有同態(tài)性的加密系統(tǒng)，若明文空間上的運算為代數(shù)加法“+”，則該加密系統(tǒng)被稱為加法同態(tài)加密系統(tǒng)；若明文空間上的運算為代數(shù)乘法“[?]”，則該加密系統(tǒng)被稱為乘法同態(tài)加密系統(tǒng)；若明文空間上的運算為算數(shù)異或“[⊕]”，則該加密系統(tǒng)被稱為異或同態(tài)加密系統(tǒng)。

（3）淺同態(tài)與全同態(tài)

只滿足一種代數(shù)（或算術(shù)）同態(tài)運算的加密系統(tǒng)，被稱作部分同態(tài)加密系統(tǒng)；同時滿足加法和乘法同態(tài)運算，且只能進(jìn)行有限次乘法或加法運算的加密系統(tǒng)稱為淺同態(tài)加密系統(tǒng)；同時滿足加法和乘法同態(tài)的加密系統(tǒng)稱為全同態(tài)加密系統(tǒng)。

2 同態(tài)加密的發(fā)展

同態(tài)加密思想從提出到現(xiàn)在，在具體實現(xiàn)方案方面，經(jīng)歷了3個重要時期：1978—1999年是部分同態(tài)加密的繁榮發(fā)展時期；1996—2009年是部分同態(tài)加密與淺同態(tài)加密的交織發(fā)展時期，也是淺同態(tài)加密方案的繁榮發(fā)展時期；2009年以后是全同態(tài)加密的繁榮發(fā)展時期。下面將以時間為主線，按照同態(tài)加密方案的類型介紹同態(tài)加密的發(fā)展。

2.1 部分同態(tài)加密方案

部分同態(tài)加密方案按照明文空間上能實現(xiàn)的代數(shù)或算術(shù)運算分為乘法同態(tài)、加同態(tài)和異或同態(tài)3種類型。下面從幾個著名的同態(tài)加密方案的優(yōu)缺點入手，總結(jié)一下乘法同態(tài)、加同態(tài)、或同態(tài)加密方案的特性。

（1）乘法同態(tài)加密方案。乘法同態(tài)加密方案的同態(tài)性表現(xiàn)為[m1×m2=D（E（m1）×E（m2））]。 RSA [5]是最早的具有乘法同態(tài)性的加密方案，它是基于因子分解困難問題的，屬于確定性加密，不能抵御選擇明文攻擊；1985年，ElGamal [3]基于有限域上的離散對數(shù)困難假設(shè)設(shè)計了ElGamal加密算法，該加密方案同樣具有乘法同態(tài)性，并且滿足選擇明文不可區(qū)分（IND-CPA） 安全。

（2）加法同態(tài)加密方案。加法同態(tài)加密方案的同態(tài)性表現(xiàn)為[m1+m2=D（E（m1）?E（m2））] （[?]為定義在密文空間上的某種代數(shù)運算或算術(shù)運算）。 具有加法同態(tài)性的加密方案有很多，應(yīng)用最為廣泛的當(dāng)屬Paillier [5]加密系統(tǒng)，該加密系統(tǒng)基于高階合數(shù)度剩余類困難問題，且具有IND-CPA安全。

（3）異或同態(tài)加密方案。乘法同態(tài)加密方案的同態(tài)性表現(xiàn)為[m1⊕m2=D（E（m1）?E（m2））]（[?]為定義在密文空間上的某種代數(shù)運算或算術(shù)運算）。目前，只有Goldwasser-Micali [15]加密系統(tǒng)屬于該類同態(tài)加密系統(tǒng)，該加密系統(tǒng)基于二次剩余困難問題，雖具有IND-CPA安全，但每次只能加密單比特，因此加密效率會比較低。

2.2 淺同態(tài)加密方案

淺同態(tài)加密方案能同時進(jìn)行有限次乘法和加法運算的加密。從某種程度上講，該類型的加密方案是人們在研究解決RSA 3個人提出的公開問題（如何設(shè)計全同態(tài)加密方案）的過程中，出現(xiàn)的“副產(chǎn)品”。1999—2005年間出現(xiàn)了不少淺同態(tài)加密方案，例如文獻(xiàn)[6]、[16-18]中提到的方案。目前最為著名的淺同態(tài)加密方案當(dāng)屬Boneh[5]等基于理想成員判定困難假設(shè)設(shè)計的加密方案。該方案能執(zhí)行一次乘法和若干次加法運算，Boneh [5]等雖然用它成功解決了2DNF問題，但是該方案在解密時需要搜索解密，因此基于此方案的2DNF保密計算協(xié)議效率很低。

雖然此類加密系統(tǒng)為實現(xiàn)全同態(tài)加密方案的設(shè)計奠定了一定的基礎(chǔ)，但是只能用于解決某些專門的問題，即能夠解決的應(yīng)用問題有限，很難將其拓展并且應(yīng)用于解決更廣泛的問題。

2.3 全同態(tài)加密方案

2009年Gentry[7]設(shè)計了首個全同態(tài)加密方案，這一里程碑事件激起了全同態(tài)研究的熱潮。到目前，全同態(tài)加密方案按照構(gòu)造思想大致可以分為以下3代。

（1）以Gentry[7]設(shè)計方案為代表的、基于格上困難問題構(gòu)造的第1代全同態(tài)加密方案，這類方案的設(shè)計思想大致如下：

·設(shè)計一個能夠執(zhí)行低次多項式運算的淺同態(tài)加密算法。

·控制密文噪聲增長，即依據(jù)稀疏子集和問題對解密電路執(zhí)行“壓縮”操作，然后再執(zhí)行自己的解密函數(shù)實現(xiàn)同態(tài)解密，從而能夠達(dá)到降噪的目的。

·依據(jù)循環(huán)安全假設(shè)（即假定用方案的公鑰加密自身密鑰作為公鑰是安全的）實現(xiàn)純的全同態(tài)加密。

（2）以Brakerski-Vaikuntanathan [9]為代表的、基于帶誤差學(xué)習(xí)或環(huán)上帶誤差學(xué)習(xí)困難問題構(gòu)造的第2代全同態(tài)加密方案，該類方案的構(gòu)造思想大致如下：

·歸約的基礎(chǔ)是誤差學(xué)習(xí)或環(huán)上帶誤差學(xué)習(xí)困難問題。

·用向量表示密鑰與密文。

·用密鑰交換技術(shù)來約減密文的膨脹維數(shù)，以達(dá)到降噪目的。

該類方案的優(yōu)點是不再需要電路自舉技術(shù)，突破了Gentry的設(shè)計框架，在效率方面實現(xiàn)了很大的提升；其缺點是在使用密鑰交換技術(shù)時需要增加大量用于密鑰交換的矩陣，從而導(dǎo)致公鑰長度的增長。

（3）以Gentry-Sahai-Waters [12]為代表的、基于帶誤差學(xué)習(xí)或環(huán)上帶誤差學(xué)習(xí)困難問題構(gòu)造的第3代全同態(tài)加密方案，此類方案的構(gòu)造思想大致如下：

·方案的安全性最終歸約到帶誤差學(xué)習(xí)或環(huán)上帶誤差學(xué)習(xí)的困難問題上。

·使用近似向量方法表示私鑰，即用戶的私鑰實際就是密文的近似特征向量。

·密文的同態(tài)計算使用的是矩陣的乘法與加法運算。

這類方案被認(rèn)為是目前最為理想的方案，它們不再需要密鑰交換與模轉(zhuǎn)換技術(shù)。

3 同態(tài)加密的應(yīng)用

同態(tài)加密技術(shù)在分布式計算環(huán)境下的密文數(shù)據(jù)計算方面有著廣泛而重要的應(yīng)用。

（1）安全云計算與委托計算。同態(tài)技術(shù)在該方面的應(yīng)用可以使得我們在云環(huán)境下，充分利用云服務(wù)器的計算能力，實現(xiàn)對明文信息的運算，而不會有損私有數(shù)據(jù)的私密性。例如醫(yī)療機構(gòu)通常擁有比較弱的數(shù)據(jù)處理能力，而需要第三方來實現(xiàn)數(shù)據(jù)處理分析以達(dá)到更好的醫(yī)療效果或者科研水平，這樣他們就需要委托有較強數(shù)據(jù)處理能力的第三方實現(xiàn)數(shù)據(jù)處理（云計算中心），但是醫(yī)院負(fù)有保護(hù)患者隱私的義務(wù)，不能直接將數(shù)據(jù)交給第三方。在同態(tài)加密技術(shù)的支持下，醫(yī)療機構(gòu)就可以將加密后的數(shù)據(jù)發(fā)送至第三方，待第三方處理完成后便可返回給醫(yī)療結(jié)構(gòu)。整個數(shù)據(jù)處理過程、數(shù)據(jù)內(nèi)容對第三方是完全透明的。

（2）遠(yuǎn)程文件存儲。用戶可以將自己的數(shù)據(jù)加密后存儲在一個不信任的遠(yuǎn)程服務(wù)器上，日后可以向遠(yuǎn)程服務(wù)器查詢自己所需要的信息，遠(yuǎn)程服務(wù)器用該用戶的公鑰將查詢結(jié)果加密，用戶可以解密得到自己需要的信息，而遠(yuǎn)程服務(wù)器卻對查詢信息一無所知。這樣做還可以實現(xiàn)遠(yuǎn)程用戶數(shù)據(jù)容災(zāi)。

（3）密文檢索。密文檢索有很多方案，例如文獻(xiàn)[7]、[19-20]中介紹的就是基于同態(tài)加密技術(shù)設(shè)計的密文檢索算法。我們僅介紹Gentry [7]用全同態(tài)加密方案實現(xiàn)密文檢索算法： 用戶將要檢索的內(nèi)容[f1，f2，…，fn]用公鑰加密成密文[c1，c2，…，cn]。將搜索引擎的查詢函數(shù)置為電路C，則搜素引擎就可以利用全同態(tài)算法中的[Evaluate]函數(shù)執(zhí)行同態(tài)運算：

[CΣ=Evaluate（pk，Ci，（c1，c2，…，cn））]（1）

其中[Ci∈C]用于計算輸出的第比特。當(dāng)服務(wù)器將[CΣ]返給用戶時，用戶用自己的私鑰解密[CΣ]即得到自己要檢索的內(nèi)容，而搜索引擎服務(wù)器卻對用戶要檢索的內(nèi)容一無所知。

（4）安全多方計算協(xié)議設(shè)計的工具。所謂安全多方計算就是分別持有私有數(shù)據(jù)[x1，x2，…，xn]的[n]個人，在分布式環(huán)境中協(xié)同計算函數(shù)[f（x1，x2，…，xn）]而不泄露各方的私有數(shù)據(jù)。以同態(tài)技術(shù)支撐的密態(tài)數(shù)據(jù)計算不僅可以滿足安全多方計算協(xié)議設(shè)計中保護(hù)各方隱私的需要，還能避開不經(jīng)意傳輸協(xié)議而大大提升協(xié)議效率。近些年來，出現(xiàn)了很多高效的基于同態(tài)加密的安全多方計算協(xié)議，例如文獻(xiàn)[6]、[21]。同態(tài)加密技術(shù)已經(jīng)成為安全多方計算協(xié)議設(shè)計的一個強有力的工具[22]。

（5）電子選舉。基于同態(tài)加密技術(shù)設(shè)計的電子選舉方案，因在計票快捷與準(zhǔn)確、節(jié)省人力與開支、投票的易用性等方面較傳統(tǒng)投票方式有著無法企及的優(yōu)越性，越來越受到人們的青睞。目前出現(xiàn)了很多基于同態(tài)的電子選舉方案，像文獻(xiàn)[23-24]中介紹的都是基于同態(tài)的電子選舉方案。在此描述一下Damg?rd [23]方案：選民將自己的選票[vi∈{0，1}]加密[ci=Enc（vi）]，選票中心統(tǒng)計部門（擁有密鑰且可信）利用同態(tài)加密方案的同態(tài)性統(tǒng)計計算選票數(shù)[V=Dec（c1×c2×…cn）=v1+v2+…+vn]。

（6）其他方面的應(yīng)用。同態(tài)加密技術(shù)在其他方面也有諸多應(yīng)用，例如多方零知識證明、軟件保護(hù)、聚合（同態(tài)）簽名等。

4 同態(tài)技術(shù)存在的問題

綜上所述，目前同態(tài)技術(shù)及其應(yīng)用方面還存在以下幾個重點問題需要我們進(jìn)一步研究。

（1）只能實現(xiàn)單比特加密，如何高效地實現(xiàn)全同態(tài)加密有待進(jìn)一步研究。

（2）大多基于未論證的困難問題，尋找可論證的困難問題依然是個擺在密碼工作者面前的難題。

（3）大多只能達(dá)到IND-CPA安全，偶有能達(dá)到IND-CCA1安全，但還未見能達(dá)到IND-CCA2安全的，同態(tài)加密系統(tǒng)的安全性研究有待進(jìn)一步提高。

（4）需要額外的消除噪音算法，依然不是自然同態(tài)，如何設(shè)計一個具有自然同態(tài)性的全同態(tài)加密方案依然是一個開問題。

（5）在安全云計算、安全多方計算、密態(tài)數(shù)據(jù)計算等領(lǐng)域的應(yīng)用還處在初級階段，有待于進(jìn)一步地拓展；同時，在其他領(lǐng)域的相關(guān)應(yīng)用也需要積極開拓。

5 結(jié)束語

隨著分布式計算的普及，如何保護(hù)分布式計算環(huán)境下的用戶隱私已經(jīng)成為一個重要問題，密碼學(xué)中的同態(tài)加密技術(shù)可以為分布式計算環(huán)境的用戶隱私保護(hù)提供強有力的技術(shù)支撐。文章介紹了同態(tài)加密技術(shù)的研究現(xiàn)狀及研究展望，并簡單介紹了基于同態(tài)加密技術(shù)的密態(tài)數(shù)據(jù)計算在分布式計算中的各種應(yīng)用。目前，同態(tài)加密方案在安全性方面大都只能達(dá)到IND-CPA安全，如何設(shè)計更高安全級別的同態(tài)加密方案依然需要進(jìn)一步研究。全同態(tài)加密方案的構(gòu)造還處于理論階段，尚不能用于實際的密態(tài)數(shù)據(jù)計算問題，如何設(shè)計基于代數(shù)系統(tǒng)的（自然）全同態(tài)加密方案依然是未來研究的重點。同態(tài)加密技術(shù)支撐的密態(tài)數(shù)據(jù)計算在其他領(lǐng)域的應(yīng)用有待進(jìn)一步拓展。

參考文獻(xiàn)

[1] RIVEST R L， ADLEMAN L， DDRTOUZOS M L. On Data Banks and Privacy Homomorphisms [J]. Foundations of secure computation， 1978， 4（11）： 169-180

[2] RIVEST R L， SHAMIR A， ADLEMAN L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems [J]. Communications of the ACM， 1978， 21（2）： 120-126. doi： 10.1145/359340.359342

[3] ELGAMAL T. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms [M]. Advances in cryptology. Germany： Springer Berlin Heidelberg， 1985： 10-18. doi： 10.1007/3-540-39568-7_2

[4] OKAMOTO T， UCHIYAMA S. A New Public-Key Cryptosystem as Secure as Factoring [M]. Advances in Cryptology—EUROCRYPT'98. Germany： Springer Berlin Heidelberg， 1998： 308-318. doi： 10.1007/BFb0054135

[5] PAILLER P. Public-Key Cryptosystems Based on Composite Degree Residuosity Classes [M]. Advances in Cryptology—EUROCRYPT99. Germany： Springer Berlin Heidelberg， 1999： 223-238. doi： 10.1007/3-540-48910-X_16

[6] BONEH D， GOH E J， NISSIM K. Evaluating 2-DNF Formulas on Ciphertexts [M]. Theory of Cryptography. Germany： Springer Berlin Heidelberg， 2005： 325-341.doi： 10.1007/978-3-540-30576-7_18

[7] GENTRY C. Fully Homomorphic Encryption Using Ideal Lattices[C]//Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing， 2009： 169-178. doi： 10.1145/1536414.1536440

[8] VAN D M， GENTRY C， HALEVI S， et al. Fully Homomorphic Encryption Over the Integers[M].Advances in Cryptology-EUROCRYPT 2010. Germany： Springer Berlin Heidelberg， 2010： 24-43

[9] BRAKERSKI Z， VALIKUNTANATHAN V. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages [M]. Advances in Cryptology-CRYPTO 2011. Germany： Springer Berlin Heidelberg， 2011： 505-524

[10] BRAKERSKI Z， GENTRY C， VAIKUNTANATHAN V. （Leveled） Fully Homomorphic Encryption without Bootstrapping [C]//Proceedings of the 3rd Innovations in Theoretical Computer Science Conference， 2012： 309-325.doi： 10.1145/2090236.2090262

[11] BRAKERSKI Z. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP [M]. Advances in Cryptology-CRYPTO 2012. Germany： Springer Berlin Heidelberg， 2012： 868-886. doi： 10.1007/978-3-642-32009-5_50

[12] GARG S， GENTRY C， HALEVI S， et al. Attribute-Based Encryption for Circuits from Multilinear Maps[M]. Advances in Cryptology-CRYPTO 2013. Germany： Springer Berlin Heidelberg， 2013： 479-499. doi： 10.1007/978-3-642-40084-1_27

[13] BRAKERSKI Z， VALIKUNTANATHAN V. Efficient Fully Homomorphic Encryption from （standard） LWE [J]. SIAM Journal on Computing， 2014， 43（2）： 831-871

[14] CHEON J H， KIM J， LEE M S， et al. CRT-Based Fully Homomorphic Encryption over the Integers[J]. Information Sciences， 2015， 310： 149-162

[15] GOLDWASSER S， MICALI S. Probabilistic Encryption [J]. Journal of computer and system sciences， 1984， 28（2）： 270-299

[16] I FERRER J D. A New Privacy Homomorphism and Applications[J]. Information Processing Letters， 1996， 60（5）： 277-282. doi： 10.1016/S0020-0190（96）00170-6

[17] DOMINGO-FERRER J. A Provably Secure Additive and Multiplicative Privacy Homomorphism*[M]. Information security. Germany： Springer Berlin Heidelberg， 2002： 471-483

[18] MELCHOR C A， GABORIT P， HERRANZ J. Additively Homomorphic Encryption with D-Operand Multiplications [M]. Advances in Cryptology-CRYPTO 2010. Germany： Springer Berlin Heidelberg， 2010： 138-154.doi： 10.1007/978-3-642-14623-7_8

[19] LI J， WANG Q， WANG C， et al. Fuzzy Keyword Search over Encrypted Data in Cloud Computing[C]//INFOCOM， 2010 Proceedings IEEE， 2010： 1-5

[20] HU H， XU J， REN C， et al. Processing Private Queries Over Untrusted Data Cloud Through Privacy Homomorphism[C]// 2011 IEEE 27th International Conference on Data Engineering （ICDE）， 2011： 601-612

[21] 李順東， 王道順. 基于同態(tài)加密的高效多方保密計算[J]. 電子學(xué)報， 2013， 41（4）： 798-803

[22] BENDLIN R， DAMGARD I， ORLANDI C， et al. Semi-Homomorphic Encryption and Multiparty Computation[M]. Advances in Cryptology-EUROCRYPT 2011. Germany： Springer Berlin Heidelberg， 2011： 169-188

[23] CRAMER R， GENNARO R， SCHOENMAKERS B. A Secure and Optimally Efficient Multi-Authority Election Scheme [J]. European Transactions on Telecommunications， 1997， 8（5）： 481-490

[24] DAMGARD I， JURIK M. A Generalisation， a Simplication and Some Applications of Paillier's Probabilistic Public-Key System[C]//Public Key Cryptography. Springer Berlin Heidelberg， 2001： 119-136.doi： 10.1007/3-540-44586-2_9