安全多方計算中的若干關鍵問題及其應用研究.pdf

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

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

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

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

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

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

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