安全多方計(jì)算幾何協(xié)議的研究與應(yīng)用.pdf

1、不斷發(fā)展的網(wǎng)絡(luò)技術(shù)以及高性能計(jì)算機(jī)、網(wǎng)格技術(shù)的出現(xiàn),極大地改變了傳統(tǒng)意義上的合作計(jì)算方式。處于不同地理位置的多個(gè)用戶可以利用性能優(yōu)良的網(wǎng)絡(luò)協(xié)同完成某個(gè)任務(wù),但這也帶來一個(gè)亟待解決的問題,敏感數(shù)據(jù)的安全性如何保證。安全多方計(jì)算(Secure Multi-Party Computation,SMC)正是在這樣的背景之下產(chǎn)生。它是指在一個(gè)互不信任的多用戶網(wǎng)絡(luò)中,兩個(gè)或多個(gè)用戶能夠在不泄漏各自私有輸入信息時(shí)協(xié)同執(zhí)行某項(xiàng)計(jì)算任務(wù)。我們在研究上將任

2、務(wù)抽象成某個(gè)具體的函數(shù),安全多方計(jì)算要求滿足兩個(gè)基本性能,一是要保證正確性,二是要達(dá)到保密性。這個(gè)問題首先由圖靈獎(jiǎng)得主A.C.Yao于上世紀(jì)80年代初提出,目前已經(jīng)產(chǎn)生了許多研究方向,比如數(shù)據(jù)挖掘,計(jì)算幾何,統(tǒng)計(jì)分析,電子選舉等。
　　本文的研究工作主要集中在保護(hù)私有信息的計(jì)算幾何問題上。計(jì)算幾何作為計(jì)算機(jī)科學(xué)的一個(gè)分支,它主要研究解決幾何問題的算法。計(jì)算幾何在現(xiàn)代工程和數(shù)學(xué)領(lǐng)域有著廣泛應(yīng)用,比如在圖像處理、機(jī)器人技術(shù)、超大規(guī)模集

3、成電路設(shè)計(jì)和統(tǒng)計(jì)等諸多領(lǐng)域有著十分重要的應(yīng)用。在安全多方計(jì)算領(lǐng)域中的計(jì)算幾何有著全新的應(yīng)用前景。目前已經(jīng)有很多學(xué)者對涉及到保護(hù)私有信息的計(jì)算幾何問題進(jìn)行了研究,并得到了很好的結(jié)果。本文的主要工作有:
　　首先,研究了最近點(diǎn)對問題。在2001年Mikhail J Atallah和Wenliang Du前瞻性的提出該問題的時(shí)候,并沒有給出具體的實(shí)現(xiàn)方法,并且直到目前為止相關(guān)的研究文獻(xiàn)很少。本文重點(diǎn)對該問題進(jìn)行分析研究,利用點(diǎn)積協(xié)議和距

4、離計(jì)算協(xié)議設(shè)計(jì)了一個(gè)保護(hù)私有信息的最近點(diǎn)對協(xié)議。并且與已有的協(xié)議進(jìn)行了比較,該協(xié)議在安全性方面有很大的提高。
　　其次,深入研究了保護(hù)私有信息的點(diǎn)包含問題。分析總結(jié)了現(xiàn)有協(xié)議的實(shí)現(xiàn)原理以及優(yōu)缺點(diǎn),包括利用三角形面積協(xié)議,利用隨機(jī)化方法以及利用叉積協(xié)議判定。在此基礎(chǔ)上針對基于叉積協(xié)議的點(diǎn)包含問題做了局部的修改,使之達(dá)到更大的安全性;文章接下來,設(shè)計(jì)了一個(gè)保護(hù)私有信息的射線與線段相交協(xié)議,并且利用該協(xié)議提出了基于交點(diǎn)個(gè)數(shù)的判定點(diǎn)是否包

5、含在凹多邊形內(nèi)部的協(xié)議。該協(xié)議可以大大的擴(kuò)大點(diǎn)包含問題的應(yīng)用范圍。
　　緊接著,研究了圓包含問題以及多邊形的包含問題。提出了解決這兩個(gè)問題的相關(guān)協(xié)議并且分析了其安全性,正確性及效率問題。類似的SMC領(lǐng)域的包含問題可以作為在軍事,商業(yè)等領(lǐng)域的計(jì)算模型,同時(shí)也有助于SMC技術(shù)在計(jì)算幾何領(lǐng)域的進(jìn)一步應(yīng)用。
　　最后,研究了幾何計(jì)算中的保護(hù)私有信息的多邊形凹凸性的判定問題。首先基于線性變換構(gòu)建了兩類叉積協(xié)議,然后結(jié)合向量優(yōu)先協(xié)議設(shè)計(jì)