圖交集和并集的安全多方計(jì)算*

魏 瓊, 李順東, 王文麗, 杜潤(rùn)萌

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

1 引言

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

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

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

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

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

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

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

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

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

2.1 安全性定義

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

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

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

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

2.2 門限解密

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

2.3 密文的重隨機(jī)化

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

3 基于門限解密的多個(gè)圖交集的保密計(jì)算

3.1 問題描述

3.2 計(jì)算原理

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

編碼方法1:

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

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

3.3 抗合謀攻擊的多個(gè)圖交集的保密計(jì)算

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

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

3.4 協(xié)議的正確性

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

3.5 協(xié)議的安全性

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

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

4 基于門限解密的多個(gè)圖并集的保密計(jì)算

4.1 問題描述

4.2 計(jì)算原理

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

4.3 抗合謀攻擊的多個(gè)圖并集的保密計(jì)算

4.4 協(xié)議的正確性

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

4.5 協(xié)議的安全性

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

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

5 性能分析

5.1 理論分析與比較

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

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

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

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

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

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

5.2 實(shí)驗(yàn)測(cè)試

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

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

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

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

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

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