安全兩方計算關鍵技術及應用研究.pdf

1、在如今的大數據時代，數據分析與挖掘已經成為從海量數據中提取出有用信息的一種必要技術手段。然而，目前存在的一個障礙是數據分析者可能并不完全擁有數據，甚至數據完全不在數據分析者手中。而將己方的私有信息透漏給不可信的第三方，由第三方對集中數據集進行分析與挖掘又會對數據持有者的利益造成不可預知的損害。這就會大幅度降低合作計算的可能性。幸運的是，安全多方計算技術的出現使得彌合上述看似矛盾的事實成為可能。其目的在于能夠讓互相不信任的各個參與方在均不

2、泄露本身私有信息的前提下，通過合作計算來完成對整體數據集的分析與挖掘，以得到更精確的分析結果，從而實現共贏。安全兩方計算是安全計算領域里的核心內容。它不僅可以直接應用于實際生活中，同時也是構建多方協(xié)議的基礎。然而，到目前為止，很多安全兩方計算中的關鍵問題尚未得到很好的解決，這也直接導致了很多數據分析與挖掘算法難以實現隱私化的目標。本文針對安全兩方計算中第k小值查詢這一關鍵問題進行深入研究，衍生出三個基本理論問題。并結合這些理論問題的解決

3、方案，實現出三個可實際應用的隱私保護系統(tǒng)。本文的主要創(chuàng)新點列舉如下:
　　1.基于安全第k小值查詢這一核心問題，我們衍生出三個基礎問題，分別為安全靜態(tài)k-近鄰查詢問題、安全動態(tài)k-近鄰查詢問題以及安全McAfee選擇問題，并給出這些問題的形式化定義。
　　2.基于給出的安全靜態(tài)k-近鄰查詢問題的解決方案，我們設計了一個完整的隱私保護協(xié)同Web服務質量預測框架，這個框架可以有效消除個性化推薦與用戶隱私信息泄露之間的矛盾性。我們

4、通過結合同態(tài)加密以及Yao協(xié)議來完成Zheng等人所提出基礎方案中算法的隱私保護實現形式，這也使得我們所提框架的預測精確性可以完全與Zheng等人方法在不考慮任何隱私信息泄露情況下一致的推薦精確性。我們通過采用FasterGC框架來實現服務質量預測協(xié)議中諸多算法的優(yōu)化，使得所提出的隱私保護技術框架不僅僅具有理論意義，而且完全滿足在現實生活中的應用。
　　3.我們設計垂直數據分布下的第k小值查詢算法，該算法可以有效得出與查詢點與數據

5、集其他點中第k小的距離分片，而且所需的通信復雜度僅為O(n)。再利用所得的分片值分別與置換后的距離序列中每個元素做比較，我們可以得到置換后的k近鄰集合，該集合的元素不會包含任何隱私信息。設計出協(xié)議來計算數據點中所有元素的k-distance值，并給出查找所有點o∈Nk(p)的k-distance分片值的高效方法。該類問題也是動態(tài)k近鄰查詢的核心問題，而且到目前為止并沒有有效的解決方法。我們證明所設計的協(xié)議是在半誠實模型下是通用可組合安全

6、的。同時還分析出，對于在具有n條數據集的數據庫O上進行安全LOF查詢協(xié)議，所需的通信和計算開銷均為O(n2)，相對于在不考慮安全情況下的分布式LOF算法運行所需的O(n2)的計算開銷以及O(n)的通信開銷來說，是完全可以被接受的。
　　4.基于Yao協(xié)議以及Batcher排序網絡，我們設計出了一個安全McAfee選擇問題的高效解決方案。該方案的主要開銷是O(nlog2n)次的對稱加密操作，其在競拍者數量相對較小時運行效率很高。針對

7、競拍者數量較多的情況，我們給出了一個更高效的安全McAfee選擇問題解決方案，該方案主要基于安全洗牌以及安全選擇，同時將主要開銷降低至O(n)次對稱加密操作?；谠O計出的安全McAfee選擇問題解決方案，我們設計了關于McAfee拍賣機制以及TRUST這兩個拍賣方案的安全協(xié)議。我們形式化證明了所提協(xié)議滿足半誠實模型下安全性定義標準，并且分析了計算及通信復雜度。另外，我們在FasterGC的基礎上實現了所提協(xié)議的系統(tǒng)，并通過衡量實際運行時