一種改進(jìn)的安全兩方矩陣計算協(xié)議

余景波，劉國林，曹振坦，崔 娟

(1.山東科技大學(xué)測繪科學(xué)與工程學(xué)院，山東青島 266510;2.海島(礁)測繪技術(shù)國家測繪局重點實驗室，山東青島 266510 3.山東省第四地質(zhì)礦產(chǎn)勘查院，山東 濰坊 261021)

安全多方計算(Secure Multi－party Compulation)問題，是Yao［1］在1982年首先提出的。Goldreich，Micali和Wigderson等人［2］將其進(jìn)行了進(jìn)一步發(fā)展和推廣。目前，多方安全計算問題一般性研究取得了很多成果［3－4］，但特殊問題研究［5－8］成果相對較少。本文只討論安全兩方計算(Secure Two－party Compulation)問題，其可定義為［9］是擁有秘密輸入的兩方，都希望用各自的秘密輸入共同計算一個函數(shù)，計算要求每方都能接收到正確的輸出(正確性)，并且每方只能了解自己的輸出(保密性)。矩陣作為科學(xué)計算的一個基本工具，在計算機應(yīng)用中顯得十分重要。Du［10］和羅文俊［11］等人對兩方安全矩陣計算協(xié)議進(jìn)行了研究。

本文在安全兩方計算環(huán)境下，利用安全兩方向量加乘混算協(xié)議和安全兩方矩陣加乘混算協(xié)議［12］基本思想，構(gòu)造和改進(jìn)了一種安全兩方矩陣計算協(xié)議。

1 預(yù)備知識

參與者，就是提供輸入，得到輸出并且執(zhí)行實際計算的各方。執(zhí)行實際計算的參與者集合表示為P，所有參與者(包括輸入，輸出和計算)的集合表示為 ^P，P和^P戶沒必要一定相等，但是一定有P∈^P。

攻擊者(或稱敵手)，就是在可信多方計算協(xié)議中，企圖破壞協(xié)議安全性或正確性的人。攻擊者可以腐敗參與者的一個子集?？梢詫⒐粽呖闯梢粋€電腦黑客，他可以破壞或控制參與者的計算機。

半誠實方(Semi－Honest Party):一個半誠實方將準(zhǔn)確地完成協(xié)議，但是，同時記錄下所有的中間結(jié)果，這些中間結(jié)果將用于推導(dǎo)額外的信息。

保密性(Privacy):任何一方都只能了解自己的信息。在實際過程中，其它一方的信息只能從自己的輸入和輸出中推得。

數(shù)據(jù)擾動假設(shè)(Data Perturbation assumption):如果一個輸入x∈X，并且，r是一個均勻分布域F中的隨機數(shù)，同時滿足|F|?|X|這個條件，那么x+r就可以有效地保護(hù)r的秘密信息。

2 改進(jìn)的安全兩方矩陣計算協(xié)議

2.1 協(xié)議的描述

假設(shè)協(xié)議的兩個參與者是Alice和Bob，具體描述如下:

輸入:Alice有一個n階方陣Ra，兩個n維列向量b11，b12;Bob有一個n階方陣Rb，兩個n維列向量b21，b22。

輸出:Alice得到一個n維列向量r1，Bob得到一個n維列向量r2，滿足r1+r2=Ra(b21+b22)+Rb(b11+b12)。

2.2 協(xié)議的具體流程

(1)Alice和Bob約定兩個正整數(shù)p和m，同時讓pm足夠大，這樣造成pm次n維方陣加法運算無法進(jìn)行的。

(2)Alice和Bob協(xié)商三個公開的數(shù)q，g，h其中q是一個大素數(shù)，g，h均是Z*q的元素，并且任何人都不知道離散對數(shù)loggh。

(3)Alice和 Bob分別擁有私鑰 zi和 ri，注冊公鑰分別為 yi=hzi和 ei=hri(i=1，…，p，zi≠ri)。

(4)Alice產(chǎn)生m個隨機n階方陣Ra1，…，Ram，使得Bob產(chǎn)生m個隨機n階方陣Rb1，…，Rbm，使得

(5)對每一個j=1，2，…，m，Alice和Bob執(zhí)行下面的子步驟:

①Alice產(chǎn)生一個秘密隨機數(shù)1≤k≤p，Bob產(chǎn)生一個秘密隨機數(shù)1≤l≤p;

④Alice 隨機選取 βi∈zq，用 Bob 的公鑰 ei=hVi進(jìn)行加密計算

Bob 隨機選取 αi∈zq，用 Alice 的公鑰 yi=hzi進(jìn)行加密計算然后，Alice 將密文(Ai，Bi)通過公共信道發(fā)送給Bob，Bob將密文(Ci，Di)通過公共信道發(fā)送給Alice;

⑤Alice和Bob收到密文后，分別用自己的私鑰計算出自己獲得的數(shù)據(jù)信息

對自己獲的n階方陣數(shù)據(jù)信息進(jìn)行驗證(如果Alice和Bob都通過驗證即⑥中兩等式成立，說明Alice和Bob各自獲得數(shù)據(jù)信息有效，反之，各自獲得數(shù)據(jù)信息無效。Alice和Bob其中任何一人獲得無效n階矩陣數(shù)據(jù)，該協(xié)議停止執(zhí)行);

⑦Alice和Bob對所有的i=1，2，…，p，都能通過⑥中公示驗證，則表明:

Alice獲得Bob發(fā)送的p個有效n階方陣(H1，H2，…，Hp)，其中H1=Rbj，其余的(p－1)個Hi是隨機n階方陣(因為ι是一個秘密數(shù)據(jù)，只有Bob知道，而Alice不知道哪一個Hi是Rbj);Bob獲得Alice發(fā)送的p個有效n階方陣(G1，G2，…，Gp)，其中Gk=Raj，其余的(p－1)個Gi是隨機n階矩陣(因為k是一個秘密數(shù)據(jù)，只有Alice知道，而Bob不知道哪一個Gi是Raj)。

⑧對所有的 i=1，2…，p，，Alice 計算 Hj，i=Hi(b11+b12)+hj，其中 hj是隨機 n 維列向量，而 Bob 計算Gj，i=Gi(b21+b22)+gj，其中 gj是隨機 n 維列向量;

3 協(xié)議分析

3.1 正確性分析

(1)協(xié)議執(zhí)行后，Alice和Bob分別得到n維列向量r1和r2，可以得:

(2)在⑤中，Alice和Bob能用各自的私鑰獲得原明文，證明如下:

通過上述①和②的分析，就可以證明了Alice和Bob能夠獲得自己的明文。

(3)如果Alice和Bob都是誠實的，那么他們所發(fā)送對方的n階方矩陣信息總有發(fā)送成功機會。

(4)如果Alice和Bob不誠實，他們發(fā)布虛假信息，可以通過⑥中公式進(jìn)行驗證;Alice和Bob其中有一個不誠實，也可以通過⑥中公式進(jìn)行驗證;攻擊者發(fā)布的虛假信息也可以通過⑥中公式進(jìn)行驗證，從而減少了攻擊者對該協(xié)議執(zhí)行的危害。

(5)證明⑥中等式的正確性，方法如下:

3.2 安全性分析

(1)對每一個 j=1，2，…，m 來說:

① Bob猜對n維矩陣Raj的概率和Alice猜對n維矩陣Rbj的概率分別為，那么Bob猜對n維矩陣Ra的概率和Alicet猜對Rb的概率分別為，又因為Pm是一個足夠大的數(shù)，所以的近值為零，由此可知Alice和Bob都不可能得到對方n維矩陣Ra和Rb的信息。

(2)Alice和Bob通過對方公鑰加密算法對自己所發(fā)送的方陣信息進(jìn)行加密，形成密文，然后通過公共信道傳輸，從而保證了數(shù)據(jù)傳輸過程中的安全性，這是計算上的安全性。

(3)攻擊者獲取了公共信道上的密文，如果沒有Alice和Bob私鑰，就不能用公式進(jìn)行解密;如果攻擊者利用已知的公鑰yi=hzi和ei=hri來獲取私鑰zi和ri，相當(dāng)于求解離散對數(shù)的困難性。

(4)攻擊者偽造私鑰，不能獲得正確n階方矩陣信息，證明如下:

①如果攻擊者偽造私鑰z＇i≠zi，也推導(dǎo)不出正確的ti，具體推導(dǎo)過程如下:

②攻擊者如果偽造r＇i≠ri，也推導(dǎo)不出正確的si，具體過程如下:

(6)由上面(5)中的分析，可以得到:

(7)因為每一個 Hi，Gi，hj和 gj(i=1，…，p，i≠k，i≠l;j=1，…，m)是隨機 n 維矩陣和隨機 n 維列向量，可以分別對b11+b12和b21+b22進(jìn)行數(shù)據(jù)偽裝(數(shù)據(jù)擾動假設(shè))，避免數(shù)據(jù)信息泄露。

4 結(jié)束語

本文通過對改進(jìn)的安全兩方矩陣計算協(xié)議從正確性和安全性分析，可以得出:

(1)參與者用公鑰對發(fā)送信息進(jìn)行加密，不需要安全秘密信道傳送信息，減少了實際應(yīng)用中代價，提高了協(xié)議安全性和傳送系統(tǒng)的利用率。

(2)引入求離散對數(shù)的困難性假設(shè)，提高了協(xié)議執(zhí)行中數(shù)據(jù)傳輸安全性。

(3)引入加密算法，能夠抵御一些攻擊者的攻擊，保證數(shù)據(jù)信息順利傳遞;

(4)引入驗證算法，可以防止參與者和攻擊者發(fā)布虛假信息，同時可以驗證數(shù)據(jù)信息的有效性，提高了該多方可信計算協(xié)議的有效性。

(5)用隨機多項式產(chǎn)生秘密份額，不但增強了秘密份額的有效性，而且增強了方矩陣秘密份額的安全性、可靠性。

但是該協(xié)議還有許多不完善之處，有待改進(jìn)和提高:

(1)該協(xié)議仍然要求參與者是誠實或半誠實的，如果參與者是很惡意的，則該協(xié)議就會被破壞，而失去作用;

(2)加密算法性能，還有待于進(jìn)一步提高和改進(jìn)，使其能適應(yīng)各種情況;

(3)驗證算法，隨著p增加，驗證次數(shù)增加，這無疑給參與者帶來計算負(fù)擔(dān)，同時也帶來了效率不高的問題。

［1］Yao A.Protocol for secure compulation［C］.//Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computers Science，Los Angeles，1982:159－164

［2］賈恒越，劉煥平.求矩陣逆的安全雙方計算協(xié)議［J］.計算機工程與應(yīng)用，2008，44(33):112－114

［3］Naor M，Pinkas B.Distributed Oblivious Transfer［A］.Advances in Cryptology:Asiacry’00 Proceedings:LNCS1976，Springer－Verlag，2000:200－219

［4］Cachin C，Micali S，Stadler M.Computationally private information retrieval with polyogarithmic communication［M］.Advances in cryptology，1998:308－319

［5］Luo Wen－jun，Li Xiang.A study of secure multi－party statistical analysis［C］.//Proceedings of IEEE International Conference on Computer Networks and Mobile Computing，Shanghai，2003:376－383

［6］Li Shun－dong，Dai Yi－qi.Secure two－party computationalgeometry［J］.Journal of Computer Science and Technology，2005，20(2):257－264

［7］Du Wenliang，Atallah M.J.Privacy－preserving cooperative scientific computation［C］.//Proceedings of the 14th IEEE Computer Security Foundations Workshop，Nova Scotia，Canada，2001:273－283

［8］王永兵，盧曉杰，張建中.一種基于身份的代理聚合簽名方案［J］.濟南大學(xué)學(xué)報(自然科學(xué)版)，2011，25(3):301－304

［9］羅文俊，李 祥.矩陣特征值的兩方安全保密計算［J］.吉首大學(xué)學(xué)報(自然科學(xué)版)，2003，24(4):31－34

［10］Du Wenliang.A study of several specific secure two－party computation problems［D］.USA:Purdue University，2001:270－280

［11］羅文俊，李 祥.多方安全矩陣乘積協(xié)議及應(yīng)用［J］.計算機學(xué)報，2005，28(7):1230－1236

［12］王小妹.安全多方計算的協(xié)議研究［D］.北京:北京郵電大學(xué)，2008:33－35