趙雪玲, 家珠亮, 李順東

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

1 引言

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

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

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

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

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

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

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

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

2.1 安全性定義

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

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

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

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

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

2.2 門限密碼體制

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

2.3 Lifted ElGamal 門限加密算法

Lifted ElGamal 門限加密算法[30]基于ElGamal 加密算法, 對(duì)ElGamal 算法中明文M進(jìn)行處理,用ρM替換M. 便可構(gòu)造lifted ElGamal 門限加密算法.

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

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

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

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

對(duì)密文消息M重隨機(jī)化的具體步驟為: 設(shè)明文消息M加密后的密文為

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

3 集合交(并) 集的勢(shì)與閾值關(guān)系的保密判定

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

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

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

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

3.2 具體計(jì)算協(xié)議

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

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

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

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

(1)P1利用計(jì)算原理, 構(gòu)造數(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 能正確判斷集合交集的勢(shì)與閾值的關(guān)系.

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

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

在計(jì)算中, 由0＜li ＜M/2 可知集合交集的勢(shì)不大于M/2, 即0＜L ＜M/2. 同時(shí)在協(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(當(dāng)且僅當(dāng)L=t時(shí),(L-t)mod M=0);

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

因此, 計(jì)算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 能正確判斷集合交集的勢(shì)與閾值的關(guān)系.

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

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

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

協(xié)議2 集合并集的勢(shì)與閾值關(guān)系的保密判定協(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ù)不變, 僅對(duì)其重隨機(jī)化.Pi得到E(Mi) = ((ui1,vi1),(ui2,vi2),··· ,(uil,vil)),并將E(Mi) 發(fā)送給Pi+1.

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

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

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

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

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

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

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

計(jì)算原理:

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

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

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

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

4.2 具體計(jì)算協(xié)議

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

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

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

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

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

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

4.4 元素與集合并集關(guān)系的保密判定

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

協(xié)議4 元素與集合并集關(guān)系的保密判定協(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ù)不變, 僅對(duì)其重隨機(jī)化.Pi得到E(Mi) = ((ui1,vi1),(ui2,vi2),··· ,(uil,vil)),并將E(Mi) 發(fā)送給Pi+1.

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

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

5.1 集合與集合交集關(guān)系的保密判定

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

計(jì)算原理: 其計(jì)算原理與集合交集的勢(shì)與閾值的判定原理前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.

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

5.2 具體計(jì)算協(xié)議

協(xié)議5 集合與集合交集關(guān)系的保密判定協(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 集合與集合并集關(guān)系的保密判定

6 效率分析

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

6.1 計(jì)算復(fù)雜度

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

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

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

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

6.2 通信復(fù)雜度

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

協(xié)議1(協(xié)議2) 中n個(gè)參與者和Alice 生成公鑰需n次通信,Pi(i= 1,2,··· ,n-1) 將密文發(fā)送給Pi+1(i=1,2,··· ,n-1) 需1 次通信. Alice 將E(-t) 發(fā)送給Pn需1 次通信.n個(gè)參與者和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é)議計(jì)算復(fù)雜性和通信復(fù)雜性分析Table 1 Analysis of the computational complexity and communication complexity of the protocol

6.3 協(xié)議效率實(shí)驗(yàn)測(cè)試

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

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

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

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

7 結(jié)論與展望

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

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