李順東， 郭奕旻， 鞏林明

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院, 陜西 西安 710062)

多方保密計(jì)算研究綜述

李順東， 郭奕旻， 鞏林明

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院, 陜西 西安 710062)

總結(jié)多方保密計(jì)算研究中使用的同態(tài)加密、單向散列函數(shù)、秘密共享與不經(jīng)意傳輸?shù)然竟ぞ?；概括保密的科學(xué)計(jì)算、保密的計(jì)算幾何、保密的統(tǒng)計(jì)分析、保密的數(shù)據(jù)挖掘等研究?jī)?nèi)容與研究現(xiàn)狀；介紹多方保密計(jì)算的安全性定義及有待進(jìn)一步研究的問(wèn)題。

密碼學(xué)；多方保密計(jì)算；同態(tài)加密；不經(jīng)意傳輸；模擬范例

多方保密計(jì)算(secure multi-party computation, SMC)是由姚期智教授提出的百萬(wàn)富翁(Millionaires’ problem)問(wèn)題[1]延伸而來(lái)。多方保密計(jì)算協(xié)議是一種一般意義上的密碼學(xué)協(xié)議，廣義上說(shuō)很多密碼學(xué)協(xié)議如Diffie-Hellman密鑰交換協(xié)議、數(shù)字簽名協(xié)議、零知識(shí)證明協(xié)議、秘密共享協(xié)議、不經(jīng)意傳輸協(xié)議等都是多方保密計(jì)算協(xié)議的特例[1-2]。多方保密計(jì)算在密碼學(xué)與虛擬世界都有廣泛的用途，特別是它將成為網(wǎng)絡(luò)空間信息安全、隱私保護(hù)與云計(jì)算安全的一項(xiàng)關(guān)鍵技術(shù)。廣泛的應(yīng)用促使多方保密計(jì)算成為近幾年國(guó)際密碼學(xué)界的一個(gè)研究熱點(diǎn)，Goldwasser曾預(yù)言[3]：“多方保密計(jì)算今天所處的地位正是公開(kāi)密鑰密碼學(xué)10年前所處的地位，成為密碼學(xué)領(lǐng)域里一個(gè)極端重要的工具；豐富的理論將使它成為計(jì)算領(lǐng)域必不可少的組成部分；它在現(xiàn)實(shí)中的應(yīng)用才剛剛開(kāi)始?！?/p>

Goldreich，Micali和Wigderson等[2,4]深入地研究了多方保密計(jì)算的理論問(wèn)題，奠定了多方保密計(jì)算的理論基礎(chǔ)。他們做出了兩個(gè)方面的重要貢獻(xiàn)：(1)通過(guò)把多方保密計(jì)算問(wèn)題轉(zhuǎn)化成智力游戲，提出了通用的多方保密計(jì)算問(wèn)題協(xié)議；(2)設(shè)計(jì)了一個(gè)編譯器，給定一個(gè)半誠(chéng)實(shí)模型下保密計(jì)算f的協(xié)議π，該編譯器能夠編譯并輸出一個(gè)在惡意參與者模型下保密計(jì)算f的協(xié)議π′，實(shí)現(xiàn)了半誠(chéng)實(shí)模型協(xié)議到惡意模型協(xié)議之間的機(jī)械化轉(zhuǎn)化。這些工作的理論意義在于告訴我們?nèi)我獾亩喾奖Ｃ苡?jì)算問(wèn)題都是可以計(jì)算的，至少有很笨拙的解決方案。

但理論上的可解并不等于現(xiàn)實(shí)中的可解決，因?yàn)槔碚撋峡山鉀](méi)有考慮解決問(wèn)題所需要的時(shí)間，理論上的可解的問(wèn)題實(shí)際上可能需要數(shù)百個(gè)世紀(jì)才能從實(shí)際上解決，從實(shí)際使用的觀點(diǎn)看這些問(wèn)題實(shí)際是不可解的。所以理論上可解應(yīng)當(dāng)被看做是多方保密計(jì)算問(wèn)題可解的理論證明。實(shí)際上的可解性要求能夠給出問(wèn)題的多項(xiàng)式時(shí)間算法,因此理論上證明多方保密計(jì)算問(wèn)題的可解并不表示不再需要對(duì)這些問(wèn)題進(jìn)行研究，相反地，理論上的可解正是要告訴人們這些問(wèn)題需要進(jìn)行更深入的研究，根據(jù)實(shí)際問(wèn)題的具體特點(diǎn)找出針對(duì)這些問(wèn)題的高效解決方案。

受Goldwasser的預(yù)言與Goldreich的觀點(diǎn)激勵(lì)，密碼學(xué)研究者廣泛開(kāi)展了各種多方保密計(jì)算問(wèn)題的研究。這些問(wèn)題可以歸納為幾個(gè)大類:(1)保密的科學(xué)計(jì)算；(2)保密的統(tǒng)計(jì)分析；(3)保密的數(shù)據(jù)挖掘；(4)保密的計(jì)算幾何；(5)其他多方保密計(jì)算問(wèn)題。本文的目的不是要介紹各種多方保密計(jì)算問(wèn)題的應(yīng)用背景和具體的解決方案，而是介紹多方保密計(jì)算研究的通用工具、安全性證明方法、已經(jīng)研究的各種問(wèn)題并給出具體的參考文獻(xiàn)(應(yīng)用背景和解決方案可以從相應(yīng)的參考文獻(xiàn)中獲得)和有待進(jìn)一步研究的問(wèn)題。期望對(duì)進(jìn)行多方保密計(jì)算研究的科研人員有所幫助。

1 研究工具

研究多方保密計(jì)算需要用到的密碼學(xué)知識(shí)很多，包括各種對(duì)稱加密算法、各種公鑰加密算法、不經(jīng)意傳輸協(xié)議、單向散列函數(shù)等。除此之外還需要靈活運(yùn)用所學(xué)到的各種數(shù)學(xué)知識(shí)。但與多方保密計(jì)算關(guān)系最為密切的知識(shí)主要包括同態(tài)加密算法、秘密共享協(xié)議、單向散列函數(shù)和不經(jīng)意傳輸協(xié)議。

1.1 同態(tài)加密算法

同態(tài)加密算法(homomorphic encryption)是具有特殊性質(zhì)的一種加密算法[5]，是構(gòu)造多方保密計(jì)算最常用的一個(gè)模塊。通常一個(gè)公鑰加密方案ε由加密算法Encryptε、解密算法Decryptε和密鑰產(chǎn)生算法KeyGenε組成。其中密鑰產(chǎn)生算法KeyGenε是一個(gè)隨機(jī)化的算法，給它提供一個(gè)安全參數(shù)，它會(huì)輸出一個(gè)公鑰sk和私鑰pk。加密算法Encryptε利用公鑰對(duì)提供的明文進(jìn)行加密，輸出密文。解密算法Decryptε利用私鑰對(duì)輸入的密文進(jìn)行解密，恢復(fù)明文消息。如果(sk,pk)是由KeyGenε生成的，密文為

c=Encryptε，

那么明文

m=Decryptε。

一個(gè)同態(tài)加密方案除了上述三個(gè)算法之外，還有一個(gè)有效算法Evaluateε。給定一組密文

c=(c1,c2,…,ct)，

其中

ci=Encryptε(pk,mi),Evaluateε(pk,f,(c1,…,ct))=Encryptε(pk,f(m1,…,mt))，

也就是說(shuō)Encryptε(pk,mi)不需要私鑰，就可以從m1,…,mt的密文直接計(jì)算出f(m1,…,mt)的密文。

著名的RSA算法[6]的密鑰生成算法KeyGenε為：給定安全參數(shù)k，KeyGenε生成兩個(gè)k比特的素?cái)?shù)p,q；計(jì)算n=pq；隨機(jī)選擇一個(gè)e使得

gcd(e,(p-1)(q-1))=1

作為公鑰，計(jì)算一個(gè)滿足

ed=1 mod (p-1)(q-1)

的d作為私鑰。加密過(guò)程為

c=Encryptε(e,m)=mdmodn,Decryptε(d,c)=cdmodn。

RSA算法具有乘法同態(tài)性，因?yàn)?/p>

但是RSA是一個(gè)確定性的乘法同態(tài)加密算法，它對(duì)于選擇明文攻擊是不安全的，這一點(diǎn)影響了它在多方保密計(jì)算中的應(yīng)用。

y=αkmodp,

以(α,y)作為公鑰。加密m時(shí)選擇一個(gè)隨機(jī)數(shù)r，加密過(guò)程為

c=Encryptε(y,m)=(αrmodp,yrmodp)=(c1,c2),

解密過(guò)程為

ElGamal算法具有乘法同態(tài)性，因?yàn)?/p>

ElGamal加密方案是概率加密，所以廣泛應(yīng)用于多方保密計(jì)算。

Paillier加密方案[8]的密鑰生成算法KeyGenε為：給定安全參數(shù)k，KeyGenε生成兩個(gè)k比特的素?cái)?shù)p,q；計(jì)算

n=pq，λ=lcm(p-1, 1-1);

計(jì)算一個(gè)g使得

gcd (L(gλmodn2),n)=1,

其中L(x)定義為

公鑰為(g,n)，私鑰為λ。加密m時(shí)選擇一個(gè)隨機(jī)數(shù)r，加密過(guò)程為

c=Encryptε(g,m)=gmrnmodn2,

解密過(guò)程為

Paillier算法具有加法同態(tài)性，因?yàn)?/p>

Paillier加密方案是概率加密，所以也廣泛應(yīng)用于多方保密計(jì)算。

1.2 單向散列函數(shù)

單向散列函數(shù)Hash()是解決多方保密計(jì)算問(wèn)題的有力工具，有很多多方保密計(jì)算協(xié)議都是利用單向散列函數(shù)設(shè)計(jì)的。我們不討論單向散列函數(shù)的定義，只討論單向散列函數(shù)的性質(zhì)，這是應(yīng)用的關(guān)鍵。單向散列函數(shù)具有以下性質(zhì)。

(1) 給定消息M，很容易計(jì)算h=Hash(M)。

(2) 給定h=Hash(M)，根據(jù)h計(jì)算其逆M=Hash-1(h)很難。

(3) 給定M，要找到另一個(gè)消息M′，使得Hash(M)=Hash(M′)很難。

(4) 找出兩個(gè)隨機(jī)的消息M,M′，使得Hash(M)=Hash(M′)很難。

(5) 給定任意長(zhǎng)度的消息，其單向散列函數(shù)值的長(zhǎng)度(比特?cái)?shù))|Hash(x)|都是相等的。

(6) 如果對(duì)x作微小的改變，即使只改變一個(gè)比特，Hash(x)的值也會(huì)發(fā)生驚人的改變。

單向散列函數(shù)值比特?cái)?shù)的不同對(duì)單向散列函數(shù)的性質(zhì)有很重要的影響。比如我們選擇的長(zhǎng)度為1，并選擇二進(jìn)制數(shù)表示，那么這樣的函數(shù)值的值域就是{0,1}。隨便找兩個(gè)不同的自變量，它們的單向散列函數(shù)值都有可能相同，相同的概率為1/2。如果找三個(gè)不同的自變量，一定有兩個(gè)自變量的函數(shù)值是相同的。

一般來(lái)說(shuō)如果|Hash(x)|=l，則任意找兩個(gè)自變量，它們的單向散列函數(shù)值相同的概率為2-l。因此在密碼學(xué)應(yīng)用中必須選擇充分大的l，這個(gè)l一般要大于128。

不同的單向散列函數(shù)在設(shè)計(jì)時(shí)選擇了不同的比特?cái)?shù)值，比如MD4、MD5算法[9]選擇的是128，而美國(guó)的安全散列標(biāo)準(zhǔn)(secure hash standard,SHS)[10]中選用的安全散列算法(secure hash algorithm, SHA)選用的是160位的長(zhǎng)度。這樣，我們?nèi)我庹覂蓚€(gè)不同的自變量，它們的單向散列函數(shù)值相同的概率分別為2-128和2-160，這兩個(gè)概率是那樣的小，以至于我們可以認(rèn)為這樣的事情根本不可能發(fā)生?？梢哉J(rèn)為實(shí)際上不可能找到兩個(gè)不同的消息生成相同的單向散列函數(shù)值，這樣我們就可以將消息的單向散列函數(shù)值看作與消息是一一對(duì)應(yīng)的(概率意義下)。在某些使用中我們就可以用單向散列函數(shù)值代表消息，因?yàn)槭菃蜗虻?，這樣做并不會(huì)泄露相應(yīng)的消息，卻可以知道兩個(gè)消息是否相同。

1.3 不經(jīng)意傳輸協(xié)議

不經(jīng)意傳輸(oblivious transfer)的概念是由Rabin[11]提出的。不經(jīng)意傳輸解決這樣的問(wèn)題：Alice有k個(gè)消息，Bob想得到其中的一個(gè)，但不希望Alice知道他想得到哪一個(gè)；Alice希望Bob只能得到一個(gè)，而其他的消息一點(diǎn)都不泄露。不經(jīng)意傳輸?shù)挠袃煞N主要形式：1-out-of-2不經(jīng)意傳輸與1-out-of-k。在1-out-of-2不經(jīng)意傳輸中Alice有50%的機(jī)會(huì)將一個(gè)消息發(fā)送給Bob。發(fā)送的結(jié)果Bob可能得到了消息，也可能沒(méi)有得到，Alice不知道結(jié)果。在1-out-of-k不經(jīng)意傳輸中Alice有k個(gè)消息，Bob能得到一個(gè)消息，而對(duì)于得到的這個(gè)消息以外的其他消息則一無(wú)所知，Alice對(duì)于Bob得到哪個(gè)消息一無(wú)所知。1-out-of-k不經(jīng)意傳輸又有兩種情況，一種情況是Bob不能選擇得到那個(gè)消息，另一種情況Bob可以選擇想得到哪個(gè)消息。1-out-of-k不經(jīng)意傳輸是1-out-of-2不經(jīng)意傳輸?shù)淖匀粩U(kuò)展。此外，還有k-out-of-n不經(jīng)意傳輸。不經(jīng)意傳輸是解決多方保密計(jì)算的主要工具，許多多方保密計(jì)算問(wèn)題離開(kāi)這個(gè)工具就沒(méi)有解決辦法。多方保密計(jì)算中用的一個(gè)重要的隱私保護(hù)技巧就是將秘密進(jìn)行分割，所以常常需要用到秘密共享協(xié)議。

1.4 秘密共享

秘密共享就是利用適當(dāng)?shù)募夹g(shù)把一個(gè)秘密拆分成n個(gè)份額分發(fā)給n個(gè)人，任意多于t(t

2 研究領(lǐng)域

多方保密計(jì)算的研究領(lǐng)域非常廣泛，凡是一項(xiàng)計(jì)算所需要的數(shù)據(jù)由多方持有，而多方都想保護(hù)自己數(shù)據(jù)的機(jī)密性，同時(shí)又有參與計(jì)算的動(dòng)機(jī)，就需要多方保密計(jì)算。例如，若干個(gè)人想知道他們的工資的平均值(最高值)，而又不想讓別人知道自己的工資數(shù)，這時(shí)就需要多方保密計(jì)算協(xié)議來(lái)解決。多方保密計(jì)算所研究的問(wèn)題大體上可以分為以下幾類。

2.1 保密的科學(xué)計(jì)算

保密的科學(xué)計(jì)算研究的問(wèn)題有下面的幾種。

(1) 保密比較兩個(gè)數(shù)的大小問(wèn)題[1]，也就是著名的百萬(wàn)富翁問(wèn)題。

這個(gè)問(wèn)題提出的最早，研究得也最充分，目前這個(gè)問(wèn)題的解決方案有10多種[12-17]。有研究?jī)蓚€(gè)較小的自然數(shù)比較的；有研究?jī)蓚€(gè)大自然數(shù)比較的；有研究?jī)蓚€(gè)整數(shù)比較的，也有研究?jī)蓚€(gè)有理數(shù)比較的[18]。有基于公鑰密碼學(xué)的解決方案，也有基于對(duì)稱密碼學(xué)的解決方案。百萬(wàn)富翁問(wèn)題的一個(gè)變形被稱為社會(huì)主義百萬(wàn)富翁問(wèn)題[19]，也就是比較兩個(gè)數(shù)是否相等。這個(gè)問(wèn)題的解決方案也有10多種[19-20]。

(2) 研究?jī)蓚€(gè)集合的關(guān)系問(wèn)題，主要是計(jì)算兩個(gè)集合的交集，兩個(gè)集合的交集的勢(shì)，判斷兩個(gè)集合是否相等[21-27]。

這個(gè)問(wèn)題也有很多解決方案，其中最有代表性的方法是把集合的元素表示成多項(xiàng)式的根，再利用同態(tài)加密算法，把一個(gè)集合的元素保密地代入另一個(gè)集合的元素所構(gòu)成的多項(xiàng)式，保密計(jì)算多項(xiàng)式的值來(lái)判斷具體的一個(gè)集合的元素在不在另一個(gè)集合里，從而確定集合的交集。能夠保密計(jì)算交集，就能夠保密計(jì)算交集的勢(shì)，但有時(shí)候我們只希望計(jì)算交集的勢(shì)，而不希望泄露交集，這就需要設(shè)計(jì)另外的協(xié)議。當(dāng)一個(gè)集合只有一個(gè)元素時(shí)，集合交集的保密計(jì)算問(wèn)題就轉(zhuǎn)化為保密計(jì)算一個(gè)元素屬不屬于另一個(gè)集合。

(3) 保密的向量計(jì)算問(wèn)題[28-29]。

這個(gè)問(wèn)題在保密的數(shù)據(jù)挖掘[31-31]中有廣泛的應(yīng)用，所以在保密數(shù)據(jù)挖掘的環(huán)境下進(jìn)行了充分的研究。目前研究的問(wèn)題主要是保密的向量點(diǎn)乘(scalar product)問(wèn)題[32]。只涉及兩個(gè)向量的點(diǎn)乘問(wèn)題，又稱為2DNF(disjunctive normal formula)問(wèn)題[33]。這個(gè)問(wèn)題也有許多解決方案，基本上都是利用同態(tài)加密和隨機(jī)置換進(jìn)行。

(4) 其他保密的科學(xué)計(jì)算問(wèn)題。

這些問(wèn)題包括保密的最小二乘估計(jì)問(wèn)題[28]，保密的線性規(guī)劃問(wèn)題[28,34]，保密的多項(xiàng)式求值問(wèn)題[35]等等。

2.2 保密的統(tǒng)計(jì)分析

統(tǒng)計(jì)分析是數(shù)據(jù)處理的主要活動(dòng)，是科學(xué)研究中發(fā)現(xiàn)新知識(shí)的主要手段。當(dāng)數(shù)據(jù)分析需要在一些機(jī)密的數(shù)據(jù)集上進(jìn)行時(shí)，就需要采用多方保密計(jì)算技術(shù)。保密的統(tǒng)計(jì)分析是多方保密計(jì)算的一個(gè)實(shí)際應(yīng)用，主要是因?yàn)樵谛畔⑸鐣?huì)不同的主體擁有不同的數(shù)據(jù)，他們希望在這些數(shù)據(jù)的基礎(chǔ)上進(jìn)行一些各自都能受益的統(tǒng)計(jì)分析，但他們都不愿意將自己擁有的數(shù)據(jù)提供給其他人，這時(shí)就需要多方保密計(jì)算來(lái)幫助實(shí)施。

(2) 保密計(jì)算一組數(shù)據(jù)與另一組數(shù)據(jù)之間的相關(guān)系數(shù)(Correlation Coefficient)；保密計(jì)算一組數(shù)據(jù)與另一組數(shù)據(jù)之間的相關(guān)關(guān)系(線性回歸分析Linear Regression Line)[36-37]；保密的方差計(jì)算。解決這一類問(wèn)題需要用向量點(diǎn)乘協(xié)議、保密置換協(xié)議。相關(guān)系數(shù)的保密計(jì)算已經(jīng)是保密統(tǒng)計(jì)分析中能解決的比較復(fù)雜的問(wèn)題。更多的保密統(tǒng)計(jì)分析問(wèn)題，比如說(shuō)協(xié)方差、非線性回歸、參數(shù)估計(jì)等現(xiàn)在都還沒(méi)有辦法解決。

2.3 保密的數(shù)據(jù)挖掘

保密數(shù)據(jù)挖掘(privacy-preserving data-mining)是數(shù)據(jù)挖掘中非?；钴S的一個(gè)研究領(lǐng)域[30-31]。這里面研究的問(wèn)題非常多，也很有實(shí)際意義。應(yīng)用背景是：不同的實(shí)體收集了關(guān)于某些對(duì)象的不同屬性值，某個(gè)實(shí)體需要利用這些屬性值挖掘出關(guān)于這些數(shù)據(jù)的另外的屬性值或者各種屬性之間的規(guī)律，但擁有這些數(shù)據(jù)的實(shí)體因?yàn)閿?shù)據(jù)的機(jī)密性問(wèn)題，不愿意將數(shù)據(jù)直接提供給需要的實(shí)體。這里面研究的問(wèn)題主要有下面一些。

(1) 數(shù)據(jù)的保密線性回歸分析與保密分類[39-41]。

保密的線性回歸分析與保密統(tǒng)計(jì)分析中的保密線性回歸沒(méi)有差別，只是在數(shù)據(jù)挖掘中也非常普遍。而保密分類在通常的統(tǒng)計(jì)分析中研究的很少。在保密數(shù)據(jù)挖掘中是指根據(jù)預(yù)先知道的分類標(biāo)準(zhǔn)，通過(guò)對(duì)反映一些對(duì)象屬性的保密數(shù)據(jù)的保密計(jì)算，確定這些對(duì)象的某一子集與哪一類對(duì)象的屬性相符，從而把這個(gè)子集的元素分到對(duì)應(yīng)的類。

(2) 數(shù)據(jù)的保密聚類[42-43]。

聚類是將數(shù)據(jù)分類到不同的類或者簇的過(guò)程，使同一個(gè)簇中的對(duì)象有很大的相似性，而不同簇間的對(duì)象有很大的相異性。保密的聚類其實(shí)也是分類，只是分類時(shí)分類的標(biāo)準(zhǔn)是已知的，可能分成多少類也是已知的，聚類時(shí)所要求劃分的類是未知的，需要根據(jù)對(duì)象的屬性值的分布，利用一定的規(guī)則確定分類的標(biāo)準(zhǔn)和分類數(shù)。而保密的聚類則是在保證數(shù)據(jù)機(jī)密的前提下進(jìn)行聚類分析。

(3) 保密的關(guān)聯(lián)規(guī)則分析。

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中的一個(gè)重要研究?jī)?nèi)容，關(guān)聯(lián)規(guī)則挖掘完全是實(shí)用性的觀點(diǎn)，只是挖掘規(guī)則而不是發(fā)現(xiàn)規(guī)律。通常是指從購(gòu)物數(shù)據(jù)中挖掘出消費(fèi)者購(gòu)買的商品中，那些之間有關(guān)聯(lián)關(guān)系，也就是說(shuō)消費(fèi)者在購(gòu)買某種商品時(shí)通常還會(huì)購(gòu)買哪種商品。這方面的文獻(xiàn)有[44-45]。還有保密的決策樹(shù)構(gòu)建[46]。

保密的數(shù)據(jù)挖掘采用的技術(shù)有兩類，一類是基于隨機(jī)化擾動(dòng)的方法[47-48]，另一類是基于密碼學(xué)的方法[49]?；陔S機(jī)擾動(dòng)的方法是給所有數(shù)據(jù)加上一些符合某種統(tǒng)計(jì)特性的噪聲，比如給一組數(shù)據(jù)加上服從標(biāo)準(zhǔn)正態(tài)分布的噪聲數(shù)據(jù)。這樣添加噪聲后隱藏了原始的真實(shí)數(shù)據(jù)，但是不影響平均值的計(jì)算。這種方法盡管不會(huì)泄漏實(shí)際數(shù)據(jù)的全部信息，但實(shí)際上還是泄露了機(jī)密數(shù)據(jù)的大量信息，在需要保證數(shù)據(jù)機(jī)密的環(huán)境中，要進(jìn)行保密的數(shù)據(jù)挖掘，唯一可以選擇的方法就是基于密碼學(xué)的方法，而基于密碼學(xué)的方法主要是多方保密計(jì)算方法。

2.4 保密的計(jì)算幾何

保密的計(jì)算幾何[29]是多方保密計(jì)算的一個(gè)重要方面。這方面的研究問(wèn)題來(lái)源于計(jì)算幾何，研究成果的應(yīng)用則包括計(jì)算幾何、工程設(shè)計(jì)、化學(xué)工業(yè)等。主要問(wèn)題有下面幾類。

(1) 保密的點(diǎn)包含問(wèn)題。

Alice有一個(gè)點(diǎn)P(x,y)，Bob有一個(gè)幾何圖形G(可以是一個(gè)凸多邊形[29]、凹多邊形[50]、圓形、橢圓形[51]、四面體或者任意形狀[52])，他們兩個(gè)想保密地判定P在不在G內(nèi)?，F(xiàn)在關(guān)于凸多邊形、凹多邊形、圓形、橢圓形、四面體的問(wèn)題都有確定性的多方保密計(jì)算協(xié)議，而對(duì)于任意形狀的圖形則只有概率解決方法[53]。

(2) 保密的點(diǎn)線關(guān)系問(wèn)題與相交問(wèn)題[54-56]。

這一類問(wèn)題主要是為了解決點(diǎn)包含問(wèn)題而研究出的附帶的解決方案。這類問(wèn)題包括：一個(gè)點(diǎn)在不在一條直線上，一個(gè)點(diǎn)在不在一條曲線上，一個(gè)點(diǎn)在不在一條直線或者曲線的上方。兩個(gè)幾何圖形是否相交。

(3) 其他多方保密計(jì)算幾何問(wèn)題。

包括范圍搜索(range search)問(wèn)題，距離最近的點(diǎn)對(duì)(closest pair)問(wèn)題，最小的凸殼(convex hull)問(wèn)題。

2.5 其他保密計(jì)算問(wèn)題

多方保密計(jì)算是一個(gè)應(yīng)用非常廣泛的研究領(lǐng)域，除了密碼學(xué)者外，其他領(lǐng)域的學(xué)者從自己領(lǐng)域的問(wèn)題出發(fā)提出了許多交叉領(lǐng)域的研究問(wèn)題，由于版面所限，本文對(duì)這些問(wèn)題不做具體的介紹，只列出這些問(wèn)題和參考文獻(xiàn)，有興趣的讀者可以查閱有關(guān)的文獻(xiàn)。這些問(wèn)題包括

(1) 保密出版問(wèn)題[57-58]；

(2) 數(shù)據(jù)保密多關(guān)鍵詞排序問(wèn)題；

(3) 保密的數(shù)據(jù)庫(kù)查詢[59]；

(4) 保密的入侵檢測(cè)問(wèn)題；

(5) 保密的數(shù)據(jù)選擇問(wèn)題；

(6) 保密的排序問(wèn)題[60]；

(7) 保密的最短路徑選擇問(wèn)題[28]；

(8) 保密的多項(xiàng)式插值問(wèn)題。

3 安全性

多方保密計(jì)算的參與者有不同的類型，對(duì)于不同的參與者應(yīng)該有不同的保證機(jī)密性的技術(shù)。如果參與者都是善意的，安全就容易保證；如果是惡意的參與者，安全就很難保證。不管什么條件下，多方保密計(jì)算都不能解決下面的問(wèn)題：(1) 讓一個(gè)不愿意參與的人參與多方保密計(jì)算；(2) 讓任何參與者都輸入真實(shí)的數(shù)據(jù)；(3) 讓任何參與者都不中途退出。因此不要試圖設(shè)計(jì)能夠解決這些問(wèn)題的多方保密計(jì)算協(xié)議。

3.1 理想多方保密計(jì)算協(xié)議

理想的多方保密計(jì)算協(xié)議需要一個(gè)絕對(duì)可信的第三者，稱為T(mén)rent。假設(shè)Alice有機(jī)密數(shù)據(jù)x，Bob有機(jī)密數(shù)據(jù)y，他們要利用Trent保密地計(jì)算函數(shù)f(x,y)。協(xié)議如下。

(1) Alice把x發(fā)送給Trent；Bob將y發(fā)送給Trent。

(2) Trent計(jì)算f(x,y)。

(3) Trent將計(jì)算結(jié)果告訴Alice和Bob。

理想的多方保密計(jì)算協(xié)議是安全性最高的多方保密計(jì)算協(xié)議，也是最有威力的多方保密計(jì)算協(xié)議。所有多方保密計(jì)算協(xié)議的安全性都是通過(guò)與理想多方保密計(jì)算協(xié)議進(jìn)行對(duì)比來(lái)評(píng)價(jià)的。如果一個(gè)實(shí)際的多方保密計(jì)算協(xié)議不比理想多方保密計(jì)算協(xié)議泄露更多的關(guān)于機(jī)密數(shù)據(jù)x,y的信息，我們就說(shuō)這個(gè)多方保密計(jì)算協(xié)議是安全的。

但理想多方保密計(jì)算協(xié)議也有嚴(yán)重的實(shí)際問(wèn)題：(1) 在網(wǎng)絡(luò)環(huán)境中找到這樣絕對(duì)可信的第三者是困難的；(2) 用可信的第三者是有代價(jià)的；(3) 在網(wǎng)絡(luò)環(huán)境中，這樣的一個(gè)可信的第三者可能成為網(wǎng)絡(luò)的瓶頸。多方保密計(jì)算研究就是要研究不需要可信第三者的計(jì)算各種f(x,y)的協(xié)議。在多方保密計(jì)算研究中，往往假設(shè)參與者有兩種類型，再針對(duì)這兩種類型設(shè)計(jì)不同的協(xié)議。

3.2 半誠(chéng)實(shí)模型下的安全性

半誠(chéng)實(shí)的參與者模型是一個(gè)重要的模型，這是因?yàn)椋?1) 實(shí)際的許多參與者都是半誠(chéng)實(shí)的，所以對(duì)于半城實(shí)的參與者安全的多方保密計(jì)算協(xié)議實(shí)際上可以解決許多多方保密計(jì)算問(wèn)題；(2) Goldreich曾設(shè)計(jì)過(guò)一個(gè)編譯器，給編譯器輸入一個(gè)在對(duì)半誠(chéng)實(shí)參與者安全的多方保密計(jì)算協(xié)議，該編譯器能夠編譯輸出一個(gè)對(duì)惡意參與者也安全的協(xié)議。另一方面，當(dāng)人們研究惡意模型下安全的協(xié)議時(shí)，往往是先設(shè)計(jì)半誠(chéng)實(shí)模型下安全的協(xié)議，然后研究惡意的參與者會(huì)如何攻擊這樣的協(xié)議，找到防止惡意攻擊的方法并把防止的方法再添加到協(xié)議中，形成對(duì)惡意參與者安全的協(xié)議。所以研究半誠(chéng)實(shí)模型下安全的協(xié)議有實(shí)際的意義。

半誠(chéng)實(shí)參與者 許多論文所提方案的安全性均假設(shè)多方保密計(jì)算的參與者為半誠(chéng)實(shí)的參與者。簡(jiǎn)單地說(shuō)，所謂半誠(chéng)實(shí)參與者是指參與者在協(xié)議執(zhí)行過(guò)程中將不折不扣地執(zhí)行協(xié)議，但他們也會(huì)保留計(jì)算的中間結(jié)果試圖推導(dǎo)出其他參與者的輸入。

隱私的模擬范例 直觀上，如果對(duì)于任一個(gè)半誠(chéng)實(shí)的參與者，他都可以直接從執(zhí)行協(xié)議時(shí)自己的輸入與協(xié)議的最終輸出，通過(guò)單獨(dú)模擬協(xié)議的執(zhí)行過(guò)程而得到在執(zhí)行協(xié)議過(guò)程中他所能得到的任何信息，這樣的協(xié)議同理想的多方保密計(jì)算協(xié)議相比，沒(méi)有更多的信息泄露，協(xié)議就是保密的。即能夠保證輸入的隱私性。簡(jiǎn)單地說(shuō)，保密計(jì)算協(xié)議要求協(xié)議執(zhí)行過(guò)程中參與者所觀察到的內(nèi)容僅用他自己的輸入與輸出就可以進(jìn)行模擬。這就是多方保密計(jì)算保密性研究中常用的模擬范例。如果一個(gè)多方計(jì)算協(xié)議能夠這樣進(jìn)行模擬，參與者就不能從協(xié)議的執(zhí)行過(guò)程中得到除計(jì)算的結(jié)果之外任何有價(jià)值的信息，這樣的多方計(jì)算過(guò)程就是保密的。下面把這樣的直觀感覺(jué)形式化。

一些記號(hào) 首先引入以下記號(hào)，假設(shè)雙方計(jì)算的參加方分別為Alice和Bob。

? 設(shè)f=(f1,f2)是一個(gè)概率多項(xiàng)式時(shí)間函數(shù)，π表示計(jì)算f的雙方計(jì)算協(xié)議。

?輸入為(x,y)時(shí)，執(zhí)行協(xié)議π以后，Alice(Bob)的輸出結(jié)果記為

定義1(半誠(chéng)實(shí)參與者的保密性)[2]對(duì)于一個(gè)函數(shù)f，如果存在概率多項(xiàng)式時(shí)間算法S1與S2(有時(shí)稱這樣的多項(xiàng)式時(shí)間算法為模擬器)使得

有關(guān)計(jì)算不可區(qū)分的詳細(xì)論述請(qǐng)看文獻(xiàn)[2]。要證明一個(gè)多方計(jì)算方案是保密的，就必須構(gòu)造滿足定義1的模擬器S1和S2。

模擬范例實(shí)際上是把實(shí)際的多方保密計(jì)算協(xié)議與理想的多方保密計(jì)算進(jìn)行比較。因?yàn)榧词菇柚诳尚诺牡谌?，Alice(Bob)在得到f1(x,y)(f2(x,y))后也可以計(jì)算出有關(guān)y(x)的一些信息。如果根據(jù)自己得到的函數(shù)值能夠單獨(dú)計(jì)算出的信息和實(shí)際執(zhí)行協(xié)議所得到的信息是計(jì)算上不可區(qū)分的，我們就說(shuō)實(shí)際的協(xié)議是安全的，因?yàn)樗](méi)有泄漏比理想?yún)f(xié)議更多的、對(duì)于參與者計(jì)算另一方的輸入有價(jià)值的信息。

3.3 雙方與多方

多方保密計(jì)算有兩種情況：(1) 只有兩個(gè)參與者，這時(shí)的多方保密計(jì)算又稱為雙方保密計(jì)算；(2) 有三個(gè)以上的參與者(包括三個(gè))，這時(shí)稱為多方保密計(jì)算。

這兩種情況一般都需要分開(kāi)研究，因?yàn)槊糠N情況都有獨(dú)特的特征。有時(shí)候兩方保密計(jì)算的協(xié)議比較好設(shè)計(jì)，有時(shí)候多方保密計(jì)算協(xié)議比較好設(shè)計(jì)。雙方保密計(jì)算的協(xié)議通常都不能簡(jiǎn)單地推廣到多方的情況；多方保密計(jì)算協(xié)議用于雙方保密計(jì)算時(shí)通常不能保證安全。雙方保密計(jì)算需要研究半誠(chéng)實(shí)參與者，也需要研究惡意參與者，但不需要研究合謀；而多方保密計(jì)算不但需要研究半誠(chéng)實(shí)參與者、惡意參與者，還要保證合謀情況下的安全。

3.4 惡意模型下的安全性

惡意參與者模型是主動(dòng)攻擊者的模型，惡意模型下安全的協(xié)議無(wú)疑具有更高的安全性。雖然理論上說(shuō)有了半誠(chéng)實(shí)模型下安全的多方保密計(jì)算協(xié)議，可以自動(dòng)地得到在惡意模型下安全的多方保密計(jì)算協(xié)議，但這樣得到的協(xié)議是低效的，因此往往需要針對(duì)具體的惡意參與者設(shè)計(jì)在惡意的參與者情況下也安全的多方保密計(jì)算協(xié)議。

惡意參與者安全的多方計(jì)算協(xié)議要求：在理想的使用可信的第三者的多方保密計(jì)算協(xié)議中得不到的信息，在我們所設(shè)計(jì)的協(xié)議中也無(wú)法得到。這樣就保證了我們的協(xié)議和理想的多方保密計(jì)算協(xié)議一樣安全。但習(xí)慣上往往是反過(guò)來(lái)說(shuō)的，即所述為上述命題的逆否命題。

定義2(惡意參與者的保密性)[2]如果一個(gè)多方保密計(jì)算協(xié)議π中的任意惡意行為能夠成功實(shí)施的話，在理想的多方保密計(jì)算協(xié)議Π中也能夠成功實(shí)施這樣的惡意行為。

4 有待研究的問(wèn)題

(1) 保密的科學(xué)計(jì)算

這里面還沒(méi)有解決的問(wèn)題非常多，比如說(shuō)保密計(jì)算

max(x1,…,xn), min(x1,…,xn),gcd(x1,…,xn), lcm(x1,…,xn)。

這些問(wèn)題現(xiàn)在還沒(méi)有好的解決方案。在集合的保密計(jì)算方面人們也進(jìn)行了充分的研究，但是判斷兩個(gè)集合的并集、一個(gè)集合是不是另一個(gè)集合的子集這類問(wèn)題也沒(méi)有好的解決方案。一般的多方保密計(jì)算要求保密計(jì)算函數(shù)z=f(x,y)，其中x,y分別為不同的參與者所擁有。但現(xiàn)在只能計(jì)算最簡(jiǎn)單的函數(shù)，比如

等一些非常簡(jiǎn)單的函數(shù)，現(xiàn)在稍微復(fù)雜一點(diǎn)的還都不能計(jì)算，所以多方保密計(jì)算可以研究的問(wèn)題還很多，但是這些問(wèn)題的難度也比較大。

(2) 保密的統(tǒng)計(jì)分析

在保密的統(tǒng)計(jì)分析中，利用多方保密計(jì)算所能計(jì)算的統(tǒng)計(jì)量和統(tǒng)計(jì)結(jié)果是非常有限的，因而還有許多工作可做。如果有一天可以利用多方保密計(jì)算獲得所有的統(tǒng)計(jì)量和所有希望的統(tǒng)計(jì)結(jié)果，那么現(xiàn)在各個(gè)實(shí)體所收集的保密數(shù)據(jù)都能夠發(fā)揮應(yīng)有的作用，將會(huì)給我們的社會(huì)帶來(lái)巨大的數(shù)據(jù)效益與經(jīng)濟(jì)效益。

(3) 保密的數(shù)據(jù)挖掘

目前用多方保密計(jì)算技術(shù)來(lái)實(shí)現(xiàn)保密的數(shù)據(jù)挖掘存在的主要問(wèn)題是：數(shù)據(jù)挖掘的數(shù)據(jù)集都是巨大的，數(shù)據(jù)極多，而多方保密計(jì)算都需要高強(qiáng)度(高復(fù)雜性)的計(jì)算，這兩者綜合作用的結(jié)果造成保密的數(shù)據(jù)挖掘效率極低，成本極高。而采用隨機(jī)擾動(dòng)的辦法不能真正保證數(shù)據(jù)的機(jī)密。所以需要進(jìn)行兩方面的工作，一是設(shè)計(jì)高效的多方保密計(jì)算協(xié)議，尤其是基于對(duì)稱密碼學(xué)理論的協(xié)議；而是設(shè)法提高基于隨機(jī)擾動(dòng)方法的協(xié)議的安全水平。

(4) 保密的計(jì)算幾何問(wèn)題

保密的計(jì)算幾何問(wèn)題有很強(qiáng)的實(shí)際應(yīng)用背景，但目前解決計(jì)算幾何問(wèn)題的多方保密計(jì)算協(xié)議需要的計(jì)算量都非常大，效率很低。所以保密的計(jì)算幾何研究主要是探索新的計(jì)算幾何問(wèn)題，同時(shí)大力改進(jìn)現(xiàn)有解決方案的效率，使有關(guān)的協(xié)議可以用于解決實(shí)際問(wèn)題。

(5) 惡意模型下的多方保密計(jì)算協(xié)議

目前的研究成果集中在半誠(chéng)實(shí)模型下的多方保密計(jì)算協(xié)議，這是有原因的。因?yàn)樵趯?shí)際工作中多數(shù)參與多方保密計(jì)算的人都是半誠(chéng)實(shí)的，因此研究半誠(chéng)實(shí)模型下的多方保密計(jì)算協(xié)議在許多情況下是比較簡(jiǎn)單的，也是符合實(shí)際的，也確實(shí)能夠解決很多的實(shí)際問(wèn)題。但畢竟我們不能限制多方保密計(jì)算協(xié)議只能用于半誠(chéng)實(shí)的環(huán)境，如果將半誠(chéng)實(shí)模型下安全的協(xié)議用于惡意模型，協(xié)議就不能保證安全，因此需要研究針對(duì)惡意參與者安全的多方保密計(jì)算協(xié)議。

(6) 多方保密計(jì)算的應(yīng)用研究

目前雖然已經(jīng)有多方保密計(jì)算的工業(yè)應(yīng)用的成功案例[61-62]，但多方保密計(jì)算的應(yīng)用研究總體上還很不充分。任何學(xué)科的發(fā)展都需要有關(guān)鍵的應(yīng)用來(lái)推動(dòng)，而多方保密計(jì)算的應(yīng)用研究比較缺乏，因此探索多方保密計(jì)算的新用途是多方保密計(jì)算研究的一個(gè)重要方面。

5 結(jié)束語(yǔ)

本文總結(jié)了多方保密計(jì)算研究的現(xiàn)狀，已經(jīng)研究的問(wèn)題，常用的多方保密計(jì)算協(xié)議的設(shè)計(jì)工具。分析了多方保密計(jì)算協(xié)議安全性的定義。指出了有待進(jìn)一步研究的問(wèn)題。

[1]YaoAC.Protocolsforsecurecomputations[C]//Proceedingsofthe23thIEEESymposiumonFoundationsofComputerScience.CALosAlamitos:IEEEComputerSocietyPress, 1982: 160-164.

[2]GoldreichO.FoundationsofCryptography:BasicApplications[M].London:CambridgeUniversityPress, 2004:599-764.

[3]GoldwasserS.Multi-partycomputations:Pastandpresent[C]//ProceedingsofthesixteenthannualACMsymposiumonPrinciplesofdistributedcomputing.NewYork:ACMPress, 1997: 21-24.

[4]GoldreichO,MicaliS,WigdersonA.HowtoplayANYmentalgame[C]//ProceedingsofthenineteenthannualACMconferenceonTheoryofcomputing.NewYork:ACMPress, 1987: 218-229.

[5]GentryC.Afullyhomomorphicencryptionscheme[D].CaliforniaStanford:StanfordUniversity, 2009.

[6]RivestRL,ShamirA,AdlemanL.Amethodforobtainingdigitalsignaturesandpublic-keycryptosystems[J].CommunicationsoftheACM, 1978, 21(2): 120-126.

[7]ElGamalT.Apublickeycryptosystemandasignatureschemebasedondiscretelogarithms[C]//ProceedingsofCrypto’ 85:LectureNoteinComputerScienceVol218.Berlin:Springer, 1985: 10-18.

[8]PaillierP.Public-keycryptosystemsbasedoncompositedegreeresiduosityclasses[C]//ProceedingsofEUROCRYPT’99:LectureNoteinComputerScienceVol1592.Berlin:Springer, 1999: 223-238.

[9]RivestR.TheMD5message-digestalgorithm[J/OL]. (1992-04-01)[2015-07-28].http://tools.ietf.org/html/rfc1321?ref=driverlayer.com.

[10]EastlakeD,JonesP.USsecurehashalgorithm1 (SHA1)[R/OL]. (2001-06-02)[2015-07-28].http://www.rfc-editor.org/rfc/rfc3174.txt.

[11]RabinMO.HowToExchangeSecretswithObliviousTransfer[R/OL].IACRCryptologyePrintArchive. (2005-12-12)[2015-07-28].https://eprint.iacr.org/2005/187.pdf.

[12]IoannidisI,GramaA.AnefficientprotocolforYao’smillionaires’problem[C]//Proceedingsofthe36thAnnualHawaiiInternationalConferenceonSystemScience.USAHawaii:IEEE, 2003: 6-10.

[13]LinHY,TzengWG.Anefficientsolutiontothemillionaires’problembasedonhomomorphicencryption[C]/Proceedingsofthe3rdInternationalConferenceonAppliedCryptographyandNetworkSecurity:LectureNoteinComputerScienceVol3531,Berlin:Springer, 2005: 456-466.

[14] 李順東，戴一奇，游啟友.姚氏百萬(wàn)富翁問(wèn)題的高效解決方案[J].電子學(xué)報(bào)，2005, 33(5): 769-773.

[15]LiSD,WangDS,DaiYQ,etal.SymmetriccryptographicsolutiontoYao’smillionaires’problemandanevaluationofsecuremultipartycomputations[J].InformationSciences, 2008, 178: 244-255.

[16]LiSD,DaiYQ,YouQY.Securemulti-partycomputationsolutiontoYao’smillionaires’problembasedonsetinclusion[J].ProgressinNaturalScience, 2005, 15(9): 851-856.

[17] 李順東, 王道順. 基于同態(tài)加密的高效多方保密計(jì)算[J]. 電子學(xué)報(bào), 2013, 41(4): 798-803.

[18]LiSD,WangDS,DaiYQ.Symmetriccryptographicprotocolsforextendedmillionaires’problem[J].ScienceinChinaSeriesF:InformationSciences, 2009, 52(6): 974-982.

[19]BoudotF,SchoenmakersB,TraoreJ.Afairandefficientsolutiontothesocialistmillionaires’problem[J].DiscreteAppliedMathematics, 2001, 111(1): 23-36.

[20]FaginR,NaorM,WinklerP.Comparinginformationwithoutleakingit[J].CommunicationsoftheACM, 1996, 39(5): 77-85.

[21]FreedmanMJ,NissimK,PinkasB.Efficientprivatematchingandsetintersection[C]//ProceedingsofEUROCRYPT2004:LectureNoteinComputerScienceVol3027.Berlin:Springer, 2004: 1-19.

[22]HazayC,LindellY.Efficientprotocolsforsetintersectionandpatternmatchingwithsecurityagainstmaliciousandcovertadversaries[J].JournalofCryptology, 2010, 23(3): 422-456.

[23]DeCristofaroE,TsudikG.Practicalprivatesetintersectionprotocolswithlinearcomplexity[C]//Proceedingsof14thInternationalConferenceonFinancialCryptographyandDataSecurity:LectureNoteinComputerScienceVol6052.Berlin:Springer, 2010: 143-159.

[24]Dachman-SoledD,MalkinT,RaykovaM,etal.Efficientrobustprivatesetintersection[J].InternationalJournalofAppliedCryptography, 2012, 2(4): 289-303.

[25]KalyanasundaramB,SchintgerG.Theprobabilisticcommunicationcomplexityofsetintersection[J].SIAMJournalonDiscreteMathematics, 1992, 5(4): 545-557.

[26]LiSD,DaiYQ,WangDS,etal.Comparingtwosetswithoutdisclosingthem[J].ScienceinChinaSeriesF:InformationSciences, 2008, 51(9): 1231-1238.

[27]KissnerL,SongD.Privacy-preservingsetoperations[C]//Proceedingsof25thAnnualInternationalCryptologyConference:LectureNoteinComputerScienceVol3621.Berlin:Springer, 2005: 241-257.

[28]DuW,AtallahJ.Securemulti-partycomputationproblemsandtheirapplications:areviewandopenproblems[C]//Proceedingsofthe2001workshoponNewsecurityparadigms.NewYork:ACMPress, 2001: 13-22.

[29]AtallahJ,DuW.Securemulti-partycomputationalgeometry[C]//ProceedingsofInternationalWorkshoponAlgorithmsandDataStructures:LectureNotesinComputerScienceVol2125.Berlin:Springer, 2001: 165-179.

[30]GoethalsB,LaurS,LipmaaH,etal.Onprivatescalarproductcomputationforprivacy-preservingdatamining[C]//ProceedingsofInternationalConferenceonInformationSecurityandCryptology2004:LectureNotesinComputerScienceVol3506.Berlin:Springer, 2005: 104-120.

[31]AgrawalR,SrikantR.Privacy-preservingdatamining[C]//ProceedingsoftheACMSIGMODConferenceonManagementofData.NewYork:ACMPress, 2000, 29(2): 439-450.

[32]AmirbekyanA,Estivill-CastroV.Anewefficientprivacy-preservingscalarproductprotocol[C]//ProceedingsofthesixthAustralasianconferenceonDataminingandanalytics(Volume70).Sydney:AustralianComputerSocietypress, 2007: 209-214.

[33]BonehD,GohEJ,NissimK.Evaluating2-DNFformulasonciphertexts[C]//ProceedingsofSecondTheoryofcryptographyConference:LectureNoteinComputerScienceVol3378.Berlin:Springer, 2005: 325-341.

[34]MangasarianOL.Privacy-preservinglinearprogramming[J].OptimizationLetters, 2011, 5(1): 165-172.

[35]NaorM,PinkasB.Obliviouspolynomialevaluation[J].SIAMJournalonComputing, 2006, 35(5): 1254-1281.

[36]DuW,AtallahMJ.Privacy-preservingcooperativestatisticalanalysis[C]//Proceedingsofthe17thAnnualComputerSecurityApplicationsConference.Washington:IEEEComputerSociety, 2001: 102-110.

[37]DuW,HanYS,ChenS.Privacy-PreservingMultivariateStatisticalAnalysis:LinearRegressionandClassification[C]//ProceedingsoftheFourthSIAMInternationalConferenceonDataMining.Philadelphia:SIAM. 2004, 4: 222-233.

[38]DongR.SecureMultipartyComputation[D].BowlingGreen:BowlingGreenStateUniversity, 2009.

[39]ChenK,LiuL.Privacypreservingdataclassificationwithrotationperturbation[C]//ProceedingsoftheFifthIEEEInternationalConferenceonDataMining.Washington:IEEEComputerSociety, 2005: 589-592.

[40]ZhongZYS,WrightRN.Privacy-preservingclassificationofcustomerdatawithoutlossofaccuracy[C]//SIAMInternationalConferenceonDataMining(SDM).NewportBeach:SIAM, 2005.

[41]AmirbekyanA,Estivill-CastroV.Privacy-preservingregressionalgorithms[C]//Proceedingsofthe7thWSEASInternationalConferenceonsimulation,modelingandoptimization.StevensPoint:WorldScientificandEngineeringAcademyandSociety(WSEAS), 2007: 37-45.

[42]VaidyaJ,CliftonC.Privacy-preservingk-meansclusteringoververticallypartitioneddata[C]//ProceedingsoftheninthACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.NewYork:ACM, 2003: 206-215.

[43]HeW,LiuX,NguyenH,etal.Pda:Privacy-preservingdataaggregationinwirelesssensornetworks[C]//INFOCOM2007 26thIEEEInternationalConferenceonComputerCommunications.NewJersey:IEEE, 2007: 2045-2053.

[44]VaidyaJ,CliftonC.Privacypreservingassociationrulemininginverticallypartitioneddata[C]//ProceedingsoftheeighthACMSIGKDDinternationalconferenceonKnowledgediscoveryanddatamining.NewYork:ACM, 2002: 639-644.

[45]EvfimievskiA,SrikantR,AgrawalR,etal.Privacypreservingminingofassociationrules[J].InformationSystems, 2004, 29(4): 343-364.

[46]EmekiF,SahinOD,AgrawalD,etal.Privacypreservingdecisiontreelearningovermultipleparties[J].Data&KnowledgeEngineering, 2007, 63(2): 348-361.

[47]VaidyaJ,CliftonC.Privacy-preservingdatamining:Why,how,andwhen[J].IEEESecurity&Privacy, 2004, 2(6): 19-27.

[48]KarguptaH,DattaS,WangQ,etal.Ontheprivacypreservingpropertiesofrandomdataperturbationtechniques[C]//ProceedingsoftheThirdIEEEInternationalConferenceonDataMining.Washington:IEEEComputerSociety, 2003: 99-106.

[49]PinkasB.Cryptographictechniquesforprivacy-preservingdatamining[J].ACMSIGKDDExplorationsNewsletter, 2002, 4(2): 12-19.

[50]LiSD,WangDS,DaiYQ.AEfficientSecureMultipartyComputationalGeometry[J].ChineseJournalofElectronics, 2010, 19(2): 324-328.

[51]LiSD,DaiYQ.Securetwo-partycomputationalgeometry[J].JournalofComputerScienceandTechnology, 2005, 20(2): 258-263.

[52]LiSD,WuCY,WangDS,etal.Securemultipartycomputationofsolidgeometricproblemsandtheirapplications[J].InformationSciences, 2014, 282: 401-413.

[53] 李順東，戴一奇.集合包含與幾何包含問(wèn)題的多方保密計(jì)算[J].計(jì)算機(jī)研究與發(fā)展，2005, 42(10): 1647-1653.

[54] 羅永龍，黃劉生，徐維江，等.一個(gè)保護(hù)私有信息的多邊形相交判定協(xié)議[J]. 電子學(xué)報(bào)，2007, 35(4): 686-691.

[55] 劉文，羅守山，陳萍. 保護(hù)私有信息的點(diǎn)線關(guān)系判定協(xié)議及其應(yīng)用[J]. 北京郵電大學(xué)學(xué)報(bào)，2008, 31(2): 72-75.

[56]LiuL,WuC,LiS.Twoprivacy-preservingprotocolsforpoint-curverelation[J].JournalofElectronics(China), 2012, 29(5): 422-430.

[57]LiT,LiN,ZhangJ,etal.Slicing:Anewapproachforprivacypreservingdatapublishing[J].IEEETransactionsonKnowledgeandDataEngineering, 2012, 24(3): 561-574.

[58]FungB,WangK,ChenR,etal.Privacy-preservingdatapublishing:Asurveyofrecentdevelopments[J].ACMComputingSurveys(CSUR), 2010, 42(4): 14.

[59]ChangYC,MitzenmacherM.Privacypreservingkeywordsearchesonremoteencrypteddata[C]//Proceedingsofthe3rdInternationalConferenceonAppliedCryptographyandNetworkSecurity:LectureNoteinComputerScienceVol3531.Berlin:Springer, 2005: 442-455.

[60]AggarwalG,MishraN,PinkasB.Securecomputationofthekth-rankedelement[C]//ProceedingsofEUROCRYPT2004:LectureNoteinComputerScienceVol3027.Berlin:Springer, 2004: 40-55.

[61]BogetoftP,ChristensenDL,DamgardI,etal.Securemultipartycomputationgoeslive[C]//Proceedingsofthe13thInternationalConferenceonFinancialCryptographyandDataSecurity:LectureNoteinComputerScienceVol5628.Berlin:Springer, 2009: 325-343.

[62]PinkasB,SchneiderT,SmartNP,etal.Securetwo-partycomputationispractical[C]//ProceedingsofASIACRYPT2009:LectureNoteinComputerScienceVol5912.Berlin:Springer, 2009: 250-267.

[責(zé)任編輯:瑞金]

Secure multiparty computation review

LI Shundong, GUO Yimin, GONG Linming

(School of Computer Science, Shaanxi Normal University, Xi’an 710062, China)

This paper first summarizes the basic primitives of secure multiparty computation including homomorphic encryption schemes, one-way hash functions, secret sharing and oblivious transfer, and then reviews the fields and the state of the art of secure multiparty scientific computation, secure multiparty computational geometry, privacy-preserving statistical analysis and privacy-preserving data-mining. Finally, it introduces the most acceptable security definition and the problems that need further studying.

cryptography, secure multiparty computation, homomorphic encryption, oblivious transfer, simulation paradigm

2015-05-18

國(guó)家自然科學(xué)基金資助項(xiàng)目(61272435,61070189)

李順東(1963-)，男，博士，教授，博士生導(dǎo)師，從事密碼學(xué)與信息安全、電子商務(wù)研究。E-mail: shundong@snnu.edu.cn 郭奕旻(1992-)，女，碩士研究生，研究方向?yàn)樾畔踩c密碼學(xué)。E-mail: yiminguo@snnu.edu.cn

10.13682/j.issn.2095-6533.2015.05.001

TP309.7

A

2095-6533(2015)05-0001-10