基于共用密鑰的高效多密鑰同態(tài)加密方案研究*

李文卿,馬 銳,張文濤

(中國航天系統(tǒng)科學與工程研究院，北京 100037)

1 引言

同態(tài)加密是一類加密技術，允許在無需解密的情況下對密文進行同態(tài)運算，解密之后可以獲得正確的結果。同態(tài)加密能夠應用于委托計算，委托方使用公鑰加密數(shù)據(jù)，將密文傳遞給計算方，計算方通過相應的計算后返還委托方加密的結果，由委托方用私鑰解密后獲得正確的結果。全同態(tài)加密的完整方案最早是由Gentry于2009年提出的[1]，目前已經(jīng)發(fā)展出了多種類型的全同態(tài)加密方案。

在許多場景中，數(shù)據(jù)可能來源于多個主體。這些主體要通過協(xié)作計算出結果，同時不能讓其他主體獲得自己的私有數(shù)據(jù)。這類問題可以歸結為安全多方計算的問題，多密鑰同態(tài)加密是這類場景下的一個解決方案[2]。該方案允許每個主體使用自己的公鑰進行加密，然后使用密文擴展將來自各方的密文進行擴展，接著在該密文上進行同態(tài)運算并得到結果的密文，最后再由各個主體聯(lián)合解密獲得正確的結果。

最早的多密鑰同態(tài)加密方案是2012年由López-Alt等人[3]提出的LTV12(以論文作者首字母和年份命名，下同)。之后，Dor?z等人[4]對LTV12方案進行了改進，提出了一個較高效的方案DHS16。2017年，Chongchitmate 等人[5]在LTV12 的基礎上構造了具備電路隱私的多密鑰全同態(tài)加密MKFHE(Multi-Key Fully Homomorphic Encryption)方案CO17。2020年，Che等人[6]利用比特丟棄技術和密文擴展技術，提出了無需計算密鑰的方案CZL+20。這類方案從NTRU(Number Theory Research Unit)型同態(tài)加密方案發(fā)展而來，所基于的困難問題假設是多項式環(huán)上的非標準假設，并且無法構造高效的聯(lián)合解密協(xié)議，實際應用受限[7]。

2015年，Clear等人[8]提出了GSW(Gentry-Sahai-Waters)型[9]的多密鑰同態(tài)加密方案CM15。該方案的安全性基于帶誤差學習LWE(Learning With Errors)問題，這一問題的困難性能被歸結到格密碼學的標準假設上。該方案首次提出了密文擴展技術，該技術能夠將一個單密鑰同態(tài)加密方案擴展為一個多密鑰同態(tài)加密方案。2016年，Mukherjee等人[10]對CM15的密文擴展過程進行了簡化，提出MW16方案。該方案允許一輪的分布式解密，并可以進一步構造兩輪的安全多方計算協(xié)議。同年，Peikert 等人[11]提出了具備多跳的方案PS16。該方案允許參與方實時、動態(tài)地加入到運算過程，但是對參與方數(shù)量有一定的限制。同年，Brakerski等人[12]提出了全動態(tài)的方案BP16。在PS16的基礎上，該方案對參與方的數(shù)量沒有限制，但此類方案存在密文擴展復雜、計算緩慢等問題。

Chen等人[13]于2017年首次提出了BGV(Brakerski-Gentry-Vaikuntanathan)型[14]的多密鑰同態(tài)加密方案CZW17。與GSW類型的方案對比，BGV型的方案密文擴展方式簡潔，擴展過程中不需要使用密文之外的數(shù)據(jù)，因此能夠有效地支持多跳特性(同態(tài)運算過程中加入新用戶)。BGV型的多密鑰同態(tài)加密方案的顯著缺陷是計算密鑰生成復雜、計算密鑰尺寸較大等。2019年，Li等人[15]利用環(huán)上的BGV型RBGV(Ring BGV)和環(huán)上的GSW型RGSW( Ring GSW)密文之間的混合同態(tài)乘法生成計算密鑰，減小了CZW17中的擴展密文尺寸，并在此基礎上設計了BGV型多密鑰同態(tài)加密方案LZY+19。同年，Chen等人[16]提出了CDKS19方案。該方案提出了新的計算密鑰生成方法，改進了同態(tài)乘法的計算過程，并將該方案運用到了神經(jīng)網(wǎng)絡的隱私計算當中。但是，BGV型多密鑰同態(tài)加密方案的密鑰交換過程仍舊比較復雜，生成計算密鑰所需的密鑰數(shù)量較多且尺寸較大。2021年，Zhou等人[17]提出了使用累加公鑰構建多密鑰同態(tài)加密的方案，然而，其解密過程可能會導致私鑰暴露。

以上多密鑰同態(tài)加密方案大多存在密鑰尺寸較大、同態(tài)運算復雜等缺點。與之相比，單密鑰同態(tài)加密則有密鑰尺寸較小、同態(tài)運算簡單等優(yōu)勢。因此，本文提出了一種基于共用密鑰的多密鑰同態(tài)加密方案，結合單密鑰同態(tài)加密和多密鑰同態(tài)加密的優(yōu)勢，并通過理論分析驗證其安全性和有效性。

2 相關知識和關鍵技術

2.1 GLWE問題

帶誤差學習LWE問題或環(huán)上的帶誤差學習RLWE(Ring Learning With Errors)問題是格密碼學中的困難問題。這2個困難問題的本質(zhì)相同，可以歸結為一般帶誤差學習GLWE(General Learning With Errors)問題。GLWE的描述如下所示：

設λ為安全參數(shù)，設多項式環(huán)R=Z[X]/xd+1,Rq=R/qR，Rq上的錯誤分布χ=χ(λ)。GLWE困難問題假定以下2種分布不可區(qū)分：

LWE問題對應GLWE問題取d=1的簡化情況，而RLWE問題對應n=1的簡化情況。GLWE問題可以歸結到格上最短向量問題，該問題的困難性是密碼學的基本假設之一。

2.2 BGV單密鑰同態(tài)加密方案

BGV方案是一個有限級數(shù)的同態(tài)加密方案，并采用了模數(shù)交換、密鑰交換等方式控制噪聲，因此每一層都有各自的公鑰和私鑰。BGV方案有2種構造方式，分別是基于LWE問題和基于RLWE問題，本文只敘述基于RLWE問題的構造方式。BGV型同態(tài)加密方案包含4部分：密鑰生成(KeyGen)、加密(Enc)、解密(Dec)和同態(tài)運算(Eval)。各個部分的具體步驟[13]如下所示：

(1)密鑰生成(KeyGen)：輸入電路深度L，安全參數(shù)λ。選擇噪聲分布χ=χ(L,λ)，該分布是R上的具有界限的分布。選擇L個遞減的模數(shù)qL>qL-1>…>q0。選擇一個與所有ql互素的整數(shù)p，對于每一個l=0,1,2,…,L，進行如下計算：

②從Rq中均勻采樣al←Rq，從錯誤分布中采樣e←χ,計算私鑰skl對應的公鑰，如式(1)所示:

pkl=(bl,al)=(-al·sl+elmodql,al)

(1)

③當l不為0的時候，還需計算密鑰交換參數(shù)，如式(2)所示：

τsk′l→skl-1=SwitchKeyGen(sk′l,skl-1)

(2)

經(jīng)過密鑰生成，得到公鑰{pkl},l=0,1,2，…，L，私鑰{skl},l=0,1,2,…,L，計算密鑰{τsl′→sl-1},l=0,1,2,…,L。

(2)加密(Enc)：對于任意需要加密的明文μ∈Rp，需要從錯誤分布中采樣獲得r←χ，e←χ，輸出第L層(初始層)的密文，如式(3)所示:

c=r·pkl+(m+e,0)

(3)

(3)解密(Dec)：為了解密第l層的密文c，需按照式(4)計算：

μ=〈c,skl〉modqlmodp

(4)

其中〈*,*〉表示內(nèi)積運算。

(4)同態(tài)運算(Eval)：輸入計算的函數(shù)C，密文ci,計算密鑰evk，輸出計算結果。BGV型同態(tài)加密方案支持同態(tài)加法運算和同態(tài)乘法運算，其實現(xiàn)分別如下所示：

①同態(tài)加法：輸入2個密文,該密文需具有相同的模數(shù)和對應私鑰。若不滿足條件，使用模數(shù)交換和密鑰交換操作密文，使其條件滿足。假設2個密文此時對應的模數(shù)是ql。首先，按式(5)計算:

(5)

(6)

最后，通過模數(shù)交換將密文的模數(shù)下降至ql-1，得到結果，如式(7)所示：

(7)

②同態(tài)乘法：若不滿足條件，使用模數(shù)交換和密鑰交換操作密文，使其條件滿足。首先，按式(8)計算：

(8)

(9)

最后，通過模數(shù)交換將密文的模數(shù)下降至ql-1，得到結果，如式(10)所示：

(10)

密鑰交換和模數(shù)交換是BGV型同態(tài)加密方案中的算法。模數(shù)交換則能夠切換密文對應的模數(shù)。在計算完成后，將密文的模數(shù)切換為較小的模數(shù)，可以減少密文中噪聲的絕對大小，控制噪聲的增長。在噪聲規(guī)模可控的前提下，這一部分不影響最終結果的正確性。密鑰交換算法能夠在不解密的前提下改變密文的私鑰，且不會改變對應的明文。同態(tài)加法運算中的密鑰交換同樣是可選的，但是同態(tài)乘法后必須使用密鑰交換來控制密文增長的規(guī)模。

2.3 密鑰交換和重線性化

BGV型同態(tài)加密方案需要在同態(tài)乘法后對密文進行密文尺寸的縮減，否則密文尺寸將會隨著乘法次數(shù)指數(shù)級膨脹。密鑰交換和重線性化是縮減密文尺寸常見的2種方法。

(11)

然后選擇nβ個RLWE實例(-aiz2+ei,ai),i=1,2,…,nβ。輸出交換密鑰,如式(12)所示:

(12)

其中，為了區(qū)分變量和向量的下標索引，使用u[i]表示取u的第i個下標的運算。

(13)

密鑰交換過程中2個重要的函數(shù)比特分解和重組分別如下所示：

這2個函數(shù)是配合使用的，易證明：

〈BitDecomp(x),Powersof2(y)〉=〈x,y〉

重線性化是BGV類型的加密方案CKKS[18]采用的減小密文尺寸的算法。其基本思想是，從密文解密后的結果來看，同態(tài)乘法的結果是一個關于私鑰的二次項，需要將它重線性化，消去二次項的部分。重線性需要使用計算密鑰。計算密鑰生成中，輸入私鑰為sk=(1,s)，從Rq上均勻采樣a′←U(Rq)，從錯誤分布中采樣e′←χ。輸出計算密鑰，如式(14)所示：

evk=(-a′·s+e′+s2,a)

(14)

使用重線性化方法的同態(tài)加密方案，再計算同態(tài)乘法時按照如下步驟計算：輸入計算密鑰evk和2個密文c1=(b1,a1)，c2=(b2,a2)。按式(15)計算:

(d0,d1,d2)=(b1b2,b1a2+b2a1,a1a2)

(15)

然后輸出同態(tài)乘法的結果，如式(16)所示：

c′=(d0,d1)+evk·d2

(16)

此時對輸出密文解密可以得到輸入的2個密文對應明文相乘的結果，且保證了密文的尺寸不會擴張。

2.4 密文擴展

多密鑰同態(tài)加密一般需要密文擴展操作，該操作將使用不同密鑰的密文進行擴展。擴展后的密文可以視為使用同一個公鑰進行加密，從而能夠進行同態(tài)運算。BGV型多密鑰同態(tài)加密的密文擴展方式如下所示：

(17)

(18)

其中，

擴展后的密文對應的密鑰如式(19)所示:

(19)

BGV型多密鑰同態(tài)加密方案的解密方式與之類似：首先將密文拆分，然后將拆分后的密文發(fā)給對應的參與方，由參與方使用各自的私鑰解密后，再將解密的結果累加起來，得到最終的計算結果。

3 方案構造過程

BGV型的多密鑰同態(tài)加密大多遵循以下規(guī)則：各參與方產(chǎn)生自己的公鑰、私鑰和計算密鑰，使用各自的公鑰為密文加密。計算方使用密文擴展的方法處理各參與方的密文，使得處理后的密文可以視為使用同一公鑰加密的密文，然后才能進行同態(tài)運算。同態(tài)運算結束后，計算方將同態(tài)運算的結果拆分，發(fā)給各個參與方單獨解密，然后由計算方累加各方的結果得到最終的運算結果。

這一類方案在密文擴展和實現(xiàn)多跳操作上具有很大的優(yōu)勢，但是其同態(tài)乘法操作非常復雜。本文將提出一個新的多密鑰同態(tài)加密方案的構造思路，并通過逐步的設計形成一個多密鑰同態(tài)加密方案。

3.1 共用密鑰加密

受文獻[17]的啟發(fā)，本文提出了一種新的同態(tài)加密方法。該方法中，各參與方協(xié)商出共用公鑰用于加密，然后使用同一公鑰進行加密，這樣可以減小密鑰和密文的尺寸。

基于多密鑰同態(tài)加密應用場景中的安全性需求，公鑰協(xié)商需要保證以下需求：(1)安全性，要保證協(xié)商過程中不會暴露用戶的私鑰和數(shù)據(jù)；(2)形式不變，協(xié)商出的密鑰最好與單密鑰同態(tài)加密有同樣的形式，從而便于計算；(3)正確性，協(xié)商出的密鑰應當保證解密結果正確，對于同態(tài)加密，這意味著〈pk,sk〉≈0。

基于以上要求，本文提出了一種公鑰協(xié)商的方法：

輸入{pki=(bi,a),i=1,…,k}為各參與方公鑰的集合，其中，a為公共參數(shù);bi由各參與方計算,bi=-a·si+ei，si為各參與方的私有參數(shù)，ei為各方選擇的誤差。公鑰的計算方式如式(20)所示：

(20)

該算法運算完成后，公鑰的形式如式(21)所示：

(21)

其對應的解密私鑰為：

(22)

(23)

可以看出，協(xié)商的密鑰滿足正確性和形式不變性的要求，安全性證明將會在第5節(jié)給出。

采用共用公鑰的多密鑰同態(tài)加密方案，來自各個參與方的密文都處于同一個公鑰的加密狀態(tài)下。這不僅避免了密文擴展使得密文的尺寸膨脹，也避免了多密鑰同態(tài)加密時復雜的同態(tài)運算。同態(tài)加密的時間復雜度和空間復雜度都降低到了與單密鑰同態(tài)加密相當?shù)乃健?/p>

3.2 同態(tài)運算獲取計算密鑰

同態(tài)乘法中重線性化操作需要向計算方提供計算密鑰，計算密鑰可以視為一個加密過的私有參數(shù)的冪。根據(jù)單密鑰同態(tài)加密中重線性化的形式，本文所提出的多密鑰同態(tài)加密方案的重線性化所需的計算密鑰如式(24)所示：

(24)

其中a′表示計算密鑰的公共參數(shù)。

可以看到，上述計算密鑰包含私有參數(shù)的累加和的冪。在不暴露私有參數(shù)的前提下，由各參與方協(xié)商獲得上述密鑰比較困難。但是，在不暴露私有數(shù)據(jù)的情況下對私有數(shù)據(jù)進行運算并獲得結果，這是多密鑰同態(tài)加密能夠解決的問題。因此，本文可以構建一個簡單的多密鑰同態(tài)加密方案來計算密鑰。

相較于通常情景下多密鑰同態(tài)加密的要求，此處對同態(tài)運算能力的要求降低了。在此處的計算中，所需計算的函數(shù)的復雜度是確定的，并且只需密文進行一次同態(tài)乘法操作和數(shù)次同態(tài)加法操作。在一個多密鑰同態(tài)加密中使用另一個多密鑰同態(tài)加密是否有用呢？在本文第5節(jié)中將詳細闡述該方案所帶來的效率的提升。

計算計算密鑰的同態(tài)加密方案可以在原方案的基礎上進行一些簡化。對于該方案所需的公共參數(shù)，本文可以使用在密鑰生成階段產(chǎn)生的公共參數(shù)；由于計算函數(shù)的深度是確定的，噪聲增長是可控的，從而無需使用很多的噪聲控制技術。具體的方案將在第4節(jié)描述。

3.3 安全解密

依據(jù)式(22)和式(23)，只需要計算式(25)即可完成解密：

〈c,sk〉modq=μ

(25)

此處的一個問題是，如何在不泄露私鑰的前提下完成解密過程，即如何在不暴露用戶私鑰的前提下，計算解密函數(shù)。對于這個問題，本文依然可以使用一個多密鑰同態(tài)加密來解決。某些計算函數(shù)可能會導致密文泄露。

為了說明何種情況下會造成數(shù)據(jù)泄露，本文考慮以下情景：

2個參與方(1,2)，分別持有明文μ1和μ2，需要計算μ1+μ2。在使用按密文擴展方式構建的多密鑰同態(tài)加密中，在完成密文擴展后，3個參與方的擴展密文分別如式(26)和式(27)所示：

(26)

(27)

在完成同態(tài)加法后，同態(tài)運算的結果如式(28)所示：

(28)

按照同態(tài)運算的解密步驟，接下來要將結果拆分為c1和c2并將其分別發(fā)給參與方1和2，解密的結果為μ1和μ2。

按照多密鑰同態(tài)加密方案，此時需要累加各方的解密結果完成最終解密。因此，每個參與方需要將自己解密的結果傳遞給計算方或某個參與方。按照前文所述，此時每個參與方解密的結果是其私鑰數(shù)據(jù)，向其他參與方或解密方傳遞該數(shù)據(jù)會導致該數(shù)據(jù)泄露。

4 方案總覽

基于共用公鑰的多密鑰同態(tài)加密方法的細節(jié)已經(jīng)在前文討論完畢，本節(jié)將會在前文討論的基礎上，構建一個完整的多密鑰同態(tài)加密方案。該方案分為4個部分，即初始化、密鑰生成、加密和解密、同態(tài)運算。其中，計算計算密鑰和解密2個過程需要使用其他多密鑰同態(tài)加密方案完成。本文使用了基于CDKS19方案的簡化方案。為了方便說明，將計算計算密鑰過程中使用到的方案稱為計算密鑰子過程，將解密過程中用到的方案稱為解密子過程，將整個方案稱為父過程。

4.1 初始化

同態(tài)加密開始時執(zhí)行初始化步驟。輸入安全參數(shù)λ、參與用戶數(shù)N，計算函數(shù)的深度，即同態(tài)乘法的次數(shù)L。根據(jù)安全參數(shù)選擇Rq上的密鑰分布ψ和錯誤分布χ。從Rq上的均勻分布采樣2個公共密鑰參數(shù)a←U(Rq)，a′←U(Rq)。輸出公共參數(shù)pp=(N,ψ,χ,a,a′)。

4.2 密鑰生成

每一位參與方和計算方都需要計算自己的公鑰和私鑰。參與方和計算方需完成如下計算：從密鑰分布中選擇私有元素si←ψ，同時該私有元素也將作為私鑰;從錯誤分布中選擇誤差ei←χ;獲得公鑰為pki=-a·ski+ei。計算方的編號為0，參與方編號為1～k。此處計算方的公鑰和私鑰是為解密階段準備的。

然后，計算共用公鑰。這需要累加各參與方公鑰得到共用公鑰，如式(29)所示:

(29)

除此以外，計算方和每個參與方還需生成一組參數(shù)，這組參數(shù)將被用于計算密鑰子方案和解密子方案中。需生成的參數(shù)如式(30)所示：

di,0=-si·di,1+ei,1+rimodq,

di,1←U(Rq),

di,2=ri·a+ei,2+simodq,

whereri←ψi

(30)

密鑰生成階段還需計算計算密鑰，這需要通過計算密鑰子過程完成，整個方案的描述如下所示：

(1)子過程的計算方和參與方為父過程的計算方和參與方，每個參與方將自己原方案的私有元素si使用自己的私鑰sk加密作為輸入。

(2)由參與方使用同態(tài)運算計算如式(31)的函數(shù)：

(31)

其中，a′為公共參數(shù)，由父過程在密鑰生成階段生成，e為誤差，從父過程的錯誤分布中采樣獲得e←χ。

(3)計算方將密文拆分，并將對應密文發(fā)給參與方解密，然后累加結果獲得父過程計算密鑰。

計算方需保存計算密鑰，以便在之后的同態(tài)運算中使用。計算密鑰子過程中使用到的簡化的多密鑰同態(tài)加密方案將在4.5節(jié)給出。

4.3 加密和解密

加密：輸入明文μ∈Rq，共用公鑰pk。從密鑰分布中采樣隨機元素r←ψ，從錯誤分布中采樣誤差：e0←χ，e1←χ，輸出密文為c=r·(pk,a)+(μ+e0,e1) modq。

解密需要由解密子過程完成，這一過程的描述如下所示：

(1)子過程的計算方為父過程的計算方，但子過程的參與方則包含父過程的所有參與方和計算方。父過程的計算方將同態(tài)運算結果使用自己的私鑰加密，父過程的參與方分別使用自己的公鑰加密自己的私有元素si。

(2)由參與方使用同態(tài)運算計算如式(32)的函數(shù)：

(32)

(3)計算完成后獲得的結果為父過程的結果的明文在子過程密鑰加密后的密文。參與方和計算方繼續(xù)執(zhí)行子過程的解密，即可獲得明文結果。該結果既是解密子過程的明文結果，也是父過程的明文結果。

解密過程所需的簡化的同態(tài)加密方案將在4.5節(jié)給出。

4.4 同態(tài)運算

本方案的同態(tài)運算支持同態(tài)加法和同態(tài)乘法，其中同態(tài)乘法縮減密文尺寸的方式采用了與CKKS類似的重線性化方法。

同態(tài)加法的正確性證明如式(33)所示：

(33)

(d0,d1,d2)=(b1b2,a1b2+a2b1,a1a2)

(34)

c3=(d0,d1)+d2·(evk,a′) modq

(35)

同態(tài)乘法的正確性證明如式(36)所示：

μ1·μ2

(36)

4.5 簡化的同態(tài)加密方案

前文所述的方案中，計算計算密鑰和解密2個過程需要引入一個外部的多密鑰同態(tài)加密方案才能完成運算。由于計算函數(shù)是確定的，該加密方案可以盡可能地簡化。

本文所采用的簡化的多密鑰同態(tài)方案從CDKS19方案[16]簡化而來。在簡化方案中，初始化生成的公共參數(shù)和密鑰生成階段采用的公鑰和私鑰均采用父方案生成的參數(shù)和公私鑰，因此簡化方案只包含加密、解密、密文擴展和同態(tài)運算。

(1)加密。

輸入明文μ，公鑰pk=-a·s+e和公共參數(shù)a。從密鑰分布采樣r←ψ，從錯誤分布中采樣e←χ。輸出如式(37)所示的密文：

(37)

(2)密文擴展。

wherec′0=c0

(38)

(3)解密。

解密分為2步。對于密文c,如式(39)所示：

(39)

首先將密文拆分，計算方保留c0，然后ci傳遞給對應的參與方。參與方進行部分解密：輸入ci，si，輸出如式(40)所示:

μi=ci·si+eimodq

(40)

其中ei←χ為從錯誤分布中采樣。

然后，計算方累加各方結果完成解密，如式(41)所示：

(41)

(4)同態(tài)運算。

同態(tài)加法只需直接相加，如式(42)所示：

ct3=ct1+ct2modq

(42)

(43)

①規(guī)約張量積中第1行第1列的元素c′0=c0;

②規(guī)約張量積中第1行和第1列中的其他元素c′i=c0,i+ci,0；

③規(guī)約張量積中除了第1行和第1列的其他元素,如式(44)所示：

c′i,j=〈ci,j,bj〉modq,

c′0=c′0+c′i,j·di,0modq,

c′i=c′i+c′i,j+di,1modq,

c′j=c′j+ci,j·di,2modq

(44)

以上為子方案采用的多密鑰同態(tài)加密方案的所有內(nèi)容。其正確性由CDKS19方案保證。

5 方案分析

本文提出的方案的根本思想是將一個多密鑰同態(tài)加密問題轉化為單密鑰同態(tài)加密問題，由此減小密文的尺寸，提高同態(tài)加密的效率。本節(jié)將會從安全性和計算效率2個方面分別分析本文提出的方案，并證明在保證安全性的前提下，對于復雜的計算函數(shù)，本文提出的方案相較于其他多密鑰同態(tài)加密方案在效率上有顯著提升。

5.1 安全性分析

本文所提出的方案中，所有參與方先產(chǎn)生一個共用的公鑰和計算密鑰。各參與方使用該公鑰加密，并使用產(chǎn)生的計算密鑰完成單密鑰同態(tài)加密的同態(tài)運算過程，獲得同態(tài)運算結果，最后由各方通過多密鑰同態(tài)加密方法共同解密，獲得運算結果。以下將分別證明這幾個過程對于誠實但是好奇的參與者而言是安全的：

對于簡化的多密鑰同態(tài)加密過程而言，此時計算過程中所需的di,0，di,1和di,2是對私鑰si使用另一個密鑰ri進行加密而得到的，并且ri也通過si加密。通過上述的di,0，di,1和di,2求解si的問題為LWE問題，因此該過程是安全的。

對于產(chǎn)生共用密鑰過程而言，此時各參與方了解公共參數(shù)a，各參與方公鑰為a·si+ei，此時獲取私鑰si的問題為LWE問題，該過程是安全的。

對于解密過程而言，一方面，解密過程使用多密鑰同態(tài)加密方案完成，另一方面，因為解密過程有計算方參與且存在同態(tài)乘法，多密鑰同態(tài)加密的部分解密結果與私鑰無關，因此該過程也是安全的。

5.2 效率分析

BGV型多密鑰同態(tài)加密的復雜度主要來源于同態(tài)乘法的相關操作。與單密鑰同態(tài)乘法相比，多密鑰同態(tài)乘法后進行重線性化所需的計算密鑰變得很復雜。為了說明這一問題，本文分析單密鑰和多密鑰情況下同態(tài)加密的計算密鑰的形式。

對于單密鑰同態(tài)加密而言，假設2個使用私鑰sk=(1,s)加密的密文分別為c1=(b1,a1)，c2=(b2,a2)。其密文解密相乘的結果如式(45)所示：

Dec(c1)·Dec(c2)=(b1+a1·s)·

(b2+a2·s)=b1b2+(b1a2+b2a1)s+a1a2s2

(45)

對于多密鑰同態(tài)乘法方案，假設有2個參與方，私鑰為sk1=(1,s1)和sk2=(1,s2)，密文分別為c1=(b1,a1，1,a1,2)，c2=(b2,a2，1,a2,2),則其密文解密后相乘的結果如式(46)所示：

Dec(c1)·Dec(c2)=(b1+a1,1s1+a1,2s2)·

(b2+a2,1s1+a2,2s2)=

a1,2a2,1s1s2+…

(46)

采用重線性化技術可以消去式(46)中關于s1和s2的二次項。與單密鑰情況下只有一個二次項的情況相比，多密鑰同態(tài)加密的二次項數(shù)目不僅數(shù)量很多，而且還包含了形如sisj的二次項。由于這樣的特殊的二次項存在，單個參與方無法完成計算密鑰的計算。現(xiàn)存的BGV型多密鑰同態(tài)加密方案中，在密鑰生成階段，各參與方只計算密鑰生成材料，再由計算方通過這些計算密鑰生成材料來計算計算密鑰。由于計算密鑰和參與方的私有元素相關，因此上述操作需要在保證不泄露私有元素的前提下進行。因此，計算計算密鑰一直是影響B(tài)GV型多密鑰同態(tài)加密效率的重要因素。

除了能夠顯著地降低計算計算密鑰的過程的復雜度，本文所提出的共用密鑰加密還能減小密鑰和密文的尺寸。對于現(xiàn)存的BGV型多密鑰同態(tài)加密方案，需要通過密文擴展的方法使得來自不同參與方的密文轉換到由同一個密鑰加密的情況，從而進行同態(tài)運算。這一過程使用了密文拼接，從而使得密文的尺寸擴大。但是，本文提出的方案因為使用了共用密鑰，從而避免了上述問題。

本文提出的方案與其他BGV型多密鑰同態(tài)加密方案在時間和空間復雜度上的對比分析如表1所示。

Table 1 Analysis of the complexity of multi-key homomorphic encryption schemes表1 同態(tài)加密效率分析

6 結束語

多密鑰同態(tài)加密有廣泛的使用場景，本文通過使用共用密鑰加密，設計了一種BGV型多密鑰同態(tài)加密方案。使用共用密鑰降低了計算密鑰的復雜度，同時還減小了密文和密鑰的尺寸。在計算計算密鑰和解密階段，改變了相關算法，從而可以在保證安全性的前提下完成計算。從理論分析的結果來看，本文提出的方案降低了計算復雜度，提高了同態(tài)加密的效率。