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

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

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

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

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

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

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

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

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

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

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

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

12、指數(shù)。 比如在上述例子中兩個(gè)數(shù)的長(zhǎng)度為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)的。因此這個(gè)方案對(duì)于比較兩個(gè)較大的數(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é)議是一個(gè)重要的密碼學(xué)協(xié)議，這個(gè)協(xié)議能夠完成以下任務(wù)：Alice有m個(gè)消息(或

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

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

15、Y=Y1，Y2，Y100，其中：Step 2：利用不經(jīng)意傳輸，Alice能夠選擇她愿意得到的唯一的數(shù)Ya=g(a，b)。不經(jīng)意傳輸方案保證了Alice可以決定要得到的唯一的數(shù)，而B(niǎo)ob并不知道Alice選擇了哪一個(gè)數(shù)。如果Ya<100，那么a=b；如果100<Ya<200，那么a>b，如果200<Ya<300，那么a<b。Step 3：Alice將結(jié)果告訴Bob。就待比較的兩數(shù)都在100以?xún)?nèi)來(lái)說(shuō)，原方案需要式（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依然是對(duì)值域的一個(gè)窮舉。除此之外，這里僅僅是討論兩方間的安全比較問(wèn)題，多方間的安全大小比較應(yīng)該怎樣實(shí)現(xiàn)呢，事實(shí)上這方面前人也有了一定研究91011，由于篇幅限制，本報(bào)告不再一一展示。4 安全電子選舉問(wèn)題當(dāng)某一電子選舉方案同時(shí)滿(mǎn)足選票保密性、無(wú)收據(jù)性、健壯性、公平性和普遍驗(yàn)證性等性質(zhì)時(shí)，我們就稱(chēng)該方案是安全的。安全電子選舉問(wèn)題可以追溯至1981年，

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

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

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

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

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

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

23、安全兩方計(jì)算環(huán)境下，判定空間幾何對(duì)象間的相對(duì)位置關(guān)系問(wèn)題。當(dāng)前，針對(duì)這一問(wèn)題的研究成果還是較為豐盛的，前人已經(jīng)給出了點(diǎn)到直線(xiàn)、平面的距離以及點(diǎn)、線(xiàn)、面等幾何對(duì)象的相對(duì)位置判定協(xié)議、線(xiàn)段相交判定協(xié)議、圓、橢圓的關(guān)系判定方法、保護(hù)隱私的圓與圓、圓與直線(xiàn)的位置判定協(xié)議等多種幾何判定協(xié)議。由于本報(bào)告的篇幅限制，不可能對(duì)這些協(xié)議一一進(jìn)行整理，但是這些協(xié)議的基礎(chǔ)大都是安全點(diǎn)積協(xié)議，因此下文中重點(diǎn)對(duì)安全點(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，而B(niǎo)ob不知道這個(gè)值。Bob不直接得到這個(gè)值，但Bob可以將該值減去v，進(jìn)而間接使用X、Y兩個(gè)向量的點(diǎn)積，可見(jiàn)滿(mǎn)足這樣定義的安全點(diǎn)積協(xié)議有著較高的安全性，為了簡(jiǎn)便起見(jiàn)，這里本文討論當(dāng)v=0的情況，即：Alice有向量X=（X1，X2，Xn)，Bob有向量Y=(Y1，Y2，Yn)，他們協(xié)作計(jì)算得到點(diǎn)積，但互相并不知道對(duì)方的數(shù)據(jù)安全點(diǎn)積協(xié)議。5.2 安全點(diǎn)積協(xié)議下面本文展示了文獻(xiàn)16和文獻(xiàn)17中設(shè)計(jì)和應(yīng)用的一個(gè)安全點(diǎn)積協(xié)議。這個(gè)協(xié)議體現(xiàn)了多方安全計(jì)算應(yīng)用的一個(gè)原則：泄露一些不重要的信息，以獲取更好的效率。輸入：Alice有向量X

25、=（X1，X2，Xn)，Bob有向量Y=(Y1，Y2，Yv)。輸出：X和Y的點(diǎn)積。Step 1：Alice和Bob協(xié)商產(chǎn)生一個(gè)隨機(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。通過(guò)文獻(xiàn)閱讀，當(dāng)前就隱私保持幾何位置判

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

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