多方安全計(jì)算經(jīng)典問題整理

1、題 目 多方安全計(jì)算經(jīng)典問題整理摘要數(shù)據(jù)挖掘可以幫助人們在紛繁多樣的數(shù)據(jù)中找出隱晦的有用信息，并且已經(jīng)在電信、銀行、保險、證券、零售、生物數(shù)據(jù)分析等領(lǐng)域得到了廣泛的應(yīng)用。然而，就在數(shù)據(jù)挖掘工作不斷深入的同時，數(shù)據(jù)隱私保護(hù)問題也日益引起人們的廣泛關(guān)注，如何在保護(hù)數(shù)據(jù)隱私的前提下進(jìn)行數(shù)據(jù)挖掘已經(jīng)成為當(dāng)前亟待解決的一個問題。本報告選取隱私保持?jǐn)?shù)據(jù)挖掘中的多方安全計(jì)算領(lǐng)域進(jìn)行相關(guān)的整理工作，羅列了多方安全計(jì)算領(lǐng)域中較為經(jīng)典的姚式百萬富翁問題、安全電子選舉問題以及幾何位置判定問題。一方面，在翻閱文獻(xiàn)的基礎(chǔ)上為這些問題篩選出前人給出的相對簡潔易懂的解決方案；另一方面也對文中所展示的解決方案從時間復(fù)雜度、應(yīng)

2、用范圍的局限性以及潛在安全隱患等角度進(jìn)行了評價。另外，本報告也對各個問題中有待進(jìn)一步研究解決的問題進(jìn)行了簡單的闡述，以起到拋磚引玉的效果。在報告的最后，也談及了自己這門課程的上課感受。感謝學(xué)院開設(shè)的這門課程，感謝授課的各位老師，讓我在較短的時間內(nèi)得以大致了解當(dāng)前數(shù)據(jù)庫領(lǐng)域中所出現(xiàn)的一些前沿性的成果和問題，著實(shí)獲益匪淺！希望這種類型的課可以繼續(xù)辦下去，越辦越好！關(guān)鍵詞：多方安全計(jì)算； 百萬富翁； 電子選舉； 幾何位置判定目錄1引言12多方安全計(jì)算概述13百萬富翁問題23.1 姚式百萬富翁問題解決方案123.1.1 方案定義23.1.2 方案評價23.2 基于不經(jīng)意傳輸協(xié)議的高效改進(jìn)方案833.2

3、.1 不經(jīng)意傳輸協(xié)議33.2.2 改進(jìn)方案34安全電子選舉問題44.1 選舉模型44.2 多選多的電子選舉方案1454.2.1 方案定義54.2.2 方案評價55保護(hù)私有信息的幾何判定問題65.1 安全點(diǎn)積定義65.2 安全點(diǎn)積協(xié)議66小結(jié)77課程感受7參考文獻(xiàn)8多方安全計(jì)算經(jīng)典問題整理1 引言隨著社會信息化和電子商務(wù)與電子政務(wù)的不斷發(fā)展，數(shù)據(jù)成為社會的重要資源，面對時刻在高速增長著的數(shù)據(jù)，越來越多的人開始思考如何將這些數(shù)據(jù)轉(zhuǎn)換成有用的信息和知識。比如連鎖超市經(jīng)理希望從交易數(shù)據(jù)庫中發(fā)掘客戶的消費(fèi)習(xí)慣，電信運(yùn)營商希望從客戶通話記錄中建立惡意欠費(fèi)用戶通話模型，銀行經(jīng)理希望能基于信用卡持卡人歷史記錄

4、建立優(yōu)良客戶特征模型，傳統(tǒng)的數(shù)據(jù)庫技術(shù)遠(yuǎn)遠(yuǎn)不能滿足這種深層次的數(shù)據(jù)分析處理需求，于是數(shù)據(jù)挖掘（Data mining，DM）應(yīng)運(yùn)而生。所謂的數(shù)據(jù)挖掘就是“從數(shù)據(jù)中提取出隱含的過去未知的有價值的潛在信息”1，它是數(shù)據(jù)庫知識發(fā)現(xiàn)（Knowledge-Discovery in Databases，KDD）中的一個步驟。然而，在數(shù)據(jù)挖掘技術(shù)應(yīng)用不斷深入的同時，數(shù)據(jù)挖掘技術(shù)對數(shù)據(jù)隱私的威脅也日益引起人們的關(guān)注。或擔(dān)心其數(shù)據(jù)被誤用，或顧慮某些隱藏于數(shù)據(jù)背后的敏感信息被“挖掘”出來，人們往往不愿意提供數(shù)據(jù)參與數(shù)據(jù)挖掘工作，這就使得數(shù)據(jù)挖掘失去了基礎(chǔ)。在這樣一個背景下，研究如何在保持?jǐn)?shù)據(jù)隱私的前提下進(jìn)行數(shù)據(jù)挖

5、掘是一件非常有意義的工作。當(dāng)前，隱私保持?jǐn)?shù)據(jù)挖掘（Privacy Preserving Data Mining，PPDM）研究引起了國內(nèi)外學(xué)者的廣泛興趣，已經(jīng)開發(fā)了一系列的技術(shù)。隱私保持?jǐn)?shù)據(jù)挖掘技術(shù)針對待處理數(shù)據(jù)分布的不同可以分為兩類：集中式和分布式。集中式的主要有隨機(jī)擾亂、隨機(jī)響應(yīng)、數(shù)據(jù)交換、規(guī)則隱藏的啟發(fā)式方法、k-匿名和l-多樣性方法等等，而分布式中最常用的是多方安全計(jì)算密碼技術(shù)。本報告主要就多方安全計(jì)算技術(shù)，選取了該領(lǐng)域比較經(jīng)典的幾個問題做了一些整理工作。2 多方安全計(jì)算概述生活中，常常會有多方各自擁有自己的數(shù)據(jù)，希望協(xié)作進(jìn)行數(shù)據(jù)挖掘，但每個參與方都不希望讓其它方看到自己原始數(shù)據(jù)的情形

6、。比如各商業(yè)銀行希望進(jìn)行合作進(jìn)行信用卡欺詐分析，各電信運(yùn)行商希望合作進(jìn)行客戶流失模型分析，它們的數(shù)據(jù)有相似的屬性，但都不希望向合作方透露具體的數(shù)據(jù)，同時希望得到數(shù)據(jù)挖掘結(jié)果。這就是多方安全計(jì)算應(yīng)用于數(shù)據(jù)挖掘的現(xiàn)實(shí)需求模型，將該現(xiàn)實(shí)需求模型抽象化，得到多方安全計(jì)算的基本任務(wù)如下：大于或等于2的參與方，在無可信第三方參與的情況下，執(zhí)行協(xié)議，得到共同或分別擁有的結(jié)果，但參與方不希望向任意其它方泄漏自身的隱私數(shù)據(jù)。多方安全計(jì)算在密碼學(xué)中更一般的描述是：n個參與方p1，p2，pn，每個參與方pi持有秘密的輸入xi，希望計(jì)算一個共同函數(shù)：f(x1，x2，xn)，計(jì)算結(jié)束的時候，各方得到正確的輸出f(x1，

7、x2，xn)，同時自己的秘密輸入xi沒有泄露給其它的參與方。注意到，如果有可信第三方，那么多方安全計(jì)算任務(wù)就變得非常簡單：各參與方把自己的輸入數(shù)據(jù)傳給可信第三方，由可信第三方將計(jì)算結(jié)果傳給參與方即可。但現(xiàn)實(shí)中可信第三方很難找到，于是多方安全計(jì)算任務(wù)就變得很困難。多方安全計(jì)算研究由華人學(xué)者姚期智開創(chuàng)23，他通過研究兩個百萬富翁希望不向?qū)Ψ酵嘎侗舜素?cái)富的情況下比較誰更富有的問題，形象地說明了多方安全計(jì)算面臨的挑戰(zhàn)和問題解決思路，并經(jīng)Oded Goldreich5、Shaft Goldwasser6等學(xué)者的眾多原始創(chuàng)新工作，逐漸發(fā)展成為密碼學(xué)的一個重要分支。接下來，本報告將會對多方安全計(jì)算領(lǐng)域中比較

8、經(jīng)典的百萬富翁問題、電子選舉問題以及保護(hù)私有信息的幾何判定問題進(jìn)行簡單的整理介紹。3 百萬富翁問題百萬富翁問題首先由華裔計(jì)算機(jī)科學(xué)家、圖靈獎獲得者姚期智教授提出2。文獻(xiàn)2中，姚教授提出了這樣一個問題：兩個百萬富翁Alice和Bob想知道他們兩個誰更富有，但他們都不想讓對方知道自己財(cái)富的任何信息，這就是百萬富翁問題。下面，整理了該問題的兩個解決方案，首先給出姚期智教授在提出問題時給出的一個解決方案，然后選取了清華大學(xué)李順東等人提出的一個高效解決方案，該方案針對姚式解決方案存在的算法復(fù)雜度太高，效率過低問題做出了改進(jìn)。3.1 姚式百萬富翁問題解決方案13.1.1 方案定義對該問題進(jìn)行抽象化其實(shí)就是

9、兩個數(shù)的安全大小比較問題，以確定哪一個較大。Alice知道一個整數(shù)i；Bob知道一個整數(shù)j。Alice與Bob希望知道究竟是i j 還是i >j，但都不想讓對方知道自己的數(shù)。為簡單起見，假設(shè)i 與j 的范圍為1，100。Bob有一個公開密鑰EB與私有密鑰DB。(1)Alice選擇一個大隨機(jī)數(shù)x，并用Bob的公開密鑰加密。(3-1)(3)Bob計(jì)算下面的100個數(shù)：(3-2)其中，DB是Bob的私有解密密鑰Bob選擇一個大的素?cái)?shù)p( p應(yīng)該比x稍小一點(diǎn)，Bob不知道x，但Alice能容易地告訴他x的大小) 然后計(jì)算下面的100個數(shù)：(3-3)然后驗(yàn)證對于所有的uv，(3-4)并對所有的u驗(yàn)

10、證：(3-5)如果不成立，Bob就選擇另一個素?cái)?shù)并重復(fù)驗(yàn)證。(4)Bob將以下數(shù)列發(fā)送給Alice：z1，z2，zj，zj+1+1，zj+2+1， ，z100+1，p(5)Alice驗(yàn)證這個數(shù)列的第i個數(shù)是否與x模p同余。如果同余，她得出的結(jié)論是ij；如果不同余，它得出的結(jié)論是i>j。(6)Alice把這個結(jié)論告訴Bob。3.1.2 方案評價該方案的設(shè)計(jì)巧妙的利用了數(shù)據(jù)i、j本身的特點(diǎn)，式（3-2）通過引用變量u窮舉整數(shù)i的值域?qū)⒄麛?shù)i隱含至最終Bob返還給Alice中的數(shù)據(jù)序列中。如果ij，那么第i個數(shù)肯定在數(shù)列z1，z2，zj之中的某一個，該數(shù)列中的數(shù)據(jù)逆向使用式（3-2）自然得到x

11、；如果i>j，那么第i個數(shù)肯定在數(shù)列zj+1+1，zj+2+1，z100+1之中的某一個，由于該數(shù)列中的數(shù)據(jù)都加了1，逆向使用公式（3-2）就得不到x了。因此，通過這種方案是可以在不知道對方數(shù)據(jù)大小的情況下得到比較結(jié)果的。但是，正是這種巧妙也為該方案設(shè)置了一定的局限性：首先該比較方案只適用于整數(shù)間甚至是正整數(shù)間的大小比較，因?yàn)閷τ趯?shí)數(shù)域，變量u是不可能窮舉實(shí)數(shù)變量i的值域的；其次該方案僅適用于較小的整數(shù)，如果變量i、j很大的話，通過接下來的時間復(fù)雜度分析，方案的效率是很低的，基本沒有實(shí)際應(yīng)用價值。 假設(shè)該方案需要比較的兩個數(shù)的長度(十進(jìn)制表示的位數(shù))為n，數(shù)的范圍就是10n，是輸入規(guī)模的

12、指數(shù)。 比如在上述例子中兩個數(shù)的長度為2，則數(shù)的范圍就是100，式(3-2)中要解密的次數(shù)、式(3-3)中模運(yùn)算的次數(shù)、式(3-5)中要驗(yàn)證的次數(shù)都是10n，式(3-4)中要驗(yàn)證的次數(shù)為102n/2。因此計(jì)算復(fù)雜性為輸入規(guī)模的指數(shù)函數(shù)。如果輸入規(guī)模為50，那么計(jì)算復(fù)雜性為O(1050)，這樣的計(jì)算復(fù)雜性，實(shí)際上是不可能實(shí)現(xiàn)的。因此這個方案對于比較兩個較大的數(shù)是不實(shí)用的。3.2 基于不經(jīng)意傳輸協(xié)議的高效改進(jìn)方案83.2.1 不經(jīng)意傳輸協(xié)議文獻(xiàn)8給出的高效解決方案是基于文獻(xiàn)6和文獻(xiàn)7提出的不經(jīng)意傳輸協(xié)議形成的，不經(jīng)意傳輸協(xié)議是一個重要的密碼學(xué)協(xié)議，這個協(xié)議能夠完成以下任務(wù)：Alice有m個消息(或

13、者數(shù)據(jù))x1，x2，xm，通過執(zhí)行不經(jīng)意傳輸協(xié)議，Bob能夠基于自己的選擇得到且只能得到其中的一個消息xi(1im)，而對其他消息x1，x2，xi-1，xi+1，xm則一無所知。Alice對Bob選擇了哪一個消息也一無所知?，F(xiàn)將文獻(xiàn)6和7提出的不經(jīng)意傳輸協(xié)議做如下整理。設(shè)q為一素?cái)?shù)，p=2q+1也是一個素?cái)?shù)。Gq為一階q群，g、h為Gq的兩個生成元，Zq表示自然數(shù)模q的最小剩余集，(g，h，Gq)為雙方共知，Alice有m個消息：M1，M2，Mm，Bob希望得到其中的一個，Alice不知道Bob得到了哪一個。協(xié)議如下：Step 1：Bob選擇一個希望的(1m)與一個隨機(jī)數(shù)rZq，計(jì)算y=grh

14、 mod p并將y發(fā)給Alice。Step 2：Alice計(jì)算下列m個二元組的序列C=(a1，b1)，(a2，b2)，(am，bm)其中：(3-6)并將序列C發(fā)給Bob。Step 3：根據(jù)c=(a，b)，Bob計(jì)算M=(b/(a)r)mod p。完成這個協(xié)議，Bob就可以得到他希望得到的M，而Alice對則一無所知。3.2.2 改進(jìn)方案接下來給出文獻(xiàn)8提出的基于該不經(jīng)意傳輸協(xié)議的大富翁問題高效解決方案。假設(shè)要保密比較兩個自然數(shù)a，b的大小，為簡單起見假設(shè)1a，b<100，方案如下：Step 1：令X=1，2， ，99，R=(X)是X的一個隨機(jī)置換。Bob計(jì)算下面的100個數(shù)，得到一個數(shù)組

15、Y=Y1，Y2，Y100，其中：Step 2：利用不經(jīng)意傳輸，Alice能夠選擇她愿意得到的唯一的數(shù)Ya=g(a，b)。不經(jīng)意傳輸方案保證了Alice可以決定要得到的唯一的數(shù)，而Bob并不知道Alice選擇了哪一個數(shù)。如果Ya<100，那么a=b；如果100<Ya<200，那么a>b，如果200<Ya<300，那么a<b。Step 3：Alice將結(jié)果告訴Bob。就待比較的兩數(shù)都在100以內(nèi)來說，原方案需要式（3-1）進(jìn)行1次模指數(shù)運(yùn)算、式（3-2）需要進(jìn)行100次模指數(shù)運(yùn)算、式（3-4）需要進(jìn)行100*100/2次比較（如果式（3-3）不成立，前述公

16、式還需從進(jìn)行運(yùn)算）、式（3-5）需要進(jìn)行100次比較；相應(yīng)地，改進(jìn)方案只需進(jìn)行100次加法運(yùn)算和101次模指數(shù)運(yùn)算，減少了大量的比較和驗(yàn)證，效率有一定提升。但是，改進(jìn)方案依然只能用于兩較小自然數(shù)間的安全比較，原因就在于它所依據(jù)的不經(jīng)意傳輸協(xié)議中，變量i依然是對值域的一個窮舉。除此之外，這里僅僅是討論兩方間的安全比較問題，多方間的安全大小比較應(yīng)該怎樣實(shí)現(xiàn)呢，事實(shí)上這方面前人也有了一定研究91011，由于篇幅限制，本報告不再一一展示。4 安全電子選舉問題當(dāng)某一電子選舉方案同時滿足選票保密性、無收據(jù)性、健壯性、公平性和普遍驗(yàn)證性等性質(zhì)時，我們就稱該方案是安全的。安全電子選舉問題可以追溯至1981年，

17、D.Chaum首先提出了電子投票思想12，至今基于傳統(tǒng)密碼領(lǐng)域雖然已經(jīng)提出了幾類電子選舉方案，但是沒有一個方案可以滿足電子選舉的所有需求，總有一些缺陷，要么是效率不高，不夠安全：要么是不夠靈活，通過篩選，下文整理了文獻(xiàn)14給出的一種基于多方安全求和協(xié)議的解決方案，該方案在整個選舉過程不需要可信第三方，任何投票人都可以計(jì)票，比一般的方案具有更強(qiáng)的安全性，同時，該方案也實(shí)現(xiàn)了選舉的無收據(jù)性和普遍驗(yàn)證性。4.1 選舉模型通常，一個完整的電子選舉方案由選民注冊階段、機(jī)構(gòu)發(fā)布選票階段、選民投票階段、機(jī)構(gòu)收集選票階段、校驗(yàn)選票階段、統(tǒng)計(jì)選票階段、對選舉結(jié)果的驗(yàn)證等階段組成，每一階段由相應(yīng)的協(xié)議實(shí)現(xiàn)其功能。

18、本報告所展示的電子選舉方案主要針對多選多的選舉情形，對選舉過程中的各個階段都做了一些簡化，以下是方案所依賴的選舉模型的定義：（1）通信信道。通信信道采用多方計(jì)算標(biāo)準(zhǔn)的安全廣播信道模型13。（2）參與方。設(shè)n個投票人（P1，P2，Pn）在投票前均已注冊，并知道所有注冊選民的合法身份標(biāo)識各選民地位平等，選票權(quán)重相同投票結(jié)束后，每個選民都可以計(jì)票，不需要設(shè)置專門的可信第三方作為計(jì)票中心。（3）選票結(jié)構(gòu)。假設(shè)最多有n個投票人（P1，P2，Pn）參與投票，共有m個候選人（C1，C2，Cn），每一張的選票由m列組成，每列由k位構(gòu)成（），其中，前k-1位為0，最后1位ai值取決于投票人，若投票人對候選人Ci

19、投贊成票，則ai=1，否則ai=0，因此選票總位數(shù)為mk，顯然上述選票是一個多精度整數(shù)。4.2 多選多的電子選舉方案144.2.1 方案定義假定選民是合法的投票人，已通過注冊，取得合法的身份標(biāo)識Pi，可以進(jìn)入投票系統(tǒng)進(jìn)行選舉活動，方案分為本地表決、發(fā)送選票、統(tǒng)計(jì)選票3個階段。（1）本地表決每個投票人Pi（i1，n）在電子選票上對Cj（j1，m）進(jìn)行表決。aj（j1，m）取值為1表示贊成，取值為0則表示反對，由此得到一個二進(jìn)制序列，并將該二進(jìn)制數(shù)轉(zhuǎn)換成十進(jìn)制數(shù)。（2）發(fā)送選票每個投票人Pi（i1，n）均將自己的選票（十進(jìn)制數(shù)）隨機(jī)地拆分為n個更小的整數(shù)vij，使得，然后利用安全信道將vij發(fā)送給

20、選民Pj（j1，n，ji）每個Pi在收到其余n-1個投票人的隨機(jī)數(shù)vji（j1，n，ji）之后，計(jì)算和式，其中vii是Pi自己持有的隨機(jī)數(shù)。3）統(tǒng)計(jì)選票每個投票人Pi（i1，n）將自己的求和結(jié)果vi廣播給其余的投票人Pj（j1，n，ji）。每個投票人Pi在收到其余n-1個投票人的廣播結(jié)果之后，即可計(jì)算所有的選票之和T。(4-1)最后每個Pi將十進(jìn)制整數(shù)轉(zhuǎn)換成二進(jìn)制數(shù)，然后對每位進(jìn)行截取，即可得到每一位候選人Cj（j1，m）的得票數(shù)。4.2.2 方案評價表面上看，以上通過安全多方求和方法進(jìn)行投票和計(jì)票，除了最終的計(jì)票結(jié)果外，不泄露任何投票人選票的秘密，實(shí)現(xiàn)了保密投票。但是仔細(xì)分析可以發(fā)現(xiàn)，當(dāng)候選

21、人數(shù)m不是特別大的時候，投票人Pi對于候選人Cj是否投票就具有可破解性，因?yàn)楹蜻x人越少，投票人投票后所產(chǎn)生的二進(jìn)制序列轉(zhuǎn)化成十進(jìn)制數(shù)得到的潛在組合就少，例如當(dāng)候選人數(shù)只有三個人的時候，投票人的投票數(shù)轉(zhuǎn)化成十進(jìn)制只有8種可能：73，72，65，64，9，8，0。在這八種組合的基礎(chǔ)上輔助以拆分項(xiàng)大小的限制等信息，對投票人的投票結(jié)構(gòu)進(jìn)行破解是完全有可能的。因此，該方案的選票保密性還有待進(jìn)一步完善，不過隨著候選人人數(shù)的增加，該方案的優(yōu)越性也會進(jìn)一步得到體現(xiàn)。目前在電子選舉問題中除了上文所展示的多選多問題外，還有許多值得研究的問題，比如電子評審和陪審團(tuán)表決時的保護(hù)隱私的電子評審問題、上市公司股東大會中的

22、含權(quán)選舉問題以及工程項(xiàng)目投標(biāo)中的平均值中標(biāo)問題等。這些問題與生活實(shí)際聯(lián)系非常緊密，解決的難度也很大，還有待進(jìn)一步研究。5 保護(hù)私有信息的幾何判定問題隨著科學(xué)技術(shù)的發(fā)展，人類研究開發(fā)太空的能力在不斷增強(qiáng)，國際上不同的科研機(jī)構(gòu)之間都希望開展合作來加快自己的研究進(jìn)程。然而由于涉及到國家的安全與利益，這種合作是極其有限的，任何一個機(jī)構(gòu)都不會輕易向其他合作方公開自己的技術(shù)。例如兩個不同的國家各自都研制出自己的太空碎片分布圖，為了確保自己的飛行器在太空飛行過程中不會與太空碎片發(fā)生碰撞，他們都希望能同時參考對方數(shù)據(jù)來提高飛行的可靠性，然而為了各自國家的利益，兩方都不會向?qū)Ψ叫孤蹲约旱臄?shù)據(jù)信息。上述問題就是在

23、安全兩方計(jì)算環(huán)境下，判定空間幾何對象間的相對位置關(guān)系問題。當(dāng)前，針對這一問題的研究成果還是較為豐盛的，前人已經(jīng)給出了點(diǎn)到直線、平面的距離以及點(diǎn)、線、面等幾何對象的相對位置判定協(xié)議、線段相交判定協(xié)議、圓、橢圓的關(guān)系判定方法、保護(hù)隱私的圓與圓、圓與直線的位置判定協(xié)議等多種幾何判定協(xié)議。由于本報告的篇幅限制，不可能對這些協(xié)議一一進(jìn)行整理，但是這些協(xié)議的基礎(chǔ)大都是安全點(diǎn)積協(xié)議，因此下文中重點(diǎn)對安全點(diǎn)積協(xié)議進(jìn)行整理介紹。5.1 安全點(diǎn)積定義安全點(diǎn)積協(xié)議更早是在Du Wenliang等學(xué)者的一系列論文中實(shí)現(xiàn)的15，他們提出了安全點(diǎn)積定義：Alice有向量X=（X1，X2，Xn)，Bob有向量Y=(Y1，Y

24、2，Yn)和標(biāo)量數(shù)值v，計(jì)算結(jié)束，Alice得到X·Y+v，而Bob不知道這個值。Bob不直接得到這個值，但Bob可以將該值減去v，進(jìn)而間接使用X、Y兩個向量的點(diǎn)積，可見滿足這樣定義的安全點(diǎn)積協(xié)議有著較高的安全性，為了簡便起見，這里本文討論當(dāng)v=0的情況，即：Alice有向量X=（X1，X2，Xn)，Bob有向量Y=(Y1，Y2，Yn)，他們協(xié)作計(jì)算得到點(diǎn)積，但互相并不知道對方的數(shù)據(jù)安全點(diǎn)積協(xié)議。5.2 安全點(diǎn)積協(xié)議下面本文展示了文獻(xiàn)16和文獻(xiàn)17中設(shè)計(jì)和應(yīng)用的一個安全點(diǎn)積協(xié)議。這個協(xié)議體現(xiàn)了多方安全計(jì)算應(yīng)用的一個原則：泄露一些不重要的信息，以獲取更好的效率。輸入：Alice有向量X

25、=（X1，X2，Xn)，Bob有向量Y=(Y1，Y2，Yv)。輸出：X和Y的點(diǎn)積。Step 1：Alice和Bob協(xié)商產(chǎn)生一個隨機(jī)n*（n/2）矩陣C。Step 2：Alice隨機(jī)產(chǎn)生向量n/2×1向量R=（r1,r2,rn/2），Alice產(chǎn)生n×1向量X，X=C×R，Alice產(chǎn)生X=X+X，Alice將X發(fā)送至Bob。 Step 3：Bob令， Bob產(chǎn)生n×1向量Y=CT×Y， Bob將S和Y向Alice發(fā)送。 Step 4：Alice計(jì)算， Alice計(jì)算s=s-s， Alice將結(jié)果告訴Bob。通過文獻(xiàn)閱讀，當(dāng)前就隱私保持幾何位置判

26、定問題前人已經(jīng)針對具體的位置關(guān)系判定分別給出了系列安全判定協(xié)議，這些安全判定協(xié)議的基礎(chǔ)大都是上文所展示的安全點(diǎn)積協(xié)議，這里本報告也僅僅是起到了一個拋磚引玉的作用。6 小結(jié)在數(shù)據(jù)挖掘得到廣泛應(yīng)用的同時，隱私數(shù)據(jù)保持?jǐn)?shù)據(jù)挖掘技術(shù)也日益受到人們的普遍關(guān)注，多方安全計(jì)算是隱私數(shù)據(jù)保持?jǐn)?shù)據(jù)挖掘領(lǐng)域的一個重要研究方向，有著深遠(yuǎn)的理論意義和廣闊的實(shí)際應(yīng)用前景。多方安全計(jì)算的研究內(nèi)容是豐富多樣的，本報告目前僅僅是對該方向中的若干經(jīng)典問題進(jìn)行了相關(guān)的整理工作，由于能力所限，相應(yīng)問題給出的解決方案也只是刪繁就簡，選取了前人簡潔易懂的解決方案進(jìn)行了展示。事實(shí)上，每一個問題截至目前為止仍有很多問題沒有解決，比如目前提

27、出的系列解決方案大都是基于半誠實(shí)模型（半誠實(shí)參與方使用正確的輸入，并遵守協(xié)議規(guī)則，但有可能根據(jù)協(xié)議執(zhí)行過程中收到的信息破解隱私數(shù)據(jù)）基礎(chǔ)上的，而現(xiàn)實(shí)生活中很多安全性的攻擊往往是惡意，這些惡意參與者除了會采取半誠實(shí)參與方的攻擊行為外，還可能不遵循協(xié)議的規(guī)則，包括偽造輸入數(shù)據(jù)、和其它參與方串謀等。因此，如何構(gòu)建基于惡意模型的安全多方數(shù)據(jù)挖掘協(xié)議還需要人們進(jìn)行更多地研究工作。再比如安全電子選舉問題，若何解決身份認(rèn)證和匿名投票問題也有必要進(jìn)一步深入研究?？傊?，多方安全計(jì)算的研究和應(yīng)用都方興未艾，仍有著很多有意義的工作值得我們?nèi)プ?，希望不遠(yuǎn)的將來本報告所羅列的一些問題可以得到圓滿的解決。參考文獻(xiàn)1 W.

28、 Frawley and G. Piatetsky-Shapiro and C. Matheus (Fall 1992). "Knowledge Discovery in Databases: An Overview". AI Magazine: pp. 213-228. ISSN 0738-4602.2 Yao A CProtocols for secure computationAIn：Proceedings of the 27th Annual IEEE Symposium on Foundations of Computer ScienceC1986:l62-l67

29、3 Yao A CHow to generate and exchange secretsAIn：Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer ScienceC1982:l60-l644 Goldreich O,Micali S,Wigderson A.How to play any mental game-a completeness theorem for protocols with honest majorityIn：Proceedings of the 19th ACM symposi

30、um 0n the Theory of ComputingC.1987:218-2295 Goldwasser S，Levin LAFair computation of general functions in presence of immoral majorityAIn：Advances in Cryptology-CRYPTO90，Proceedings of the10th Annual Intematioal Cryptology Conference，LNCS 537C1990:77-936 M Naor,B Pinkas.Efficient oblivious transfer protocolsA. Proc 12th Ann Symp Discrete AlgorithmsC. NewYork:ACMPress,2001. 448- 457.7 Wen Guey Tzeng. Efficient 12out2of2noblivious transfer schemes with universally usable parametersJ. IEEE TRANSACTIONS ON COMPUTERS,2004,53(2) :232- 240.8