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

張卷美　徐榮華

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

關鍵詞：安全多方計算；同態加密；格密碼

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

1 安全多方計算的概念

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

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

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

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

2 同態加密理論在安全多方

計算中的應用

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

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

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

4 結束語

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

參考文獻

[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] 劉文， 王永濱. 安全多方信息比較相等協議及其應用[J]. 電子學報， 2012， 40（5）： 871-876

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

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

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