歡迎光臨第一論文網,權威的論文發表,我們將竭誠為您服務!
您的位置: 第一論文網 -> 信息安全論文 -> 文章內容

安全多方計算理論研究的理論綜述

作者:第一論文網 更新時間:2015年10月26日 21:04:51

1 引言
  安全多方計算(Secure Mutiparty Computation,SMC)是解決在一個互不信任的多用戶網絡中,兩個或多個用戶能夠在不泄漏各自私有輸入信息時,協同合作執行某項計算任務的問題。它在密碼學中擁有相當重要的地位,是電子選舉、門限簽名以及電子拍賣等諸多應用得以實施的密碼學基礎。
  本文首先介紹安全多方計算理論的相關概念和數學模型,分析它與密碼學的關系,進一步指出它的應用領域,然后綜述其基本協議和近年來的研究成果,從存在的問題入手探討其研究熱點。
  2 基本概念和數學模型
  考慮這樣一個問題,一組參與者,他們之間互不信任,但是他們希望計算一個約定函數時都能得到正確的結果,同時每個參與者的輸入是保密的,這就是安全多方計算問題。
  如果有可信第三方(Trusted Third Party,TTP),參與者只需將自己的輸入保密傳輸給TTP,由TTP計算這個約定函數后,將結果廣播給每個參與者,上述問題得以解決。但是事實上,很難讓所有參與者都信任TTP。因此,安全多方計算的研究主要是針對無TTP情況下,如何安全計算一個約定函數的問題。
  通俗地說,安全多方計算是指在一個分布式網絡中,多個用戶各自持有一個秘密輸入,他們希望共同完成對某個函數的計算,而要求每個用戶除計算結果外均不能夠得到其他用戶的任何輸入信息。
  可以將安全多方計算簡單地概括成如下數學模型:在一個分布式網絡中,有n個互不信任的參與者P1,P2,...Pn,每個參與者Pi秘密輸入xi,他們需要共同執行函數
  F:(x1,x2,...,xn)→(y1,y2,...,yn)
  其中yi為Pi得到的相應輸出。在函數F的計算過程中,要求任意參與者Pi除yi外,均不能夠得到其他參與者Pj(j≠i)的任何輸入信息。
  由于在大多數情況下y1=y2=...=yn,因此,我們可以將函數簡單表示為F:(x1,x2,...,xn)→y。
  3 安全多方計算理論的特點
  安全多方計算理論主要研究參與者的隱私信息保護問題,它與傳統的密碼學有著緊密的聯系,但又不等同。同時,也不同于傳統的分布式計算,有其獨有的特點。
  3.1 安全多方計算是許多密碼協議的基礎
  從廣義上講,多方參與的密碼協議是安全多方計算的一個特例。這些密碼協議可以看成是一組參與者之間存在著各[第一論文網專業提供代寫論文和論文代寫服務,歡迎您的光臨www.ihkdbk.live]種各樣的信任關系(最弱的信任關系就是互不信任),他們通過交互或者非交互操作來完成某一任務(計算約定函數)。這些密碼協議的不同之處在于協議的計算函數不一樣,如電子拍賣是計算出所有參與者輸入的最大值或最小值,而門限簽名是計算出一個正確簽名。
  3.2 安全多方計算不同于傳統的密碼學
  密碼學研究的是在不安全的媒體上提供安全通信的問題。一般來說,一個加密系統由某一信道上通信的雙方組成,此信道可能被攻擊者(竊聽者)竊聽,通信雙方希望交換信息,并且信息盡可能不被竊聽者知道。因此,加密機制就是將信息進行變換,在信息傳送過程中防止信息的篡改和泄漏,目的是系統內部阻止系統外部的攻擊。
  而安全多方計算研究的是系統內部各參與方在協作計算時如何對各自的隱私數據進行保護,也就是說安全多方計算考慮的是系統內部各參與方之間的安全性問題。
  3.3 安全多方計算也不同于傳統的分布式計算
  分布式計算在計算過程中必須有一個領導者(Leader)來協調各用戶的計算進程,當系統崩潰時首要的工作也是選舉Leader;而在安全多方計算中各參與方的地位是平等的,不存在任何有特權的參與方或第三方。
  因此,安全多方計算拓展了傳統的分布式計算以及信息安全的范疇,為網絡計算提供了一種新的計算模式,也為數據保護建立了一種安全策略,并開辟了信息安全新的應用領域。
  4 安全多方計算理論的應用領域
  目前的應用主要在電子選舉、門限簽名、電子拍賣、聯合數據查詢和私有信息安全查詢等方面。
 4.1 電子選舉
  電子選舉協議是安全多方計算的典型應用,也得到研究者們的廣泛重視。將一個安全多方計算協議具體應用到電子選舉工作中,設計出的電子選舉協議可滿足幾個功能:計票的完整性、投票過程的魯棒性、選票內容的保密性、不可復用性和可證實性。
  4.2 門限簽名
  門限簽名是最為熟知的一個安全多方計算的例子,研究門限簽名的文獻很多,目前也比較成熟。應用安全多方計算理論的門限簽名能夠很好地解決這個問題,門限簽名有兩個好處:一是主密鑰不是放在一個地方,而是在一群服務器中分享,即使其中某些服務器被攻破,也不會泄露主密鑰;二是即使某些服務器受到攻擊,不能履行簽名的任務,其他的服務器還可以繼續保持CA的功能,完成簽名任務。這樣CA的安全性可以得到大大提高。
  4.3 電子拍賣
  安全多方計算理論的提出,使得網上拍賣成為現實,電子拍賣是電子商務中非常活躍的一個方面,已經提出的電子拍賣方案很多,大部分方案都是采用可驗證秘密共享協議(Verifiable Secret Sharing,VSS)或使用其思想。電子拍賣協議應該具有一些性質:協議的靈活性、保密性、魯棒性、可驗證性。
  4.4 聯合數據查詢
  信息技術的發展,促進了多學科的交叉協同,資源共享成為新技術研究的必要手段。但是各個數據庫經營者都要求自己的私有信息或知識版權等,避免資源共享時泄露自身保密數據。安全多方計算理論可以解決上述問題,即在不同數據庫資源共享時,多個數據庫可以看成多個用戶聯合起來進行數據查詢。
  4.5 私有信息安全查詢
  在數據庫查詢中,如果能夠保證用戶方僅得到查詢結果,但不了解數據庫其它記錄的信息;同時,擁有數據庫的一方,也不知道用戶方要查詢哪一條記錄,這樣的查詢過程被稱為安全查詢。
  5 安全多方計算理論的基礎協議
  5.1 茫然傳輸協議
  茫然傳輸協議(Oblivious Transfer Protocol,OTP)是SMC的一個極其重要的基礎協議,從理論上說,一般模型下的安全多方計算問題均可以通過茫然傳輸協議來求解。
  茫然傳輸(Oblivious Transfer,OT)的概念是M.Rabin等人于1981年首次提出來的。它是指發送方Alice僅有一個秘密輸入m,他希望以50%的概率讓接收方Bob獲得m,然而Bob不希望Alice知道他是否得到秘密m。隨后,產生了很多OT的變種,如S.Even等人于1985年提出二選一茫然傳輸、G.Brassar等人于1987年推廣為多選一茫然傳輸。
  5.2 秘密比較協議
  秘密數據比較是安全多方計算的一個基本操作,它是指計算雙方各輸入一個數值,他們希望在不向對方泄露自己數據的前提下比較出這兩個數的大小,當這兩個數不相等時,雙方都不能夠知道對方數據的任何信息。該[第一論文網專業提供代寫論文和論文代寫服務,歡迎您的光臨www.ihkdbk.live]問題在設計高效的安全多方計算協議中起著關鍵作用。
  目前有兩類秘密判定協議:第一類秘密判定協議是判定兩個數據是否相等,若不相等則雙方均無法知道對方的任何數據信息;另一類秘密比較協議能判定出兩個輸人的大小關系。
  5.3 置換協議
  安全多方置換問題可以描述為:Alice有一個私密向量X=(x1,x2,...,xn),Bob有一個私密置換函數?仔和私密向量R=(r1,r2,...,rn),Alice需要獲得?仔(X+R),同時要求Alice不能獲得?仔和任何ri的信息,Bob也不能獲得任何xi的信息。
  5.4 點積協議
  點積問題可以描述為:Alice有一個私密向量X=(x1,x2,...,xn),Bob有另一個私密向量Y=(y1,y2,...,yn),Alice需要獲得u=X·Y+v=■xiyi+v,這里v僅是Bob知道的隨機數。同時要求Alice不能獲得X·Y的值和任何yi的信息,Bob也不能獲得u的值和任何xi的信息。
  6 安全多方計算理論研究進展
  安全多方計算理論自提出起,由于它拓展了計算和信息安全范疇,其研究者眾多、發展迅速,并取得了較大的成績,研究進展經歷了理論形成、協議設計完善和應用研究等階段。
  6.1 理論形成
  安全多方計算問題首先由A.C.Yao于1982年提出。5年后,O.Goldreich、S.M icali和A.Wigderson三位學者提出了密碼學安全的可以計算任意函數的安全多方計算協議。他們證明了在被動攻擊情況下,n-private協議是存在的,在主動攻擊情況下,n-resilient協議是存在的,并展示了如何構造這些協議。
  1988年,M.Ben-Or、S.Goldwasse和A.Wigderson,以及D.Chaum、C.Crepeau和I.Damgard幾乎同時證明了在信息論安全模型中,被動攻擊情況下當串通攻擊者數t  6.2 安全多方計算協議的設計完善
  隨后,安全多方計算吸引了大量學者的注意,他們根據不同的計算模型與安全模型對安全多方計算協議做了一些有益的改進,主要體現在幾個方面,這也是研究者們關注的焦點:①設計一般意義的安全多方計算協議;②對安全多方計算協議進行形式化的定義;③對通用的安全多方計算協議進行裁減將其應用于不同的實際問題;④構造新的安全多方計算協議;⑤對安全多方計算攻擊者的結構進行定義。
  6.3 應用研究
  1998年,Gold Reich指出用通用協議來解決安全多方計算問題中的一些特殊實例是不切實際的,對于一些特殊問題需要用一些特殊方法才能達到高效性。這一思想迅速促進了安全多方計算在一些特殊領域應用研究的發展,近年來很多學者已將安全多方計算技術引入傳統的數據挖掘、計算幾何、私有信息檢索、統計分析等領域。
 由此產生了新的研究方向,如保護隱私的數據挖掘(Privacy Preserving Data Mining,PPDM)、保護隱私的計[第一論文網專業提供代寫論文和論文代寫服務,歡迎您的光臨www.ihkdbk.live]算幾何(Privacy Preserving Computation Geometry,PPCG)、私有信息檢索(Private Information Retrieval,PIR)、保護隱私的統計分析(Privacy Preserving Statiscal Analysis,PPSA)等,為解決一些重要的安全應用問題提供了技術基礎。
  7 安全多方計算理論研究熱點
  目前學者們針對安全多方計算理論的研究,主要在密碼學和信息論兩種安全模型下進行,研究熱點集中在幾個方面。
  7.1 一般安全多方計算協議
  為節省資源,研究一種通用一般化的協議,目的在于設計一種高效、安全、能夠計算任意函數的安全多方計算協議,通過這種通用協議來解決所有涉及到的安全多方計算問題。
  7.2 對一般安全多方計算協議裁減
  如果一個協議是普適的,那么必然會犧牲一些性能上的代價來滿足其廣泛適用性。針對一個具體的應用,如電子選舉,對一般化的安全多方計算協議進行一點裁減,去掉一些對這個具體應用沒有意義的部分,可以大大地提高效率。具體地說,是如何將安全多方計算理論與技術應用到具體的環境。
  7.3 安全多方計算的定義
  由于安全多方計算協議的構造形式多種多樣,而各研究者基于的安全模型不一致,而得出的應用條件也是不一樣的。如R.Canetti等人針對安全信道模型下的安全多方計算給出了形式化的定義,首先提出可信第三方TTP的安全多方計算,然后考慮如何用協議來模擬TTP的作用。這與其他模型下的安全多方計算的思路和協議構建方法完全不同,即使在同一模型下,但協議的構造方法也會影響到具體應用。
  雖然安全多方計算的目的、性質、應用環境都得到本領域學者的認可,但是至今還沒有一個大家認同的、完備的定義。因此,安全多方計算的完備定義一直是研究熱點。
  7.4 新的安全多方計算協議構造方法
  目前大部分研究者們在設計安全多方計算協議時,基本都以VSS的子協議為構造基石,設計出的協議在答題結構上都是類似的,這樣在解決通信效率和安全性上沒有實質性突破。是否存在新的構造方法來設計高效安全多方計算協議,這是研究者們一直在探索的問題之一。
  7.5 安全多方計算協議生成器
  現有的許多安全多方計算協議的研究,基本在于安全域定義上如何完成基本運算就停止了。因為,從理論上講,任何函數可以安全地被計算就已解決私有信息保護問題。但是,距離實際應用還有一步需要跨越。
  安全多方計算協議計算器目的在于聯系基本定義和函數安全計算,其作用就是彌補這具體應用一步,多方計算生成器的輸入就是任意函數f和計算域上基本運算的子協議,輸出是安全計算函數f的協議。目前,許多學者已經提到了安全多方計算生成器的重要性,但并沒有深入研究。
  7.6 惡意模型下的安全多方計算
  現在對安全多方計算問題的研究主要基于密碼學和信息論等安全模型,要求所有參與方必須嚴格按照協議的流程進行計算,不能惡意修改協議的運行或提供虛假數據。
  而在[第一論文網專業提供代寫論文和論文代寫服務,歡迎您的光臨www.ihkdbk.live]實際的協作計算中,可能協議的參與方是惡意用戶,此時,我們需要設計高效的惡意模型下的安全多方計算協議。盡管從理論上說,任何通用模型下的SMC協議都可以轉換成惡意模型下的SMC協議,但這種理論轉換在效率上是不可行的。因此,惡意模型下的安全多方計算問題需要得到進一步的研究。
  8 結束語
  安全多方計算理論及其應用是一個迅速崛起的、理論性很強的研究領域,它牽涉到密碼學的各個分支,有著廣闊的應用領域。從理論上講在分布式的環境中,有多個參與者的任何協議都可以看作是安全多方計算的一個特例。如果我們設計了一個安全高效的安全多方計算協議,那么理論上所有的分布式環境中的多個參與者的協議,都可以用這個安全多方計算協議來解決。所以,從這個意義上來看,安全多方計算協議有著非常誘人的應用前景。
  參考文獻
  [1] 秦靜,張振峰,馮登國 等. 無信息泄漏的比較協議. 軟件學報,2004,15(3):421-427.
  [2] 羅永龍. 安全多方計算若干關鍵問題及其應用研究. 中國科學技術大學博士學位論文,2005.
  [3] 劉木蘭,張志芳. 密鑰共享體制和安全多方計算. 北京:電子工業出版社,2008.
  [4] Atallah M J,Du W. Secure Multi-Party Computational Geometry. In Lecture Notes in Computer Science, 2125,Springer Verlag. Proceedings of 7th International Work shop on Algorithms and Data Structures(WADS 2001),Providence, RhodeIsland ,USA. 2001:165-179.
  [5] Alfred J M, Paul C V, Scott A V.著,胡磊,王鵬等譯 . 應用密碼學手冊. 北京:電子工業出版社,2005:107-223.
  [6] Li S D, Dai Y Q. Secure Two-Party Computational Geometry. Journal of Computer Science and Technology, 2005,20(2):258-263.
  [7] Ronald Cramer, Ivan Damgfird, Ueli Maurer. General secure multi-party computation from any linear secret-sharing scheme. Lecture Notes in Computer Science, 2000(1807):316-325.
  作者簡介:
  王婷(1981-),女,北京師范大學,本科學士學位,首都醫科大學附屬北京婦產醫院信息科,助理工程師;主要研究方向和關注領域:網絡信息安全。 本文選自《信息安全與技術》2014年第5期,版權歸原作者和期刊所有。

广西快乐10分结果分布图