王穎囡, 竇家維, 葛 雪

陜西師范大學(xué) 數(shù)學(xué)與信息科學(xué)學(xué)院, 西安710119

1 引言

在實際生活中, 很多問題都可以抽象為向量比較問題從而得以解決. 例如公司A 要找尋商業(yè)合作伙伴, 但希望合作公司在某些方面能達到一定的條件(例如總資產(chǎn)、信譽值等), 對這些條件進行一定的標準化即可表示為向量x= (x1,··· ,xn), 而B 公司的數(shù)據(jù)也可表示成對應(yīng)的向量y= (y1,··· ,yn), 要判定公司A 與公司B 是否能達成合作就轉(zhuǎn)化為判定xi ＞yi的分量個數(shù)是否達到了公司A 自己的設(shè)定值t.此外, 在進行樣本特征匹配檢測時, 僅需要判定兩特征串相同字符個數(shù)是否達到某個閾值, 若達到設(shè)定的閾值, 就說明兩者匹配, 否則不匹配, 將兩特征串表示成向量x= (x1,··· ,xn),y= (y1,··· ,yn), 則問題就轉(zhuǎn)化為判定xi=yi的分量個數(shù)是否達到了閾值t. 由此可見, 向量為解決一些實際問題提供了基本方法. 但在很多情況下, 向量中的數(shù)據(jù)涉及到人們的隱私, 人們不希望在計算的過程中泄露信息. 因此在保護隱私的前提下進行向量計算有很大的實際意義. 安全多方計算作為密碼學(xué)的一個重要研究方向, 可以很好地解決這一問題.

安全多方計算是一種保護隱私數(shù)據(jù)的計算方式, 是指參與者利用其私有數(shù)據(jù)進行合作計算, 并得到所需結(jié)果, 同時在計算結(jié)束后, 每個參與者不能獲得其他參與者隱私數(shù)據(jù)的任何額外信息. Yao 在文獻[1]中最早提出兩方安全計算問題, 隨后, Goldreich 等人提出了安全多方計算問題, 并對其進行了深入的研究[2,3], 他們證明了所有的安全多方計算問題理論上都是可解的并提出了通用的解決方案, 推動了安全多方計算的研究發(fā)展. 由于通用方案的復(fù)雜性較高而不實用, 人們需要針對具體問題尋求具體的簡單高效的解決方案. 目前已研究的問題主要包括保密的科學(xué)計算[4,5]、保密的計算幾何問題[6-8]、保密的數(shù)據(jù)挖掘[9]、保密的集合運算[10,11]、保密的向量計算[12-18]以及其他安全多方計算問題.

目前, 有關(guān)向量的安全計算問題的研究包括向量的求和[12]、向量的線性組合[13]、向量內(nèi)積的計算[14]、向量優(yōu)勢計算[15-18]. 文獻[15] 首次提出安全向量優(yōu)勢問題, 即對于向量x= (x1,··· ,xn),y=(y1,··· ,yn), 保密判定是否x,y的所有分量具有關(guān)系xi ＞yi. 文獻[15] 將兩個向量x,y分別轉(zhuǎn)化為4n維向量并借助百萬富翁協(xié)議對于向量中對應(yīng)分量分別進行大小比較, 從而得到所需結(jié)果, 計算復(fù)雜性較高.文獻[16] 將向量的每個分量轉(zhuǎn)化為二進制數(shù)表示, 通過對二進制數(shù)大小比較的方法解決向量優(yōu)勢問題, 由于在協(xié)議中需要加密每個二進制串, 協(xié)議的復(fù)雜性也非常高.

文獻[17] 對于向量優(yōu)勢問題進行了推廣, 研究向量優(yōu)勢統(tǒng)計問題, 即統(tǒng)計向量x,y中, 滿足xi ＞yi,i ∈[1,n] 的分量個數(shù), 雖然相比文獻[15,16] 計算復(fù)雜性有所降低, 但協(xié)議需要借助茫然第三方幫助執(zhí)行. 文獻[18] 在研究向量優(yōu)勢統(tǒng)計問題時假設(shè)向量的所有分量限制在某個全集內(nèi)取值, 應(yīng)用編碼方法解決問題, 由于所設(shè)計協(xié)議要求數(shù)據(jù)在一個全集內(nèi)取值, 并且協(xié)議的計算復(fù)雜性與全集的勢線性相關(guān), 這些都限制了協(xié)議的應(yīng)用范圍. 我們也注意到, 文獻[17,18] 中構(gòu)造的向量優(yōu)勢保密統(tǒng)計協(xié)議無法直接用于解決向量優(yōu)勢問題, 這是由于在向量x關(guān)于向量y不具有向量優(yōu)勢情形下, 將會泄露滿足xi ＞yi,i ∈[1,n]的分量個數(shù), 這在向量優(yōu)勢保密判定中是不允許的.

從上面分析可知, 對于向量優(yōu)勢統(tǒng)計問題, 或者更進一步, 判斷向量x,y中滿足xi ＞yi,i ∈[1,n] 的分量個數(shù)是否達到某個閾值t的問題(稱其為向量優(yōu)勢閾值問題), 以及對于向量優(yōu)勢判定問題需要設(shè)計更高效的安全計算協(xié)議.

另一方面, 向量相等問題在實際中有很多應(yīng)用, 這個問題作為兩數(shù)相等判定問題的推廣, 可通過約定向量分量位數(shù)從而把向量與整數(shù)一一對應(yīng)(例如約定分量位數(shù)為2, 將向量(2,1,0,42) 對應(yīng)于整數(shù)02010042), 并應(yīng)用已有的兩數(shù)相等比較協(xié)議[4]獲得解決. 而對于某些實際應(yīng)用問題, 比如在上面所述的信息匹配問題, 我們需要保密判定兩個向量x和y中滿足xi=yi,i ∈[1,n] 的分量個數(shù)是否達到某個閾值t, 而不希望泄露其他信息(稱其為向量等分量數(shù)閾值問題), 這一問題很難直接應(yīng)用兩數(shù)相等比較協(xié)議獲得解決. 在之前的工作中, 為解決這一問題, 我們將向量的各個分量限制在一個全集中, 并給出了具體的解決方案. 但全集的限制也增加了協(xié)議的局限性, 因此設(shè)計新的無全集限制的向量等分量數(shù)閾值計算協(xié)議是必要的.

本文主要研究上面所提出的向量優(yōu)勢閾值問題(包括向量優(yōu)勢判定問題) 與向量等分量數(shù)閾值問題,對于這些問題設(shè)計高效的保密計算協(xié)議. 本文主要貢獻如下:

(1) 對向量優(yōu)勢統(tǒng)計與向量等分量數(shù)統(tǒng)計問題進行擴展, 將其與閾值結(jié)合, 解決向量優(yōu)勢閾值問題與等分量數(shù)閾值保密計算問題. 特別地, 當(dāng)設(shè)置閾值t為向量的維數(shù)時即可獲得向量優(yōu)勢問題與向量相等判定問題的解決方案.

(2) 以Paillier 加密方案為基礎(chǔ), 靈活運用加密算法的加法同態(tài)性, 并以命題2 和注解2 所給的性質(zhì)和保密比較兩數(shù)大小的方法為基礎(chǔ), 結(jié)合問題轉(zhuǎn)化及加密選擇等技巧, 在無全集限制條件下對于上述問題設(shè)計保密計算協(xié)議. 應(yīng)用模擬范例嚴格證明了協(xié)議的安全性. 所得到的向量優(yōu)勢判定協(xié)議與已有相關(guān)結(jié)果比較, 具有較低的計算復(fù)雜度與通信復(fù)雜度.

(3) 本文所研究問題具有重要的實際意義, 所設(shè)計的協(xié)議具有廣泛的應(yīng)用性, 可作為基本工具解決更多的實際應(yīng)用問題(具體參看第6 節(jié)推廣應(yīng)用部分).

2 預(yù)備知識

2.1 安全性定義

半誠實模型 半誠實參與者[3]是指在協(xié)議執(zhí)行過程中按照協(xié)議要求忠實地履行協(xié)議的參與者, 與此同時, 他們可能會收集和保留在協(xié)議執(zhí)行過程中獲得的所有信息, 并在協(xié)議執(zhí)行后試圖根據(jù)這些信息推算出其他參與者數(shù)據(jù)的額外信息. 若在協(xié)議中, 所有的參與者均為半誠實參與者, 稱這樣的計算模型為半誠實模型. 本文協(xié)議均在半誠實模型下設(shè)計.

安全性定義模擬范例是目前多方保密計算研究中普遍采用的證明方法. 在執(zhí)行協(xié)議過程中, 如果任何半誠實參與者所獲得的信息都可以通過自己的輸入和輸出進行模擬, 若模擬時得到的消息序列與實際過程得到的消息序列不可區(qū)分, 即參與者從協(xié)議執(zhí)行過程中得不到其他參與者的任何有價值信息, 就認為該協(xié)議是安全的. 本文采用模擬范例對協(xié)議進行安全性證明. 具體過程如下.

假設(shè)有概率多項式時間函數(shù)f(x,y) : (x,y)→(f1(x,y),f2(x,y)),π為計算函數(shù)f的一個兩方協(xié)議.記協(xié)議的參與者為Alice 和Bob, 他們的輸入分別為x,y, 協(xié)議執(zhí)行中Alice 得到的信息序列記為

2.2 Paillier 加密方案

因此Paillier 加密方案具有加法同態(tài)性.

Paillier 密碼系統(tǒng)是語義安全的. 一個密碼系統(tǒng)是語義安全的, 意味著同一明文可以加密成多個不同的密文形式, 并且所有密文在計算上都是不可區(qū)分的.

注解1 關(guān)于Paillier 加密方案的安全性簡單敘述如下: 首先, 由于Paillier 加密方案是概率加密方案, 因此是IND-CPA 安全的; 又由于Paillier 加密方案具有加法同態(tài)性, 因此不具有IND-CCA2 安全性. Paillier 加密方案是否具有同態(tài)加密方案中最強的IND-CCA1 安全性是眾多學(xué)者近年來一直努力解決的一個公開問題. 近期文獻[20] 關(guān)于這一問題給出了下面的結(jié)果: Paillier 方案是IND-CCA1 安全的當(dāng)且僅當(dāng)DCRSCCR問題是困難的(上面所出現(xiàn)的各種縮寫符號的具體含義以及對于研究結(jié)果的詳細論證請參閱文獻[20]). 一個密碼系統(tǒng)是IND-CPA 安全的(即語義安全的), 意味著同一明文可以加密成多個不同的密文形式, 并且所有密文都是計算不可區(qū)分的. 在這個安全性概念中, 任何具有概率多項式時間圖靈機的敵手都無法獲得關(guān)于給定密文所對應(yīng)明文的任何信息. 本文主要以Paillier 加密方案為基礎(chǔ)設(shè)計協(xié)議, 在下文中所做的密文乘積運算和模乘運算均是在模N2的意義下進行的.

3 向量優(yōu)勢閾值問題保密計算

3.1 問題描述及計算原理

問題描述 為了敘述方便, 我們首先引入下面概念和函數(shù).

定義1 對于兩個n維向量x= (x1,··· ,xn) 和y= (y1,··· ,yn), 將兩個向量中滿足關(guān)系xi ＞yi,i ∈[1,n] 的元素個數(shù)稱為x關(guān)于y的優(yōu)勢度, 用記號F(x,y) 表示.

對于給定的向量x,y以及一個正整數(shù)t, 定義函數(shù)Ft(x,y) 如下: 如果F(x,y)≥t, 令Ft(x,y)=1,否則令Ft(x,y)=0, 并稱Ft(x,y) 為向量優(yōu)勢閾值函數(shù).

定義2 假設(shè)C=E(h) 是應(yīng)用Paillier 加密方案中公鑰pk 加密的0 或1 的密文,C?1為其在密文空間乘法群中的逆元. 根據(jù)Paillier 加密算法的加法同態(tài)性可知,T(C) =E(1)C?1=E(1?h), 即如果C為0 的密文, 則T(C) 為1 的密文; 如果C為1 的密文, 則T(C) 為0 的密文, 即密文T(C) 對于C所對應(yīng)的明文1 或0 進行了翻轉(zhuǎn). 在此意義下我們稱T(C)=E(1)C?1為翻轉(zhuǎn)運算.

本節(jié)中我們希望研究的問題是: 假設(shè)Alice 和Bob 分別擁有私密向量x和y, 并有一個商定好的閾值t, 他們希望合作保密計算函數(shù)Ft(x,y), 計算結(jié)束后不泄露兩個私密向量的任何額外信息.

基本結(jié)論 在下面討論中, 需要用到一些基本結(jié)論, 首先對其進行陳述并給出證明.

命題1 對任意整數(shù)a,b, 有下面結(jié)論成立:

(a)a ＞b當(dāng)且僅當(dāng)2a ＞2b+1;

(b)a ≥b當(dāng)且僅當(dāng)2a+1＞2b.

命題1 的作用在計算原理部分以及本節(jié)最后注解2 中有特別說明.

本文主要是應(yīng)用Paillier 加密方案設(shè)計協(xié)議, 我們希望根據(jù)某一密文的解密結(jié)果來判定其對應(yīng)明文的符號, 因此證明下面命題.

命題2 在Paillier 加密方案中, 假設(shè)a,b在明文空間ZN中取值. 令C=E(a)E(b)?1以及w=D(C). 則有下面結(jié)論:

(a)w=0 當(dāng)且僅當(dāng)a=b;

(b) 如果0≤a,b ＜N/2, 則可知: 0＜w ＜N/2 當(dāng)且僅當(dāng)a ＞b;N/2＜w ＜N當(dāng)且僅當(dāng)a ＜b.證明: 根據(jù)Paillier 加密算法的加法同態(tài)性,C=E(a)E(b)?1=E(a ?bmodN), 對C進行解密,解密結(jié)果為w=D(C)=a ?bmodN.

(a) 首先,w=a ?bmodN= 0 當(dāng)且僅當(dāng)存在整數(shù)k, 使得a ?b=kN. 又根據(jù)a,b ∈ZN, 可知?N ＜a ?b ＜N, 于是可知a ?b=kN成立當(dāng)且僅當(dāng)k=0, 即a=b.

(b) 在條件0≤a,b ＜N/2 之下,?N/2＜a ?b ＜N/2. 有下面結(jié)論成立:

(i) 首先可知w=a ?bmodN ?=N/2;

(ii) 由(a) 可知, 如果a=b, 則有w=0;

(iii) 若a ＞b, 則有0＜a ?b ＜N/2, 因此0＜w=a ?bmodN=a ?b ＜N/2;

(iv) 若a ＜b, 則有?N/2＜a ?b ＜0, 因此N/2＜w=a ?bmodN=a ?b+N ＜N.綜上, 命題2(b) 得證.

注解2 在下文中主要應(yīng)用命題2 的基本思想保密比較兩個數(shù)的大小關(guān)系. 假設(shè)Alice 和Bob 的私密數(shù)據(jù)分別為x和y, 且Alice 具有私鑰, 比較方法為: (i) Alice 加密x并將E(x) 發(fā)送給Bob; (ii) Bob 選擇隨機正整數(shù)r, 計算C= [E(x)E(y)?1]r, 將C發(fā)送給Alice; (iii) Alice 解密C, 得到m=r(x ?y)modN.

記a=rx,b=ry, 如果a,b滿足命題2(b) 的條件, 則由命題2, Alice 根據(jù)m的值可以獲得x,y的大小關(guān)系, 而Alice(或Bob) 不能獲得數(shù)據(jù)y(或x) 的任何額外信息.

計算原理 向量優(yōu)勢閾值問題的保密計算主要分為兩部分, 首先計算h=F(x,y), 在此基礎(chǔ)上進一步比較h與t的大小關(guān)系. 具體如下:

(1) 假設(shè)在協(xié)議中Alice 和Bob 應(yīng)用Paillier 加密算法進行保密計算, Alice 具有私鑰.

(a) 為了在計算F(x,y) 的過程中隱藏向量x與y中有哪些分量對應(yīng)相等, Alice 和Bob 需要分別將x和y轉(zhuǎn)化為u=(u1,··· ,un) 和v=(v1,··· ,vn), 其中ui=2xi和vi=2yi+1(此時必有ui ?=vi). 由命題1(a) 可知,F(x,y) =F(u,v). 因此可將計算F(x,y) 的問題轉(zhuǎn)化為計算F(u,v).

(b) 為了保密計算F(u,v), 基本思想是利用加密算法的加法同態(tài)性進行有關(guān)計算, 使得Alice 持有向量t= (r1(u1?v1),··· ,rn(un ?vn)) := (t1,··· ,tn), Bob 持有隨機向量r=(r1,··· ,rn)(其中每個分量為非零隨機整數(shù)).

(2) Alice 和Bob 合作進行加密選擇運算, 以確定F(u,v). 具體過程如下.

(a) Alice 加密. Alice 對向量t中各分量ti的符號信息(即正或負) 進行標記, 如果ti為正(負),則以hi=1(hi=0) 進行標記. Alice 加密hi, 并將E(h1),··· ,E(hn) 發(fā)送給Bob;

(b) Bob 進行選擇運算. Bob 根據(jù)自己持有的隨機向量r中各分量ri,i ∈[1,n] 的符號對于E(hi)選擇不同的運算方式, 以便將hi的符號信息轉(zhuǎn)化為ui ?vi的符號信息. 具體運算方式是, 當(dāng)ri為正時保持E(hi) 不變; 當(dāng)ri為負時, 對密文E(hi) 進行翻轉(zhuǎn)運算得到T[E(hi)].此時u,v中具有ui ＞vi性質(zhì)的分量對應(yīng)1 的密文, 其他分量對應(yīng)0 的密文.

(c) 應(yīng)用加密算法的加法同態(tài)性, 根據(jù)(b) 最后得到的密文即可計算得到F(u,v) 的密文.

(3) 根據(jù)F(u,v) 的密文以及閾值t, 以命題1(b) 與命題2 為基礎(chǔ)可以判定兩者大小關(guān)系, 最終得到Ft(u,v), 即Ft(x,y).

由于在計算中多次應(yīng)用命題2, 因此在協(xié)議設(shè)計中對于輸入數(shù)據(jù)以及隨機數(shù)的選擇范圍需有一定限制,以保證應(yīng)用命題2 所得結(jié)果是正確的. 具體協(xié)議設(shè)計如下.

3.2 協(xié)議設(shè)計

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

下面分別證明協(xié)議1 的正確性和安全性. 我們有下面結(jié)果.

定理1 協(xié)議1 能夠正確地計算向量優(yōu)勢閾值函數(shù)Ft(x,y).

證明: (1) 在協(xié)議第(2) 步中, Bob 對于Alice 發(fā)來的加密數(shù)據(jù)E(u), 選擇隨機向量r計算wi. 根據(jù)Paillier 加密方案的加法同態(tài)性,wi=E(ri(ui ?vi)modN), 因此Alice 在協(xié)議第(3) 步得到的解密結(jié)果是di=ri(ui ?vi)modN.

綜合(i)(ii) 可知, 在協(xié)議第(4)(a) 步中, 對于每個i ∈[1,n], Bob 計算得到的密文數(shù)據(jù)Hi為1 的密文當(dāng)且僅當(dāng)ui ＞vi, 而Hi為0 的密文當(dāng)且僅當(dāng)ui ＜vi. 協(xié)議第(4)(b) 步中Bob 計算所有H1,··· ,Hn的乘積H, 由加密算法的加法同態(tài)性可知乘積密文H即為F(u,v) 的密文.

(4) 協(xié)議第(4)(c) 和第(5) 步主要是根據(jù)F(u,v) 的密文H對F(u,v) 與閾值t進行大小比較.

由于對每個i ∈[1,n],wi=[E(ui)E(vi)?1]ri, 其中ri為Bob 選擇的非零隨機整數(shù), Alice 解密后得到di=ri(ui ?vi)modN. 這時考慮兩種情形: 如果0＜di ＜N/2, Alice 可知di=ri(ui ?vi); 如果N/2＜di ＜N, Alice 可知di=ri(ui ?vi)+N. 這時由于ri為Bob 選擇的隨機數(shù),ui又不等于vi, 因此無論對于哪種情形, 對于Alice 來說di都和隨機數(shù)不可區(qū)分, 因此對于Alice 來說,wc≡w′.

同理, Alice 在解密S=[E(1)H2E(2t)?1]r后得到s=r(2h+1?2t)modN, 其中h=F(u,v). 這時仍需要考慮兩種情形: 如果0＜s ＜N/2, 則Alice 可知s=r(2h+1?2t); 如果N/2＜s ＜N, 則Alice 可知s=r(2h+1?2t)+N. 由正確性證明過程知, Alice 根據(jù)s的取值范圍僅可獲知(2h+1?2t)的正負, 從而獲知h和t的大小關(guān)系, 這是協(xié)議規(guī)定的輸出結(jié)果. 由于r為Bob 選擇的任意隨機正整數(shù),無論對于哪種情形,S對于Alice 來說都和隨機數(shù)不可區(qū)分, 故有Sc≡S′. 又由于Ft(x,y′) =Ft(x,y),因此

綜上所述, 在半誠實模型下協(xié)議1 是CPA 安全的, 如果DCRSCCR問題是困難的, 協(xié)議1 還是CCA1安全的.

注解3 協(xié)議1 所解決的向量優(yōu)勢閾值保密計算問題可看成是向量優(yōu)勢保密判定問題的拓展. 因為當(dāng)設(shè)置閾值t=n時, 協(xié)議1 可用于解決向量優(yōu)勢保密判定問題, 此時, 根據(jù)協(xié)議1 的輸出結(jié)果, 如果Ft(x,y)=1, 則知F(x,y)≥n, 說明x是y的優(yōu)勢向量; 否則, 即可知x不是y的優(yōu)勢向量.

注解4 (1) 在協(xié)議1 中, 我們首先將計算F(x,y) 的問題轉(zhuǎn)化為計算F(u,v) 的問題, 這個轉(zhuǎn)化過程在保證安全性部分是非常重要的. 這是因為若不進行轉(zhuǎn)化, 在協(xié)議1 的(3)(a) 步, Alice 解密wi會得到di=ri(xi ?yi)modN. 此時若存在j ∈[1,n], 使得dj= 0, Alice 根據(jù)命題2 將得到xj=yj, 即得到Bob 向量中yj的值. 此外, Alice 還可根據(jù)使得di= 0 的元素個數(shù)獲知滿足xi=yi的分量個數(shù). 這些信息都是協(xié)議不允許泄露的額外信息. 因此在協(xié)議中需要將xi,yi轉(zhuǎn)化為ui= 2xi,vi= 2yi+1, 以保證di=ri(ui ?vi)modN恒不為0.

(2) 在協(xié)議第二部分, 比較h=F(u,v) 與閾值t的大小時, 也是將問題轉(zhuǎn)化為確定r(2h+1?2t) 的正負問題. 若不進行轉(zhuǎn)化, 在Alice 解密后會得到s=r(h ?t), 從而得到h=t是否成立, 這一信息也是協(xié)議不允許泄露的額外信息. 通過轉(zhuǎn)化保證了在解密S后得到的s=D(S)=r(2h+1?2t)modN ?=0,從而根據(jù)命題2, Alice 僅能得知2h+1＞2t或2h+1＜2t, 即h ≥t或h ＜t.

我們注意到, 文獻[21] 設(shè)計了一個云服務(wù)器外包計算方式的數(shù)據(jù)比較大小協(xié)議, 在此協(xié)議中用到了類似命題1(b) 的轉(zhuǎn)換技巧. 在本文協(xié)議1(或下面的協(xié)議2) 中, 需要計算滿足xi ＞yi(或xi=yi) 的個數(shù)h(或l), 以及其與閾值的大小關(guān)系, 即h ≥t(或l ≥t) 是否成立, 命題1(a)(b) 的轉(zhuǎn)化技巧在協(xié)議設(shè)計中都將發(fā)揮作用.

4 向量等分量數(shù)閾值保密計算

問題描述 類似地, 為了本部分敘述方便, 我們引入下面概念和函數(shù).

定義3 對于兩個n維向量x= (x1,··· ,xn) 和y= (y1,··· ,yn), 將兩個向量中滿足關(guān)系xi=yi,i ∈[1,n] 的分量個數(shù)稱為x與y的等分量數(shù), 用記號L(x,y) 來表示.

對于給定的向量x,y以及一個正整數(shù)t, 定義函數(shù)Lt(x,y) 如下: 如果L(x,y)≥t, 令Lt(x,y)=1,否則令Lt(x,y)=0. 并稱Lt(x,y) 為等分量數(shù)閾值函數(shù).

本節(jié)中我們希望研究的問題是: 假設(shè)Alice 和Bob 分別擁有私密向量x和y, 并有一個商定好的閾值t, 他們希望合作保密計算函數(shù)Lt(x,y), 計算結(jié)束后不泄露兩個私密向量的任何額外信息.

計算原理

由于協(xié)議2 的(1)-(4)(a) 步實際上是對不同的輸入并行(兩次) 執(zhí)行協(xié)議1 的(1)-(4)(a) 步, 協(xié)議的第(4)(b)(c) 與第(5) 步執(zhí)行都類似于協(xié)議1 的相應(yīng)執(zhí)行過程. 由協(xié)議1 類似可得, 如果DCRSCCR問題是困難的, Paillier 加密方案就是CCA1 安全的, 協(xié)議2 就是CCA1 安全的. 類似于協(xié)議1, 可證明協(xié)議2 的安全性, 此處不再贅述, 僅給出下面定理.

定理4 在半誠實模型下協(xié)議2 是CPA 安全的.

注解5 協(xié)議2 所解決的向量等分量數(shù)閾值保密計算問題可看成向量相等判定問題的推廣. 由于當(dāng)設(shè)置閾值t=n時, 此時若Lt(x,y)=1, 則說明l ≥n, 即兩向量相等; 否則說明兩向量不相等.

5 協(xié)議效率分析

5.1 本文協(xié)議復(fù)雜性分析

為了便于分析和比較, 在進行計算復(fù)雜性分析時, 僅考慮費時較多的模指數(shù)運算, 忽略其他簡單運算.在Paillier 加密方案中, 一次加密或解密各需要2 次模指數(shù)運算, 下面將以執(zhí)行協(xié)議所需要的模指數(shù)運算次數(shù)來衡量計算復(fù)雜性.

假設(shè)向量的維數(shù)為n, 在協(xié)議1 中, Alice 共需進行2n次加密運算與n+1 次解密運算, Bob 需要進行n+2 次加密運算與n+2 次模指數(shù)運算. 此外, 記滿足ri ＜0,i ∈[1,n] 的隨機數(shù)個數(shù)為c1, 在協(xié)議中Bob 需進行c1次翻轉(zhuǎn)運算, 相當(dāng)于進行c1次模指數(shù)運算(每次翻轉(zhuǎn)運算采用相同的1 的密文E(1)).綜上, 協(xié)議1 共需進行3n+2 次加密運算,n+1 次解密運算與n+c1+2 次模指數(shù)運算, 共相當(dāng)于進行了8n+c1+7 次模指數(shù)運算. 當(dāng)c1=n時, 協(xié)議1 具有最高的計算復(fù)雜度, 需進行9n+7 次模指數(shù)運算.

在協(xié)議2 中, Alice 共需進行4n次加密運算與2n+1 次解密運算. Bob 需進行2n+2 次加密運算與3n+2 次模指數(shù)運算. 此外, 若記滿足ri,?ri的隨機數(shù)個數(shù)為c2, 則在協(xié)議中需進行c2次翻轉(zhuǎn)運算, 即進行c2次模指數(shù)運算. 綜上, 協(xié)議2 共需進行6n+2 次加密運算, 2n+1 次解密運算與3n+c2+2 次模指數(shù)運算, 相當(dāng)于進行了17n+c2+7 次模指數(shù)運算. 當(dāng)c2=2n時, 協(xié)議2 具有最高的計算復(fù)雜度, 需進行19n+7 次模指數(shù)運算.

本文協(xié)議的通信復(fù)雜性以通信輪數(shù)來衡量. 在協(xié)議1 中, (1)-(2) 步Alice 和Bob 進行了1 輪通信,(3)-(4) 步又進行了1 輪通信, 故通信復(fù)雜性為2. 同樣地, 協(xié)議2 的(1)-(2), (3)-(4) 步Alice 和Bob 分別進行了1 輪通信, 故共需進行2 輪通信.

5.2 與已有協(xié)議對比分析

當(dāng)閾值t=n時, 本文協(xié)議1 即為安全向量優(yōu)勢協(xié)議. 文獻[15,16] 對這一問題進行了研究, 在文獻[15] 中, 協(xié)議4 計算向量優(yōu)勢問題. 在協(xié)議的前兩步中, Alice 需要進行4n次加密與4n次解密, Bob需要進行1 次加密運算. 相當(dāng)于共進行12n+2 次模指數(shù)運算. 此外, 協(xié)議最后兩步還需調(diào)用4n次百萬富翁協(xié)議以及4n次相等測試協(xié)議才能得到結(jié)果. 協(xié)議的前兩步共需要進行1 輪通信, 在并行執(zhí)行時, 百萬富翁協(xié)議與相等測試部分各需要1 輪通信, 故協(xié)議的通信復(fù)雜度為3. 在文獻[16] 中, 運用具有加法同態(tài)的ElGamal 加密方案解決這一問題. 在加法同態(tài)的ElGamal 加密方案中, 進行1 次加密相當(dāng)于進行3次模指數(shù)運算, 解密則需要進行1 次模指數(shù)運算. 若約定二進制數(shù)位數(shù)為k, 在協(xié)議1 中Alice 對自己的向量數(shù)據(jù)需進行nk次加密運算, 此外還需要進行kn次解密運算, 相當(dāng)于共進行3nk+k次模指數(shù)運算.Bob 則需要進行2nk+2 次加密運算以及kn次模指數(shù)運算, 相當(dāng)于共進行了3nk+kn+6 次模指數(shù)運算. 因此, 文獻[16] 中向量優(yōu)勢判定協(xié)議計算復(fù)雜度為6nk+2kn+6. 在協(xié)議執(zhí)行中, Alice 與Bob 之間共進行了1 輪通信. 由此可知, 相比文獻[15,16], 本文協(xié)議1 效率更高.

此外, 文獻[18] 應(yīng)用Paillier 加密方案研究向量優(yōu)勢統(tǒng)計問題, 若全集的勢為m, 向量的維數(shù)為n, 在協(xié)議執(zhí)行過程中共需要進行mn次加密運算與1 次解密運算, 即2(mn+1) 次模指數(shù)運算. 本文協(xié)議1 作為向量優(yōu)勢統(tǒng)計問題的推廣問題, 相比文獻[18] 去除了元素范圍的限制, 在元素范圍取值較大時(即m較大時) 本文協(xié)議1 也有著明顯的優(yōu)勢.

5.3 實驗分析

為了進一步測試本文協(xié)議的執(zhí)行效率與實際可行性, 設(shè)計模擬實驗來測試執(zhí)行協(xié)議所需要的時間.

實驗測試環(huán)境: Windows 10 64 位(家庭版) 操作系統(tǒng), 處理器是Intel(R)Core(TM)i5-6600 CPU@3.30 GHz, 內(nèi)存是8.00 GB, 用Java 語言在MyEclipse 上運行實現(xiàn).

實驗方法: 通過模擬實驗測試本文協(xié)議所用時間, 根據(jù)協(xié)議執(zhí)行時間驗證方案效率. 在本文中, 在向量維數(shù)n分別為2,4,6,··· ,20 時, 對n的每個設(shè)定值進行1000 次模擬實驗, 并統(tǒng)計協(xié)議1 與協(xié)議2 的執(zhí)行時間的平均值.

協(xié)議1 與協(xié)議2 的運行時間如圖1 所示. 由圖1 可知, 隨著向量維數(shù)的增大, 協(xié)議1 和協(xié)議2 的執(zhí)行時間都線性增加, 協(xié)議2 的執(zhí)行時間高于協(xié)議1.

當(dāng)向量維數(shù)較高時, 協(xié)議1, 2 的執(zhí)行時間也隨之線性增加. 經(jīng)實驗, 對于較高維數(shù)的向量, 本文協(xié)議仍適用. 當(dāng)向量維數(shù)為500 維時, 執(zhí)行協(xié)議1 耗時13 415 毫秒, 近似于13 秒. 執(zhí)行協(xié)議2 耗時27 918 毫秒,近似于28 秒.

圖1 協(xié)議1,2 的執(zhí)行時間隨向量維數(shù)增大的變化規(guī)律Figure 1 Execution time of protocol 1,2 with increase of vector dimension

6 推廣應(yīng)用

6.1 區(qū)間關(guān)系判定

區(qū)間關(guān)系保密判定問題在實際生活中有著廣泛的應(yīng)用. 例如公司A 與公司B 希望進行商品交易,在進行價格協(xié)商時需要先確認兩公司是否有達成交易的可能性. 假設(shè)A 公司認為商品的理想出售價格在a1到b1之間, B 公司則想以最低a2, 最高b2的價格購買A 公司的商品. 因此首先需要判定區(qū)間(a1,b1),(a2,b2) 是否相交, 即兩者是否有達成交易的可能. 由于區(qū)間(a1,b1) 中a1,b1分別表示A 公司能接受的最低成交價與預(yù)計的最高成交價,a2,b2分別表示B 公司開出的購買價格范圍, 這兩個區(qū)間均屬于公司的商業(yè)機密. 因此需要在保證兩方數(shù)據(jù)隱私的情況下對兩區(qū)間關(guān)系進行判定, 以判定兩公司是否有達成交易的可能. 利用本文所設(shè)計的協(xié)議即可解決這一問題. 具體描述如下.

問題描述: 假設(shè)Alice 有私密區(qū)間(a1,b1), Bob 有私密區(qū)間(a2,b2), 他們希望保密判定兩區(qū)間是否相交.

基本原理: 如圖2 所示, 區(qū)間(a1,b1),(a2,b2) 相交當(dāng)且僅當(dāng)b1＞a2,a1＜b2.

圖2 兩區(qū)間相交Figure 2 Intersection of two intervals

首先,Alice 和Bob 商定一個較大的正數(shù)d,使得b1,b2＜d. 記向量x=(d?a1,b1),y=(d?b2,a2),設(shè)閾值t= 2. 于是判定兩區(qū)間是否相交的問題即可轉(zhuǎn)化為計算向量優(yōu)勢閾值函數(shù)Ft(x,y) 的問題, 調(diào)用協(xié)議1 即可.

6.2 字符串模式匹配

保護隱私的字符串模式匹配在信息查詢與過濾、病毒檢測、生物信息檢測等方面都有著廣泛的應(yīng)用.例如在郵件收發(fā)中, 系統(tǒng)會根據(jù)郵件內(nèi)容是否包含某些不良信息決定是否對郵件進行攔截. 但考慮到郵件屬于私密信件, 用戶不希望泄露給其他方, 包括系統(tǒng). 因此需要在不泄露郵件內(nèi)容的情況下判定其中是否包含不良信息. 此時, 將需要攔截的關(guān)鍵詞構(gòu)成不良信息庫, 通過對這些關(guān)鍵詞與郵件內(nèi)容進行保密的字符串模式匹配即可實現(xiàn)保護隱私的郵件攔截. 由此可見, 保護隱私的字符串模式匹配問題研究有很大的實際意義. 利用本文所設(shè)計的協(xié)議即可解決這一問題. 具體描述如下.

問題描述Alice 有目標字符串A=a1···an, Bob 有模式字符串B=b1···bm(m ≤n). 他們希望保密判定在A中是否存在子串SAi=ai···ai+m?1=B.

計算原理 首先運用ASCII 碼將每個字符與一個三位十進制數(shù)一一對應(yīng)(例如對于字符串‘Love’, 字符‘L’ 對應(yīng)的ASCII 碼為076, ‘o’ 對應(yīng)為111, ‘v’ 對應(yīng)為118, ‘e’ 對應(yīng)為101, 因此‘Love’ 所對應(yīng)的數(shù)字串即為076111118101). Bob 將字符串B所對應(yīng)的數(shù)字串記為y. Alice 將字符串A=a1···an以m個連續(xù)字符為單位進行分割, 記分割后的字符串依次為SA1=a1···am,··· ,SA,n?m+1=an?m+1···am.并分別用xA1,··· ,xA,n?m+1表示其所對應(yīng)的數(shù)字串. 令閾值t=1,數(shù)組x=(xA1,··· ,xA,n?m+1),y=(y,··· ,y) 應(yīng)用協(xié)議2 計算向量x,y的等分量數(shù)與t的大小關(guān)系Lt(x,y) 即可得到匹配結(jié)果. 若Lt(x,y) = 1, 則說明滿足xAi=y的元素個數(shù)至少為1, 即必存在k ∈[1,n ?m+1], 使得xAk=y. 由于xAk與字符串SAk,y與字符串B一一對應(yīng), 故必存在SAk=B, 即A,B模式匹配, 反之則不匹配.

7 結(jié)論

本文在安全向量優(yōu)勢問題的基礎(chǔ)上, 將向量優(yōu)勢統(tǒng)計與閾值計算相結(jié)合, 研究更為一般的問題, 即向量優(yōu)勢與等分量數(shù)閾值計算問題. 若閾值與向量維數(shù)相等, 則為安全向量優(yōu)勢與向量相等問題. 本文針對這兩個問題設(shè)計了高效的計算協(xié)議, 同時, 將所設(shè)計的協(xié)議作為基本工具去解決其他安全多方計算問題,具體例舉了區(qū)間關(guān)系判定問題與方程組解的判定問題. 在下一步工作中, 將繼續(xù)研究在惡意模型下的高效安全向量計算方案.