基于全同態加密的安全多方計算探討

李習習 胡業周

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

關鍵詞：全同態加密;安全多方計算;LWE;（半）惡意敵手;CRS模型

中圖分類號：TP309.7 文獻標識碼：A

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

開放科學（資源服務）標識碼（OSID）：

1 引言

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

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

2 基于GSW全同態加密的安全多方計算協議的構造

在本節中，我們描述在三種不同模型中以GSW全同態加密方案為基礎的安全多方計算協議，三種模型分別為CRS模

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

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

3 協議的安全類型

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

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

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

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

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

3.1 CRS模型中安全多方計算協議的安全性

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

3.2 分布式設置模型中安全多方計算協議的安全性

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

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

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

4 協議的更多功能

4.1基于多跳全同態加密方案的安全多方計算

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

4.2 基于多比特全同態加密的安全多方計算

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

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

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

5 其他的基于全同態加密的安全多方計算

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

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

6 結論

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

參考文獻：

[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.

基金項目：廣州市教育局協同創新重大項目（1201610005）

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