魏 瓊, 李順東, 王文麗, 杜潤萌

陜西師范大學(xué) 計算機科學(xué)學(xué)院, 西安710119

1 引言

安全多方計算(Secure Multi-party Computation, MPC) 指的是兩個或更多的參與者利用各自的保密數(shù)據(jù)作為計算的輸入, 聯(lián)合進(jìn)行的保密計算, 計算結(jié)束后沒有參與方能獲得多于規(guī)定輸出的信息, 是信息社會隱私保護(hù)的重要技術(shù). 通過安全多方計算, 參與者可以在互不信任的網(wǎng)絡(luò)環(huán)境中聯(lián)合計算, 以實現(xiàn)保密的數(shù)據(jù)挖掘[1]、數(shù)據(jù)查詢[2,3]、外包計算[4]等, 解決了數(shù)據(jù)的隱私性和安全性問題, 因此安全多方計算在國際密碼學(xué)界研究中具有重要地位. 安全多方計算由圖靈獎獲得者姚期智首次提出[5], Goldreich、Micali 等人在此基礎(chǔ)上做了大量研究[6,7], 他們的研究成果奠定了安全多方計算的理論基礎(chǔ)[8-10]. 圖靈獎獲得者Goldwasser 認(rèn)為安全多方計算是密碼學(xué)一個極其重要的工具, 將成為計算科學(xué)一個必不可少的組成部分[11]. 目前研究的安全多方計算問題包括科學(xué)計算[12-15]、計算幾何[16-19]、統(tǒng)計分析[20,21]等方面, 但此類安全多方計算問題大多限于整數(shù)數(shù)據(jù)為輸入的保密計算, 未涉及描述事物關(guān)聯(lián)的隱私數(shù)據(jù)的保密計算. 研究事物之間關(guān)聯(lián)并發(fā)現(xiàn)規(guī)律, 對于認(rèn)識世界、改造世界至關(guān)重要.

圖論模型是一種強大而靈活的科學(xué)建模與數(shù)據(jù)分析工具, 是研究事物之間相互關(guān)聯(lián)、相互影響最有效的模型. 事物之間的相互關(guān)聯(lián)與影響構(gòu)成了各種各樣的網(wǎng)絡(luò), 如社交網(wǎng)絡(luò)、交通網(wǎng)絡(luò)、信息傳播網(wǎng)絡(luò)、疾病傳播網(wǎng)絡(luò)等, 這些網(wǎng)絡(luò)都是圖, 圖可以直觀地表達(dá)事物之間的關(guān)聯(lián), 有利于發(fā)現(xiàn)數(shù)據(jù)之間的關(guān)系, 能把紛雜的信息變得有序、直觀、清晰. 圖的節(jié)點可以表示任何事物, 邊可以表示事物之間的任何關(guān)系, 因此幾乎所有涉及事物間聯(lián)系的系統(tǒng)都可以用圖來建模與表達(dá). 將圖論方法用于醫(yī)學(xué)研究破譯了肝癌細(xì)胞向肺轉(zhuǎn)移的預(yù)警網(wǎng)絡(luò)信號[22]; 社交網(wǎng)絡(luò)分析發(fā)現(xiàn)一個人的信用與其朋友的信用關(guān)系密切, 可以借此對某人進(jìn)行信用評級[23]; 谷歌只是將圖論中節(jié)點度的概念用于評價網(wǎng)頁的重要程度, 就取得了出乎意料的成功. 然而很多時候, 事物之間的關(guān)聯(lián)數(shù)據(jù)中存在大量的隱私數(shù)據(jù), 即圖結(jié)構(gòu)形式的隱私數(shù)據(jù), 如家族病史、基因圖譜、基因缺陷、交易對象、犯罪記錄、是否吸毒、政治傾向、朋友圈、喜歡或討厭某人等數(shù)據(jù), 以及涉及經(jīng)濟、軍事活動的機密數(shù)據(jù)等. 如果直接利用這些數(shù)據(jù)進(jìn)行聯(lián)合計算以及科學(xué)研究與分析, 就有可能泄露機密信息或隱私, 導(dǎo)致嚴(yán)重的后果. 對隱私泄露的擔(dān)心使得人們不愿共享這些數(shù)據(jù). 許多國家、地區(qū)以及大型企業(yè)都對數(shù)據(jù)的使用施加嚴(yán)格的限制[24], 這些限制使得很多實體采集的數(shù)據(jù)無法充分利用, 難以發(fā)掘數(shù)據(jù)的價值, 發(fā)揮其應(yīng)有的作用. 如何在充分保護(hù)隱私數(shù)據(jù)機密性的前提下利用數(shù)據(jù)的價值, 使數(shù)據(jù)的社會效益與經(jīng)濟效益得到充分的發(fā)揮, 是亟待解決的問題, 具有非常現(xiàn)實和重要的意義, 這就需要研究圖結(jié)構(gòu)數(shù)據(jù)利用中的隱私保護(hù)問題.

目前這方面的研究才剛剛起步. 本文提出了保密求多個圖的交集和并集的問題, 并給出解決方案, 這些問題都具有重要的研究意義. 比如, 幾家航空公司想在某一地區(qū)開通航線, 但正式開通之前所有線路都是保密的, 為了避免某些航班的飛行班次過多而造成資源的浪費, 就需要提前知道它們在該區(qū)域內(nèi)有哪些共同的航線, 各航空公司則可根據(jù)這一結(jié)果對該公司的飛行班次做出調(diào)整. 令區(qū)域內(nèi)的所有城市為頂點,其飛行路線作為邊, 則該問題就抽象成多個圖交集的保密計算問題. 又如, 公司內(nèi)部想要在諸多員工中選出一位擔(dān)任某項目組長, 這就需要多方面考查員工之間的社交關(guān)系, 如喜歡、支持、合作等, 選擇在各方面關(guān)系中都與他人保持良好者擔(dān)任組長, 可大大提高工作效率. 但這些社交關(guān)系均屬于隱私信息, 因此不應(yīng)泄露. 令每位員工為節(jié)點, 相互之間的關(guān)系為邊, 則問題就抽象為多個圖并集的保密計算問題. 當(dāng)求出多種關(guān)系圖的并集后, 并集中度最大的頂點即為度中心性最高的點, 該節(jié)點在整個網(wǎng)絡(luò)中最重要, 那么由該節(jié)點所代表的成員擔(dān)任項目組長.

關(guān)于圖的安全多方計算問題, 已有的研究是文獻(xiàn)[25,26] 以各參與者與其他參與者的邊信息為基礎(chǔ),在保證隱私的前提下生成某種網(wǎng)絡(luò)圖. 其中文獻(xiàn)[25] 主要應(yīng)用秘密分享的方法構(gòu)造方案, 解決方案是初級的、計算復(fù)雜性與通信復(fù)雜性都很高; 文獻(xiàn)[26] 應(yīng)用同態(tài)加密的方法構(gòu)造方案, 解決方案中需要若干個權(quán)威機構(gòu)幫助實現(xiàn), 且由于所用加密及密文重隨機化次數(shù)較多, 計算復(fù)雜性也很高, 這些方案離實際應(yīng)用還很遠(yuǎn). 文獻(xiàn)[27] 提出了一種在線社交網(wǎng)絡(luò)中的安全鏈路預(yù)測技術(shù). 文獻(xiàn)[28] 研究了圖中最短路徑的安全計算問題. 文獻(xiàn)[29] 假定網(wǎng)絡(luò)信息是分布式存儲的, 其中每個參與者都擁有網(wǎng)絡(luò)的部分信息, 進(jìn)而研究基礎(chǔ)圖的安全生成問題, 但方案中使用了可信第三方, 通信成本和計算成本都很高. 文獻(xiàn)[30] 計算近似的圖編輯距離, 提出了確定容錯圖匹配的方案. 文獻(xiàn)[31] 中提出了圖的交集保密計算方案, 該方案首先利用文獻(xiàn)[32] 中提出的第一個安全的兩方保密集合交集協(xié)議(FNP 協(xié)議) 作為子協(xié)議, 先計算出服務(wù)器和客戶端兩方圖的頂點交集, 服務(wù)器再根據(jù)頂點交集和邊構(gòu)造出一個鄰接矩陣并加密, 最后客戶端利用Paillier 加密系統(tǒng)對雙方的鄰接矩陣做同態(tài)加密運算, 解密結(jié)果就是兩方圖的交集. 但該方案存在以下問題: 調(diào)用的FNP 協(xié)議是將集合表示成多項式的方式來計算集合的交集, 而FNP 協(xié)議的計算復(fù)雜性與多項式的次數(shù)密切相關(guān), 且同樣使用了Paillier 加密方案, 因此文獻(xiàn)[31] 中求圖的交集方案的計算復(fù)雜性非常高, 并且該方案僅限于兩方之間求圖的交集, 對于更實際的多方求圖的交集問題未能解決.

本文主要研究圖交集和并集的安全多方計算問題, 給出求解這些問題的高效解決方案. 本文的主要貢獻(xiàn)如下:

(1) 提出了一種新的編碼方法, 使圖中的邊和頂點都可以準(zhǔn)確的表示在一個特殊的矩陣中. 與無向圖的鄰接矩陣稍有不同的是, 本文編碼所得矩陣的主對角線元素不全為0, 而主對角線元素代表無向圖的頂點, 故本文編碼方法可以將無向圖的頂點和邊的都在矩陣中表示出來, 后續(xù)對于圖的頂點和邊的加密則可以轉(zhuǎn)化為對矩陣中相應(yīng)元素的加密. 這樣的編碼方法可以為其他圖論的安全多方計算問題提供一種新的途徑.

(2) 利用所提出的編碼方法, 保密替換方法[33]、Lifted-ElGamal 門限密碼系統(tǒng), 分別設(shè)計了求圖交集和并集的安全多方計算協(xié)議, 對所提出協(xié)議的正確性進(jìn)行了分析, 并通過模擬范例嚴(yán)格證明了協(xié)議的安全性, 得出本文協(xié)議均能抵抗任意程度合謀攻擊的結(jié)論.

(3) 只需將本文協(xié)議所用Lifted-ElGamal 門限密碼系統(tǒng)改為ElGamal 密碼系統(tǒng), 也可實現(xiàn)圖交集和并集的安全兩方計算, 比現(xiàn)有圖交集的兩方計算協(xié)議更具普適性, 應(yīng)用場景和應(yīng)用范圍更廣泛. 且通過效率分析和實驗數(shù)據(jù), 證明了本文協(xié)議與現(xiàn)有方案相比, 計算效率和通信效率都大大提升.

2 預(yù)備知識

2.1 安全性定義

理想模型 假設(shè)有一個通信雙方都完全信任的第三方, 稱為可信的第三方(Trusted Third Party,TTP), 他在任何情況下都會嚴(yán)格的按照通信雙方的要求執(zhí)行每一步操作, 同時也不會泄露通信雙方的私密信息. 安全多方計算中的理想模型可以描述為:n個參與者P1,··· ,Pn, 他們分別將各自的秘密x1,··· ,xn告訴可信第三方, 由他單獨計算函數(shù)f:

然后將計算結(jié)果分別告訴n個參與者. 除此計算結(jié)果之外,P1,··· ,Pn得不到任何其他信息. 理想模型雖然安全但并不適用于實際應(yīng)用, 在實際中限制性較強, 這是因為網(wǎng)絡(luò)環(huán)境紛繁復(fù)雜, 合作計算方共同信任的第三方很難找到, 且使用可信第三方也必將花費大量時間和金錢, 導(dǎo)致執(zhí)行協(xié)議的成本過高.

半誠實模型 本文假設(shè)所有參與者均為半誠實參與者[6]. 所謂半誠實參與者是指參與者會按要求忠實地履行協(xié)議, 協(xié)議執(zhí)行完成后, 所有參與者只知道協(xié)議的最終結(jié)果, 無法獲得其他參與者輸入的保密信息,但他們可能在協(xié)議執(zhí)行的過程中將收集到的所有信息記錄下來, 在協(xié)議執(zhí)行后試圖根據(jù)記錄的信息推算出其他參與者的輸入.

設(shè)有n個半誠實參與者P1,··· ,Pn, 分別擁有私有數(shù)據(jù)x1,··· ,xn, 他們合作執(zhí)行一個保密計算函數(shù)f(x1,··· ,xn) 的協(xié)議Π, 并在協(xié)議完成后得到最終結(jié)果. 這種參與者都是半誠實的安全多方計算協(xié)議稱為半誠實模型下的安全多方計算協(xié)議(簡稱半誠實協(xié)議). 令X= (x1,··· ,xn), 在執(zhí)行協(xié)議過程中, 參與者Pi得到的消息序列記為

2.2 門限解密

在安全多方計算協(xié)議中, 當(dāng)參與方數(shù)量超過兩方時, 需要考慮合謀攻擊的問題, 即: 幾個參與者之間合作, 利用執(zhí)行協(xié)議各自所得到的信息去獲取其他參與者的私有信息. 解決這一問題的有力工具就是門限解密[34,35]. 首先n個參與者聯(lián)合生成一個門限解密的密碼系統(tǒng), 每個參與者持有私鑰的一個份額, 公布生成的公鑰. 每個參與者都可用公鑰加密, 但只有n個參與者合作才能解密密文. 假設(shè)至少t個參與者合作才能解密, 那么這樣的密碼體制稱為(t,n) 門限密碼體制, 少于t個參與者合作則無法得到明文信息.RSA、ElGamal、Paillier 等密碼系統(tǒng)都可以用來構(gòu)造門限密碼系統(tǒng), 本文利用ElGamal 乘法同態(tài)加密方案構(gòu)造一個具有加法同態(tài)性的門限密碼系統(tǒng)—Lifted-ElGamal 門限密碼系統(tǒng)[36], 以此抵抗n ?1 個參與者的合謀攻擊. 具體構(gòu)造如下:

2.3 密文的重隨機化

在概率加密系統(tǒng)中, 一個明文可以有多個不可區(qū)分的密文, 很多密文都被解密為同一個明文. 無須私鑰, 而將某一密文改變?yōu)橥粋€明文的不同密文, 這樣的操作稱為密文的重隨機化[37]. 事實上, 所有由概率同態(tài)加密系統(tǒng)加密得到的密文, 都可對其進(jìn)行重隨機化. 例如, 在上述Lifted-ElGamal 密碼系統(tǒng)中,根據(jù)其加法同態(tài)性可知, 對于一個密文E(M), 乘“0” 的密文就可將原有密文改變?yōu)榱硪粋€密文, 而保持明文不變, 即通過計算E(M)×E(0) =E(M+0) =E′(M) 來實現(xiàn)密文的重隨機化,E′(M) 表示密文E(M) 重隨機化后的密文, 并且E′(M) 與密文E(M) 是計算不可區(qū)分的. 因此, Lifted-ElGamal 密碼系統(tǒng)具有重隨機化特性(re-randomizing property).

3 基于門限解密的多個圖交集的保密計算

3.1 問題描述

3.2 計算原理

首先提出編碼方法1, 將圖的頂點和邊信息都存儲在一個矩陣中, 編碼方式如下: 當(dāng)圖中有頂點vi時,矩陣元素mii值為1, 否則為0. 如果頂點vi和vj之間有邊, 那么矩陣中mij值為1, 否則值為0.

編碼方法1:

根據(jù)編碼方式1,P1,P2,P3,P4分別生成其存儲矩陣M1,M2,M3,M4:

以上提出的方案就是本文計算多個圖交集的基本原理. 直接這樣計算是無法保密的, 而在密文的條件下進(jìn)行這樣的操作則可以實現(xiàn)保密. 本文利用Lifted-ElGamal 門限密碼系統(tǒng)構(gòu)造一個抗合謀攻擊的圖交集的安全多方計算協(xié)議. 對向量中的0 和1 進(jìn)行概率加密, 使得任何參與者都無法分辨出向量中的0 與1. 在每個參與者完成密文替換的操作后, 將未替換過的密文進(jìn)行重隨機化來保證協(xié)議的安全性.

3.3 抗合謀攻擊的多個圖交集的保密計算

協(xié)議1 基于門限解密的多個圖交集保密計算協(xié)議.

輸入:P1,··· ,Pn各自的私有圖G1,··· ,Gn.

3.4 協(xié)議的正確性

協(xié)議1 是正確的意味著對于任意輸入的圖Gi(G0的子圖, 1≤i ≤n), 能正確求出n個圖的交集G,協(xié)議1 的正確性可由3.2 節(jié)所述計算原理保證. 具體地, 如果某個頂點或者某條邊在n個圖中均存在, 則每個圖Gi轉(zhuǎn)換后的向量Xi中, 對應(yīng)該頂點或邊的分量值為1. 在保密替換的過程中, 始終是用后者向量中的“0” 替換前者對應(yīng)位置的分量, 相當(dāng)于將非交集中的所有元素表示成了“0”, 而那些任意向量Xi中值均為1 的分量, 則被保留了下來, 替換過程僅僅是對其進(jìn)行了重隨機化, 根據(jù)保密替換完成后的最終向量, 即可恢復(fù)出交集圖G. 因此, 協(xié)議1 是正確的.

3.5 協(xié)議的安全性

定理1 基于門限解密的多個圖交集的保密計算協(xié)議1 是安全的, 能抵抗任意程度的合謀攻擊.

證明: 任意n ?1 個參與者構(gòu)成的合謀者集合, 可以產(chǎn)生最大程度的合謀攻擊, 因此只需證明協(xié)議1 對此合謀者結(jié)構(gòu)是安全的, 則對于其他任意程度的合謀攻擊都是安全的. 對于任意n ?1 個參與者構(gòu)成的合謀者集合I, 構(gòu)造相應(yīng)的模擬器S, 使得式(1) 成立. 由于各參與者地位的平等性, 不妨設(shè)I={P2,··· ,Pn}, 他們試圖合謀想獲取P1的私密圖G1,P1不參與合謀,P2,··· ,Pn對于P1的密文信息E(X1) = (E(x11),E(x12),··· ,E(x1t)) 無法正確解密, 根據(jù)加密方案的語義安全性可知,E(X1) =(E(x11),··· ,E(x1t)) 和t個隨機數(shù)是計算不可區(qū)分的, 在此情況下:

4 基于門限解密的多個圖并集的保密計算

4.1 問題描述

4.2 計算原理

以上方案就是本文計算多個圖并集的基本原理. 本文利用Lifted-ElGamal 門限密碼系統(tǒng)構(gòu)造一個抗合謀攻擊的圖并集的安全多方計算協(xié)議. 對向量中的0 和1 進(jìn)行概率加密, 使得任何參與者都無法分辨出向量中的0 與1. 在每個參與者完成密文替換的操作后, 將未替換過的密文進(jìn)行重隨機化來保證協(xié)議的安全性.

4.3 抗合謀攻擊的多個圖并集的保密計算

4.4 協(xié)議的正確性

協(xié)議2 是正確的意味著對于任意輸入的圖Gi(G0的子圖, 1≤i ≤n), 能正確求出n個圖的并集G?,協(xié)議2 的正確性可由4.2 節(jié)所述計算原理保證. 具體地, 如果某個頂點或者某條邊是n個圖并集中的元素,則至少存在一個圖Gi, 其轉(zhuǎn)換后的向量Xi中對應(yīng)該頂點或邊的分量值為1. 在保密替換的過程中, 始終是用后者向量中的“1” 替換前者對應(yīng)位置的分量, 相當(dāng)于將并集中的所有元素表示成了“1”. 而在任意向量Xi中值均為0 的分量, 僅對其進(jìn)行了重隨機化, 根據(jù)保密替換完成后的最終向量, 即可恢復(fù)出并集圖G?. 因此, 協(xié)議2 是正確的.

4.5 協(xié)議的安全性

門限解密方案的安全性可以為協(xié)議2 提供安全性保證. 由于門限ElGamal 公鑰系統(tǒng)的公鑰是由所有參與者共同產(chǎn)生的, 即h ≡gΣni=1skimodp, 其中ski是參與者Pi所持有的私鑰碎片, 因此解密需要所有參與者合作才能完成. 由概率門限加密算法的語義安全性可知, 若沒有全部參與者合作解密, 那么每個參與者產(chǎn)生的密文對其他任一參與者來說都是計算不可區(qū)分的. 因此, 只要任一參與者不參與合謀, 對其余n ?1 個參與者來說, 它們執(zhí)行協(xié)議時得到的view 與用滿足圖并集不變的任一組輸入進(jìn)行模擬相比, 最終所得信息序列在計算上是不可區(qū)分的, 也就是說協(xié)議2 可以抵抗合謀攻擊.

定理2 基于門限解密的多個圖并集的保密計算協(xié)議2 是安全的, 能抵抗任意程度的合謀攻擊.

5 性能分析

5.1 理論分析與比較

本節(jié)將本文方案與相關(guān)文獻(xiàn)方案的效率進(jìn)行對比. 由于目前關(guān)于圖的交集保密計算問題僅有文獻(xiàn)[31]中的方案, 尚無關(guān)于圖的并集的保密計算問題的研究, 且本文計算圖的交集和并集的計算復(fù)雜性基本相同,因此將協(xié)議1 與文獻(xiàn)[31] 進(jìn)行比較.

計算復(fù)雜性分析 由于文獻(xiàn)[31] 使用了Paillier 加密方案, 本文協(xié)議使用了ElGamal 加密方案, 因此以開銷較大的模指數(shù)運算次數(shù)作為衡量計算開銷的指標(biāo), 其他忽略不計. 用MP表示Paillier 加密方案中的模指數(shù)運算, 用ME表示ElGamal 加密方案中的模指數(shù)運算.密文m2+m個.

當(dāng)考慮n個參與者的情況, 本文協(xié)議1 中n個參與者首先構(gòu)造門限, 總共需要通信n ?1 次, 傳輸密文n ?1 個; 加密和替換過程, 每個參與者將向量按規(guī)則處理后發(fā)送給下一個參與者, 每次需傳輸t個密文, 該過程共需通信n ?1 次, 傳輸密文t(n ?1) 個; 聯(lián)合解密過程每次需傳輸t個密文, 該過程共需通信n ?1 次, 傳輸密文t(n ?1) 個. 因此協(xié)議1 共需要通信3(n ?1) 次, 傳輸密文2(t+1)(n ?1) 個, 即傳輸密文(n ?1)m2+(n ?1)m+n ?1 個.

綜合以上分析, 得到本文方案與文獻(xiàn)[31] 方案的對比如表1.

表1 本文方案與現(xiàn)有方案的比較Table 1 Comparison between scheme in this paper and existing schemes

從表1 可以看出, 當(dāng)研究兩個參與者的情況時, 文獻(xiàn)[31] 在計算復(fù)雜性和通信復(fù)雜度兩方面均高于本文協(xié)議. 且文獻(xiàn)[31] 僅限于研究兩個參與者的情況, 而本文設(shè)計的兩個協(xié)議則均可擴展至多個參與者的情況, 并且能夠抵抗任意程度的合謀攻擊.

5.2 實驗測試

本文通過模擬實驗測試執(zhí)行文獻(xiàn)[31] 方案與本文協(xié)議1 所用時間, 以此驗證并對比各方案的效率.

實驗?zāi)M 本文的試驗測試環(huán)境: Windows 10 64 位操作系統(tǒng), 處理器是Intel(R) Core(TM) i5-6600 CPU@3.30 GHZ, 內(nèi)存是8 GB, 用JAVA 語言編程實現(xiàn). 本文協(xié)議1 在兩方情況下使用的ElGamal加密系統(tǒng), 素數(shù)p設(shè)為512 比特, 在文獻(xiàn)[31] 協(xié)議中使用的Paillier 加密系統(tǒng), 兩個素數(shù)p,q設(shè)為256 比特. 實驗以保密求兩個圖的交集為例, 測試在同一組參數(shù)下, 文獻(xiàn)[31] 方案與本文協(xié)議1 在最壞情況下求圖的交集所需時長(僅考慮加密與解密過程所耗費的時間), 其中每組圖的頂點數(shù)分別設(shè)置為m= 10,20,··· ,100. 為了保證數(shù)據(jù)的準(zhǔn)確性, 我們對每組參數(shù)設(shè)定值進(jìn)行100 次模擬實驗, 取實驗結(jié)果的平均值, 實驗結(jié)果如圖1 所示.

圖1 保密求兩圖交集的執(zhí)行時間隨圖的頂點數(shù)增長的變化規(guī)律Figure 1 Rule of execution time of privately computing intersection of two graphs with growth of vertex number of graphs

為進(jìn)一步提高安全等級, 將協(xié)議1 的ElGamal 加密系統(tǒng)的素數(shù)p取為安全素數(shù)(即p=rq+1,q是一個大素數(shù)), 即令p為3072 比特,q為256 比特, 選取階數(shù)為q的生成元g. 文獻(xiàn)[31] 協(xié)議中使用的Paillier 加密系統(tǒng), 兩個素數(shù)p,q取為1536 比特, 隨機數(shù)的取值范圍不變, 實驗結(jié)果如圖2 所示.

實驗結(jié)果 對于兩圖交集的保密計算問題, 本文協(xié)議1 將圖做了簡化表示成向量, 加密和解密過程的數(shù)據(jù)量不大, 且使用了效率較高的ElGamal 加密方案, 而文獻(xiàn)[31] 的方案調(diào)用的子協(xié)議復(fù)雜, 對圖的加密和解密量也很大, 使用的Paillier 加密方案效率相對低. 從圖1 和圖2 可以看出, 無論在何種安全等級下, 文獻(xiàn)[31] 協(xié)議的執(zhí)行時間都明顯高于本文協(xié)議1, 且隨著圖的頂點數(shù)增大, 文獻(xiàn)[31] 協(xié)議執(zhí)行時間的增長速度也明顯較本文協(xié)議1 更快.

圖2 更高安全等級下保密求兩圖交集的執(zhí)行時間隨圖的頂點數(shù)增長的變化規(guī)律Figure 2 Rule of execution time of privately computing intersection of two graphs with growth of vertex number of graphs at a higher level of security

6 結(jié)論

圖結(jié)構(gòu)數(shù)據(jù)的安全多方計算是一個新的研究領(lǐng)域. 本文提出了一種新的編碼方法來存儲圖, 以新編碼方法和門限解密方案為基礎(chǔ), 并結(jié)合密文替換和密文重隨機化的方法, 分別設(shè)計了圖交集和并集的安全多方計算協(xié)議, 且只需稍加修改就能用于兩方參與者的情況. 我們應(yīng)用模擬范例嚴(yán)格證明了本文協(xié)議在半誠實模型下都是安全的, 可以抵抗任意程度的合謀攻擊. 在今后的研究中, 我們將致力于更高效的圖的交集、并集問題的解決方案, 以及更多具有重要意義的圖論問題的安全多方計算, 并嘗試開展對惡意模型下圖論問題的安全多方計算研究.