基于全同態(tài)加密的安全多方計算探討

李習(xí)習(xí) 胡業(yè)周

摘要：隨著云計算的發(fā)展與應(yīng)用，數(shù)據(jù)的隱私保護越來越受到人們的關(guān)注。而全同態(tài)加密這一密碼學(xué)原語的提出，為數(shù)據(jù)的隱私計算提供了一個強有力的工具。另一方面，安全多方計算允許人們共同計算一個函數(shù)得到想要的結(jié)果而不泄露自己的私有數(shù)據(jù)，在現(xiàn)實生活中有著眾多的應(yīng)用。研究發(fā)現(xiàn)全同態(tài)加密可以作為安全多方計算協(xié)議的構(gòu)建模塊，且在LWE的假設(shè)下，協(xié)議在面對一個半惡意的敵手是安全的，進一步，在CRS模型下可由非交互的零知識證明將協(xié)議轉(zhuǎn)換成面對惡意敵手也是安全的。

關(guān)鍵詞：全同態(tài)加密;安全多方計算;LWE;（半）惡意敵手;CRS模型

中圖分類號：TP309.7 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2020）21-0019-04

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

1 引言

云計算作為一種新的計算方式，在生產(chǎn)生活中扮演著重要的角色，當(dāng)用戶將自己的私有數(shù)據(jù)上傳到一個不可信的云服務(wù)器上進行計算，如何能夠保證數(shù)據(jù)不會泄露，這給云計算的應(yīng)用帶來巨大的挑戰(zhàn)。隨著量子計算機的不斷發(fā)展，一些傳統(tǒng)的加密體制在量子計算機面前將會變得不再安全，如RSA，EIGa-mal等。后量子時代的到來迫切需要能夠抵抗量子計算攻擊的密碼體制，如基于糾錯碼的公鑰密碼體制，基于格的公鑰密碼體制等。

全同態(tài)加密（FHE）的出現(xiàn)上述問題提供了一個很好的解決方案，F(xiàn)HE的一個顯著特征就是允許對密文直接進行計算操作，解密結(jié)果相當(dāng)于對明文做同樣的計算操作，即：如，（f （Enc（m1），Enc（m2），…，Enc（mn）=f（m1，m2，...'mn）。安全多方計算的提出允許人們在不揭露自身的數(shù)據(jù)而安全的計算出一個函數(shù)，參與方除了最終的計算結(jié)果得不到任何其他的信息。自1986年姚期智構(gòu)造一個基于混淆電路的安全多方計算協(xié)議以來[1]，安全多方計算得到了快速地發(fā)展。2012年，LOPEZ-AltA等人提出多密鑰（MFHE）全同態(tài)加密的概念并基于NUTR構(gòu)造了第一個MFHE方案[2]，很自然的，以MFHE為基礎(chǔ)，可以創(chuàng)建一個安全多方計算協(xié)議。之后，大量基于多密鑰全同態(tài)加密的安全多方計算被提出。在本文中，我們主要探討以GSW全同態(tài)加密方案為基礎(chǔ)的安全多方計算，因為該類方案的密文不會隨著同態(tài)操作發(fā)生擴張也不需要運行密鑰。我們從MW（16）中的安全多方計算協(xié)議展開[3]，對不同模型下的安全多方計算協(xié)議的構(gòu)造、協(xié)議的安全性、協(xié)議的功能性進行探討。

2 基于GSW全同態(tài)加密的安全多方計算協(xié)議的構(gòu)造

在本節(jié)中，我們描述在三種不同模型中以GSW全同態(tài)加密方案為基礎(chǔ)的安全多方計算協(xié)議，三種模型分別為CRS模

通常，一個全同態(tài)加密方案包含以下幾個步驟：SetUp（參數(shù)設(shè)置）、KeyGen（密鑰對生成）、Enc（加密）、Eval（評估密文）、Dec（解密）。然后若想能夠應(yīng)用在安全多方計算中，需要將一個單密鑰的全同態(tài)加密方案擴展成多密鑰，即在原有方案的基礎(chǔ)上增加一個步驟為Expand（擴展）。最后一個安全多方計算協(xié)議以下幾個過程：輸入（一個想要計算的函數(shù)以及不同參與方的私有數(shù)據(jù)）、交互（所有的參與方在協(xié)議內(nèi)進行交互，參與方當(dāng)中可能有被敵手腐敗的人員，他們不一定忠實地履行協(xié)議。判斷一個協(xié)議的優(yōu)良與否在于交互的輪數(shù)，一般輪數(shù)越低，協(xié)議的性能越好）、輸出（交互完成后，每個參與方輸出自己的結(jié)果，最后聯(lián)合所有參與方的輸出，即可得到最終想要計算的結(jié)果）。

2.1 CRS模型中的安全多方計算協(xié)議議的安全性可由LWE假設(shè)來保證，具體我們將在下節(jié)討論。

3 協(xié)議的安全類型

我們首先給出安全多方計算中常見的敵手類型。

（1）半誠實敵手：忠實地履行協(xié)議但是想根據(jù)自己的信息窺探出其他參與方的私有信息。

（2）半惡意敵手：可以腐敗任意多個誠實方，除了標(biāo)準(zhǔn)磁帶外，還擁有一個證據(jù)磁帶，該敵手必須將自己代表的誠實方的輸入記錄到證據(jù)磁帶上。敵手可以根據(jù)輸入和一定的隨機性來決定是否忠實地履行協(xié)議。

（3）惡意敵手：可以任意篡改、泄露協(xié)議和私有數(shù)據(jù)，甚至可以中斷協(xié)議。

通常利用理想現(xiàn)實模型證明一個安全多方計算協(xié)議的安全性，即通過一系列的混合游戲來證明理想=現(xiàn)實，其中。o表示計算不可區(qū)分。下面我們分別描述在不同模型下的安全多方計算協(xié)議的安全性。

3.1 CRS模型中安全多方計算協(xié)議的安全性

在CRS模型中，安全多方計算協(xié)議在面對一個惡意的敵手是安全的。首先利用理想現(xiàn)實模型證明協(xié)議在面對一個半惡意的敵手是安全的，即存在一個模擬算法S thr，假設(shè)共有Ⅳ個參與方，當(dāng)一個半惡意的敵手恰好腐?、?l個參與方時，模擬器S thr在第一輪用0代替唯一誠實方Ph的真實輸入進行加密并發(fā)布出去，在第二輪中得到模擬解密p h并在第二輪結(jié)束前用模姒部分解密代替真實解密發(fā)布出去。通過定義混合游戲REAL πAZ，HYB πAZ，IDEALFSZ利用LWE假設(shè)得到IDEAL FSZ≈ REAL πAz，安全性得證。在證明協(xié)議在面對一個半惡意的敵手之后，通過一個非交互的零知識證明可以將協(xié)議轉(zhuǎn)化成在面對惡意敵手也是安全的。

3.2 分布式設(shè)置模型中安全多方計算協(xié)議的安全性

在分布式設(shè)置中，安全多方計算協(xié)議在面對一個惡意的敵手是安全的。和上述證明方法類似，首先證明在面對一個半惡意的敵手協(xié)議是安全的，過程與上述方案相同。之后，在轉(zhuǎn)化成為面對惡意敵手也是安全的，需要一個兩輪的自適應(yīng)安全承諾方案，一個單向函數(shù)，一個三輪的隨機硬幣帶有延遲輸入的不可區(qū)分混淆器，一個四輪的零知識證明系統(tǒng)，利用這些可以將上述3輪半惡意安全的協(xié)議轉(zhuǎn)化成一個4輪惡意安全的協(xié)議。

3.3 無CRS模型中安全多方計算協(xié)議的安全性

在無CRS模型中，安全多方計算協(xié)議在面對一個半惡意的敵手是安全的，證明方法與上述方案相同。但如何從一個半惡意安全轉(zhuǎn)化為惡意安全仍然是一個公開的問題。

4 協(xié)議的更多功能

4.1基于多跳全同態(tài)加密方案的安全多方計算

上面的方案都只支持單跳，在2016年，[BP16]、[PS16]構(gòu)造了多跳的全同態(tài)加密方案（動態(tài)多密鑰全同態(tài)加密方案），即在一組密鑰下的密文（擴展密文）在增加若干個私鑰后仍然可以進行同態(tài)運算。其中[BP16]利用了自舉技術(shù)，優(yōu)點是密文尺寸伴隨著密鑰個數(shù)呈線性增長，密文尺寸小，缺點是在自舉過程中操作量過大[7];[PS16]利用加密承諾矩陣來構(gòu)造多跳全同態(tài)加密方案，優(yōu)點是操作量小，更有效率，缺點是密文尺寸過大且隨著密鑰個數(shù)呈四次增長[8]?；诙嗵瑧B(tài)加密方案的安全多方計算允許在密文同態(tài)運算這一階段加入新的用戶。

4.2 基于多比特全同態(tài)加密的安全多方計算

在2017年，李增鵬等人基于GSW全同態(tài)加密方案構(gòu)造了兩個多比特全同態(tài)加密方案，并利用編碼技術(shù)提出了一個新的密文擴張方案，可以以此為基礎(chǔ)構(gòu)造了一個兩輪的安全多方計算協(xié)議。該協(xié)議在面對一個惡意敵手是安全的[9]。

4.3 抵抗混合型敵手的安全多方計算協(xié)議

混合型敵手指的是集合（A Sh，A Sm，A Fc），代表的是在一組被敵手腐敗的參與方中，有一部分是被半誠實敵手腐敗，有一部分是被半惡意敵手腐敗，有一部分是腐敗失?。☉卸璧膮⑴c方）;集合（ASm，A mal，AFc）表示的是在一組被敵手腐敗的參與方中，有一部分是被半惡意敵手腐敗，有一部分是被惡意敵手腐敗，有一部分是腐敗失敗。其中懶惰的參與方是指協(xié)議中途離開的參與方。在[BJMS19]利用{0，1}- LSSSD訪問結(jié)構(gòu)和一個非交互的零知識證明系統(tǒng)，證明了在CRS模型中以及分布式設(shè)置中的安全多方計算協(xié)議，當(dāng)（Ash，Asm）不屬于訪問結(jié)構(gòu)時，協(xié)議在面對一個混合型敵手（Ash，，Asm，AFc）是安全的。同第三節(jié)方案類似，利用非交互的零知識證明，當(dāng)（AMa;，As）不屬于訪問結(jié)構(gòu)時，可以將協(xié)議轉(zhuǎn)化成在面對一個混合型敵手（ASm，AMal，AFc）是安全的。

5 其他的基于全同態(tài)加密的安全多方計算

在2017年，王會勇等人在GSW全同態(tài)加密的基礎(chǔ)上，利用密鑰同態(tài)的性質(zhì)在CRS模型中構(gòu)造了一個三輪的安全多方計算協(xié)議，該方案與上述在CRS模型中的方案相比，優(yōu)點是不用進行密文擴展操作，缺點是要增加一輪交互用來得到所有參與方的公鑰[10]。

在文獻(xiàn)[BJMS19]中構(gòu)造了一個三輪的誠實方占大多數(shù)的安全多方計算協(xié)議，該協(xié)議能夠保證每一個誠實的參與方在協(xié)議結(jié)束之后都可以得到最終的結(jié)果，并證明了該協(xié)議在面對混合敵手是安全的。

6 結(jié)論

在云計算的快速發(fā)展下，全同態(tài)加密和安全多方計算計算的研究越來越受到入們的重視，在本文中我們對基于GSW全同態(tài)加密的安全多方計算做了全面研究，在第二節(jié)給出了在CRS模型、分布式設(shè)置、無CRS模型中基于GSW全同態(tài)加密的安全多方計算協(xié)議。在第三節(jié)分別給出了不同模型下協(xié)議的安全性，在第四節(jié)我們給出了安全多方計算協(xié)議的更多功能，在第五節(jié)給出了其他基于GSW全同態(tài)加密的安全多方計算。

參考文獻(xiàn)：

[1] YAO A. Protocols for secure computations[C]//Proceedings ofthe 23rd Annual Symposium on Foundations of Computer Sci-ence， New York， USA， 1982： 160-164.

[2] Stehle D， Steinfe R. Making NTRU as secure as worst-caseproblems over ideal lattic[Cy/Advances in Cryptology-EURO-CRYPT 2011， Tallinn， Estonia， 2011： 27-47.

[3]P. Mukherjee，D.Wichs. Two Round Multiparty Computationvia Multi-key FHE[[C]. M. Fischlin，J.-S. Coron. EURO-CRYPT 2016， Part ll. Springer， Heidelberg， 2016， 9666： 735- 763.

[4] M. Clear， C. McGoldrick. Multi-identity and Multi-key Lev- eled FHE from Leaming with Errors[C].R. Gennaro， M. J. B. Robsha，v. CRYPT0 2015， Part lI. Springer，Heidelberg， 2015，9216：630 ～ 65.

[5] Zvika Brakerski. Shai Halevi， and Antigoni Polychroniadou.Four round secure computat-ion without setup// TCC2017：lnTheory of Cryptography， Baltimore， MD， USA， 2017：678-710.

[6] Kim E ， Lee H S ， Park J . Towards Round-Optimal SecureMultiparty Computations： Multikey FHE Without a CRS[M].Information Security and Privacy. Springer， Cham， 2018：101-113 .

[7] Z. Brakerski and R. Perlman. Lattice based fully dynamicmulti key FHE with short ciphertexts. key FHE with short ci-phertexts. In CRYPTO， 2016： 190 ～ 213.

[8] Sina Shiehian. Multi-Key FHE from LWE， Revisited. 2016.

[9] Li Z ， Ma C ， Morais E . et al. Multi-bit Leveled Homomor-phic Encryption via DuaI.LWE -Based[Cy]/lntemational Con-ference on Information Security and Cryptology， Seoul， Korea2017：221-242.

[10] WANG Hui-yong FENG Yong ZHAO Ling-zhong TANG Shi-jie. A Secure Multi-Party Computation Protocol on the Ba-sis of Multi-Key Homomorphism[J]. JSCUT（Natural ScienceEdition）， 2017， 45（7）： 69-76.

基金項目：廣州市教育局協(xié)同創(chuàng)新重大項目（1201610005）

作者簡介：李習(xí)習(xí)（1996-），女，安徽蕭縣人，學(xué)生，碩士，主要研究方向為全同態(tài)加密與安全多方計算;胡業(yè)周（1996-），男，安徽明光人，學(xué)生，碩士，主要研究方向為全同態(tài)加密與安全多方計算。