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

1、安全多方計(jì)算(簡(jiǎn)稱SMC)是指在一個(gè)互不信任的多用戶網(wǎng)絡(luò)中，兩個(gè)或多個(gè)用戶能夠在不泄漏各自私有輸入信息時(shí)協(xié)同合作執(zhí)行某項(xiàng)計(jì)算任務(wù)。該問(wèn)題首先由圖靈獎(jiǎng)得主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é)議的存在性，并分別指出了被動(dòng)攻擊與主動(dòng)攻擊情況下串通攻擊者數(shù)目的理論上界。上述工作都集中于從理論上證明安全多方計(jì)算問(wèn)題的可解性，由于其中大量使用零知識(shí)證明，使得協(xié)議的通信復(fù)雜性很高而極不實(shí)用。此后，安全多方計(jì)算吸引了許多學(xué)者的注意，他們?cè)诓煌哪Ｐ拖聦?duì)協(xié)議做了一些有益的改進(jìn)。 隨著Internet的發(fā)展和普及，人們開始意識(shí)到應(yīng)該有實(shí)用的SMC系統(tǒng)來(lái)解決某些特定的實(shí)際問(wèn)題。直到1998

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

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

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

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

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