夏 超 ，仲 紅 ，2，石潤華 ，2

1.安徽大學(xué) 計算機科學(xué)與技術(shù)學(xué)院，合肥 230601

2.安徽大學(xué) 計算與信號處理教育部重點實驗室，合肥 230039

1 引言

安全多方計算[1-2]（Secure Multi-party Computation，SMC）主要研究網(wǎng)絡(luò)環(huán)境下互不信任參與方之間的協(xié)作計算問題。通常有多個成員參與協(xié)作計算，但目前安全多方計算問題多數(shù)局限在兩方安全計算問題[3-4]的研究中。文獻[5]總結(jié)了部分特殊的安全兩方計算問題，包括安全兩方科學(xué)計算、安全兩方幾何計算、安全兩方統(tǒng)計分析等，并指出了多方計算協(xié)議由兩方協(xié)議推廣得到的方法。雖然安全多方計算問題的研究取得了一定的成果[6-7]，但是特殊的安全多方計算協(xié)議距離應(yīng)用需求還有很大的差距。安全多方乘積（SMC）正是這樣的一類特殊安全多方計算問題。

安全多方乘積作為SMC最基本的運算之一，近年來得到了廣泛的關(guān)注。文獻[8]將一般的多方求積問題轉(zhuǎn)化成求和問題；在此基礎(chǔ)上，文獻[9]給出一個安全兩方乘積協(xié)議并應(yīng)用到除法協(xié)議中；文獻[10]提出基于簽名技術(shù)的安全多方乘積協(xié)議，可有效地防止攻擊者對信息的篡改；文獻[11]將普通的數(shù)量乘法擴展到矩陣乘法，提出了多方安全矩陣乘積協(xié)議并應(yīng)用到求解線性方程組、矩陣特征值的SMC協(xié)議中?，F(xiàn)有這些協(xié)議因采用茫然傳輸技術(shù)[12]，協(xié)議無須第三方的參與，安全性高，在秘密分享、科學(xué)計算等安全多方計算領(lǐng)域中具有重要價值。但是，這些多方乘積協(xié)議都是由兩方協(xié)議的擴展得到的，參與方兩兩之間需要頻繁通信，造成協(xié)議的通信代價高；而利用茫然傳輸技術(shù)的數(shù)據(jù)量大，造成了網(wǎng)絡(luò)帶寬消耗大，協(xié)議的執(zhí)行效率低等問題。

多方參與的協(xié)作計算中，通信代價是衡量協(xié)議性能的重要因素。本文利用同態(tài)加密技術(shù)，在半誠實模型下，設(shè)計了適用于不同通信環(huán)境下的串行和并行的安全多方乘積協(xié)議。比如，在這樣的復(fù)雜通信環(huán)境中：參與方Alice計算一個中間數(shù)據(jù)時間為1，而Alice與其他參與方通信一次的時間要遠遠超過1。此時，參與方之間如果頻繁的通信會造成較高的通信代價，不利于協(xié)議執(zhí)行。選擇通信輪次少的串行協(xié)議可有效的降低通信代價；相反，如果參與方之間通信一次的時間接近或小于1，通信環(huán)境較為理想的時候，并行協(xié)議能有效地減少參與方的等待時間，提高協(xié)議執(zhí)行效率。

2 預(yù)備知識

2.1 同態(tài)加密

設(shè)加密算法為E(·)，解密算法為D(·)，明文空間M∈Z。如果對任意明文x，y∈M，x+y∈M，不存在多項式時間算法區(qū)分E(x)和E(y)，且對任意k∈Z，滿足E(x+y)=E(x)E(y)，E(kx)=E(x)k，那么此算法是加同態(tài)加密算法。Paillier算法[13]就是這樣的一個算法。

2.2 Paillier算法

加密：任意明文m∈Zn，隨機選擇r∈Z*N，那么密文c=gmrNmodN2。

解密：解密密文c得到明文m=L(cλ(N)modN2)/L(gλ(N)modN2)。

2.3 半誠實模型下的安全性

本文假定各參與方是半誠實的，其安全性定義與文獻[14]相同，即n個參與方P1，P2，…，Pn，他們各自擁有xi，在不泄露各自任何信息的情況下合作計算多項式時間函數(shù)：

其中fi(x1，x2，…，xn)表示第i個分量。設(shè)計算f的協(xié)議標記為π，那么Pi(i=1，2，…，n)在執(zhí)行協(xié)議π后得到的視圖(x1，x2， …xn)=(xi，ri，vi，1，vi，2， …，vi，m) ，其中ri是Pi隨機選擇的結(jié)果，vi，j表示Pi接收到的第j個消息。協(xié)議執(zhí)行后，Pi得到的輸出序列為(x1，x2，…，xn)。

上述各方Pi(i=1，2，…，n)執(zhí)行協(xié)議π能夠安全地計算出f，當且僅當下面的多項式時間算法Si(i=1，2，…，n)成立，即：

3 安全多方乘積協(xié)議

3.1 問題描述

假設(shè)有n個參與方Pi(i=1，2，…，n)，每個參與方Pi擁有一個秘密整數(shù)xi。所有參與方希望在不泄露各自秘密的前提下，計算出所有xi的乘積并且由參與方共享計算結(jié)果。

3.2 相關(guān)符號說明

RANDOM SELECTr1，r2，…，rn，表示選擇隨機n個整數(shù)r1，r2，…，rn；

x→y，表示將變量x賦值給變量y；

SEND(Alice，Bob，s1，s2，…，sn)，表示 Alice將信息s1，s2，…，sn發(fā)送給Bob；

Alice COMPUTE，表示Alice進行計算；

Alice GETs，表示Alice獲得信息s。

3.3 具體協(xié)議

以下給出串行和并行安全多方乘積協(xié)議的詳細步驟，數(shù)據(jù)傳輸流程分別如圖1、圖2所示。

圖1 串行協(xié)議數(shù)據(jù)傳輸流程

圖2 并行協(xié)議數(shù)據(jù)傳輸流程

協(xié)議1串行的安全多方乘積協(xié)議

輸入：參與方Pi(i=1，2，…，n)擁有整數(shù)xi，Pi選擇2.2節(jié)Paillier算法并產(chǎn)生公私鑰(pki，ski)。

協(xié)議步驟如下：

協(xié)議1中，參與方Pi存在等待時間，改變協(xié)議的執(zhí)行規(guī)則，得到協(xié)議2。

協(xié)議2并行的安全多方乘積協(xié)議

輸入：參與方Pi(i=1，2，…，n)擁有整數(shù)xi，Pi選擇2.2節(jié)Paillier算法并產(chǎn)生公私鑰(pki，ski)。

協(xié)議步驟如下：

3.4 協(xié)議分析

本節(jié)主要針對協(xié)議1和協(xié)議2的正確性、安全性和效率進行分析。

3.4.1 協(xié)議1的性能分析

正確性證明：

證明 在協(xié)議1步驟2中：

根據(jù)2.1節(jié)加同態(tài)性質(zhì)，Pi解密zn，i得到：

綜上所述，協(xié)議1是正確的。

表1 安全多方乘積協(xié)議比較

安全性分析：

定理2在半誠實模型下，串行多方乘積協(xié)議參與方除了得到y(tǒng)i，無法得到其他參與方秘密。

證明設(shè)串行多方乘積協(xié)議標記為π，通過構(gòu)造模擬器的方式對π進行安全性證明：

對Pi(i=1，2，…，n)的視圖：Pi通過協(xié)議π在步驟2中得到由Pi-1發(fā)送的數(shù)據(jù)zi-1，1，zi-1，2，…，zi-1，i-1。對Pi產(chǎn)生視圖可記為：

綜上所述，串行多方乘積協(xié)議是安全的，參與方除了得到y(tǒng)i，無法得到其他參與方秘密。

效率分析：

（1）計算復(fù)雜度。假設(shè)本協(xié)議的數(shù)據(jù)長度為mbit，Paillier加密方案的模為M，那么一次加密或者解密需要2lbM次模乘，一次模指運算E(x)k最多2m+1次模乘。步驟2中，Pi加密計算i個中間數(shù)據(jù)，需要i-1次模指運算和i次加密運算，步驟4中進行一次解密運算。所以總計算復(fù)雜度為O(n2(m+lbM))次比特模乘運算。

（2）通信 復(fù)雜 度。 由步 驟 2 中 SEND(Pi，Pi+1，zi，1，zi，2， …，zi，i) 和 步 驟 3 中 SEND(Pi，Pi+1，zn，i+1，zn，i+2， …，zn，n)可知，協(xié)議1的參與方Pi只與Pi+1進行兩次通信，發(fā)送n個數(shù)據(jù)。所以總的通信輪次是線性的，帶寬O(mn2)。

3.4.2 協(xié)議2的性能分析

定理3協(xié)議2的正確性、安全性以及計算復(fù)雜度同協(xié)議1，協(xié)議2通信輪次O(n2)，帶寬O(mn2)。

證明 在協(xié)議1中，參與方Pi一次計算i個中間數(shù)據(jù)且等全部計算結(jié)束之后發(fā)送給Pi+1。而由協(xié)議2的執(zhí)行步驟步驟2可知，Pi每當計算出一個中間數(shù)據(jù)就立即發(fā)送給Pi+1。因此，協(xié)議2與協(xié)議1僅僅是數(shù)據(jù)流的不同，數(shù)據(jù)量以及計算方法沒有發(fā)生變化，所以協(xié)議2的正確性、安全性以及計算復(fù)雜度同協(xié)議1。由定理1和定理2可知協(xié)議2是安全正確的。

另外，協(xié)議2總數(shù)據(jù)量沒有變化，所以總帶寬為O(mn2)。但每次只實時發(fā)送一個數(shù)據(jù)，因此增加了參與方之間的通信輪次，總通信輪次為O(n2)。

3.4.3 協(xié)議比較

本協(xié)議與現(xiàn)有安全多方乘積協(xié)議的性能比較，如表1所示。表中，l、p為茫然傳輸安全系數(shù)，n為參與方個數(shù)，m為數(shù)據(jù)長度。文獻[11]提出多方矩陣乘積協(xié)議，當矩陣維數(shù)是1的時候就退化為數(shù)量乘積。假設(shè)在理想通信環(huán)境下，計算一個中間數(shù)據(jù)的時間為1。

由表1可知，本文利用同態(tài)加密技術(shù)，在保證安全性的同時，減少了數(shù)據(jù)量，避免了文獻[10]和文獻[11]中所有參與方兩兩之間都需要頻繁通信的情況，降低了通信代價。在計算代價相當?shù)那闆r下，協(xié)議1和協(xié)議2各有優(yōu)勢，串行協(xié)議通信輪次少，適用于通信較為復(fù)雜的網(wǎng)絡(luò)環(huán)境；當網(wǎng)絡(luò)環(huán)境較為理想或者參與方數(shù)量較多時，并行協(xié)議參與方無須等待，可以減少協(xié)議的執(zhí)行時間。

此外，本文的通信模型為環(huán)形，此模型可進一步優(yōu)化。根據(jù)參與方之間的通信代價，設(shè)計一個通信代價最低的環(huán)，提高協(xié)議執(zhí)行效率；也可以結(jié)合信任評估模型[15]設(shè)計一個通信方之間信任度最高的環(huán)，提高協(xié)議的安全性。與文獻[10]和文獻[11]中的復(fù)雜網(wǎng)狀模型相比，本文降低了對通信環(huán)境的要求，無需所有參與方之間都存在通信關(guān)系，只要能形成一個通信環(huán)，協(xié)議便能正確執(zhí)行，減少了被攻擊的途徑。

4 結(jié)束語

安全多方計算在信息和通信安全中都占有重要的地位，而同態(tài)加密技術(shù)是安全多方計算中的關(guān)鍵技術(shù)之一。結(jié)合實際，本文提出了兩個適用不同環(huán)境的安全多方乘積協(xié)議，協(xié)議無須第三方的參與，在保證安全性的同時降低了通信代價，提高了協(xié)議的執(zhí)行效率。此外，現(xiàn)有的安全多方計算協(xié)議多為兩方協(xié)議的擴展，本文提出一個SMC基礎(chǔ)協(xié)議，為研究安全多方計算其他問題提供了新思路。本文是基于半誠實模型下的協(xié)議，惡意模型下參與方可能不完全遵守協(xié)議，如何對參與方的行為進行驗證，構(gòu)建安全的多方計算協(xié)議有待進一步研究。

[1]Yao A C.Protocols for secure computations[C]//Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science.Los Alamitos：IEEE Computer Society Press，1982：160-164.

[2]Goldreich O，Micali S，Wigderson A.How to play any mental game[C]//Proceedings of the 19th Annual ACM Conference on Theory of Computing，1987：218-229.

[3]劉文，羅守山，王永濱.安全兩方向量優(yōu)勢統(tǒng)計協(xié)議及其應(yīng)用[J].電子學(xué)報，2010，38（11）：2573-2577.

[4]秦靜，張振峰，馮登國，等.一個特殊的安全雙方計算協(xié)議[J].通信學(xué)報，2004，25（11）：35-42.

[5]Du Wenliang.A study of several specific secure two-party computation problems[D].West Lafayette：Purdue University，2001.

[6]肖倩，羅守山，陳萍，等.半誠實模型下安全多方排序問題的研究[J].電子學(xué)報，2008，36（4）：709-714.

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

[8]Maurer U.Secure multi-party computation made simple[C]//Proceedings of the 3rd International Conference on Security in Communication Networks，2003：14-28.

[9]李禾，王述洋.關(guān)于除法的安全兩方計算協(xié)議[J].計算機工程與應(yīng)用，2010，46（6）：86-88.

[10]張華.陳智雄.肖國鎮(zhèn).一個基于簽密技術(shù)的安全多方乘積協(xié)議[J].計算機科學(xué)，2005，32（2）：50-52.

[11]羅文俊，李祥.多方安全矩陣乘積協(xié)議及應(yīng)用[J].計算機學(xué)報，2005，28（7）：1230-1235.

[12]Naor M，Pinkas B.Oblivious transfer with adaptive queries[C]//Advancesin Cryptology（CRYPTO’99）.Berlin Heidelberg：Springer-Verlag，1999.

[13]Paillier P.Public-key cryptosystems based on composite degreeresiduosity classes[C]//Advancesin Cryptology（EUROCRYPT’99）.Berlin Heidelberg：Springer-Verlag，1999：223-238.

[14]Goldreich O.Secure multi-party computation（manuscript Version1.3）[EB/OL].（2009-10-09）[2013-01-18].htttp：//www.wisdom.weizmann.ac.il/～oded/pp.html.

[15]Duma C，Shahmehri N，Caronni G.Dynamic trust metrics for peer-to-peer systems[C]//Proceedings of the 16th International Workshopon DatabaseandExpertSystems Applications.[S.l.]：IEEE，2005：776-781.