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

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

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

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

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

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