同態(tài)加密的發(fā)展及應用
2016-03-01 00:20:50鞏林明李順東郭奕
中興通訊技術 2016年1期
鞏林明 李順東 郭奕
摘要：認為密碼學中的同態(tài)加密技術可以為分布式計算環(huán)境的用戶隱私保護提供強有力的技術支撐。同態(tài)加密方案被分成3種類型：部分同態(tài)加密、淺同態(tài)加密和全同態(tài)加密。同態(tài)加密方案在分布式計算環(huán)境下的密文數(shù)據(jù)計算方面有著重要的應用，包括：安全云計算與委托計算、遠程文件存儲、密文檢索等。指出目前全同態(tài)加密方案的構造還處于理論階段，尚不能用于實際的密態(tài)數(shù)據(jù)計算問題，如何設計基于代數(shù)系統(tǒng)的（自然）全同態(tài)加密方案依然是未來研究的重點。
關鍵詞：同態(tài)加密；密態(tài)計算；安全多方計算；安全云計算；分布式計算
Rivest、Adleman和Dertouzos[1]于1978年提出了秘密同態(tài)的思想：對幾個數(shù)據(jù)的加密結果進行運算后再解密，得到的結果與這些數(shù)據(jù)未加密時執(zhí)行某一運算所得的結果一致。此后，研究人員在同態(tài)加密方案設計方面做了大量的工作并取得了大量的研究成果。例如，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]兩人提出的基于誤差學習的FHE方案、2012年由Brakerski和 Gentry[10]等提出的無需電路自舉的分層FHE方案、同年由Brakerski[11]提出的無需模轉換的FHE方案、2013年由Gentry[12]等提出的環(huán)上的FHE方案、2014年由Brakerski[13]等提出的基于標準誤差學習的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)絡技術的發(fā)展，以同態(tài)加密技術為支撐的密文數(shù)據(jù)計算越來越多地被應用于各種分布式計算中，例如，安全云計算與安全云存儲中有關用戶隱私的保護和高效的安全多方計算協(xié)議，都需要同態(tài)加密技術支持；其他應用如電子選舉、遠程文件存儲、密文檢索、版權保護等也都需要同態(tài)技術的支持。
1 同態(tài)加密系統(tǒng)中的一些定義
（1）同態(tài)性
假設一個加密系統(tǒng)的加密函數(shù)與解密函數(shù)分別為[E：?→C]與[D：C→?]，其中[?]與[C]分別為明文空間與密文空間；令[?]和[?]分別為定義在明文空間和密文空間上的代數(shù)運算或算術運算。則加密方案的同態(tài)性定義為：給定任意的兩個[m1，m2∈?]，如果一個加密系統(tǒng)的加密函數(shù)與解密函數(shù)滿足代數(shù)關系[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ù)（或算術）同態(tài)運算的加密系統(tǒng)，被稱作部分同態(tài)加密系統(tǒng)；同時滿足加法和乘法同態(tài)運算，且只能進行有限次乘法或加法運算的加密系統(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ù)或算術運算分為乘法同態(tài)、加同態(tài)和異或同態(tài)3種類型。下面從幾個著名的同態(tài)加密方案的優(yōu)缺點入手，總結一下乘法同態(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ù)困難假設設計了ElGamal加密算法，該加密方案同樣具有乘法同態(tài)性，并且滿足選擇明文不可區(qū)分（IND-CPA） 安全。
（2）加法同態(tài)加密方案。加法同態(tài)加密方案的同態(tài)性表現(xiàn)為[m1+m2=D（E（m1）?E（m2））] （[?]為定義在密文空間上的某種代數(shù)運算或算術運算）。 具有加法同態(tài)性的加密方案有很多，應用最為廣泛的當屬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ù)運算或算術運算）。目前，只有Goldwasser-Micali [15]加密系統(tǒng)屬于該類同態(tài)加密系統(tǒng)，該加密系統(tǒng)基于二次剩余困難問題，雖具有IND-CPA安全，但每次只能加密單比特，因此加密效率會比較低。
2.2 淺同態(tài)加密方案
淺同態(tài)加密方案能同時進行有限次乘法和加法運算的加密。從某種程度上講，該類型的加密方案是人們在研究解決RSA 3個人提出的公開問題（如何設計全同態(tài)加密方案）的過程中，出現(xiàn)的“副產(chǎn)品”。1999—2005年間出現(xiàn)了不少淺同態(tài)加密方案，例如文獻[6]、[16-18]中提到的方案。目前最為著名的淺同態(tài)加密方案當屬Boneh[5]等基于理想成員判定困難假設設計的加密方案。該方案能執(zhí)行一次乘法和若干次加法運算，Boneh [5]等雖然用它成功解決了2DNF問題，但是該方案在解密時需要搜索解密，因此基于此方案的2DNF保密計算協(xié)議效率很低。
雖然此類加密系統(tǒng)為實現(xiàn)全同態(tài)加密方案的設計奠定了一定的基礎，但是只能用于解決某些專門的問題，即能夠解決的應用問題有限，很難將其拓展并且應用于解決更廣泛的問題。
2.3 全同態(tài)加密方案
2009年Gentry[7]設計了首個全同態(tài)加密方案，這一里程碑事件激起了全同態(tài)研究的熱潮。到目前，全同態(tài)加密方案按照構造思想大致可以分為以下3代。
（1）以Gentry[7]設計方案為代表的、基于格上困難問題構造的第1代全同態(tài)加密方案，這類方案的設計思想大致如下：
·設計一個能夠執(zhí)行低次多項式運算的淺同態(tài)加密算法。
·控制密文噪聲增長，即依據(jù)稀疏子集和問題對解密電路執(zhí)行“壓縮”操作，然后再執(zhí)行自己的解密函數(shù)實現(xiàn)同態(tài)解密，從而能夠達到降噪的目的。
·依據(jù)循環(huán)安全假設（即假定用方案的公鑰加密自身密鑰作為公鑰是安全的）實現(xiàn)純的全同態(tài)加密。
（2）以Brakerski-Vaikuntanathan [9]為代表的、基于帶誤差學習或環(huán)上帶誤差學習困難問題構造的第2代全同態(tài)加密方案，該類方案的構造思想大致如下：
·歸約的基礎是誤差學習或環(huán)上帶誤差學習困難問題。
·用向量表示密鑰與密文。
·用密鑰交換技術來約減密文的膨脹維數(shù)，以達到降噪目的。
該類方案的優(yōu)點是不再需要電路自舉技術，突破了Gentry的設計框架，在效率方面實現(xiàn)了很大的提升；其缺點是在使用密鑰交換技術時需要增加大量用于密鑰交換的矩陣，從而導致公鑰長度的增長。
（3）以Gentry-Sahai-Waters [12]為代表的、基于帶誤差學習或環(huán)上帶誤差學習困難問題構造的第3代全同態(tài)加密方案，此類方案的構造思想大致如下：
·方案的安全性最終歸約到帶誤差學習或環(huán)上帶誤差學習的困難問題上。
·使用近似向量方法表示私鑰，即用戶的私鑰實際就是密文的近似特征向量。
·密文的同態(tài)計算使用的是矩陣的乘法與加法運算。
這類方案被認為是目前最為理想的方案，它們不再需要密鑰交換與模轉換技術。
3 同態(tài)加密的應用
同態(tài)加密技術在分布式計算環(huán)境下的密文數(shù)據(jù)計算方面有著廣泛而重要的應用。
（1）安全云計算與委托計算。同態(tài)技術在該方面的應用可以使得我們在云環(huán)境下，充分利用云服務器的計算能力，實現(xiàn)對明文信息的運算，而不會有損私有數(shù)據(jù)的私密性。例如醫(yī)療機構通常擁有比較弱的數(shù)據(jù)處理能力，而需要第三方來實現(xiàn)數(shù)據(jù)處理分析以達到更好的醫(yī)療效果或者科研水平，這樣他們就需要委托有較強數(shù)據(jù)處理能力的第三方實現(xiàn)數(shù)據(jù)處理（云計算中心），但是醫(yī)院負有保護患者隱私的義務，不能直接將數(shù)據(jù)交給第三方。在同態(tài)加密技術的支持下，醫(yī)療機構就可以將加密后的數(shù)據(jù)發(fā)送至第三方，待第三方處理完成后便可返回給醫(yī)療結構。整個數(shù)據(jù)處理過程、數(shù)據(jù)內(nèi)容對第三方是完全透明的。
（2）遠程文件存儲。用戶可以將自己的數(shù)據(jù)加密后存儲在一個不信任的遠程服務器上，日后可以向遠程服務器查詢自己所需要的信息，遠程服務器用該用戶的公鑰將查詢結果加密，用戶可以解密得到自己需要的信息，而遠程服務器卻對查詢信息一無所知。這樣做還可以實現(xiàn)遠程用戶數(shù)據(jù)容災。
（3）密文檢索。密文檢索有很多方案，例如文獻[7]、[19-20]中介紹的就是基于同態(tài)加密技術設計的密文檢索算法。我們僅介紹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]用于計算輸出的第
（4）安全多方計算協(xié)議設計的工具。所謂安全多方計算就是分別持有私有數(shù)據(jù)[x1，x2，…，xn]的[n]個人，在分布式環(huán)境中協(xié)同計算函數(shù)[f（x1，x2，…，xn）]而不泄露各方的私有數(shù)據(jù)。以同態(tài)技術支撐的密態(tài)數(shù)據(jù)計算不僅可以滿足安全多方計算協(xié)議設計中保護各方隱私的需要，還能避開不經(jīng)意傳輸協(xié)議而大大提升協(xié)議效率。近些年來，出現(xiàn)了很多高效的基于同態(tài)加密的安全多方計算協(xié)議，例如文獻[6]、[21]。同態(tài)加密技術已經(jīng)成為安全多方計算協(xié)議設計的一個強有力的工具[22]。
（5）電子選舉。基于同態(tài)加密技術設計的電子選舉方案，因在計票快捷與準確、節(jié)省人力與開支、投票的易用性等方面較傳統(tǒng)投票方式有著無法企及的優(yōu)越性，越來越受到人們的青睞。目前出現(xiàn)了很多基于同態(tài)的電子選舉方案，像文獻[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）其他方面的應用。同態(tài)加密技術在其他方面也有諸多應用，例如多方零知識證明、軟件保護、聚合（同態(tài)）簽名等。
4 同態(tài)技術存在的問題
綜上所述，目前同態(tài)技術及其應用方面還存在以下幾個重點問題需要我們進一步研究。
（1）只能實現(xiàn)單比特加密，如何高效地實現(xiàn)全同態(tài)加密有待進一步研究。
（2）大多基于未論證的困難問題，尋找可論證的困難問題依然是個擺在密碼工作者面前的難題。
（3）大多只能達到IND-CPA安全，偶有能達到IND-CCA1安全，但還未見能達到IND-CCA2安全的，同態(tài)加密系統(tǒng)的安全性研究有待進一步提高。
（4）需要額外的消除噪音算法，依然不是自然同態(tài)，如何設計一個具有自然同態(tài)性的全同態(tài)加密方案依然是一個開問題。
（5）在安全云計算、安全多方計算、密態(tài)數(shù)據(jù)計算等領域的應用還處在初級階段，有待于進一步地拓展；同時，在其他領域的相關應用也需要積極開拓。
5 結束語
隨著分布式計算的普及，如何保護分布式計算環(huán)境下的用戶隱私已經(jīng)成為一個重要問題，密碼學中的同態(tài)加密技術可以為分布式計算環(huán)境的用戶隱私保護提供強有力的技術支撐。文章介紹了同態(tài)加密技術的研究現(xiàn)狀及研究展望，并簡單介紹了基于同態(tài)加密技術的密態(tài)數(shù)據(jù)計算在分布式計算中的各種應用。目前，同態(tài)加密方案在安全性方面大都只能達到IND-CPA安全，如何設計更高安全級別的同態(tài)加密方案依然需要進一步研究。全同態(tài)加密方案的構造還處于理論階段，尚不能用于實際的密態(tài)數(shù)據(jù)計算問題，如何設計基于代數(shù)系統(tǒng)的（自然）全同態(tài)加密方案依然是未來研究的重點。同態(tài)加密技術支撐的密態(tài)數(shù)據(jù)計算在其他領域的應用有待進一步拓展。
參考文獻
[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]. 電子學報， 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
