安全多方計(jì)算中的若干關(guān)鍵問題及其應(yīng)用研究.pdf

1、安全多方計(jì)算(簡稱SMC)是指在一個(gè)互不信任的多用戶網(wǎng)絡(luò)中，兩個(gè)或多個(gè)用戶能夠在不泄漏各自私有輸入信息時(shí)協(xié)同合作執(zhí)行某項(xiàng)計(jì)算任務(wù)。該問題首先由圖靈獎得主A.C.Yao于上世紀(jì)80年代初提出，而后O.Goldreich，S.Micali和A.Wigderson提出了密碼學(xué)安全的可以計(jì)算任意函數(shù)的安全多方計(jì)算協(xié)議。1988年，M.Ben-Or，S.Goldwasser和A.Wigderson與D.Chaum，C.Crepeau和I.Damg

2、ard幾乎同時(shí)證明了信息論安全的安全多方計(jì)算協(xié)議的存在性，并分別指出了被動攻擊與主動攻擊情況下串通攻擊者數(shù)目的理論上界。上述工作都集中于從理論上證明安全多方計(jì)算問題的可解性，由于其中大量使用零知識證明，使得協(xié)議的通信復(fù)雜性很高而極不實(shí)用。此后，安全多方計(jì)算吸引了許多學(xué)者的注意，他們在不同的模型下對協(xié)議做了一些有益的改進(jìn)。 隨著Internet的發(fā)展和普及，人們開始意識到應(yīng)該有實(shí)用的SMC系統(tǒng)來解決某些特定的實(shí)際問題。直到1998

3、年，O.GoldRiech指出用通用協(xié)議來解決安全多方計(jì)算問題的一些特殊實(shí)例是不切實(shí)際的，對于一些特殊問題需要用一些特殊方法才能達(dá)到高效性，正是這一思想使得近年來不少學(xué)者逐漸將SMC技術(shù)引入到數(shù)據(jù)挖掘、計(jì)算幾何、統(tǒng)計(jì)分析、電子選舉等領(lǐng)域，促進(jìn)安全多方計(jì)算朝著能夠解決各類實(shí)際應(yīng)用問題的方向發(fā)展。目前這些求解方法基本都是將待解決問題轉(zhuǎn)換為目前已有的基本SMC協(xié)議后求解，但是缺乏求解特殊SMC問題的基本方法和步驟，可用于求解SMC問題的基礎(chǔ)協(xié)

4、議也極少，并且現(xiàn)有的一些SMC基礎(chǔ)協(xié)議在性能上也遠(yuǎn)未達(dá)到實(shí)用的程度，這都制約了SMC技術(shù)的進(jìn)一步發(fā)展。 本論文的研究工作分為兩部分，第一部分致力于研究SMC的基本理論及基礎(chǔ)協(xié)議。 首先，本文對特殊安全多方計(jì)算問題的求解方法進(jìn)行了研究，提出了按照“數(shù)據(jù)偽裝-交互計(jì)算-結(jié)果還原-協(xié)議分析”的過程求解SMC問題的基本策略，即：協(xié)作計(jì)算用戶首先使用數(shù)據(jù)偽裝技術(shù)對自己輸入的隱私信息進(jìn)行偽裝，然后他們在偽裝的數(shù)據(jù)集合上借助SMC基礎(chǔ)

5、協(xié)議進(jìn)行交互計(jì)算，再結(jié)合問題的具體特性，將得到的解恢復(fù)成原問題的最終解。這一方法準(zhǔn)確概括了求解特殊SMC問題所必需的基本步驟，為解決各類特殊SMC問題提供了基本思路。 緊接著本文研究了數(shù)據(jù)偽裝技術(shù)，介紹了函數(shù)的秘密共享方法及Z+V偽裝技術(shù)，從多精度計(jì)算的角度探討了同態(tài)加密技術(shù)在SMC中的性能，并對其中最核心的方冪模算法及多精度除法進(jìn)行了研究，設(shè)計(jì)出了快速的改進(jìn)算法。數(shù)據(jù)偽裝技術(shù)的研究為設(shè)計(jì)SMC協(xié)議做了重要鋪墊。 在此基

6、礎(chǔ)上，本文提出了若干基礎(chǔ)的安全多方計(jì)算問題并設(shè)計(jì)了一組高效的SMC基礎(chǔ)協(xié)議，包括乘法協(xié)議、叉積協(xié)議、秘密比較協(xié)議、數(shù)據(jù)對應(yīng)成比例協(xié)議及距離協(xié)議等。尤其是創(chuàng)造性地將計(jì)算幾何中叉積的概念應(yīng)用于秘密數(shù)據(jù)比較，提出了一個(gè)新的秘密比較方法。這些基礎(chǔ)協(xié)議為安全多方計(jì)算中各參與方能在偽裝的數(shù)據(jù)集上進(jìn)行交互計(jì)算奠定了基礎(chǔ)，是解決SMC問題的關(guān)鍵技術(shù)。 本文的第二部分主要研究安全多方計(jì)算在一些特殊領(lǐng)域的應(yīng)用問題。 首先，本文探討了SMC在

7、計(jì)算幾何中的應(yīng)用問題，系統(tǒng)研究了保護(hù)私有信息的平面及空間幾何對象之間的相對位置判定方法并設(shè)計(jì)了相應(yīng)的判定協(xié)議。這些問題不僅在軍事、商業(yè)、金融等領(lǐng)域有著重要的應(yīng)用前景，也有助于SMC技術(shù)在計(jì)算幾何領(lǐng)域的進(jìn)一步應(yīng)用。 其次，本文首次提出了將隨機(jī)化算法應(yīng)用于求解SMC問題的思想，并以多邊形相交判定及兩圓相交面積計(jì)算為例研究了蒙特卡洛算法、數(shù)值概率算法在安全多方計(jì)算中的應(yīng)用。這兩個(gè)問題的解決為求解特殊SMC問題提供了一種新的思路與方法。