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

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

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

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

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

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