基于云計(jì)算服務(wù)的安全多方計(jì)算

蔣 瀚 徐秋亮

(山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 濟(jì)南 250101) (jianghan@sdu.edu.cn)

?

基于云計(jì)算服務(wù)的安全多方計(jì)算

蔣 瀚 徐秋亮

(山東大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 濟(jì)南 250101) (jianghan@sdu.edu.cn)

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

安全多方計(jì)算；云計(jì)算；云輔助安全多方計(jì)算；安全外包計(jì)算

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

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

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

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

Fig. 1 IdealReal simulation paradigm.圖1 理想現(xiàn)實(shí)模擬范例

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

1 基于云的通用安全多方計(jì)算

因?yàn)槿我饪捎?jì)算的函數(shù)都存在一個(gè)與之等價(jià)的電路，因此通過對(duì)電路門的依次安全計(jì)算可以解決任意可計(jì)算函數(shù)的安全計(jì)算問題，以此為基礎(chǔ)的安全計(jì)算協(xié)議一般稱為通用的安全多方計(jì)算協(xié)議.

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

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

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

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

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

1.1 云中基于Yao混亂電路的安全兩方計(jì)算協(xié)議

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

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

在考慮外包場(chǎng)景時(shí)，電路生成或計(jì)算均可以外包給云服務(wù)器，將任務(wù)外包出去的參與方即稱為外包方，而其他參與方即為非外包方.Kamara定義的效率目標(biāo)非常明確，就是計(jì)算任務(wù)外包之后，外包方的計(jì)算量、通信量只與他的輸入輸出相關(guān)，而與要計(jì)算的函數(shù)規(guī)模無關(guān).這個(gè)目標(biāo)事實(shí)上已經(jīng)最小化了外包方的工作量，因?yàn)榧词乖诶硐胧澜缰?，參與方的計(jì)算量、通信量也與他的輸入輸出相關(guān)，因?yàn)樗辽傩枰蚩尚诺谌缴蟼鬏斎?，同時(shí)要從可信第三方獲得輸出.

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

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

Kamara等人的上述工作奠定了基于Yao混亂電路的云輔助安全多方計(jì)算協(xié)議的基礎(chǔ).此后，基于特定的應(yīng)用背景，不同的外包計(jì)算任務(wù)、及不同服務(wù)器的數(shù)量，又出現(xiàn)了一些研究成果.

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

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

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

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

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

1.2 云中基于秘密共享的安全多方計(jì)算協(xié)議

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

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

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

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

1.3 云中基于同態(tài)加密的安全多方計(jì)算協(xié)議

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

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

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

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

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

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

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

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

1.4 云中通用安全多方計(jì)算協(xié)議的分析比較

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

而基于Yao混亂電路所構(gòu)造的云輔助安全多方計(jì)算協(xié)議不需要使用低效的非對(duì)稱密碼操作，但是也存在2點(diǎn)不足：1)較之于基于同態(tài)加密的方案，其安全模型有所降低.因?yàn)樵跇?biāo)準(zhǔn)SMPC模型下，不誠(chéng)實(shí)參與方是允許合謀的；然而上述安全模型要求不誠(chéng)實(shí)參與方是不能合謀的.2)基于Yao混亂電路的協(xié)議要求至少一個(gè)非服務(wù)器參與方必須做與電路大小線性相關(guān)的工作；而在基于同態(tài)加密的方案中，所有非服務(wù)器參與方只需做與輸入輸出相關(guān)的工作.

基于秘密分享的云輔助安全計(jì)算協(xié)議，可以完全轉(zhuǎn)化為標(biāo)準(zhǔn)的安全多方計(jì)算協(xié)議，不需要在安全模型上做出進(jìn)一步的改進(jìn)，但是協(xié)議效率低.

2 基于云的幾類特定的安全多方計(jì)算協(xié)議

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

2.1 云輔助秘密集合求交

Freedman首先提出秘密集合求交協(xié)議[21].在秘密集合求交協(xié)議中，雙方希望得到他們所持有集合的交集，同時(shí)不向?qū)Ψ叫孤╆P(guān)于自己所持有的那個(gè)集合的任何信息.秘密集合求交協(xié)議在現(xiàn)實(shí)世界中有廣泛的應(yīng)用，如數(shù)據(jù)挖掘、社交網(wǎng)絡(luò)分析及健康數(shù)據(jù)處理中的隱私保護(hù)等.

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

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

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

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

2.2 隱私保護(hù)的信息檢索及其外包

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

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

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

2.3 外包數(shù)據(jù)庫(kù)查詢及安全多方計(jì)算

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

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

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

2.4 推薦系統(tǒng)

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

Veugen等人針對(duì)推薦系統(tǒng)這一類特殊應(yīng)用構(gòu)造一個(gè)云輔助的安全多方計(jì)算協(xié)議[37].同文獻(xiàn)[19]類似，作者同樣利用2個(gè)不合謀的云服務(wù)器，具體來說，他們?cè)?個(gè)服務(wù)器之間運(yùn)行一個(gè)基于秘密分享的安全多方計(jì)算協(xié)議，而用戶僅需在協(xié)議執(zhí)行之初向2個(gè)服務(wù)器上傳秘密分享份額，并在協(xié)議完成后下載相應(yīng)的數(shù)據(jù)即可.

3 結(jié)束語

云計(jì)算環(huán)境正在逐步帶來一種新的資源組織、利用模式，在云計(jì)算環(huán)境下考慮各種安全協(xié)議的設(shè)計(jì)與實(shí)施已成為必然，安全多方計(jì)算協(xié)議也不例外.針對(duì)云計(jì)算環(huán)境建立新的安全多方計(jì)算協(xié)議的計(jì)算與安全模型是一個(gè)迫切的任務(wù).

對(duì)于傳統(tǒng)的通用安全多方計(jì)算協(xié)議，安全理論上發(fā)展已經(jīng)較為成熟.而對(duì)于云中的安全多方計(jì)算，現(xiàn)有的安全模型只是將云服務(wù)器看成普通參與方而納入原有的安全框架下，雖然這樣也可以設(shè)計(jì)和分析云中的安全多方計(jì)算協(xié)議，但這種方式不自然，反映不出云環(huán)境的特點(diǎn)，最終的結(jié)果就是設(shè)計(jì)出的協(xié)議只是將計(jì)算量遷移到云中，同時(shí)為了遷移計(jì)算量又帶來了相當(dāng)大的額外計(jì)算負(fù)載，因此計(jì)算負(fù)載總量事實(shí)上是遠(yuǎn)高于非云環(huán)境中的協(xié)議.這種問題的根源在于傳統(tǒng)的安全多方計(jì)算中理想現(xiàn)實(shí)模擬范例中，現(xiàn)實(shí)世界中都是平等的參與方，與云環(huán)境并不貼合.云作為無輸入輸出，并且具有超級(jí)計(jì)算能力的一方，與普通的參與方并不平等.而如果將云看作第三方，因?yàn)槠洳豢尚牛峙c理想世界不同，而且第三方與參與方的合謀會(huì)帶來新的問題.如何合理定義這種介于理想和現(xiàn)實(shí)之間的模型來反映云計(jì)算協(xié)議的特點(diǎn)，是一個(gè)需要進(jìn)一步解決的難點(diǎn).

隨著云計(jì)算的不斷發(fā)展，越來越多不同領(lǐng)域內(nèi)的應(yīng)用也逐漸轉(zhuǎn)移到云平臺(tái)上.針對(duì)這些特性找到合適的密碼學(xué)工具，包括安全多方計(jì)算工具是一個(gè)新興的、廣泛的研究領(lǐng)域.這些領(lǐng)域應(yīng)用抽象成數(shù)學(xué)問題，其對(duì)應(yīng)的功能函數(shù)可能有不同的特點(diǎn)，同時(shí)這些領(lǐng)域應(yīng)用可能會(huì)要求不同的安全特性.對(duì)于這些問題，使用通用的安全多方計(jì)算協(xié)議效率較低，因此，針對(duì)具體問題設(shè)計(jì)特定的高效安全計(jì)算協(xié)議，具有很高的應(yīng)用意義.

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

[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

國(guó)家自然科學(xué)基金項(xiàng)目(61572294)；山東大學(xué)基本科研業(yè)務(wù)費(fèi)專項(xiàng)資金項(xiàng)目(2016JC029)

TP309

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