特殊安全多方計算協(xié)議的研究.pdf

1、因特網的發(fā)展使不同地域的網絡用戶的合作計算蓬勃發(fā)展。如果這種計算可以交給一個可信方完成，那么這個問題是非常簡單的?？尚欧皆谑盏礁饔脩舻拿孛軘?shù)據(jù)后，計算目標函數(shù)的值，并把結果返回給每個用戶。然而，在現(xiàn)實中很難找到這樣的可信方。如果不允許有可信方，那么安全多方計算就提供了必要的技術解決這一實際問題。
　　 安全多方計算協(xié)議要解決的問題可以描述如下：設P={P1，P2，…，Pn）是n個參與者的集合，他們想要通過相互傳遞信息的方式“安全

2、地”計算某個給定函數(shù)f（x1，x2，…，xn）=（y1，y2，…，yn）。其中，函數(shù)f的n個輸入x1，x2，…，xn分別由n個參與者P1，P2，…，Pn秘密地掌握而不被其他人知道，在計算結束后，要求P1，P2，…，Pn分別得到y(tǒng)1，y2，…，yn，這里的安全性主要指參與者Pi（i=1，2，…，n）得不到關于參與者Pj的xj和yj（j=1，2，…，i-1，i+1，…，n）的任何信息（xi和yi隱含信息除外）。
　　 在過去的三十年

3、中，有大量工作是針對一般函數(shù)研究的，即對一般安全多方計算的研究，這極大地豐富了安全多方計算的理論。然而，針對一般函數(shù)設計的安全多方計算協(xié)議由于復雜度過高而在實際應用中并不可行，所以一些國際國內的密碼學者轉向對特定函數(shù)進行特殊安全多方計算的研究。
　　 本文研究了兩類特殊安全多方計算協(xié)議--保密比較協(xié)議和安全凸包協(xié)議，主要貢獻如下：
　　 1.定義了帶有茫然第三方的兩方保密比較的安全性，并在此基礎上分析了基于φ-隱性假設和

4、同態(tài)公鑰加密的帶有茫然第三方的兩方保密比較協(xié)議的正確性與安全性；設計了一個基于對稱加密的帶有茫然第三方的兩方保密比較協(xié)議，并在安全模型下證明了該協(xié)議的秘密性；對基于同態(tài)公鑰加密的保密比較協(xié)議和基于對稱加密的比較協(xié)議，從通信復雜度、計算復雜度和安全性等方面分析和比較得出：前者更具有理論價值，而后者更具有實際應用價值。
　　 2.Wang第一次基于包裹法和快包法設計了兩個安全兩方凸包計算協(xié)議，本文分析了其基于快包法協(xié)議的錯誤；在此基

5、礎上遞進地提出了兩個改進協(xié)議，并分析了改進協(xié)議的正確性和秘密性；從計算復雜度和通信復雜度兩個方面對包裹法協(xié)議和兩個改進協(xié)議分析和比較后發(fā)現(xiàn)：改進協(xié)議Ⅰ在效率上優(yōu)于包裹法協(xié)議；改進協(xié)議Ⅱ在一般情況（已知點個數(shù)遠大于凸包邊界點個數(shù)）下的效率優(yōu)于其他兩者的結論。
　　 3.改進協(xié)議Ⅱ是在改進協(xié)議Ⅰ的基礎上提出的，其調用了改進協(xié)議Ⅰ，本質上說，改進協(xié)議Ⅰ是改進協(xié)議Ⅱ的核心。本文實現(xiàn)了改進協(xié)議Ⅰ的核心算法，從而驗證了兩個改進協(xié)議的正確性。