基于同態(tài)加密技術(shù)的安全多方乘積協(xié)議

夏 超 ，仲 紅 ，2，石潤(rùn)華 ，2

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

2.安徽大學(xué) 計(jì)算與信號(hào)處理教育部重點(diǎn)實(shí)驗(yàn)室，合肥 230039

1 引言

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

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

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

2 預(yù)備知識(shí)

2.1 同態(tài)加密

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

2.2 Paillier算法

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

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

2.3 半誠(chéng)實(shí)模型下的安全性

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

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

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

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

3.1 問(wèn)題描述

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

3.2 相關(guān)符號(hào)說(shuō)明

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

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

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

Alice COMPUTE，表示Alice進(jìn)行計(jì)算；

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

3.3 具體協(xié)議

以下給出串行和并行安全多方乘積協(xié)議的詳細(xì)步驟，數(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存在等待時(shí)間，改變協(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é)主要針對(duì)協(xié)議1和協(xié)議2的正確性、安全性和效率進(jìn)行分析。

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

正確性證明：

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

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

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

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

安全性分析：

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

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

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

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

效率分析：

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

（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進(jìn)行兩次通信，發(fā)送n個(gè)數(shù)據(jù)。所以總的通信輪次是線性的，帶寬O(mn2)。

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

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

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

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

3.4.3 協(xié)議比較

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

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

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

4 結(jié)束語(yǔ)

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

[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]劉文，羅守山，王永濱.安全兩方向量?jī)?yōu)勢(shì)統(tǒng)計(jì)協(xié)議及其應(yīng)用[J].電子學(xué)報(bào)，2010，38（11）：2573-2577.

[4]秦靜，張振峰，馮登國(guó)，等.一個(gè)特殊的安全雙方計(jì)算協(xié)議[J].通信學(xué)報(bào)，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]肖倩，羅守山，陳萍，等.半誠(chéng)實(shí)模型下安全多方排序問(wèn)題的研究[J].電子學(xué)報(bào)，2008，36（4）：709-714.

[7]劉文，王永濱.安全多方信息比較相等協(xié)議及其應(yīng)用[J].電子學(xué)報(bào)，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)于除法的安全兩方計(jì)算協(xié)議[J].計(jì)算機(jī)工程與應(yīng)用，2010，46（6）：86-88.

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

[11]羅文俊，李祥.多方安全矩陣乘積協(xié)議及應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，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.