幾種重要FHE加密結構的深入研究與分析*

馬　飛，李　娟

(1．北方民族大學 計算機科學與工程學院， 寧夏 銀川 750021;2．合肥工業大學 計算機與信息學院，安徽 合肥 230009)

?

幾種重要FHE加密結構的深入研究與分析*

馬飛1,2，李娟1

(1．北方民族大學 計算機科學與工程學院， 寧夏 銀川 750021;2．合肥工業大學 計算機與信息學院，安徽 合肥 230009)

摘要：對當前幾種重要的全同態加密結構的構造原理及性質進行了深入剖析，重點對FHE加解密算法、算法基于的難題假設、算法復雜度、密鑰特征、密文擴展性等特點進行了深入分析與詳細比較，并針對結構中的不足之處提出了改進與優化建議，為進一步對FHE結構優化提供借鑒。最后對全同態加密的應用前景進行了全面展望。

關鍵詞：全同態加密；結構比較；云計算；LWE/RLWE

0引言

Rivest等人在上世紀70年代末引入了稱為“隱私同態”的概念[1]，在該加密結構的構想下，能允許在密文域中做任意操作，而無需進行解密。隨后的研究人員提出了一些操作受限的稱之為“半同態”的加密結構，如RSA加密算法[2]與ElGamal加密算法[3-4]是具有任意次乘法運算的乘法同態性加密結構，而其加法運算不具有同態性。Paillier算法[5]與Bresson 等人提出的加密算法具有加法同態性，不具有乘法同態性。而Boneh-Goh-Nissim加密算法[6]支持任意次數的加法運算，但只持一次乘法運算，該算法是最接近于全同態的加密結構之一。直到2009年，IBM公司的Graig Gentry在歐密會上發表了一篇名為《基于理想格的全同態加密》的文章，這一被命名為“全同態加密”(Fully Homomorphic Encryption,FHE)的技術被冠以密碼學“圣杯”的稱號，成為了密碼學最新的研究熱點。之后，研究者又在Gentry基礎之上提出了一些各有特點的重要的全同態加密方案。本文就幾種重要的具有代表性的全同態加密結構進行深入剖析，對它們的特點進行詳細比較，并且提出相應的優化建議，為設計新的FHE方案提供一定的借鑒。

1全同態加密及LWE/RLWE難題假設

1.1全同態加密

令P為明文空間，并定義其上有“+”和“×”兩種運算，令C為密文空間，在其上定義“⊕”和“?”兩種運算，E(p)為加密操作，D(c)為解密操作。當公鑰加密系統具有全同態性，當且僅當：

?a,b∈P，D(E(a)⊕E(b))=a+b

(1)

D(E(a)?E(b))=a×b

(2)

對于同態評價函數f與g，g:Pn→P,和f:Cn→C，有下式成立：

D(f(c1,…,cn))=g(p1,…pn)，ci=E(pi)

(3)

式中，g由運算“+”和“×”構成，而f由“⊕”和“?”兩種運算構成。在全同態加密方案中要求在密文上可直接做任意多次相應運算，然后對結果進行解密，其結果為在對應的明文上進行相應的操作而產生的結果。

1.2LWE與RLWE難題假設

本文所分析的五種全同態加密結構都是基于著名的LWE[7]或RLWE難題假設[8]。

LWE難題假設是機器學習中“奇偶性學習問題”的一般化，由Regev首次提出的，并將它應用到公鑰加密方案構造中。

1.2.1LWE(Learning With Errors)

LWEn,q,x問題：從分布χ中取出一些樣本，不能近似估計出S的值。

Regev使用量子歸約算法證明在一般情況下，只要選擇正確的參數n、q和χ，LWEn,q,x問題和最壞情況下任意n維格上的SVP(Shortest Vector Problem)問題和SIVP(Shortest Independent Vector Problem)問題的困難性等價[7]。

1.2.2RLWE(Ring Learning with Errors)

設λ為安全參數，并且f(x)=xd+1且，d=d(λ)，冪為2。令q=q(λ)≥2是一整數。并且滿足q≡1modd。令R=[x]/(f(x))和Rq=R/qR。最后令χ=χ(λ)為環R上的誤差分布。RLWEd,q,x難題假設可以區分以下兩個分布：

1.2.3LWE與RLWE

2重要全同態加密結構剖析

2.1基于理想格的Gentry結構

Gentry方案[9]是構建在環的“理想”概念上。

假設環為R，該環上的一個“理想”為I。運算過程中產生的噪聲被定義在I上，即：e=rI，其中r∈R，對m加密：C=m+rI，而解密過程是去掉噪音rI理想的過程。而該結構具有的同態性質：

其中，c1=m1+r1I，c2=m2+r2I。

c1+c2=(m1+m2)+(r1+r2)I

(4)

c1c2=(m1+r1I)(m2+r1I)=

(m1m2)+(m1r2+m2r1+r1r2I)I

(5)

由式(4)和式(5)可知，當進行加法運算時，噪聲為(r1+r2)I，乘法運算時，噪聲主要由r1r2I產生。做加法運算時噪音是倍加，做乘法運算時，噪音以平方的形式增加，隨著運算次數不斷增加，噪音將變的很大時將產生譯碼錯誤。而Gentry結構中是采用叫做“評價同態解密函數”來處理，該函數是以具有噪音的密文作為輸入，而其輸出是一個具有小噪音的一個密文，而對噪音不超過閥值的密文可以正確解密。

Gentry結構依賴于基于理想格的困難性假設，而其不足之處在于現在對于理想格域的研究還不是非常完善，并且該結構需要十分有效的壓縮步驟去減小譯碼的復雜度。除了基于理想格的困難假設外，該結構還需要一個基于“松散子集和”的假設。雖然Gentry結構只是一種理論化的模型，但由于它是第一個被證明為全同態的加密結構，所以具有很重要的現實意義，在其基礎上出現了一些結構更加優化并且也具有全同態性的加密結構。

2.2Brakerski和Vaikuntanathan結構

簡稱為BV結構，BV結構[10]比之于Gentry結構的一個顯著不同之處在于使用了著名的DLWE安全假設，并且引入了“再線性化”和“模轉換”技術[9]，而模轉換技術的出現可去掉在Gentry結構中出現的復雜的壓縮過程并且可以有效的對噪聲進行控制。結構的“自舉性”使其很容易構造成全同態結構。該方案基于LWE假設，其結構如下：

假設要加密比特m∈{0,1}，首先隨機選擇r∈{0,1}k，然后計算:

a=ATr，b=vTr+m

(6)

最后輸出(a,b)。為解密密文(a,b)，先計算：

b′=b-〈a,s〉=2e+m∈q

(7)

式中，e為噪聲，〈a,s〉為內積計算，最后輸出：

m=b′ mod 2

(8)

2.3Brakerski和Gentry, Vaikuntanatuhan結構

該結構簡稱為BGV結構[11]，BGV結構是基于環[x]/(f(x))，f(x)為次n的不可約多項式，且Rq=R/qR，q為一個素數模。另外一個參數是基于環R的錯誤分布χ。BGV結構與BV結構相比，其顯著的擴展是使用了RLWE假設，而該假設對提高同態加密結構的加密效率做出了很大的貢獻，而且由于仔細使用了 “模轉換”技術使得可以去掉在Gentry方案中提出的“自舉”過程而獲得“全同態”性質，從而提高了該結構的工作效率。

在該結構中既可以使用LWE假設，也可以使用RLWE假設，本文分析的是效率更高的基于RLWE難題假設的結構方案。該結構可描述如下：

選擇λ作為安全參數，另一個參數為μ，首先選擇一個μ比特去計算modq。然后選擇d=d(λ,μ)，χ=χ(λ,μ)，n=「3logq?。令Rq=q[x]/(f(x))。為獲得私鑰，從分布χ中均勻取出S′，私鑰則為：

(9)

(10)

(11)

根據RLWEd,q,x問題假設(此處的χ為基于Rq的均勻分布)，在此結構下，攻擊者在多項式時間里猜測出的S的概率可以忽略為0。對于解密而言，只需計算b′=[〈c,s〉]q，然后輸出m=[b′]2。

2.4Brakerski結構

Brakerski結構[12](Bra結構)使用了與Regevs相似的基于LWE的公鑰加密結構。其加密結構可描述為：

給定一個安全參數n，令q=q(n)為一個整數。而χ=χ(n)是基于整數集的一個分布。令私鑰為。

為取得公鑰，令：N=(n+1)·(logq+ο(1))并且A←N×n，e←χN。計算b=[A·s+e]q，而公鑰為：P=[b|-A]∈N×(n+1)。假設要加密密文：m∈{0,1}，可首先隨機選擇一個r∈{0,1}N，設m=(m,0,…,0)∈{0,1}n+1，最后輸出的密文為。而解密c，可先計算c0=[〈c,(1,s)〉]q，則明文為m=[「2·c0/q」]2。

2.5Fan和Vercauteren結構

Fan和Vercauteren結構[13](FV結構)，該結構使用了經過修改后的基于RLWE問題的LPR結構，在效率上比之于使用LWE假設的Bra結構有了進一步的提高，由于它包含了一個經過修改后的LPR結構，使得結構更容易優化與分析。

(12)

a取自于Rq。假設對m∈Rt進行加密，從分布χ中取出r，e1，e2。然后計算：

u=a·r+e1+Δ·mmodq

(13)

v=b·r+e2modq

(14)

返回(u,v)。而解密時，首先計算下式：

u+v·s=(r·e-s·e1+e2)+Δ·mmodq

(15)

然后去乘t/q，然后把結果值取整再與t取模。

3FHE結構特征與性能比較和分析

3.1FHE結構性能比較

(1)對于“BV結構”，按其構造原理分析得到：其公鑰尺寸為O(n2log2q)，私鑰尺寸為nlogq，密文尺寸為(n+1)logq，基于的數學難題為LWE。

(2)對于“FV結構”，按其構造原理分析得到：其公鑰尺寸為2dlogq，而私鑰尺寸為d，密文尺寸為2dlogq，基于的難題假設為RLWE。

(3)對于“Bra結構”，按其構造原理分析得到：其公鑰尺寸為O(n2log2q)，私鑰尺寸為nlogq，密文尺寸(n+1)logq，基于的難題假設為LWE。

(4)對于“BGV結構”，按其構造原理分析得到：其公鑰尺寸為2dnlogq，私鑰尺寸為2dlogq，密文尺寸2dlogq，基于的難題假設為LWE或RLWE。

根據這幾種FHE結構的公鑰尺寸、私鑰尺寸、密文尺寸以及基于的難題假設這幾個特征可以看到，當加密方案采用相同的難題假設時，結構間的性能，比如密鑰的長度和輸出密文尺寸都具有一定的相似性。而由于FV結構和BGV結構都采用了RLWE難題假設，所以它們的密鑰尺寸和輸出的密文尺寸都要小于基于LWE難題假設的BV結構和Bra結構。綜合比較，這四種方案中FV的密鑰尺寸最小，究其原因在于其對密鑰尺寸進行了優化，并且沒有采用其它方案經常采用的矩陣形式作為公鑰，從而進一步降低了公鑰的尺寸。

3.2FHE結構分析

(1)BV結構對Gentry結構的改進主要是針對安全性這一方面而言的，BV結構是基于LWE問題，其安全性要優于基于理想格的Gentry結構。并且，它所采用的“再線性化”技術使其能夠保持密文長度基本恒定，并且易于建立“類全同態”結構。而“模轉換”技術能對執行同態操作時產生的噪聲進行有效的控制，從而不必采用Gentry結構中復雜的壓縮步驟。

(2)對于BGV結構而言，它既可以采用LWE難題假設，也可采用RLWE難題假設。在通常情況下，采用的RLWE難題的結構效率要優于BV結構。而同樣采用的“模數轉換”技術可以比較好的減少噪音，所以該結構也不需要Gentry結構中的“自舉”技術，而且比之于BV結構更易于對噪音進行分析。

(3)Bra結構中用到的LWE問題與經典問題GapSVP的困難性一致。在該方案中，噪音不是以乘法平方的形式增大，而只是以固定多項式倍乘的形式增大。該方案中也使用了BGV結構中的密鑰轉換技術。

(4)在FV結構中把Bra方案中的RLWE應用到了結構設計中，這個結構是本文所討論的全同態方案中最有效率的，而解密電路也是這幾個方案中最簡單的。該結構中使用了兩種“再線性化”技術來使其具有“類同態”性質。第一種“再線性化”技術和BGV結構中的密鑰轉換技術類似，而第二種“再線性化”技術與“模轉換”技術相似。幾種全同態加密結構的主要思想見表1。

表1　幾種全同態加密結構的主要思想

3.3改進建議

(1)在BGV結構，一些性能都與擴展因子有關，而通過試驗研究，這個擴展因子的值會小于一個特定值，若能找到這個特定值或其上界，則可以進一步改善與該擴展因子相關的一些性能界限。

(2)在基于RLWE的BGV結構中，當并行計算評價多個功能函數時，可嘗試利用“中國剩余定理”，只用一個比較大的模數來評價一個單獨的功能函數，來替代對多個功能函數進行的評估。

以上是針對這幾種FHE方案所采取的結構、參數特征、基于的難題假設等方面進行的深入對比與分析。這幾個方案都有各自的特點，但它們都有一個共同的問題：效率比較低。因為它們都具有高的算法復雜度，龐大的密鑰尺寸等問題，使得目前的這些全同態加密結構在實用性方面還不盡如人意。所以研究者在不斷優化FHE加密結構的同時，也提出了一些所謂有限全同態加密結構，即“類同態”結構。該結構可支持多次加法，一定量次的乘法運算，而這些“類同態”結構相對于全同態加密結構而言具有算法復雜度小的特點，在不要求全同態的應用領域有更多的實踐意義，這也是全同態結構在完全實用化之前可選的一種折衷方案。所以，全同態加密下一步的研究工作就是實用化，而這要求研究者繼續尋找更加優良的加密結構。

4FHE應用展望

(1)全同態加密領域的突破性進展為云計算和物聯網的發展帶來了新的契機，而云計算中數據安全和隱私保護是云計算發展的關鍵，將直接影響人們對云計算的接受程度。全同態加密有助于推動云計算和物聯網的普及和應用，使其為更多的企業、用戶認知和接納。

(2)全同態加密為云計算和物聯網的數據安全和隱私保護提供了全新的思路，使得對存儲在云端服務器中的加密數據進行運算和操作成為可能，不僅極大地減少了云端服務器和用戶的通信及計算開銷，也保證了數據處理過程中的安全性。

(3)利用全同態加密技術，在保護用戶數據隱私性的同時，為分析和挖掘云服務商CSP(Cloud Service Provider) 所存儲的海量數據開辟了無限的商機。目前的全同態加密方案計算量巨大，難以在現有計算技術條件下實現。如何提高全同態加密方案的加解密效率、降低密鑰存儲空間，都是當前的研究難點。

5結語

本文重點對當前幾種重要的全同態加密結構：Gentry結構、BV結構、BGV結構、Bra結構和FV結構的構造過程及各自具有的特性進行了深入的剖析。著重從幾種方案的加解密算法結構、算法基于的難題假設、算法的復雜度、密鑰特征、密文擴展性等特點進行了深入分析與詳細比較。從分析與比較結果看，在安全性方面，基于理想格的Gentry結構弱于基于LWE或RLWE的其它幾種結構。在結構的性能比較上，FV結構的靈活性及方案效率是優于其它幾種結構。文章最后還針對幾種結構中的不足之處提出了改進與優化建議，為FHE進一步進行結構優化提供了一定的借鑒。

參考文獻：

[1]Ronald L. Rivest, Leonard M. Adleman, Dertouzos M L. On Data Banks and Privacy Homomorphisms[J]. Foundations of Secure Computation,1978,4(11):169-180.

[2]Ronald L. Rivest, Adi Shamir, Leonard M. Adleman. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems[J]. Communications of the ACM, 1978, 21(2): 120-126.

[3]Taher ElGamal. A Public Key Cryptosystem and A Signature Scheme based on Discrete Logarithms[C] //Advances in Cryptology. Springer Berlin Heidelberg, 1984: 10-18.

[4]白永祥.一種高效群簽名方案的設計與分析[J]. 通信技術,2015,48 (02):214-218.

BAI Yong-xiang. Design and Analysis of Efficient Group-Signature Scheme[J]. Communications Technology, 2015,Vol 48 (2):214-218

[5]Pascal Paillier. Public-Key Cryptosystems based on Composite Degree Residuosity Classes[C]// Advances in cryptology—EUROCRYPT’99. Springer Berlin Heidelberg, 1999: 223-238.

[6]Dan Boneh, Eu-Jin Goh, Kobbi Nissim. Evaluating 2-DNF Formulas on CipherTexts[M]//Theory of Cryptography. Springer Berlin Heidelberg, 2005:325-341.

[7]Oded Regev. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography[J]. Journal of the ACM (JACM),2009,56(6):34.

[8]Zvika Brakerski, Vinod Vaikuntanathan. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages[M]//Advances in Cryptology-CRYPTO 2011. Springer Berlin Heidelberg,2011:505-524.

[9]Craig Gentry. Fully Homomorphic Encryption using Ideal Lattices[C]//STOC(Proceedings of the Forty-first Annual ACM Symposium on Theory of Computing), New York. 2009, 9: 169-178.

[10]Zvika Brakerski, Vinod Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE [J]. SIAM Journal on Computing, 2014, 43(2): 831-871.

[11]Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping[J]. ACM Transactions on Computation Theory, 2014, 6(3): 169-178.

[12]Zvika Brakerski. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP[M]//Advances in Cryptology-CRYPTO 2012. Springer Berlin Heidelberg, 2013: 868-886.

[13]FAN Jun-feng, Federik, Vercauteren. Somewhat Practical Fully Homomorphic Encryption[C] //Crypto Cambridge, UK ,2013:247-249.

Research and Analysis of Several Key FHE Structures

MA Fei1,2, LI Juan1

(1.School of Computer Science and Engineering, Beifang University of Nationalities,Yinchuan Ningxia 750021,China;2.School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009,China)

Abstract：In-depth study on principles and properties of the current most important FHE (Fully Homomorphic Encryption) structures is done,with focus on analysis and comparison of FHE encryption and decryption, algorithm based on hard problem, algorithm complexity, key characteristics and ciphertext expansion. In light of the deficiencies, some modified and optimized solutions are presented, and these could serve as a reference for further optimization of FHE structure. Finally, application prospects of FHE are forecasted.

Key words：FHE; structure comparison; cloud computing; LWE/RLWE

doi:10.3969/j.issn.1002-0802.2016.04.019

*收稿日期：2015-11-17；修回日期：2016-03-05Received date:2015-11-17；Revised date：2016-03-05

基金項目：獲得寧夏回族自治區‘計算機應用技術’重點學科項目資助；寧夏教育廳“十三五”自治區重點專業——網絡工程專業重點建設項目資助

Foundation Item:Key Discipline Project (Computer Application Technology) of Ningxia;Foundation Project( Priority Majors of Network Engineering ) of the Education Department of Ningxia in the 13th Five-Year Plan

中圖分類號：TN918.4

文獻標志碼：A

文章編號：1002-0802(2016)04-0481-05

作者簡介：

馬飛(1976—),男，副教授，博士，主要研究方向為網絡安全、云計算，全同態加密，社交網絡與隱私保護;

李娟(1975—)，女，副教授，碩士，主要研究方向為云計算、社會計算、社交網絡與隱私保護。