一種改進的安全兩方矩陣計算協議

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

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

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

本文在安全兩方計算環境下，利用安全兩方向量加乘混算協議和安全兩方矩陣加乘混算協議［12］基本思想，構造和改進了一種安全兩方矩陣計算協議。

1 預備知識

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

攻擊者(或稱敵手)，就是在可信多方計算協議中，企圖破壞協議安全性或正確性的人。攻擊者可以腐敗參與者的一個子集。可以將攻擊者看成一個電腦黑客，他可以破壞或控制參與者的計算機。

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

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

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

2 改進的安全兩方矩陣計算協議

2.1 協議的描述

假設協議的兩個參與者是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 協議的具體流程

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

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

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

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

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

①Alice產生一個秘密隨機數1≤k≤p，Bob產生一個秘密隨機數1≤l≤p;

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

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

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

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

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

Alice獲得Bob發送的p個有效n階方陣(H1，H2，…，Hp)，其中H1=Rbj，其余的(p－1)個Hi是隨機n階方陣(因為ι是一個秘密數據，只有Bob知道，而Alice不知道哪一個Hi是Rbj);Bob獲得Alice發送的p個有效n階方陣(G1，G2，…，Gp)，其中Gk=Raj，其余的(p－1)個Gi是隨機n階矩陣(因為k是一個秘密數據，只有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 協議分析

3.1 正確性分析

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

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

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

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

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

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

3.2 安全性分析

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

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

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

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

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

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

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

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

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

4 結束語

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

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

(2)引入求離散對數的困難性假設，提高了協議執行中數據傳輸安全性。

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

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

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

但是該協議還有許多不完善之處，有待改進和提高:

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

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

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

［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］賈恒越，劉煥平.求矩陣逆的安全雙方計算協議［J］.計算機工程與應用，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］.濟南大學學報(自然科學版)，2011，25(3):301－304

［9］羅文俊，李 祥.矩陣特征值的兩方安全保密計算［J］.吉首大學學報(自然科學版)，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］羅文俊，李 祥.多方安全矩陣乘積協議及應用［J］.計算機學報，2005，28(7):1230－1236

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