圖交集和并集的安全多方計算*

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

陜西師范大學 計算機科學學院, 西安710119

1 引言

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

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

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

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

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

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

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

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

2 預備知識

2.1 安全性定義

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

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

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

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

2.2 門限解密

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

2.3 密文的重隨機化

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

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

3.1 問題描述

3.2 計算原理

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

編碼方法1:

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

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

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

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

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

3.4 協議的正確性

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

3.5 協議的安全性

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

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

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

4.1 問題描述

4.2 計算原理

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

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

4.4 協議的正確性

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

4.5 協議的安全性

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

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

5 性能分析

5.1 理論分析與比較

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

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

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

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

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

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

5.2 實驗測試

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

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

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

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

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

圖2 更高安全等級下保密求兩圖交集的執行時間隨圖的頂點數增長的變化規律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 結論

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