安全兩方計(jì)算關(guān)鍵技術(shù)及應(yīng)用研究.pdf

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

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

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

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

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

6、的。同時(shí)還分析出，對(duì)于在具有n條數(shù)據(jù)集的數(shù)據(jù)庫(kù)O上進(jìn)行安全LOF查詢(xún)協(xié)議，所需的通信和計(jì)算開(kāi)銷(xiāo)均為O(n2)，相對(duì)于在不考慮安全情況下的分布式LOF算法運(yùn)行所需的O(n2)的計(jì)算開(kāi)銷(xiāo)以及O(n)的通信開(kāi)銷(xiāo)來(lái)說(shuō)，是完全可以被接受的。
　　4.基于Yao協(xié)議以及Batcher排序網(wǎng)絡(luò)，我們?cè)O(shè)計(jì)出了一個(gè)安全McAfee選擇問(wèn)題的高效解決方案。該方案的主要開(kāi)銷(xiāo)是O(nlog2n)次的對(duì)稱(chēng)加密操作，其在競(jìng)拍者數(shù)量相對(duì)較小時(shí)運(yùn)行效率很高。針對(duì)

7、競(jìng)拍者數(shù)量較多的情況，我們給出了一個(gè)更高效的安全McAfee選擇問(wèn)題解決方案，該方案主要基于安全洗牌以及安全選擇，同時(shí)將主要開(kāi)銷(xiāo)降低至O(n)次對(duì)稱(chēng)加密操作。基于設(shè)計(jì)出的安全McAfee選擇問(wèn)題解決方案，我們?cè)O(shè)計(jì)了關(guān)于McAfee拍賣(mài)機(jī)制以及TRUST這兩個(gè)拍賣(mài)方案的安全協(xié)議。我們形式化證明了所提協(xié)議滿足半誠(chéng)實(shí)模型下安全性定義標(biāo)準(zhǔn)，并且分析了計(jì)算及通信復(fù)雜度。另外，我們?cè)贔asterGC的基礎(chǔ)上實(shí)現(xiàn)了所提協(xié)議的系統(tǒng)，并通過(guò)衡量實(shí)際運(yùn)行時(shí)