安全多方計算技術研究與應用

張卷美　徐榮華

摘要：認為同態(tài)密碼的本質是通過密文運算，實現(xiàn)相對應的明文運算?；谕瑧B(tài)密碼、格理論密碼，分別設計了安全多方計算協(xié)議，解決了安全兩方線段求解直線相交問題和聚類分析中一種經常遇到的加權平均問題。認為目前安全多方計算的實際應用比較滯后，但隨著其理論的不斷成熟以及各種密碼理論基礎技術的不斷發(fā)展，安全多方計算最終會為新時代下的信息安全提供服務。

關鍵詞：安全多方計算；同態(tài)加密；格密碼

安全多方計算是密碼學的基礎問題之一，概括了大多數(shù)密碼協(xié)議，如認證協(xié)議、在線支付協(xié)議、公平交換協(xié)議、拍賣協(xié)議、選舉協(xié)議、密文數(shù)據庫查詢與統(tǒng)計等等。在電子選舉、電子投票、秘密共享等場景有關廣泛的應用[1-2]。

1 安全多方計算的概念

針對安全多方計算，2004年Goldreich給出了一個簡單、完整、統(tǒng)一形式化定義[3]。他將安全多方計算抽象成一個隨機過程：[U1、U2、……、Un]是n互不信任的參與方，共同計算函數(shù)[f（x1，x2，…，xn）=（y1，y2，…，yn）]，其中函數(shù)f是一個計算復雜度為概率多項式的隨機函數(shù)，Ui擁有秘密輸入[xi∈（0，1）*]，通過計算希望獲得[yi∈（0，1）*]，但不向其他參與方泄露任何信息。

在理想的世界中，假設第三方是可信的，計算函數(shù)f，則其計算時間亦為概率多項式時間，抽象為交互式圖靈機，其執(zhí)行過程為可信第三方收集各方輸入，然后計算結果，再分別秘密發(fā)送結果給對應參與方。理想世界中敵手IA執(zhí)行協(xié)議過程中獲取到的輸出變量為IDEAL（IA）。

在現(xiàn)實的世界中，可信第三方不存在，同樣計算函數(shù)f，則需要收集各方輸入，然后計算輸出結果，再分別秘密發(fā)送結果給對應參與方。理想世界不同的是敵手RA可以竊聽并收集誠實參與方之間的通信信息，但不能修改其通信內容。現(xiàn)實世界中敵手IA執(zhí)行協(xié)議過程中獲取到的輸出變量為REAL（RA）。

對于現(xiàn)實世界中的任意敵手RA，都存在相應理想敵手IS，若在計算過程中，使得IDEAL（IA）和REAL（RA）計算不可區(qū)分，即 IDEAL（IA）≈REAL（RA），則認為安全多方計算協(xié)議是安全的。

2 同態(tài)加密理論在安全多方

計算中的應用

同態(tài)加密[4]能夠在不對密文解密的情況下，對密文進行計算，從而實現(xiàn)對明文的計算，這與安全多方計算中在不泄露任何數(shù)據隱私信息的情況下完成安全計算的需求不謀而合。

目前，同態(tài)密碼是密碼學領域研究的熱點之一。同態(tài)的分類較為常見的是：單同態(tài)、雙同態(tài)、無限同態(tài)和有限同態(tài)，這是一個較為概括性的分類方法。

上述安全多方計算協(xié)議借助交互多方中的某一位成員進行計算，其他成員只與該成員進行交互，最終計算方將所得結果秘密傳送給各個成員。該方案類似于單方交互協(xié)議，可以最終實現(xiàn)安全多方計算，但是在效率上有待提高。

4 結束語

作為密碼學研究的一個重要方向，安全多方計算既古老又年輕。與理論研究成果相比，安全多方計算的實際應用比較滯后，主要是效率和安全性還不能完全滿足現(xiàn)實的需求。根據安全多方計算的特點，我們已經為各種不同的應用場景設計了相應的安全多方計算方案，主要集中在大數(shù)據隱私保護、云計算和文數(shù)據庫檢索和統(tǒng)計等安全性需求較高的應用場景中。未來還有很多研究要做，主要集中在惡意型下的多方安全計算問題中，因為惡意模型環(huán)境下參與方可以完全不遵守協(xié)議規(guī)則。雖然在現(xiàn)階段，安全多方計算的應用還存在困難，但是隨著安全多方計算理論的不斷成熟以及各種密碼理論基礎技術的不斷應用，安全多方計算最終會走入我們的實際生活，為互聯(lián)網時代、云計算時代、大數(shù)據時代的信息安全服務。

參考文獻

[1] YAO Q Z. Protocols for Secure Computations[C]// Proceedings of 23rd Annual IEEE Symposium on Foundations of Computer Science，Chicago， USA， 1982： 160- 164

[2] GOLDREICH O， MICALI S， WIGDERSON A. How to Play Any Mental Game or A Completeness Theorem for Protocols with Honest Majority [C]//STOC 1987， 1987： 218-229

[3] GOLDREICH O. Foundations of Cryptography： Volume II - Basic Applications [M]. Britain： Cambridge University Press， 2004

[4] GENTRY C. A Fully Homomorphic Encryption Scheme [D]. USA： Stanford University， 2009

[5] DU W L. Secure Multiparty Computation Problems and Their Applications[C]//A Review and Open Problems New Security Paradigms Workshop 2001， Cloudcroft ， New Mexico， USA， 2001

[6] 劉文， 王永濱. 安全多方信息比較相等協(xié)議及其應用[J]. 電子學報， 2012， 40（5）： 871-876

[7] 陳志偉，張卷美，李子臣. 基于ElGamal變體同態(tài)的安全兩方計算協(xié)議設計[J]. 通信學報， 2015， 36（2）： 1-8

[8] 劉立強，李子臣.一種基于NTRU的安全兩方計算協(xié)議[C]//全國信息隱藏暨多媒體信息安全學術大會（CIHW）， 北京， 中國， 2012

[9] 胡予濮. 一個新型的NTRU類數(shù)字簽名方案[J]. 計算機學報， 2008， 31（9）： 1661-1666