保護(hù)私有數(shù)據(jù)的合作計(jì)算問(wèn)題及其應(yīng)用研究.pdf

1、網(wǎng)絡(luò)技術(shù)的不斷進(jìn)步使得網(wǎng)絡(luò)中的合作計(jì)算也不斷地向前發(fā)展，用戶通過(guò)在網(wǎng)絡(luò)環(huán)境中交互信息并且完成一些復(fù)雜函數(shù)的計(jì)算變得越來(lái)越普遍。然而，參與合作計(jì)算的用戶數(shù)據(jù)常常屬于個(gè)人私有信息或者涉密信息，因此信息保護(hù)問(wèn)題一直是制約網(wǎng)絡(luò)合作計(jì)算重要問(wèn)題。讓用戶共享自己的私有信息參與合作計(jì)算并且保護(hù)其私有信息不泄露成為了眾多研究者的重要研究目標(biāo)。1982年，A.C.Yao首先提出了安全多方計(jì)算的概念，就是針對(duì)保護(hù)私有信息的合作計(jì)算問(wèn)題而做的最早的研究，一直

2、以來(lái)都引起了眾多研究者的高度重視，并繼承和發(fā)展了眾多的安全多方計(jì)算理論與應(yīng)用方面的研究。
　　 安全多方計(jì)算主要是研究?jī)蓚€(gè)或者多個(gè)用戶在提供各自私有數(shù)據(jù)信息參與聯(lián)合計(jì)算某一個(gè)函數(shù)的同時(shí)保證各自私有數(shù)據(jù)的安全性。一個(gè)安全多方計(jì)算協(xié)議能夠經(jīng)得住無(wú)限計(jì)算能力的攻擊而仍然能保證數(shù)據(jù)安全，那么就稱為信息論安全的；而一個(gè)安全多方計(jì)算協(xié)議如果能經(jīng)得住多項(xiàng)式計(jì)算能力的攻擊，則稱之為密碼學(xué)安全的。A.C.Yao在1982年給出了一個(gè)使用密碼學(xué)方式

3、來(lái)實(shí)現(xiàn)的兩方計(jì)算的安全協(xié)議，求解百萬(wàn)富翁問(wèn)題。S.Goldwasser等人1985年首次提出了零知識(shí)證明系統(tǒng)，將安全多方計(jì)算模型簡(jiǎn)化為只需研究半誠(chéng)實(shí)模型下的安全協(xié)議，惡意模型下的安全協(xié)議可以通過(guò)零知識(shí)證明系統(tǒng)從半誠(chéng)實(shí)模型轉(zhuǎn)化得到。MO.Rabin在1981年提出茫然傳送協(xié)議，由J．Kilian于1988年將其應(yīng)用到了安全多方計(jì)算的協(xié)議設(shè)計(jì)中。0.Goldreich等人1987年將A.C.Yao的理論推廣到多方參與的安全計(jì)算范圍，并提出了

4、密碼學(xué)安全的可以計(jì)算任意函數(shù)的安全協(xié)議。M.Ben-Or等人在1988年得出了與D.Chaum等人類(lèi)似的理論研究結(jié)果，即在信息論安全模型中，被動(dòng)攻擊情況下當(dāng)串通攻擊者的數(shù)目小于一半時(shí)(t＜n/2）或者主動(dòng)攻擊情況下攻擊者的數(shù)目小于1/3時(shí)(t＜n/3)，任意函數(shù)都可以被安全的計(jì)算。Goldreich于1998年將前人研究成果進(jìn)行總結(jié)，從而形成了比較完整的安全多方計(jì)算的理論體系。
　　 安全多方計(jì)算在很多情況下都有著重要應(yīng)用，尤其

5、在涉密領(lǐng)域，包括軍事、商業(yè)等領(lǐng)域，有著不可替代的地位。例如多個(gè)國(guó)家之間的聯(lián)合防御中需要保密計(jì)算防御區(qū)域交叉情況、相互競(jìng)爭(zhēng)的商家共同開(kāi)發(fā)商業(yè)區(qū)域時(shí)的商業(yè)網(wǎng)點(diǎn)的布局等。
　　 本文對(duì)前人的研究進(jìn)行了總結(jié)分析。第1章緒論中介紹了安全多方計(jì)算的研究背景和研究現(xiàn)狀，通過(guò)對(duì)前人研究的概述，給出了本文的研究?jī)?nèi)容安排。同時(shí)也給出了本文的結(jié)構(gòu)框架。
　　 第2章從安全多方計(jì)算的定義、理論以及應(yīng)用等方面介紹了安全多方計(jì)算的發(fā)展和出現(xiàn)的問(wèn)題。

6、提出了一般安全協(xié)議設(shè)計(jì)的流程和思想路線，比較系統(tǒng)的介紹了安全多方計(jì)算的基礎(chǔ)協(xié)議，并給出了相關(guān)協(xié)議的實(shí)現(xiàn)思想。為了后續(xù)章節(jié)中安全協(xié)議的規(guī)范化，給出了本文中設(shè)計(jì)協(xié)議時(shí)用到的表示符號(hào)。
　　 第3章研究了點(diǎn)與凸包的靜態(tài)與動(dòng)態(tài)兩種情況下的包含判定問(wèn)題。首先給出了點(diǎn)與直線相對(duì)位置判定協(xié)議，能夠判斷出點(diǎn)在直線的哪一側(cè)。然后考慮在安全性和計(jì)算效率方面的折中，適當(dāng)?shù)男孤兑徊糠贮c(diǎn)的方位信息換取計(jì)算效率的大幅度提升。將動(dòng)態(tài)判定問(wèn)題引入到此協(xié)議中，給

7、出了根據(jù)速度變化動(dòng)態(tài)調(diào)整檢測(cè)包含關(guān)系的時(shí)間間隔協(xié)議，能夠及時(shí)的檢測(cè)出點(diǎn)與凸包的平行運(yùn)動(dòng)中的包含關(guān)系。接著研究了凸包旋轉(zhuǎn)運(yùn)動(dòng)的狀態(tài)下，檢測(cè)點(diǎn)與凸包包含關(guān)系的判定協(xié)議。本章的研究使得點(diǎn)與凸包包含判定協(xié)議更加具有實(shí)用性。
　　 第4章研究了凸包構(gòu)造問(wèn)題。首先將兩方叉積運(yùn)算拓展為任意三方參與的三點(diǎn)位置關(guān)系判定協(xié)議。在此協(xié)議基礎(chǔ)上，構(gòu)建出了任意多方聯(lián)合構(gòu)建凸包的凸包安全構(gòu)造協(xié)議。此協(xié)議可以很好的適應(yīng)點(diǎn)和參與者動(dòng)態(tài)變化情況。當(dāng)某一參與方加入

8、計(jì)算，只需要將其本地凸包的點(diǎn)加入計(jì)算即可判定自己哪些點(diǎn)是最終凸包的點(diǎn)。當(dāng)某一些點(diǎn)增加進(jìn)來(lái)或者被刪除，只需要將點(diǎn)與其他點(diǎn)進(jìn)行叉積即可判定點(diǎn)是否構(gòu)成最終凸包的點(diǎn)。因此，本文的凸包構(gòu)建協(xié)議具有很好的靈活性。
　　 第5章研究了兩圓相交交點(diǎn)共享問(wèn)題。例如在科學(xué)計(jì)算結(jié)果的分析中需要聯(lián)合分析各自私有實(shí)驗(yàn)結(jié)果，確定實(shí)驗(yàn)結(jié)果的邊界條件等信息。兩個(gè)圓可以看做實(shí)驗(yàn)結(jié)果豹范圍，每一個(gè)用戶獲取一個(gè)且僅獲取一個(gè)交點(diǎn)。本文中基于二分迭代算法的思想，將交點(diǎn)的

9、求解轉(zhuǎn)化為求相交的近似值，即數(shù)值解。調(diào)用的子協(xié)議保證了協(xié)議執(zhí)行過(guò)程中任何一方都不能根據(jù)中間結(jié)果和最終結(jié)果推斷另一方的相對(duì)位置，哪怕是方位信息也不會(huì)泄露。
　　 第6章研究了保護(hù)隱私的個(gè)性化推薦協(xié)議。本章中首先設(shè)計(jì)了一個(gè)具有反饋?zhàn)哉{(diào)節(jié)功能的二部圖網(wǎng)絡(luò)（即Heat Conduction算法和Mass Diffusion算法），將每一條連接邊看作一條導(dǎo)線將二部圖的兩邊（用戶和產(chǎn)品）進(jìn)行連接。在資源值傳遞的過(guò)程中，我們使得導(dǎo)線具有傳輸阻