安全多方計算中若干基礎(chǔ)協(xié)議及應(yīng)用的研究.pdf

1、安全多方計算(Secure Multi-party Computation，SMC)是指一組互不信任的參與者，在不泄漏各自私有信息的前提下進行的多方合作計算。自圖靈獎得主A.C.Yao于上世紀(jì)80年代初提出安全多方計算的概念以來，該領(lǐng)域已經(jīng)成為現(xiàn)代密碼學(xué)的重要研究內(nèi)容之一，引起了眾多研究者的興趣。目前，安全多方計算研究主要分為兩個方面：一方面是對安全多方計算基礎(chǔ)理論的研究，包括對安全性定義的研究、安全模型和敵手模型的研究、安全性相關(guān)的基

2、本定理研究以及安全多方計算協(xié)議的通用設(shè)計方法研究等。這部分研究取得了眾多的成果，例如，目前已經(jīng)有嚴(yán)格、合理的半誠實模型下和惡意模型下的安全性定義，已經(jīng)有若干安全可行性的一般性結(jié)論，已經(jīng)出現(xiàn)通用的方法來設(shè)計計算任意函數(shù)性的安全協(xié)議等。另一方面，隨著合作計算與隱私保護越來越受到人們的重視，安全多方計算被引入到各個應(yīng)用領(lǐng)域，力求解決實際應(yīng)用問題中的隱私保護問題。這些領(lǐng)域包括數(shù)據(jù)挖掘、計算幾何、統(tǒng)計分析與科學(xué)計算、電子選舉等等。盡管基礎(chǔ)理論的研

3、究已經(jīng)提供了通用的方法來設(shè)計任意函數(shù)性的安全多方計算協(xié)議，但研究者普遍認(rèn)為，通用方法來解決安全多方計算問題的一些特殊實例是不切實際的，對于一些特殊問題需要用一些特殊方法才能達到高效性。因此，在應(yīng)用領(lǐng)域出現(xiàn)了許多特定的安全多方計算協(xié)議，如一些保護私有信息的數(shù)據(jù)挖掘協(xié)議，一些保護私有信息的計算幾何協(xié)議以及一些安全多方統(tǒng)計計算協(xié)議等。 盡管已經(jīng)有不少的研究成果，但安全多方計算領(lǐng)域仍然有許多值得研究的內(nèi)容．在基礎(chǔ)理論方面，更實用的理論模

4、型需要被進一步研究。在安全協(xié)議設(shè)計方面，目前用來計算基本函數(shù)性的安全多方計算基礎(chǔ)協(xié)議還不夠充分，許多新的從應(yīng)用問題中抽象出來的基本函數(shù)性，需要設(shè)計新的安全基礎(chǔ)協(xié)議。在應(yīng)用領(lǐng)域，應(yīng)用的多樣性使得目前的安全多方計算應(yīng)用協(xié)議還遠遠不能滿足需求。無論是設(shè)計新的應(yīng)用協(xié)議解決新問題，還是改進已有應(yīng)用協(xié)議使之更高效更安全，都需要更進一步的工作。 有鑒于此，本文的研究內(nèi)容主要包括以下幾個方面： 1)研究安全模型和安全性分析方法的適用性，

5、探討合理有效的安全性分析方法。 2)研究安全多方計算基礎(chǔ)問題，設(shè)計若干新的安全多方計算基礎(chǔ)協(xié)議，為應(yīng)用協(xié)議的設(shè)計提供更多的工具。 3)研究數(shù)據(jù)挖掘中關(guān)聯(lián)規(guī)則挖掘的隱私保護問題，設(shè)計安全多方計算協(xié)議，在數(shù)據(jù)水平劃分的共享方式下，保護各種不同形式關(guān)聯(lián)規(guī)則挖掘中的私有信息。 4)研究安全多方計算在計算幾何問題中的應(yīng)用，設(shè)計新協(xié)議解決若干計算幾何問題中的隱私保護問題。 5)研究安全多方計算在安全查詢中的應(yīng)用，設(shè)計

6、實用解決方案解決安全查詢問題。 與之對應(yīng)，本文取得了一些研究成果，主要包括： 1)探討了多種新的可能的安全性分析模型的構(gòu)建方法，分析了各個模型之間的層次關(guān)系，提出了根據(jù)協(xié)議設(shè)計需要來選擇不同的安全性分析方法的思路，并作為本文研究的指導(dǎo)思想。 2)在基礎(chǔ)協(xié)議的設(shè)計方面，提交了若干新的基礎(chǔ)協(xié)議，分別改進了安全求并集協(xié)議的效率；完成了兩個共享秘密的安全兩方乘法計算：完成了兩多項式的安全乘法計算等。這些新的基礎(chǔ)協(xié)議為解決

7、應(yīng)用問題提供了更多的有效工具。 3)在保護私有信息的關(guān)聯(lián)規(guī)則挖掘方面，設(shè)計了保護私有信息的量化關(guān)聯(lián)規(guī)則挖掘協(xié)議，在不泄漏私有信息的前提下完成了量化關(guān)聯(lián)規(guī)則挖掘；設(shè)計了安全的統(tǒng)計量化規(guī)則挖掘協(xié)議；探討了帶權(quán)關(guān)聯(lián)規(guī)則挖掘與多支持度關(guān)聯(lián)規(guī)則挖掘中的隱私保護問題。這一系列的協(xié)議豐富了保護私有信息的數(shù)據(jù)挖掘的研究內(nèi)容，也為安全多方計算技術(shù)的應(yīng)用推廣做出了一定的貢獻。 4)在保護私有信息的計算幾何方面，設(shè)計了新的安全多方計算協(xié)議，分