基于云計算服務的安全多方計算

蔣 瀚 徐秋亮

(山東大學計算機科學與技術學院 濟南 250101) (jianghan@sdu.edu.cn)

?

基于云計算服務的安全多方計算

蔣 瀚 徐秋亮

(山東大學計算機科學與技術學院 濟南 250101) (jianghan@sdu.edu.cn)

云計算的出現及迅速發展，使得安全多方計算模型面臨結構上的變化.云計算資源的引入，使得安全計算的計算任務、參與方、計算執行的外部環境變得多樣和復雜.利用強大的云計算資源來設計、實施安全多方計算協議，成為安全多方計算領域一個新的研究課題.云計算環境為安全多方計算的實施提供了條件，同時但也帶來新的挑戰.對云環境下通用安全多方計算協議的研究進行了梳理和分析，給出一個較為清晰的發展脈絡，對一些基于云的典型特定安全多方計算協議做了簡要介紹，并對目前云中安全多方計算存在的問題及未來研究的方向提出了自己的見解.

安全多方計算；云計算；云輔助安全多方計算；安全外包計算

2006年3月亞馬遜推出Web服務(Amazon Web services, AWS),2006年8月Google在搜索引擎大會上首次提出“云計算”的概念.之后，云計算的發展迅速形成燎原之勢，并引發了第三次信息技術革命的浪潮.

美國國家標準與技術研究院(National Institute of Standards and Technology, NIST)定義云計算是一種按使用量付費的模式，這種模式提供可用的、便捷的、按需的網絡訪問，進入可配置的計算資源共享池(資源包括網絡、服務器、存儲、應用軟件、服務)，這些資源能夠被快速提供，只需投入很少的管理工作，或與服務供應商進行很少的交互.從這個定義中可以看出，在云計算環境中，用戶的數據和計算都被移植到一個外部的、虛擬化的“云端”，雖然這種計算模式可以簡化用戶對信息系統的維護工作，但同時也為信息安全帶來新的挑戰.

云計算面臨的主要安全風險是數據的泄漏、丟失以及隱私泄漏，因此從信息安全的角度，比之傳統互聯網環境，我們更加需要對數據的機密性、完整性以及隱私性等進行保護.不同于傳統的計算場景，云服務用戶需要把數據和計算外包給云，因此將失去對資源的完全掌控權.如何利用密碼技術解決這種新形勢下的信息安全問題，成為云計算研究領域目前最為迫切、最被關注的問題之一.

安全多方計算(secure multi-party computation, SMPC)是解決云計算安全的關鍵技術之一.在安全多方計算場景中，持有秘密輸入的兩方或者多方，希望共同計算一個函數并得到各自的輸出，在這個過程中，除了得到應得的輸出(及可以由輸出推導而來的信息)之外，參與方得不到任何額外信息.安全多方計算的這一特點，對于云計算的安全保障有得天獨厚的優勢.

Fig. 1 IdealReal simulation paradigm.圖1 理想現實模擬范例

安全多方計算自20世紀80年代由姚期智提出[1]之后，經過幾十年的研究，積累了豐富的理論成果，促進了零知識證明、不經意傳輸、秘密共享等密碼學基礎原語的發展，奠定了安全協議可證明安全理論基礎，極大地推動了現代密碼學進展.而在當前云計算廣泛應用與發展的新背景下，安全多方計算同樣構成云計算環境下應用密碼學的理論基礎，其安全模型的定義及安全性證明的方法是各類安全協議的共用技術，對一些特定問題安全計算高效實現的研究，則具有重要應用意義.

1 基于云的通用安全多方計算

因為任意可計算的函數都存在一個與之等價的電路，因此通過對電路門的依次安全計算可以解決任意可計算函數的安全計算問題，以此為基礎的安全計算協議一般稱為通用的安全多方計算協議.

通用的安全多方計算協議雖然可以解決一般性的安全多方計算問題，但是計算效率很低，盡管近年來研究者努力進行實用化技術的研究，并取得一些成果，但是還不能真正實用.

安全多方計算協議的執行會受到某個外部敵手或者某些內部參與方的攻擊，因此，在安全多方計算的安全模型中，定義了一個敵手，這個敵手可以控制一個腐化的參與方子集，這種定義方式涵蓋了外部攻擊、內部攻擊及各類合謀攻擊的場景.而敵手類型按照行為可以分為半誠實的、惡意的及隱蔽的等.

通用安全多方計算效率較低是由2個主要因素疊加而成的：1)為了解決通用性而將函數運算分解為電路門運算；2)為了抵抗敵手的攻擊而依次對每個電路門實施安全計算.而云計算的出現改變了現有的計算模式，為提高通用安全多方計算效率提供了一些新的可能性.既然云作為一種強大的外部計算資源，那么我們完全可以將安全多方計算中的那些復雜的計算任務安全外包給云，從而極大地簡化參與方的計算負載，變相提高協議的計算效率.

在云計算概念出現之前，Feige等人就基于第三方服務器，提出了對安全兩方計算的一個擴展[2]：除了2個參與方Alice和Bob之外，增加了一個稱為Carol的服務器，用于執行協議的相關操作.該協議的通信模式是“最小”的：Alice和Bob協商(或被給定)一個秘密的隨機串，然后他們每人向Carol發送一個消息，這個消息實際是他們利用自己的秘密輸入和隨機值計算出來的.基于從Alice和Bob收到的消息，Carol計算函數值并宣布計算結果.注意在這種模式下，計算結果是盲化的，Carol不能得到Alice和Bob輸入的任何知識.

一般來說，通用的安全多方計算協議主要有3類，基于Yao混亂電路的構造方法[1]、基于秘密分享的構造方法[3]以及基于同態加密的構造方法[4]，下面分別基于這種分類來介紹云中的通用安全多方計算協議.

1.1 云中基于Yao混亂電路的安全兩方計算協議

基于Yao混亂電路的安全兩方計算協議將任意的功能函數看作是一個等價的邏輯電路，由基本的與門、或門、非門組成，而協議的參與方分為電路生成方和電路計算方.最初的Yao協議[1]，對于每一個基本的邏輯電路門，電路構造方針對電路門的每一條輸入輸出線上的真值選擇一個隨機數與之對應.而對于該邏輯電路的計算真值表，將2條輸入線上的輸入真值對應的隨機數作為密鑰，利用一個對稱加密算法，雙重加密輸出線上輸出真值對應的隨機數，以構造一個混亂表.隨后，電路構造方將以自己實際輸入對應的隨機數發送給電路計算方，然后通過一個不經意傳輸協議，把與電路計算方實際輸入真值對應的隨機數發送給電路計算方.電路計算方拿到2個隨機數后，作為解密密鑰，雙重解密混亂表里的密文，得到唯一正確的、與輸出真值對應的隨機數.如果該邏輯門是最終的輸出門，電路計算方通過查詢輸出線的真值-隨機數對應表，可以得到最終輸出的真值.可以看到，在基于Yao混亂電路的安全兩方計算協議中，電路生成和電路計算都是復雜的計算任務.

2011年Kamara等人首先研究了將基于Yao混亂電路的通用安全多方計算協議中參與方的復雜計算任務外包給服務器[5].在他們的設定中，除了要計算函數的參與方之外，還有一個不可信的服務器(云)，該服務器：1)沒有函數的輸入；2)得不到函數的輸出；3)具備強大(但是有界)的計算資源.這種設置被稱為服務器輔助的安全多方計算(或云輔助的安全多方計算).雖然這篇文章的動機不同于Feige等人[2]的工作，但他們的想法類似.

在考慮外包場景時，電路生成或計算均可以外包給云服務器，將任務外包出去的參與方即稱為外包方，而其他參與方即為非外包方.Kamara定義的效率目標非常明確，就是計算任務外包之后，外包方的計算量、通信量只與他的輸入輸出相關，而與要計算的函數規模無關.這個目標事實上已經最小化了外包方的工作量，因為即使在理想世界中，參與方的計算量、通信量也與他的輸入輸出相關，因為他至少需要向可信第三方上傳輸入，同時要從可信第三方獲得輸出.

為了安全地實現這一效率目標，Kamara等人首先提出了服務器(云)輔助安全多方計算的形式化定義，在他們的定義中，云服務器被看作一個特殊的參與方，它擁有強大的計算能力，但是沒有輸入輸出，這一點本質上沒有改變安全多方計算的定義.但是不同于傳統的惡意敵手攻擊下的安全模型，在Kamara等人的定義安全模型上，要求普通參與方與服務器之間不存在合謀.他們這樣規定的原因在于，依照安全多方計算的敵手模型，相互合謀的參與方事實上是由一個敵手刻畫的，因此他們退化成一個參與方.如果允許普通參與方與服務器合謀，那將違背外包計算的效率目標.舉例來說，當電路計算任務被外包給云服務器時，如果存在一個電路生成方(非外包方)可以與云服務器合謀，那么云輔助的安全多方計算協議將退化成一個安全兩方計算協議，而且一方(電路計算方)的計算效率僅與他的輸入輸出有關.而Damg?rd等人在文獻[6]中指出，達到該復雜度的安全兩方計算協議，只能通過全同態加密實現(也就是說無法通過混亂電路實現).鑒于文獻[5]的方案是基于Yao混亂電路構造的，因此為達到效率目標，Kamara等人在安全模型中引入了額外的假設：1)云服務器是惡意的但是不與其他參與方合謀，其他參與方是半誠實的；2)至少有一個參與方不是惡意的，云服務器是半誠實的.

很明顯，Kamara等人的非合謀模型相對于標準惡意模型是較弱的，但是與半誠實模型相比則更強，而且也有著廣泛的應用背景，在文獻[5]中，基于他們定義的安全模型，Kamara等人構造了一個電路計算任務外包的服務器輔助安全多方計算協議.隨后Kamara等人在工作[5]的基礎上，針對安全函數計算(secure function evaluation, SFE)問題，提出云輔助的安全函數計算的概念[7]，并構造了高效的單一服務器輔助的安全函數計算協議.此外，該文還通過擴展云輔助模型，實現了安全函數計算的公平性.

Kamara等人的上述工作奠定了基于Yao混亂電路的云輔助安全多方計算協議的基礎.此后，基于特定的應用背景，不同的外包計算任務、及不同服務器的數量，又出現了一些研究成果.

隨著便捷移動設備的不斷推廣，在這些計算能力有限的設備上進行復雜運算成為一個新的廣受關注的研究方向.Carter等人研究移動設備的外包安全函數計算問題[8]，事實上，他們的方案是基于Cut-and-Choose技術的Yao混亂電路兩方安全計算協議的，他們將移動設備看作電路計算方，將電路計算任務安全外包給云服務器.在基于Yao混亂電路的通用兩方安全計算協議中，Cut-and-Choose技術用于實現抵抗惡意敵手攻擊，電路生成方需要構造多個混亂電路的副本，供電路計算方選擇進行檢測或計算.雖然Cut-and-Choose技術有效提高了惡意敵手下安全兩方計算的效率，但協議參與方仍需要完成大量的計算任務，諸如多個電路副本的構造、輸入一致性檢測、混亂電路相關密鑰傳輸、電路計算等.

文獻[8]針對基于Cut-and-Choose技術的Yao混亂電路兩方安全計算協議中不同的計算任務，提出了在云環境下實現數據隱私性保護的實現機制.具體地，針對混亂電路密鑰傳輸問題，該文提出外包茫然傳輸機制，旨在將茫然傳輸過程中涉及到的復雜計算任務外包給云服務器.針對混亂電路的正確性檢測以及電路生成方輸入一致性檢測問題，該文給出了外包的電路正確性檢測和輸入一致性驗證機制.該驗證機制完全由云服務器執行，既避免了惡意的電路生成方通過惡意構造混亂電路從而獲取對方輸入的惡意行為，也使得作為電路計算方的移動設備不需要耗費過多的計算量.此外，該機制也有效地阻止了云服務商的不誠實行為，迫使云服務器必須返回正確的驗證結果.針對電路計算問題，在保證輸出信息保密的前提下，云服務器完成所有計算電路的計算和輸出一致性驗證，最后參與方輸出各自的輸出.該文章給出了外包協議的性能測試數據，協議的運行時間和帶寬分別降低了98.92%和99.95%.為了更好地說明云輔助安全計算協議的實用性，文章針對Dijkstra’s最短路徑算法實現了有效的外包轉換，為如何設計隱私保護的導航應用系統指明了方向.

與文獻[8]中構造的場景不同，Carter等人隨后將移動設備設定為混亂電路生成方，并將電路的生成任務安全外包給不可信的云服務器[9].雖然只是角色的轉換，但是外包協議的設計和安全性證明都具有很多的不同.混亂電路的生成外包主要運用到2-Universal Hash Function技術，而且協議過程中也避免了外包茫然傳輸機制的使用，從而使得電路生成方的計算復雜度與電路大小不相關.考慮到安全性，該文首次考慮了一種不同于文獻[5]中非合謀假設所預設的合謀場景，即允許電路生成方(外包方)與云服務器合謀，并形式化地證明了在該合謀場景下，所設計的外包安全兩方計算協議的安全性.此外，針對某些具體的函數，該文給出了上述協議的性能評估.這些函數主要包括海明距離計算、矩陣相乘、Dijkstra算法、RSA函數等，主要思想是針對這些函數對應的電路構造，比較計算外包前后在移動設備上需要執行的時間和帶寬.測試結果顯示，借助于云計算的輔助，移動設備的效率得到明顯的提高.

以上工作主要考慮單一云服務器輔助模型，Kerschbaum等人針對Yao混亂電路的外包計算，將計算分給2個或多個相互獨立的服務器，這些服務器在計算時合作但是不共享數據[10].該文提出了茫然外包計算的概念，即一個服務器不知道其他服務器是否參與外包計算，并基于格密碼構造了一個混亂電路生成外包方案，使得電路生成效率得以提高，但是并不增加電路的計算量.該文主要實現以下3種茫然性，即輸入輸出茫然性、函數茫然性以及外包茫然性.此外，針對Ajtai和SHA-3密碼學Hash函數，秘密分享的生成和組合問題，作者給出了具體的性能測試，結果顯示外包方案的效率較之于參與方本地實現，有明顯的提高.

隨著云存儲的不斷發展，在不同的應用中重復使用云中的數據也日益成為信息共享的發展趨勢.Mood 等人研究了安全函數計算過程中加密數據的再次使用問題[11].因為移動設備上的操作具有連續性，所以將計算過程中的狀態信息存儲下來，在其他計算需要的時候重新利用，可以使得效率大大提升.該文針對基于Yao混亂電路的函數計算問題，研究如何重復使用混亂電路計算過程中的加密值，從而降低重復操作.該文提出PartialGC的概念，基本思想是將一個大的程序分割成許多小片，并在混亂電路計算過程中引入交互式IO操作，這也是在基于Cut-and-Choose技術的混亂電路安全計算問題中首次允許交互式IO操作.

1.2 云中基于秘密共享的安全多方計算協議

在基于秘密共享的安全多方計算協議中，任意的功能函數被看作是一個算法電路，由基本的加法門和乘法門構成.對于每個基本的運算門，電路的輸入以一種秘密共享的方式分享于各個協議的參與方，而協議的參與方以共享份額作為輸入，針對加法門和乘法門的不同，執行不同的交互協議，完成電路門的計算，而計算結果(加法和或者乘法積)，也是以一種共享份額的形式，分享于參與方.可以看到，在基于秘密共享的安全多方計算協議中，加法門和乘法門的交互計算是其中復雜的計算任務，它即需要參與方做大量的計算，又需要參與方之間多次的交互.

Jakobsen等人研究將基于秘密共享的安全多方計算協議中n個參與方之間的算法電路門計算的交互協議，外包到m個云服務器(文中稱為Workers)來做[12].在他們的安全模型中，云服務器可以是不可信的，但前提是至少有一個服務器是誠實的，并且不需要文獻[5]中規定的非合謀這一弱安全假設.他們的安全目標是同時滿足隱私性和正確性要求，即每個參與方的輸入(對其他用戶和每個云服務器)是保密的，同時每個用戶都能得到正確的結果，即使惡意的云服務器依然無法篡改每個用戶應該得到的輸出.而他們協議的效率目標是參與方的通信復雜度最小(僅上傳輸入和接收輸出)，同時也盡可能減少所有服務器的工作量.

文獻[12]分別給出了半誠實參與方和惡意參與方模型下安全的方案.具體來講，半誠實參與方協議較為平凡，主要分為3個步驟：1)每個用戶通過秘密分享方案將自己的輸入和一個盲化值(其中盲化值用于盲化功能函數的輸出結果，從而功能函數的輸出對云服務器來說是保密的)分享給m個Workers；2)在這些Workers之間運行一個現有的安全多方計算協議，該協議的運行結果為每個用戶的盲化輸出(用戶的真實輸出加上他的盲化值);3)每個Worker將盲化輸出值分享給用戶，每個用戶使用來自于各個Worker的份額恢復出自己的盲化輸出，減去自己的盲化因子便得到各自的輸出.

但是對于惡意敵手模型，上述協議有3個問題需要解決：1)惡意的Worker可能會篡改來自用戶的輸入，因此，需要在各個Worker拿到各自輸入之后，先運行一個校驗協議，來確認每個Worker輸入到Worker之間的安全多方計算協議是正確的輸入值;2)惡意的服務器在輸出的時候，可能會輸出錯誤的結果;3)協議的公平性未得到保障，即由于Worker或者參與方發現錯誤而終止協議，會導致有的用戶得到了輸出，有的用戶沒有得到輸出.對于2),3)，可以通過修改Worker之間安全多方計算的功能函數使得每個Worker都得到全部用戶的盲化輸出，之后都向全部用戶發送各自的盲化輸出，這樣，用戶可以校驗是否來自每個Worker的輸出都相同.這樣既可以發現Worker的惡意行為，又能保證要么所有的用戶都拿到輸出，要么任何一個用戶都拿不到輸出.

1.3 云中基于同態加密的安全多方計算協議

在傳統的安全多方計算現實世界的協議中沒有第三方的輔助，而在云計算環境下，云服務器可以視為一個第三方.如果把云服務器看作完全可信的，那么只要保證有一個可信信道，那就與理想世界完全相同，參與方將輸入發送給云服務器，由云服務器來計算功能函數，并將計算結果返回給各參與方即可.但是云服務器，特別是公共云服務器，不是被完全信任的，云計算要求保證參與方數據對云服務器的機密性.當全同態加密方案出現之后，參與方將各自輸入利用全同態密碼算法加密之后，上傳到云服務器，由云服務器對同態密文進行計算并返回結果，從而可以保證數據機密性.

上述平凡的思想存在一個問題，那就是全同態加密方案一般是有一對公私鑰，而在安全多方計算中有多個參與方，全同態加密方案的私鑰不能被任一個參與方掌握，因此，Asharov等人利用門限全同態加密方案(threshold fully homomorphic encryption, TFHE)，將同態私鑰共享于所有參與方，從而構造了一個云輔助的安全多方計算協議[13].具體來說，在運算之前，各參與方運行一個密鑰生成協議共同產生方案的公鑰，并且保留各自關于私鑰的秘密分享份額；然后各方將自己的數據加密，上傳到云服務器，由云服務器對密文進行同態計算并返回結果；最后各方運行解密協議對此結果進行解密以得到最終的計算結果.

由于通用的門限全同態加密方案相對低效，Asharov等人基于文獻[14-15]中的FHE方案給出了相對比較高效的TFHE方案的構造.文獻[14-15]中的FHE方案為密鑰加同態的，即多個私鑰的和所對應的公鑰即為這些私鑰所對應的公鑰之和；使用此公共公鑰加密所得到的密文，可以使用上述每個私鑰分別進行部分解密，然后利用這些部分結果解密出明文.Asharov的TFHE方案使用2輪即可產生所需要的公鑰(公鑰用于加密)與計算密鑰(計算密鑰用于對密文進行計算)：第1輪各方產生公共公鑰與各自的私鑰份額，第2輪各方產生公共的計算密鑰；并且使用一輪即可完成解密協議.基于此TFHE方案，他們又構造了4輪的基于云服務器的安全多方計算協議.第1輪，各參與方運行TFHE密鑰生成協議的第1輪并產生公共的公鑰；第2輪，各方運行TFHE密鑰生成協議的第2輪，產生公共的計算密鑰，并利用第1輪的公共公鑰將各自的輸入加密，廣播出去；第3輪，云服務器拿到方案的公鑰、計算密鑰以及所有的密文之后自行算出計算結果的密文然后將此密文廣播；最后，各參與方拿到計算結果的密文后運行解密協議即可得到真正的計算結果.在上述過程中，各參與方僅需要執行與TFHE相關的計算，而真正的計算任務則在云服務器進行.因此對各參與方來說，計算量不是很大.

該協議可以被證明在半惡意模型下安全，即模型中敵手基本遵照協議進行，但是可能會根據自己的視圖惡意地產生運算中使用的隨機數.因此，云服務器可以僅利用簡明非交互零知識論證系統(succinct non-interactive argument systems)，而不使用擲幣協議來證明它在誠實地執行協議，從而將其轉化為惡意敵手模型下安全的協議，轉化后的協議仍然可以在4輪內完成.

在文獻[13]所考慮的場景中，參與方需要在每次計算時，與參與這次運算的用戶共同臨時產生本次計算所需要的全同態密鑰.但在實際應用中，用戶更傾向于在系統建立之初就產生自己的公私鑰對，并長期使用.因此，López-Alt 等人提出了動態多方計算(On-the-Fly Multiparty Computation)的概念[16].在他們所考慮的場景中，用戶各自擁有長期的公私鑰對，并利用自己的公鑰加密自己的數據，然后將密文上傳到云服務器；當有計算任務需要執行時，云服務器利用相應的密文進行計算；最后，在計算完成后云服務器與相關的用戶共同執行多方解密協議，用戶得到最終結果.在解密過程中，要求計算量與具體計算任務無關.

在文獻[16]中，López-Alt 等人提出了多密鑰全同態加密方案(multikey fully homomorphic encryption, MFHE)，并基于此構造了On-the-Fly Multiparty Computation.本質上來說，MFHE還是一個全同態加密方案，但是運算可以在利用不同公鑰加密的密文之間進行；運算后的結果密文大小與運算電路以及運算中使用的密文個數無關，而僅與運算中涉及到的公鑰數量相關；要解密運算得到的結果密文，需使用涉及到的公鑰所對應的私鑰共同運算進行解密.López-Alt 等人觀察到NTRU加密方案[17-18]本身就在一定程度上滿足了上述要求，因此，他們使用了文獻[14-15]中的方法將NTRU轉化為MFHE方案.而在他們的On-the-Fly Multiparty Computation協議中，使用到了MFHE方案的這一特性，并通過一些合適的零知識證明系統與擲幣協議，將協議編譯成惡意敵手下安全的.

前面的工作對于解決云環境下多方計算的安全性問題有著很大的理論意義，但是他們所構造的協議的效率卻受到了全同態加密方案的制約.因此Peter等人僅利用加同態給出了一個實用的解決方案[19].Peter等人所考慮的場景與動態安全多方計算的場景類似，但是在他們的場景中，用戶并不需要交互式地對結果密文進行解密，與之相反，用戶僅需從云服務器將結果密文下載然后自行解密即可.為了達到這樣的效果，他們的協議中使用了一個帶有主私鑰的加同態加密方案[20](下文稱之為BCP方案，BCP方案除了用戶的公私鑰對之外，系統中還存在一個主私鑰，主私鑰可以用來解密在公開參數下使用任意公鑰加密的密文)，并假設用戶使用2個不合謀的云服務器，一個云服務器掌握加密方案的主私鑰，可以解密所有出現的密文；另一個云服務器保存所有的用戶密文.在用戶將數據上傳之后，二者可以運行安全多方計算協議自行計算出結果.具體來說，在系統建立階段，其中一個服務器S產生BCP方案的主私鑰與公共參數，隨后它公開此公共參數并自己保留主私鑰；然后用戶利用此公開參數產生自己的公私鑰對，利用公鑰加密自己的數據，并將密文上傳到另一個云服務器C；當有計算任務需要執行時，云服務器C和云服務器S共同完成此計算：1)C和S運行一個子協議，將所有用到的密文轉化成在某個特定公鑰下加密的密文，由于所使用的加密方案為加同態的，所以此時C和S可以利用文獻[4]中的基于加同態的安全多方計算方法在密文下進行函數運算，并保證C得到運算結果在特定公鑰下的密文；2)C和S執行另一個子協議，將此密文轉化成參與用戶所對應的公鑰下的密文；3)用戶僅需下載相應密文即可得到計算結果.在上述過程中，用戶僅需執行上傳和下載操作，并不需要進行額外的交互.

文獻[19]方案是在半誠實敵手模型下安全的，所有的用戶，包括云服務器，均為半誠實的.為了說明所構造的協議的高效性以及實用性，作者還在文中給出了協議各部分的實際運行時間，以及2個特定應用協議的總體運行時間(隱私保護的人臉識別以及隱私保護的智能測量).從這些實驗數據可以看出，文中的協議確實有很強的實用性.

1.4 云中通用安全多方計算協議的分析比較

從現有的研究結果可以看到，基于同態加密的云輔助安全多方計算，協議結構最為簡單，它對整個功能函數進行密態計算，避免了將任意功能函數轉化為相應的電路，然后依次對電路門進行安全計算.事實上，它將對任意功能函數的計算能力，封裝到全同態加密方案中.這類方法受到了全同態密碼算法的限制，目前的全同態密碼事實上也是針對電路設計的，并且效率完全無法實用.基于同態加密的云輔助安全多方計算真正實用還有待全同態加密算法進一步突破.但是，如果我們的目標不是解決所有的功能函數，對于某些特定的實際的計算任務，可能只需部分同態密碼算法即可完成，這時完全可以得到真正實用的方案，但這不是通用的方案.

而基于Yao混亂電路所構造的云輔助安全多方計算協議不需要使用低效的非對稱密碼操作，但是也存在2點不足：1)較之于基于同態加密的方案，其安全模型有所降低.因為在標準SMPC模型下，不誠實參與方是允許合謀的；然而上述安全模型要求不誠實參與方是不能合謀的.2)基于Yao混亂電路的協議要求至少一個非服務器參與方必須做與電路大小線性相關的工作；而在基于同態加密的方案中，所有非服務器參與方只需做與輸入輸出相關的工作.

基于秘密分享的云輔助安全計算協議，可以完全轉化為標準的安全多方計算協議，不需要在安全模型上做出進一步的改進，但是協議效率低.

2 基于云的幾類特定的安全多方計算協議

通用的云輔助安全多方計算協議雖然也能用于構建特定應用的外包方案，但其效率較低.因而設計針對于特定的應用設計專用的高效協議，逐漸受到研究者的重視.比如云環境下基于安全多方計算技術的秘密集合求交(private set intersection, PSI)、隱私保護的信息檢索(private information retrieval, PIR)、數據庫查詢和推薦系統等具體應用協議.

2.1 云輔助秘密集合求交

Freedman首先提出秘密集合求交協議[21].在秘密集合求交協議中，雙方希望得到他們所持有集合的交集，同時不向對方泄漏關于自己所持有的那個集合的任何信息.秘密集合求交協議在現實世界中有廣泛的應用，如數據挖掘、社交網絡分析及健康數據處理中的隱私保護等.

云輔助的集合求交方案，將集合求交任務交給云服務器，同時保證隱私性.Kerschbaum提出了抗合謀的外包秘密集合求交協議[22]，即用戶分別將自己的集合加密上傳到服務器之后，服務器計算得到用戶集合的交集并分別返回給用戶，在服務器和任意一個用戶合謀的情況下，該協議依然是安全的.文獻[22]中提供了2個外包協議，即服務器可獲得交集大小的協議，服務器無法獲知任何信息的協議.隨后，Kerschbaum又在文獻[23]中提出另一種解決方案，在該方案中用戶不是直接將集合的密文外包給云服務器，而是將集合轉換成相應的布隆過濾器(Bloom filter)，之后將布隆過濾器加密后外包給服務器.云服務器利用加密的布隆過濾器進行求交操作，因而，為了獲得求交結果用戶不得不自己保存整個集合的副本.

在文獻[24]提出的協議中，用戶首先對集合中的每個元素做一次Hash之后，再加上一個隨機值，以此來保證隱私性.隨后將處理后的集合上傳到云服務器，由云端在散列值下進行交集操作.文獻[25]類似于文獻[24]的方案，但提供了可驗證機制.文獻[24-25]都存在相同的信息泄漏量較大的問題.具體來說，服務器可獲知求交結果集合的基數；并且如果2個集合都和第3個集合求過交集，那么這2個集合是否有交集這一信息也被服務器知道了.

Kamara等人提供了較為完善、多個不同安全模型下可證明安全的云輔助集合求交方案[26](半誠實的和惡意的服務器)，同時給出了保證公平性和能夠隱藏交集大小的方案.具體來講，在半誠實模型下，用戶通過一個偽隨機函數對集合每個元素進行盲化，再利用一個偽隨機置換將集合內元素順序打亂.隨后將處理過的集合發送給云服務器，服務器只需直接在集合密文上做“求交”操作，而不需要任何的密碼學操作.之后服務器將所得交集的密文返回給用戶，而用戶利用偽隨機函數的逆過程，獲得交集的明文.在惡意服務器的模型下，為了防止服務器返回錯誤的求交結果，在半誠實模型下安全的協議的基礎上，用戶將集合的每個元素復制λ份，并在每一份后面聯接上相應的序號.當服務器返回求交結果后，用戶只需檢查每個元素的序號是否完備，便可知道服務器是否返回了錯誤結果.

Abadi等人提出了一個多用戶外包秘密集合求交協議[27]，允許無限多個用戶將自己的集合加密后，上傳到云服務器，只有在得到每個用戶的允許后，服務器才能夠求這幾個用戶的交集.另外，每個用戶在將他的集合外包給服務器之后，便可和其他不同集合的用戶進行求交操作(即和不同用戶的集合進行求交，不需要再用不同的密鑰進行重加密).在安全性方面，服務器無法獲得任何信息.

2.2 隱私保護的信息檢索及其外包

Chor等人最先提出隱私保護的信息檢索[28].隱私保護的信息檢索是一種隱私增強技術，它可以使客戶以一種隱私保護的方式來查詢一個數據庫.具體來說，它允許客戶從一個數據庫中檢索一些項目，但是不向服務器泄漏任何客戶檢索項目的信息.隱私保護的信息檢索的一個平凡的構造就是將數據庫整個下載到客戶端進行本地查詢，盡管這種方式可以達到理論上的安全性，但是對大數據庫來說，需要巨大通信帶寬及客戶端的存儲和計算能力.因此，一個可行的隱私保護的信息檢索方案除了需要滿足正確性和隱私性需求外，還要求協議的傳輸量遠遠小于整個數據庫的規模.

隱私保護的信息檢索本身就是一個客戶端服務器的結構，完全適合云計算的架構，但是傳統的隱私保護的信息檢索方案遇到云計算海量數據時，云端的計算效率急劇惡化.其原因在于，由于內存空間的限制，在運行該協議的時候需要將大量的數據從硬盤調度到內存，該調度過程(硬盤尋址與讀取)造成了極大的負載.Olumofin等人的實驗顯示[29]，傳統隱私保護的信息檢模式在數據量增加到TB級別的時候，僅執行云端的計算任務就需要10 min的時間.因而，學者希望針對云計算特定的高性能軟硬架構，來設計適應超大規模數據庫的隱私保護的信息檢方案.主要手段是利用MapReduce[30]范型將大數據庫下的查詢，分解成多個數據庫存儲上面的并行子查詢，而每個服務器上面子查詢，采用傳統的隱私保護的信息檢索方案即可達到效率要求[31-32].

上述方案都是針對公開數據的隱私保護的信息檢索，Jarecki等人提出了外包隱私保護的信息檢索[33]的概念：數據擁有者將自己的數據庫外包給了云服務商，用戶在得到數據擁有者授權后，可以獲取服務器上面相應的數據，其安全性要求，只有相應權限的用戶可以得到授權，而數據擁有者不知道用戶獲取了那些數據，同時云服務提供商既不能獲知存在其上面的數據信息，也不可知用戶查詢的具體內容.Huang 等人同時考慮了外包數據庫的茫然更新問題[34]，除需保證數據庫用戶訪問模式的隱私性之外，還需要保證數據庫本身及其更新模式不被云服務器獲取.

2.3 外包數據庫查詢及安全多方計算

在云計算數據即服務(data as a service, DaaS)模式下，用戶將數據庫外包到云服務器，隨后執行查詢操作，并得到相應的查詢結果.為了保護敏感數據的機密性，用戶需要將數據庫加密后，再上傳到云服務器，因而，如何在加密的數據上執行檢索操作是數據庫安全外包中的核心問題.

為了解決在加密數據上的查詢問題，一種稱為可搜索加密(searchable encryption, SE)的概念被提出，并有大量的構造方案出現.在將可搜索加密方案應用到加密數據庫查詢協議時，安全多方計算協議是一個重要的工具.例如在Cash等人提出的支持布爾查詢的大數據可搜索對稱加密方案[35]中，就使用了一個安全兩方計算協議，這樣既利用了數據擁有者的秘密陷門，又保護了陷門數據的機密性.

從安全多方計算的角度講，數據庫安全外包與檢索協議的功能函數分為2個階段：初始化階段與檢索階段.考慮到網絡狀況的限制，協議的設計希望達到最少的交互輪數和最小的通信量.Hazay等人[36]從安全多方計算的角度，在理論上系統地分析了在半誠實模型下，外包數據庫查詢協議的通信輪數和通信量的下界，并指出為設計出達到該下界的協議，可信的初始化階段和隨機預言機(Random Oracle)是必要的.同時給出了一個達到最小交互輪數和最小通信量的具體協議.

2.4 推薦系統

推薦系統也是一個很重要的多方應用協議.在一個推薦系統中，存在一個服務器與多個客戶，服務器利用客戶的個人信息為客戶推薦他可能需要的內容.推薦系統被廣泛的應用在電子商務、社交網絡、搜索引擎等應用中，并為人們獲取信息帶來了極大的便利.在一個沒有密碼學工具保護的推薦系統中，服務器可以分析掌握用戶的消費習慣等隱私信息，同時，惡意的服務器也會向用戶推薦一些不正確的內容(如那些用戶不需要，但產品供應方付出廣告費的內容).

Veugen等人針對推薦系統這一類特殊應用構造一個云輔助的安全多方計算協議[37].同文獻[19]類似，作者同樣利用2個不合謀的云服務器，具體來說，他們在2個服務器之間運行一個基于秘密分享的安全多方計算協議，而用戶僅需在協議執行之初向2個服務器上傳秘密分享份額，并在協議完成后下載相應的數據即可.

3 結束語

云計算環境正在逐步帶來一種新的資源組織、利用模式，在云計算環境下考慮各種安全協議的設計與實施已成為必然，安全多方計算協議也不例外.針對云計算環境建立新的安全多方計算協議的計算與安全模型是一個迫切的任務.

對于傳統的通用安全多方計算協議，安全理論上發展已經較為成熟.而對于云中的安全多方計算，現有的安全模型只是將云服務器看成普通參與方而納入原有的安全框架下，雖然這樣也可以設計和分析云中的安全多方計算協議，但這種方式不自然，反映不出云環境的特點，最終的結果就是設計出的協議只是將計算量遷移到云中，同時為了遷移計算量又帶來了相當大的額外計算負載，因此計算負載總量事實上是遠高于非云環境中的協議.這種問題的根源在于傳統的安全多方計算中理想現實模擬范例中，現實世界中都是平等的參與方，與云環境并不貼合.云作為無輸入輸出，并且具有超級計算能力的一方，與普通的參與方并不平等.而如果將云看作第三方，因為其不可信，又與理想世界不同，而且第三方與參與方的合謀會帶來新的問題.如何合理定義這種介于理想和現實之間的模型來反映云計算協議的特點，是一個需要進一步解決的難點.

隨著云計算的不斷發展，越來越多不同領域內的應用也逐漸轉移到云平臺上.針對這些特性找到合適的密碼學工具，包括安全多方計算工具是一個新興的、廣泛的研究領域.這些領域應用抽象成數學問題，其對應的功能函數可能有不同的特點，同時這些領域應用可能會要求不同的安全特性.對于這些問題，使用通用的安全多方計算協議效率較低，因此，針對具體問題設計特定的高效安全計算協議，具有很高的應用意義.

綜上所述，云不僅僅是一個強大的外部服務器，不僅僅可以作為安全多方計算的一個輔助設施，也應該能夠被利用來獨立可信地完成某些安全計算任務，另一方面，云本身所需要完成的計算任務，比如保護隱私的數據處理、加密數據的處理等，也應該能夠抽象成安全多方計算的任務來完成.云中的安全多方計算，從基礎理論到高層的應用，都有廣闊的研究空間.

[1]Yao A C C. How to generate and exchange secrets[C] //Proc of the 27th Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1986: 162-167

[2]Feige U, Kilian J, Naor M. A minimal model for secure computation (extendedabstract)[C] //Proc of the 26th ACM Symp on Theory of Computing. New York: ACM, 1994: 554-563

[3]Cramer R, Damg?rd I, Maurer U. General secure multi-party computation from any linear secret-sharing scheme[C] //Proc of the 19th Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2000: 316-334

[4]Cramer R, Damg?rd I, Nielsen J B. Multiparty computation from threshold homomorphic encryption[C] //Proc of the 20th Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2001: 280-300

[5]Kamara S, Mohassel P, Raykova M. Outsourcing multi-party computation[J/OL]. IACR Cryptology ePrint Archive, 2011 [2016-06-15]. http://eprint.iacr.org/2011/272

[6]Damg?rd I, Faust S, Hazay C. Secure two-party computation with low communication[C] //Proc of the 9th Theory of Cryptography Conf. Berlin: Springer, 2012: 54-74

[7]Kamara S, Mohassel P, Riva B. Salus: A system for server-aided secure function evaluation[C] //Proc of the 2012 ACM Conf on Computer and communications security. New York: ACM, 2012: 797-808

[8]Carter H, Mood B, Traynor P, et al. Secure outsourced garbled circuit evaluation for mobile devices[J]. Journal of Computer Security, 2016, 24(2): 137-180

[9]Carter H, Lever C, Traynor P. Whitewash: Outsourcing garbled circuit generation for mobile devices[C] //Proc of the 30th Annual Computer Security Applications Conf. New York: ACM, 2014: 266-275

[10]Kerschbaum F. Oblivious outsourcing of garbled circuit generation[C] //Proc of the 30th Annual ACM Symp on Applied Computing. New York: ACM, 2015: 2134-2140

[11]Mood B, Gupta D, Butler K, et al. Reuse it or lose it: More efficient secure computation through reuse of encrypted values[C] //Proc of the 2014 ACM SIGSAC Conf on Computer and Communications Security. New York: ACM, 2014: 582-596

[12]Jakobsen T P, Nielsen J B, Orlandi C. A framework for outsourcing of secure computation[C] //Proc of the 6th Edition of the ACM Workshop on Cloud Computing Security. New York: ACM, 2014: 81-92

[13]Asharov G, Jain A, López-Alt A, et al. Multiparty computation with low communication, computation and interaction via threshold FHE[C] // Proc of the 31st Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2012: 483-501

[14]Brakerski Z, Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE[J]. SIAM Journal on Computing, 2014, 43(2): 831-871

[15]Brakerski Z, Gentry C, Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping[C] //Proc of the 3rd Innovations in Theoretical Computer Science Conf. New York: ACM, 2012: 309-325

[16]López-Alt A, Tromer E, Vaikuntanathan V. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption[C] //Proc of the 44th Annual ACM Symp on Theory of Computing. New York: ACM, 2012: 1219-1234

[17]Hoffstein J, Pipher J, Silverman J H. NTRU: A ring-based public key cryptosystem[C] // Proc of the 5th Int Algorithmic Number Theory Symp. Berlin: Springer, 1998: 267-288

[18]Stehlé D, Steinfeld R. Making NTRU as secure as worst-case problems over ideal lattices[C] // Proc of the 30th Annual Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2011: 27-47

[19]Peter A, Tews E, Katzenbeisser S. Efficiently outsourcing multiparty computation under multiple keys[J]. IEEE Trans on Information Forensics and Security, 2013, 8(12): 2046-2058

[20]Bresson E, Catalano D, Pointcheval D. A simple public-key cryptosystem with a double trapdoor decryption mechanism and its applications[C] // Proc of the 2003 Int Conf on the Theory and Application of Cryptology and Information Security. Berlin: Springer, 2003: 37-54

[21]Freedman M J, Nissim K, Pinkas B. Efficient private matching and set intersection[C] // Proc of the 2004 Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2004: 1-19

[22]Kerschbaum F. Collusion-resistant outsourcing of private set intersection[C] //Proc of the 27th Annual ACM Symp on Applied Computing. New York: ACM, 2012: 1451-1456

[23]Kerschbaum F. Outsourced private set intersection using homomorphic encryption[C] //Proc of the 7th ACM Symp on Information, Computer and Communications Security. New York: ACM, 2012: 85-86

[24]Liu F, Ng W K, Zhang W, et al. Encrypted set intersection protocol for outsourced datasets[C] // Proc of the 2014 IEEE Int Conf on Cloud Engineering (IC2E). Piscataway, NJ: IEEE, 2014: 135-140

[25]Zheng Q, Xu S. Verifiable delegated set intersection operations on outsourced encrypted data[C] // Proc of the 2015 IEEE Int Conf on Cloud Engineering (IC2E). Piscataway, NJ: IEEE, 2015: 175-184

[26]Kamara S, Mohassel P, Raykova M, et al. Scaling private set intersection to billion-element sets[C] // Proc of the 2014 Int Conf on Financial Cryptography and Data Security. Berlin: Springer, 2014: 195-215

[27]Abadi A, Terzis S, Dong C. O-PSI: Delegated private set intersection on outsourced datasets[C] //Proc of the 2015 IFIP Int Information Security Conf. Berlin: Springer, 2015: 3-17

[28]Chor B, Goldreich O, Kushilevitz E, et al. Private information retrieval[C] //Proc of the 36th Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1995

[29]Olumofin F, Goldberg I. Revisiting the computational practicality of private information retrieval[C] // Proc of the 2011 Int Conf on Financial Cryptography and Data Security. Berlin: Springer, 2011: 158-172

[30]Dean J, Ghemawat S. MapReduce: Simplified data processing on large clusters[C] // Proc of the 6th Symp on Operating System Design and Implementation. San Francisco: USENIX Association, 2004: 107-113

[31]Blass E O, Di Pietro R, Molva R, et al. PRISM-privacy-preserving search in MapReduce[C] //Proc of the 2012 Int Symp on Privacy Enhancing Technologies Symp. Berlin: Springer, 2012: 180-200

[32]Mayberry T, Blass E O, Chan A H. PIRMAP: Efficient private information retrieval for MapReduce[C] //Proc of the 2013 Int Conf on Financial Cryptography and Data Security. Berlin: Springer, 2013: 371-385

[33]Jarecki S, Jutla C, Krawczyk H, et al. Outsourced symmetric private information retrieval[C] //Proc of the 2013 ACM SIGSAC Conf on Computer & Communications Security. New York: ACM, 2013: 875-888

[34]Huang Y, Goldberg I. Outsourced private information retrieval[C] //Proc of the 12th ACM Workshop on Privacy in the Electronic Society. New York: ACM, 2013: 119-130

[35]Cash D, Jarecki S, Jutla C, et al. Highly-scalable searchable symmetric encryption with support for boolean queries[C] // Proc of the Advances in Cryptology (CRYPTO 2013). Berlin: Springer, 2013: 353-373

[36]Hazay C, Zarosim H. The feasibility of outsourced database search in the plain model[J/OL]. IACR Cryptology ePrint Archive, 2014 [2016-06-15]. http://eprint.iacr.org/2014/706

[37]Veugen T, de Haan R, Cramer R, et al. A framework for secure computations with two non-colluding servers and multiple clients, applied to recommendations[J]. IEEE Trans on Information Forensics and Security, 2015, 10(3): 445-457

Jiang Han, born in 1974.Lecturer of Shandong University since 2009. His main research interests include cryptography and information security, especially secure multi-party computation.

Xu Qiuliang, born in 1960. Currently professor and PhD supervisor in Shandong University. His research interests include public key cryptography and multi-party secure computation.

Secure Multiparty Computation in Cloud Computing

Jiang Han and Xu Qiuliang

(SchoolofComputerScienceandTechnology,ShandongUniversity,Jinan250101)

The emergence and rapid development of cloud computing structurally change the computation models of secure multi-party computation. In cloud environment, the computation task, the participants and the external environment of secure multi-party computation are becoming diversified and complicated. Using huge cloud resources to design and implement the secure multi-party computation protocol becomes a new research area. Cloud computing provides the resources to implement secure multi-party computation protocols, meanwhile, it also brings new challenge. In this paper, a survey for generalmulti-party computation in cloud setting, as well as some specific cloud-based secure multi-party computation protocols are given. Also, our opinions of the problem in the current researches and the directions for future works on multi-party computation in cloud setting are proposed.

secure multiparty computation; cloud computing; cloud-assisted secure multiparty computation; secure outsourced computation

2016-06-16；

2016-09-08

國家自然科學基金項目(61572294)；山東大學基本科研業務費專項資金項目(2016JC029)

TP309

This work was supported by the National Natural Science Foundation of China (61572294) and the Fundamental Research Funds of Shandong University (2016JC029).