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

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

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

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

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

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

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

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

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

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