集合交集問題的安全計算*

趙雪玲, 家珠亮, 李順東

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

1 引言

網(wǎng)絡迅速發(fā)展, 為人們的生活帶來很大便利, 但同時也帶來了各種挑戰(zhàn), 隱私泄露便是一個巨大挑戰(zhàn).安全多方計算(secure multi-party computation, SMC) 是隱私保護的核心技術, 也是目前密碼學界研究的熱點. 安全多方計算(SMC)[1–5]主要是在無可信第三方情況下, 解決兩個或多個互不信任參與者間進行聯(lián)合計算時的隱私保護問題. 在計算中既要確保輸入的獨立性、計算的正確性, 又要保證計算結束后, 每個參與者的信息都沒有泄露給其他參與者.

姚期智[6]于1982 年提出了兩方安全計算, Ben-Or 和Goldwasser 等[7]于1988 年提出了安全多方計算, Goldwasser[8]預言安全多方計算將成為計算科學中必不可少的組成部分. Goldreich[9]等從理論方面證明了任意安全多方計算問題都是可解的. 多位學者的研究, 推動了安全多方計算的發(fā)展, 使安全多方計算成為一個完整的體系. 目前, 安全多方計算研究范圍很廣, 包括保密的科學計算[10–13]、保密的統(tǒng)計分析[14,15]、保密的數(shù)據(jù)挖掘[16]等. 而集合計算問題是保密科學計算中的重要內容, 在數(shù)據(jù)外包[17]、醫(yī)療數(shù)據(jù)分析[18]等方面有廣泛的應用.

目前對集合的保密計算已有很多研究成果. 文獻[19] 利用不經(jīng)意多項式計算了集合的交集. 文獻[20]中研究了惡意模型下的集合的交(并) 集. 文獻[21] 首次得到了具有線性復雜度的集合交(并) 集的保密協(xié)議. 文獻[22] 在大數(shù)據(jù)下提出了近似計算集合交集并集勢的方法. 文獻[23] 中根據(jù)編碼方法解決了標準集合之間的交(并) 集以及勢和閾值并集問題. 文獻[24] 將多重集轉化為矩陣形式, 研究了兩方多重集的交(并) 集等計算問題. 文獻[25] 將集合表示為多項式, 設計出不需要密碼原語的多方集合相交協(xié)議. 文獻[26] 利用范德蒙行列式求值問題, 解決了集合成員與集合的判定問題.

對于集合交(并) 集的勢與閾值的關系、元素與集合交(并) 集的關系、以及集合與集合交(并) 集的關系研究較少, 但其研究卻具有重要意義. 比如: (1) 在一公司中, 公司全部中層領導構成全集Q, 員工Pi(i=1,2,··· ,n) 滿意的領導構成集合Xi={xi1,xi2,··· ,xili}. 公司想了解所有員工都滿意的中層領導人數(shù)是否達到閾值t. 為保護員工權益, 不能泄露員工滿意的領導名單. 此時, 就需保密判斷集合交集的勢是否大于閾值t. (2)每個人的信用報告由多個指標組成(比如: 犯罪記錄、銀行信貸交易、其他部門采集的可以反映用戶收入、繳欠費或其他資信狀況的信息等). 每個指標信息由不同機構(比如: 公安局、銀行、鐵路局等) 掌握, 機構Pi(i= 1,2,··· ,n) 有完成該項指標人員名單, 構成集合Xi={xi1,xi2,··· ,xili}.用戶若想判斷自己信用是否良好, 就需判斷自己是否屬于n個機構名單的交集. 由于各部門名單為機密文件, 用戶也不想泄露自己的信息. 此場景便可轉化為元素與集合交集關系的保密判定. (3) 同樣考慮場景(2). 設B為一個公司, 其員工名單構成集合A={a1,a2,··· ,as}, 機構Pi(i= 1,2,··· ,n) 的人員名單構成集合Xi={xi1,xi2,··· ,xili}.B公司想判斷所有員工的信用是否全部良好, 即判斷集合A是否包含于Xi的交集. 此問題可利用元素與集合交集關系的保密判定解決, 但在計算中需對每個元素調用協(xié)議.不僅計算效率低, 還泄露了某一元素是否屬于集合交集. 因此設計出高效判定集合與集合交集關系的協(xié)議是必要的. 本文主要對這三個問題進行安全多方保密判定, 主要貢獻如下:

(1) 采用0-1 編碼, 利用保密替換、加密選擇和加密系統(tǒng)的加法同態(tài)性對范圍有限的問題求解.

(2) 本文解決了集合交(并) 集的勢與閾值關系的判定、元素與集合交(并) 集關系的判定、集合與集合交(并) 集關系的判定問題.

(3) 設計基于lifted ElGamal 門限加密的安全協(xié)議, 解決參與者合謀問題, 并對協(xié)議的安全性和正確性進行證明.

2 預備知識

2.1 安全性定義

理想保密計算協(xié)議: 如果有一個信賴的第三方(trusted third party, TTP), 他在任何計算情況下都是誠實的, 不會泄露任何不允許泄露的信息, 就可以采用可信賴的第三方完成安全計算, 其具體的執(zhí)行過程為:P1,P2,··· ,Pn將自己的信息X1,X2,··· ,Xn發(fā)送給TTP, TTP 單獨計算函數(shù)

然后將結果(f1(X1,X2,··· ,Xn),··· ,fn(X1,X2,··· ,Xn)) 分別告訴Pi(i= 1,2,··· ,n). 因為Pi只能得到信息fi(X1,X2,··· ,Xn), 此外再無法獲取其他任何信息. 因此此協(xié)議是安全多方計算中計算效率和安全性最高的協(xié)議. 其他任何多方保密計算fi(X1,X2,··· ,Xn) 協(xié)議的安全性都不可能超過理想?yún)f(xié)議的安全性.

半誠實參與者[27]: 半誠實參與者是指在計算過程中, 計算的參與者會嚴格按照協(xié)議規(guī)定執(zhí)行, 但是會在計算過程中收集、記錄信息, 試圖推導其他參與者的數(shù)據(jù)信息.

對于半誠實參與者的安全性證明目前最常用的是模擬范例[28]. 該方法的原理是將實際協(xié)議的安全性和理想安全多方計算協(xié)議的安全性進行比較, 如果實際計算協(xié)議泄露的信息不比理想計算協(xié)議泄露的信息多, 則證明實際的計算協(xié)議是安全的.

設參與者P1,P2,··· ,Pn分別擁有數(shù)據(jù)X1,X2,··· ,Xn, 令X= (X1,X2,··· ,Xn),n個參與者想要借助協(xié)議π保密計算函數(shù)f(X). 在整個協(xié)議的計算過程中參與者Pi(i=1,2,··· ,n) 可以得到的信息記為

2.2 門限密碼體制

門限密碼體制[29]是安全多方計算中對抗合謀攻擊的一個重要工具. 在門限密碼體制中,n個參與者聯(lián)合生成公鑰, 解密密鑰由n個參與者聯(lián)合持有. 公鑰可以直接加密消息, 但解密需要n個參與者中一定數(shù)量人員參與才能正確解密. 如果至少需要t個人參與才能解密, 少于t個人時無法獲取明文的任何信息,這樣的密碼體制稱為(t,n) 門限密碼體制. 本文需要的是(n,n) 門限密碼體制, 它是抵抗合謀攻擊的一種有效方法.

2.3 Lifted ElGamal 門限加密算法

Lifted ElGamal 門限加密算法[30]基于ElGamal 加密算法, 對ElGamal 算法中明文M進行處理,用ρM替換M. 便可構造lifted ElGamal 門限加密算法.

密鑰生成: 給定安全參數(shù)k, 密鑰生成算法生成一個k比特的大素數(shù)p, 以及Z*p的一個生成元g.n個參與者P1,P2,··· ,Pn商定一個小素數(shù)ρ(lifted ElGamal 門限加密算法解密結果為ρM, 此時, 需進一步計算離散對數(shù), 為簡化計算, 選擇小素數(shù)ρ. 同時, 本文解密結果均為小數(shù)據(jù), 因此可以通過離散對數(shù)表獲取離散對數(shù)計算結果). 選取ki ∈Z*p作為Pi(i= 1,2,··· ,n) 的私鑰, 計算Ki=gkimodp, 并聯(lián)合

因此，lifted ElGamal 門限加密算法具有加法同態(tài)性.

2.4 密文的重隨機化

本文的所有通信信道都是公開的, 且使用了加密選擇和保密替換求集合的交集. 在加密選擇時, 若直接將選擇的數(shù)據(jù)保存, 所有選擇數(shù)據(jù)的密文保持不變, 其他參與者便知道某一參與者在前一個參與者數(shù)據(jù)的基礎上選擇了哪些密文, 替換了哪些密文, 這樣無安全性可言. 因此, 參與者Pi(i= 1,2,··· ,n) 需對選擇的數(shù)據(jù)隨機化, 隨機化后僅相當于對明文M的重新加密, 但不改變原有明文消息M. 此隨機化使每個參與者都無法了解其余參與者到底是選擇了哪些數(shù)據(jù), 替換了哪些數(shù)據(jù), 進而實現(xiàn)保密替換.

對密文消息M重隨機化的具體步驟為: 設明文消息M加密后的密文為

經(jīng)過隨機化后, 相當于對明文M重新加密, 和選擇的密文不再相同.

3 集合交(并) 集的勢與閾值關系的保密判定

3.1 集合交集的勢與閾值關系的保密判定協(xié)議

問題描述: 假設n個參與者Pi(i= 1,2,··· ,n), 分別擁有集合Xi={xi1,xi2,··· ,xili} ?Q. 其中,Q={q1,q2,··· ,ql} 且q1＜q2＜···＜ql. 另一參與者Alice 擁有閾值t ∈Q.n個參與者和Alice 想要保密計算他們交集的勢|∩ni=1Xi| 是否達到閾值t, 而不泄露參與者和集合交集的任何信息.

計算原理:Pi根據(jù)全集對自己的數(shù)據(jù)進行編碼和選擇. 具體步驟如下:

(1)P1構造數(shù)組M1=(m11,m12,··· ,m1l). 其中, 若qj ∈X1(1≤j ≤l),m1j=1; 若qj/∈X1(1≤j ≤l),m1j=0. 即:

3.2 具體計算協(xié)議

協(xié)議1 集合交集的勢與閾值關系的保密判定協(xié)議.

輸入:Pi(i=1,2,··· ,n) 輸入集合Xi={xi1,xi2,··· ,xili}?Q, Alice 輸入閾值t ∈Q.

輸出:Ft(X1,X2,··· ,Xn).

準備:n個參與者和Alice 執(zhí)行l(wèi)ifted ElGamal 門限加密算法, 得到私鑰ki和公鑰h.

(1)P1利用計算原理, 構造數(shù)組M1=(m11,m12,··· ,m1l).

(2)P1將明文M1加密, 得到E(M1) = ((u11,v11),(u12,v12),··· ,(u1l,v1l)).其中, (u1j,v1j) =(gr1jmodp, ρm1jhr1jmodp).P1將E(M1) 發(fā)送給P2.

3.3 協(xié)議的安全性和正確性

協(xié)議1 能正確判斷集合交集的勢與閾值的關系.

根據(jù)加密方案的加法同態(tài)性和保密替換的性質保證協(xié)議1 的正確性. 在保密替換和加密選擇過程中,Pi(i=2,3,··· ,n) 執(zhí)行協(xié)議, 當qj ∈Xi時, 保持(u(i-1)j,v(i-1)j) 不變, 僅對其隨機化. 若Pi-1的集合中含有qj, 則(u(i-1)j,v(i-1)j) 為1 的密文, 若Pi-1集合中不含qj, 則(u(i-1)j,v(i-1)j) 為0 的密文. 當qj/∈Xi時, 使用0 的密文替換(u(i-1)j,v(i-1)j), 其本質為Pi刪除不屬于自己集合的元素. 協(xié)議執(zhí)行完成, 數(shù)組Mn中編碼為1 的位置對應全集中的元素即為集合交集的元素.

由于lifted ElGamal 具有加法同態(tài)性, 將E(Mn) 中全部元素相乘, 相當于明文相加. 得到E(L) 即為集合交集勢的密文. 若Pn將E(L) 發(fā)送給Alice 計算, 當完全解密后, Alice 便可得到集合交集的勢.因此, Alice 將E(-t) 發(fā)送給Pn, 由Pn計算. 因為集合交集的勢和閾值均為密文, 所以Pn得不到任何額外信息.

在計算中, 由0＜li ＜M/2 可知集合交集的勢不大于M/2, 即0＜L ＜M/2. 同時在協(xié)議中我們要求xij,t均在明文空間ZM中取值且0＜t ＜M/2. 由此可知-2/M＜L-t ＜M/2.

(1) 若L ≥t, 則0≤L-t ＜M/2, 因此有0≤(L-t)mod M=L-t ＜M/2(當且僅當L=t時,(L-t)mod M=0);

(2) 若L ＜t, 則-M/2＜L-t ＜0, 因此有M/2＜(L-t)mod M=(L-t)+M＜M.

因此, 計算Z后, 若0≤Z ＜M/2, 則L ≥t, 即Ft(X1,X2,··· ,Xn) = 1; 若M/2＜Z ＜M, 則L ＜t, 即Ft(X1,X2,··· ,Xn)=0.

綜上所述, 協(xié)議1 能正確判斷集合交集的勢與閾值的關系.

在協(xié)議執(zhí)行中, 加密選擇后,Pi(i= 2,3,··· ,n) 選擇隨機數(shù)rij, 對加密選擇的數(shù)據(jù)重隨機化. 計算(u(i-1)jgrijmodp,v(i-1)jhrijmodp), 相當于對選擇數(shù)據(jù)對應的明文重新加密. 保密替換時使用0 的密文替換(u(i-1)j,v(i-1)j). 因此Pi+1(i= 2,3,··· ,n-1) 收到的是一個重新加密的數(shù)組, 此時Pi+1知道所有的E(Mi)(i= 1,2,··· ,n-1), 但是所有的E(Mi) 中沒有一個與E(Mi-1) 中密文相同的密文,Pi+1無法判斷Pi對選擇了哪些數(shù)據(jù), 替換了哪些數(shù)據(jù). 因此, 即使Pi+1(i=2,3,··· ,n-1) 得到所有的E(Mi)(i=1,2,··· ,n-1) 也無法獲取前i個參與者的任何信息.

3.4 集合并集的勢與閾值關系的保密判定協(xié)議

集合并集的勢與閾值關系的保密判定協(xié)議和集合交集的勢與閾值關系的保密判定協(xié)議幾乎相同. 只需對集合交集勢與閾值關系的保密判定協(xié)議進行簡單修改. 具體修改步驟如下:

協(xié)議2 集合并集的勢與閾值關系的保密判定協(xié)議.

輸入:Pi(i=1,2,··· ,n) 輸入集合Xi={xi1,xi2,··· ,xili}?Q, Alice 輸入閾值t ∈Q.

輸出:Ft(X1,X2,··· ,Xn)

僅修改協(xié)議1 的第(3) 步, 其余步驟與協(xié)議1 均相同.

(3)Pi(i= 2,3,··· ,n) 保密替換和選擇E(Mi-1) 中數(shù)據(jù). 保密替換和加密選擇具體步驟為: 若qj ∈Xi, 則將(u(i-1)j,v(i-1)j) 采用1 的密文(grijmodp, ρ1hrijmodp) 替換; 若qj/∈Xi, 則保持(u(i-1)j,v(i-1)j) 原有數(shù)據(jù)不變, 僅對其重隨機化.Pi得到E(Mi) = ((ui1,vi1),(ui2,vi2),··· ,(uil,vil)),并將E(Mi) 發(fā)送給Pi+1.

3.5 協(xié)議的安全性和正確性

協(xié)議2 能正確判斷集合并集勢與閾值的關系. 其正確性分析與協(xié)議1 類似. 在保密替換過程中,Pi執(zhí)行協(xié)議, 當qj ∈Xi時, 使用1 的密文替換原有集合數(shù)據(jù),Pi將自己元素添加到集合并集中. 經(jīng)過n個參與者合作計算, 數(shù)組E(Mn) 中編碼為1 的位置對應全集中的元素即為集合并集的元素. 由lifted ElGamal 加法同態(tài)性, 得到E(L) 為集合并集勢的密文, 結合密文E(t) 得到集合并集的勢與閾值的關系.

協(xié)議2 在半誠實模型下是安全的, 能抵抗任意合謀. 協(xié)議2 安全性證明與協(xié)議1 相同, 故省略.

4 元素與集合交(并) 集關系的保密判定

利用協(xié)議1(協(xié)議2) 編碼方式和思想, 可以判斷元素與集合交(并) 集的關系. 在設計元素與集合交(并) 集關系的保密判定協(xié)議時, 只需對協(xié)議1(協(xié)議2) 做相應修改. 其主要的區(qū)別在最后幾步處理方式不同.

4.1 元素與集合交集關系的保密判定協(xié)議

問題描述: 假設n個參與者Pi(i=1,2,··· ,n), 分別擁有集合Xi={xi1,xi2,··· ,xili}?Q. 其中Q={q1,q2,··· ,ql} 且q1＜q2＜··· ＜ql. Alice 擁有一個元素x ∈Q,n個參與者和Alice 想要保密判斷元素x是否屬于n個集合的交集, 且不泄露參與者和交集的任何信息.

計算原理:

其計算原理與集合交集的勢與閾值關系的判定原理前3 步相同, 本節(jié)只寫出修改的集合交集的勢與閾值關系判定原理的第(4) 步和第(5) 步.

(4)Pn根據(jù)(3) 修改Mn-1, 得到數(shù)組Mn=(mn1,mn2,··· ,mnl). 并將Mn發(fā)送給Alice.

(5) 設x=qj, Alice 選擇Mn中mnj. 若mnj= 1, 則元素x屬于集合交集, 記為:F(x,X1,X2,··· ,Xn)=1; 若mnj=0, 則元素x不屬于集合交集, 記為:F(x,X1,X2,··· ,Xn)=0.

以上所述是元素與集合交集關系的判定原理, 我們基于此原理設計了保密判定協(xié)議3.

4.2 具體計算協(xié)議

(7) Alice 收到其余參與者發(fā)送的ti后計算

并計算Z= logρY, 若Z= 1, 輸出F(x,X1,X2,··· ,Xn) = 1; 若Z= 0, 輸出F(x,X1,X2,··· ,Xn)=0.

4.3 協(xié)議的安全性和正確性

協(xié)議3 能正確判斷集元素與集合交集的關系.

協(xié)議3 的安全性分析與協(xié)議1 類似. 協(xié)議3 的前3 步與協(xié)議1 相同. 數(shù)組E(Mn) 中編碼為1 的位置對應全集中的元素即為集合交集的元素.Pn將E(Mn) 發(fā)送給Alice, Alice 選擇qj=x對應的密文. 若x屬于集合交集, 根據(jù)計算原理可知(u,v) 必為1 的密文.

協(xié)議3 在半誠實模型下是安全的, 能抵抗任意合謀攻擊. 證明過程參考協(xié)議1. 在協(xié)議1 基礎上, 證明集合交集元素的安全性. Alice 僅選擇qj=x, 除此之外, Alice 無法獲取有關集合交集的任何信息, 且集合交集元素也無需解密. 故集合交集元素信息是安全的.

4.4 元素與集合并集關系的保密判定

與協(xié)議2 類似, 對協(xié)議3 修改得到元素與集合并集關系的保密判定協(xié)議. 具體協(xié)議參看協(xié)議4.

協(xié)議4 元素與集合并集關系的保密判定協(xié)議.

輸入:Pi(i=1,2,··· ,n) 輸入集合Xi={xi1,xi2,··· ,xili}?Q. Alice 輸入x ∈Q.

輸出:F(x,X1,X2,··· ,Xn)

協(xié)議4 除第(3) 步外, 其余步驟均與協(xié)議3 相同, 協(xié)議4 只給出修改的第(3) 步.

(3)Pi(i= 2,3,··· ,n) 保密替換和選擇E(Mi-1) 中數(shù)據(jù). 保密替換和加密選擇具體步驟為: 若qj ∈Xi, 則將(u(i-1)j,v(i-1)j) 采用1 的密文(grijmodp, ρ1hrijmodp) 替換; 若qj/∈Xi, 則保持(u(i-1)j,v(i-1)j) 原有數(shù)據(jù)不變, 僅對其重隨機化.Pi得到E(Mi) = ((ui1,vi1),(ui2,vi2),··· ,(uil,vil)),并將E(Mi) 發(fā)送給Pi+1.

5 集合與集合交(并) 集關系的保密判定

將協(xié)議1(協(xié)議2) 和協(xié)議3(協(xié)議4) 的處理方式結合改進, 可以判斷集合與集合交(并) 集的關系. 判斷集合與集合交(并) 集的關系時, 同樣只需對協(xié)議1(協(xié)議2) 后幾步修改.

5.1 集合與集合交集關系的保密判定

問題描述: 假設n個參與者Pi(i= 1,2,··· ,n), 分別擁有集合Xi={xi1,xi2,··· ,xili} ?Q, Alice擁有集合A={a1,a2,··· ,as} ?Q. 其中Q={q1,q2,··· ,ql} 且q1＜q2＜··· ＜ql.n個參與者和Alice 想要保密判斷集合A是否包含于n個集合的交集, 且不泄露參與者和集合交集的任何信息.

計算原理: 其計算原理與集合交集的勢與閾值的判定原理前3 步相同. 本節(jié)給出修改的第(4) 步和第(5) 步.

(4)Pn根據(jù)(3) 修改Mn-1, 得到數(shù)組Mn=(mn1,mn2,··· ,mnl).Pn將Mn發(fā)送給Alice.

(5) Alice 根據(jù)自己數(shù)據(jù)在Mn中選擇. 若qj ∈A, 則Alice 將Mn中的mnj選擇保存. 選擇完成后,將選擇的mnj全部相加,記為L. 若L=s,則集合A包含于集合交集,記為:F(A,X1,X2,··· ,Xn)=1;若L／=s, 則集合A不包含于集合交集, 記為:F(A,X1,X2,··· ,Xn)=0.

以上所述是集合與集合交集關系的判定原理, 同樣需設計保密的判定協(xié)議. 集合與集合交集關系的保密判定為協(xié)議5.

5.2 具體計算協(xié)議

協(xié)議5 集合與集合交集關系的保密判定協(xié)議.

輸入:Pi(i= 1,2,··· ,n) 輸入集合Xi={xi1,xi2,··· ,xili} ?Q. Alice 輸入A={a1,a2,··· ,as}?Q.

輸出:F(A,X1,X2,··· ,Xn)

5.3 協(xié)議的安全性和正確性

5.4 集合與集合并集關系的保密判定

6 效率分析

我們從計算復雜度和通信復雜度兩方面分析協(xié)議效率.

6.1 計算復雜度

在分析協(xié)議效率時, 由于乘法和選擇耗時相對模指數(shù)運算可忽略, 因此計算復雜度以運算過程中最耗時的模指數(shù)運算衡量. 利用lifted ElGamal 密碼系統(tǒng)加密時,n個參與者聯(lián)合生成公鑰需n次模指數(shù)運算, 同一元素加密需3 次模指數(shù)運算, 但加密數(shù)據(jù)較小時, 僅需2 次模指數(shù)運算. 解密過程中,n個參與者合作解密一個元素需n+1 次模指數(shù)運算.

協(xié)議1(協(xié)議2) 中P1將X1={x11,x12,··· ,x1l1}轉化為數(shù)組M1= (m11,m12,··· ,m1l). 利用lifted ElGamal 公鑰加密,n個參與者和Alice 聯(lián)合生成公鑰需n+1 次模指數(shù)運算, 加密M1需2l次模指數(shù)運算. 忽略Pi選擇時間,Pi(i= 2,3,··· ,n-1) 對選擇的數(shù)據(jù)重隨機化, 同時對自己不存在的數(shù)據(jù)用0 的密文替換,Pi需重新加密所有數(shù)據(jù). 此時Pi共需2l次模指數(shù)運算. 因此n-1 個參與者共需2(n-1)l次模指數(shù)運算,Pn選擇數(shù)據(jù)并結合t計算后, 僅對計算結果重隨機化, 需2 次模指數(shù)運算. Alice執(zhí)行協(xié)議時, 忽略其他運算, 對t加密需2 次模指數(shù)運算. 加上n個參與者和Alice 合作解密的n+2 次模指數(shù)運算. 協(xié)議1(協(xié)議2) 共需2n(l+1)-2l+7 次模指數(shù)運算.

協(xié)議3(協(xié)議4) 前幾步執(zhí)行過程與協(xié)議1(協(xié)議2) 相同, 因此在數(shù)組加密選擇重隨機化和保密替換中所需的模指數(shù)運算相同. 其不同主要為Pn需要加密2l個數(shù)據(jù), Alice 從Pn發(fā)送的密文選擇一個數(shù)即可,但Alice 選擇后需對選擇數(shù)據(jù)重隨機化. 因此協(xié)議3(協(xié)議4) 比協(xié)議1(協(xié)議2) 多了Pn加密自己數(shù)據(jù)的模指數(shù)運算, 少了Pn對計算結果的2 次模指數(shù)運算. 所需模指數(shù)運算為2n(l+1)+5.

協(xié)議5(協(xié)議6) 分析與協(xié)議3(協(xié)議4) 類似. 執(zhí)行協(xié)議時關鍵在Alice 處理方式不同, 協(xié)議5(協(xié)議6)與協(xié)議3(協(xié)議4) 不同之處在于Alice 從E(Mn) 中選擇的不是一個數(shù), 而是s個數(shù). 但選擇完成后并非直接解密, 而是將選擇數(shù)據(jù)全部相乘. 此時僅需對計算結果重隨機化, 需2 次模指數(shù)運算.

6.2 通信復雜度

通信復雜度以運算過程中的交互次數(shù)衡量.

協(xié)議1(協(xié)議2) 中n個參與者和Alice 生成公鑰需n次通信,Pi(i= 1,2,··· ,n-1) 將密文發(fā)送給Pi+1(i=1,2,··· ,n-1) 需1 次通信. Alice 將E(-t) 發(fā)送給Pn需1 次通信.n個參與者和Alice 完成協(xié)議共需n次通信. 參與者合作解密需n+1 次通信. 因此, 總共需要3n+1 次通信.

協(xié)議3(協(xié)議4) 和協(xié)議5(協(xié)議6)Alice 無需向Pn傳輸信息, 但Pn需將加密數(shù)據(jù)發(fā)送給Alice. 因此通信次數(shù)和協(xié)議1(協(xié)議2) 通信次數(shù)相同, 總共需要3n+1 次通信.

表1 本文協(xié)議計算復雜性和通信復雜性分析Table 1 Analysis of the computational complexity and communication complexity of the protocol

6.3 協(xié)議效率實驗測試

上節(jié)從理論方面分析了協(xié)議效率, 本節(jié)主要利用實驗數(shù)據(jù)對協(xié)議進行測試. 協(xié)議的模指數(shù)運算依賴參與者的數(shù)量n和全集的勢l, 因此協(xié)議執(zhí)行時間受參與者的數(shù)量n和全集的勢l影響. 我們在實驗中選擇的模數(shù)p為1024 比特, 系統(tǒng)類型為windows10 64 位操作系統(tǒng), 處理器為Intel(R) Core(TM) i5-6600 CPU@3.30 GHz 3.31 GHz. 實驗平臺為jdk 1.8.0, 使用java 語言在Eclipse 上實現(xiàn). 設共有10 個參與者參與計算, Alice 擁有t,Pi(i= 1,2,··· ,9) 擁有的元素個數(shù)不超過l. 協(xié)議執(zhí)行時間隨全集的勢l變化規(guī)律如圖1 所示. 設每個參與者Pi擁有的元素個數(shù)不超過10, 即固定全集的勢l= 10, 協(xié)議執(zhí)行時間隨參與者數(shù)量n(n個參與者不包含Alice) 的變化規(guī)律如圖2 所示.

由圖1 可知固定參與者數(shù)量n= 10, 執(zhí)行時間隨著全集的勢線性增長. 由圖2 可知固定全集的勢l=10, 協(xié)議的執(zhí)行時間同樣隨參與者數(shù)量線性增長.

圖1 執(zhí)行時間隨全集勢的變化規(guī)律Figure 1 Execution time changes with cardinality of set

圖2 執(zhí)行時間隨參與者總數(shù)量的變化規(guī)律Figure 2 Execution time changes with total number of participants

7 結論與展望

集合交集和并集的保密計算在生活中有著重要的作用, 目前對集合交集和并集的研究很多. 但生活中很多問題也可轉為集合交(并) 集上的進一步運算. 本文主要解決了數(shù)據(jù)范圍有限情況下對集合交(并) 集的進一步計算, 包括集合交(并) 集的勢與閾值關系的保密判定、元素與集合交(并) 集關系的保密判定和集合與集合交(并) 集關系的保密判定, 同時利用加密算法構造了抗合謀的安全協(xié)議.

本文提出的判定方法只適合數(shù)據(jù)范圍已知的情況, 隨著數(shù)據(jù)范圍的增長, 計算復雜性也隨著線性增長.因此, 需設計更高效的判定方法, 也就是數(shù)據(jù)范圍未知情況下對本文問題的進一步考慮. 今后我們將會研究更一般的情況. 同時考慮惡意模型的安全協(xié)議也是我們今后的研究方向.