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

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

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

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

文章編號(hào)：1009-3044（2020）21-0019-04

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6 結(jié)論

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

參考文獻(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àng)目：廣州市教育局協(xié)同創(chuàng)新重大項(xiàng)目（1201610005）

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