王穎囡,竇家維,葛 雪

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

1 引言

向量是既有大小又有方向的量,可以用來解決許多科學技術問題與實際應用問題.在數(shù)學中,可由向量的點積(叉積)是否為零來判定兩直線是否正交(平行).在物理學中力和速度的分解及求和也都離不開向量運算.同時,向量在選舉、信息推薦等方面也有著重要的應用.在選舉過程中,把全體候選人的得票數(shù)記為向量,便可以解決復雜的選舉問題.同樣地,在進行信息推薦時,可以把用戶的有用信息表示成向量,將其與商品信息組成的向量進行對比并計算匹配性,從而為用戶推薦最可能需求的商品.但在進行各種向量計算時,保護用戶的隱私也尤為重要.比如,在人們收到推銷電話時會考慮自己的需求與手機號碼在何時已泄露出去,同樣,在檢測一篇很有價值的論文的重復率時,用戶會擔心自己的成果會不會在檢測過程中被剽竊.為了在保護隱私的條件下解決上述問題,就需要將其轉(zhuǎn)化為有關的向量安全多方計算問題來解決.

安全多方計算是指多個持有私有數(shù)據(jù)的參與者在保證其私有數(shù)據(jù)安全性的基礎上,利用這些私有數(shù)據(jù)共同參與某些聯(lián)合計算,得到參與者想要計算的結果.安全多方計算是由姚期智教授[1]首次提出的,Goldreich,Micali等人[2–5]對其進行了深入的研究,使其發(fā)展成為計算機科學中必不可少的組成部分,也成了信息安全的理論基礎.目前,在安全多方計算方面,人們研究了各種各樣的問題,包括保密的信息比較[6–8]、集合問題[9–12]、保密的計算幾何[13–16]、保密的數(shù)據(jù)挖掘[17]等.

目前,有關向量的安全計算問題的研究有向量的求和[18,19]、向量的線性組合[20]、向量內(nèi)積的計算[21,22]、向量優(yōu)勢的判定[4,23].文獻 [18]對向量的求和問題進行了研究,用 Paillier加密方案將每個向量進行加密并利用其具有的加法同態(tài)性得到向量和的密文,為了抵抗合謀攻擊,借助可信的第三方將解密密鑰拆分給多個權威中心,并由權威中心聯(lián)合解密得到所需結果.但由于加密次數(shù)過多,解密又要借助難以找到的可信第三方,協(xié)議的實現(xiàn)性較差.文獻[19]應用改進的ElGamal加密系統(tǒng)設計向量求和協(xié)議,但由于改進的ElGamal加密系統(tǒng)把要加密的消息放在指數(shù)上,解密時會涉及到求解離散對數(shù)問題,而由于計算離散對數(shù)問題的困難性,協(xié)議不能完全解密,最終需要通過窮舉法等方法來獲得明文,計算效率較低.文獻[20]利用NTRU公鑰加密和 ElGamal加密實現(xiàn)了向量線性組合的保密計算,并在此基礎上解決可抵抗量子攻擊的多項數(shù)據(jù)安全統(tǒng)計問題和選舉問題.文獻[21,22]研究了向量內(nèi)積的保密計算.文獻[4]首次提出安全向量優(yōu)勢問題,借助百萬富翁協(xié)議對于向量中對應分量分別進行大小比較,效率較低.文獻 [23]應用適當?shù)木幋a方法解決了安全向量優(yōu)勢問題,并以此為基礎研究了整除問題以及點與若干直線位置關系判定問題.

在對事物進行分析與研究時,通常會把有關研究對象的重要特征提取出來用一個向量表示,并根據(jù)向量之間的匹配程度對研究對象進行分類、聚類,進而研究其性質(zhì).向量的匹配程度可以應用向量中對應分量相等的分量個數(shù)來衡量,而相等分量數(shù)目計算問題可看成海明距離的推廣.文獻 [24]主要研究了海明距離及其一些推廣應用問題的保密計算,其中,binHDOT協(xié)議研究了半誠實模型下兩方參與者對其具有的比特字符串海明距離的保密計算 (參看文獻 [24]的 Figure 1),以 binHDOT協(xié)議為基礎,HDOT協(xié)議進一步研究了由任意字符數(shù)據(jù)構成的字符串的海明距離 (參看文獻 [24]的 Figure 2),HDOT協(xié)議的設計思想是兩方參與者首先將其具有的字符串中各個字符數(shù)據(jù)表示為具有相同長度的二進制串,進一步以binHDOT協(xié)議為基礎對變換后的二進制串逐對進行相等判定,最終獲得兩字符串的海明距離(字符串中對應字符數(shù)據(jù)不相等的字符數(shù)目).如果將HDOT協(xié)議中兩方字符串中各個字符數(shù)據(jù)看作一個向量的分量,則可以直接應用文獻[24]的HDOT協(xié)議解決兩個向量的等分量數(shù)問題.但由于在文獻[24]的HDOT協(xié)議中需要多次調(diào)用兩比特串海明距離計算協(xié)議,協(xié)議復雜性較高.本文主要對于向量等分量數(shù)保密計算問題設計高效的保密計算協(xié)議(文獻[24]中HDOT協(xié)議與本文協(xié)議的效率比較將在第5節(jié)詳細討論).

本文主要貢獻如下:

(1)應用新的方法解決向量等分量數(shù)保密計算問題.分別設計了對向量數(shù)據(jù)有全集限制以及無全集限制情形下向量等分量數(shù)保密計算協(xié)議,應用模擬范例方法嚴格證明了所設計的協(xié)議在半誠實模型下是安全的.

(2)進一步設計了向量等分量數(shù)閾值問題的保密判定協(xié)議和向量優(yōu)勢統(tǒng)計方案.

(3)本文協(xié)議可以作為構建其他安全多方計算問題協(xié)議的基本模塊,用于解決其他很多安全多方計算問題,文中給出了一些具體的應用舉例.

本文組織如下:第2節(jié)介紹了本文需要用到的一些預備知識;第3節(jié)設計了有全集限制和無全集限制條件下向量等分量數(shù)計算協(xié)議,并嚴格證明了協(xié)議的安全性;第4節(jié)主要研究向量等分量數(shù)閾值問題保密判定和向量優(yōu)勢統(tǒng)計問題;第5節(jié)分析了本文協(xié)議的復雜度,并對具體計算問題進行實驗測試;第6節(jié)給出了向量等分量數(shù)計算協(xié)議在解決實際問題中的兩個具體應用;第7節(jié)對全文進行總結.

2 預備知識

2.1 安全性定義

理想模型m個參與者P1,···,Pm,分別把私密數(shù)據(jù)x1,···,xm發(fā)送給一個可信的第三者TTP,TTP計算函數(shù)f(x1,···,xm)=(f1(x1,···,xm),···,fm(x1,···,xm)),將結果fi(x1,···,xm),i∈[1,m]={1,2,···,m}分別發(fā)送給參與者Pi.參與者Pi在協(xié)議中除了獲得規(guī)定的輸出結果fi(x1,···,xm)外,得不到其他參與者數(shù)據(jù)的任何額外信息.這樣的安全計算模型稱為理想模型.

由于在任何情況下,TTP都不會泄露任何不該泄露的信息,因此理想模型下的計算協(xié)議是安全性最高的多方計算協(xié)議,由于理想模型有賴于TTP,而在實際中要找到一個可信的第三方并非易事,因此需要設計不依賴于TTP的實際安全計算協(xié)議,通過和理想?yún)f(xié)議進行比較來檢驗實際計算協(xié)議的安全性.

半誠實模型所謂半誠實參與者是指那些在協(xié)議執(zhí)行過程中按照協(xié)議要求忠實地履行協(xié)議的參與者,但他們可能會收集和保留在協(xié)議執(zhí)行過程中獲得的所有信息,在協(xié)議執(zhí)行后試圖根據(jù)這些信息推算出其他參與者數(shù)據(jù)的額外信息.如果所有參與者均為半誠實參與者,稱這樣的計算模型為半誠實模型[3].文獻[3]給出了一個將半誠實模型下安全協(xié)議直接編譯成惡意模型下安全協(xié)議的一般方法,因此設計半誠實模型下安全計算協(xié)議是基本而重要的.本文主要研究半誠實模型下的兩方向量保密計算問題.

安全性定義假設有概率多項式時間函數(shù)f(x,y):(x,y)→(f1(x,y),f2(x,y)),π為計算函數(shù)f的一個兩方協(xié)議.記協(xié)議的參與者為 Alice和 Bob,他們的輸入分別為x,y,協(xié)議執(zhí)行中 Alice得到的信息序列記為其中r1為 Alice選擇的隨機數(shù),為 Alice收到的第i個信息,f1(x,y)為 Alice獲得的輸出結果,類似定義 Bob在協(xié)議執(zhí)行中得到的信息序列為

如果存在概率多項式時間算法S1,S2,使得下面兩式成立

則稱協(xié)議π安全地計算了函數(shù)f.其中表示計算上不可區(qū)分.要證明一個兩方計算協(xié)議是安全的,就必須構造滿足式(1)和式(2)的模擬器.這種證明安全性的方法是多方保密計算中普遍接受的模擬范例方法.若在協(xié)議執(zhí)行中某參與方未獲得任何輸出,約定該參與方的輸出為空串λ.

2.2 Paillier加密方案

Paillier加密方案具體過程如下[25]:

密鑰生成選取大素數(shù)p,q,并令N=pq,ω=lcm(p?1,q?1).設函數(shù)L(x)=,隨機選取g∈滿足gcd(L(gωmodN2),N)=1,則公鑰為pk=(g,N),私鑰為sk=ω.加密算法和解密算法分別記為E和D.

加密對于明文m∈ZN,選擇隨機數(shù)r∈,計算密文c=E(m)=gmrNmodN2.

解密對于密文c∈,解密得到明文m=D(c)如下:

加法同態(tài)性由于E(m1)E(m2)=gm1+m2(r1r2)NmodN2=E(m1+m2),因此Paillier加密方案具有加法同態(tài)性.

密文重隨機化假設E(m)是應用公鑰pk加密m得到的一個密文,給E(m)乘上0的一個密文后,得到C=E(m)E(0),根據(jù)Paillier加密方案的加法同態(tài)性,可知C為m的一個新的密文形式.這個過程稱為密文的重隨機化.

Paillier加密方案是語義安全的.一個密碼系統(tǒng)是語義安全的,意味著同一明文可以加密成多個不同的密文形式,并且這些密文都是計算不可區(qū)分的.在下文中,以 Paillier加密方案為基礎所做的密文乘積運算和模乘運算均是在模N2的意義下進行的.文中E(?m)=E(N?m),m>0代表?m的密文.

3 向量等分量數(shù)保密計算

問題描述:對于兩個n維向量U=(u1,···,un),V=(v1,···,vn),定義函數(shù)?i=Φi(ui,vi):如果ui=vi,則?i=1;否則?i=0.定義兩向量U,V的等分量數(shù)為?=Φ(U,V)=Φi(ui,vi).

假設Alice和 Bob各自擁有保密的n維向量U和V,他們希望在不泄露各自隱私數(shù)據(jù)的條件下合作計算向量等分量數(shù)?=Φ(U,V).即他們希望保密計算兩個向量中具有性質(zhì)ui=vi,i∈[1,n]的分量數(shù)目.

3.1 向量等分量數(shù)保密計算協(xié)議1

本節(jié)主要研究在有全集限制條件下兩向量等分量數(shù)保密計算問題.即假設在保證參與者輸入數(shù)據(jù)隱私的前提下,參與者雙方可以商定一個全集,記為Q={q1,q2,···,qm},滿足q1<···

假設參與者的集合U與V都含于全集Q中,并假設ui∈U以及vi∈V在Q中的序位分別為ki以及l(fā)i.

編碼方法 1Alice對向量U進行編碼,編碼結果是一個矩陣,記為WU=(uij)n×m,其中uij(i∈[1,n],j∈[1,m])定義如下:如果t=ki,令uit=1;否則,令uit=0.

選擇方法對于每一個i∈[1,n],Bob在WU的第i行中選擇第li列元素uili,Bob再將所選擇的元素相加,得到?=u1l1+···+unln,?即為兩向量對應分量相等的數(shù)目.

例 1對于向量U=(7,3,0,5,3),V=(5,3,0,6,5),根據(jù)全集Q={0,1,2,3,4,5,6,7,8},對U進行編碼得到矩陣

由于v1=5,在Q中的序位為6,因此,Bob在矩陣的第1行選擇元素u16=0,同理,在矩陣的第2–5行分別選擇元素u24=1,u31=1,u47=0,u56=0,這五個元素的和為2,因此向量U,V等分量數(shù)為?=2.

為了進行保密計算,我們結合Paillier加密方案實現(xiàn)上述計算過程,具體協(xié)議如下:

協(xié)議 1:兩向量等分量數(shù)保密計算協(xié)議1.

輸入:Alice輸入向量U=(u1,···,un),Bob輸入向量V=(v1,···,vn),其中ui,vi∈Q.

輸出:滿足ui=vi,i∈[1,n]的分量數(shù)目?=Φ(U,V).

準備工作:(a)Alice運行Paillier同態(tài)加密方案,生成私鑰sk和公鑰pk,將公鑰發(fā)送給云,并借助云生成若干個0的密文與1的密文,將生成的0與1的密文集合分別記為H0與H1;根據(jù)密文重隨機化原理,Alice適當選擇H0以及H1中不同的密文進行模乘運算,生成兩個分別由0和1的密文構成的新集合中至少包含n(m?1)個0的密文,中至少包含n個1的密文,對于云來說(或)中的元素與隨機數(shù)不可區(qū)分).

(b)Alice按照編碼方法1,對向量U進行編碼,得到編碼矩陣WU=(uij)n×m,并應用中0與1的密文構造加密矩陣

(1)Alice將公鑰pk=(g,N)以及E(WU)發(fā)送給Bob.

(2)對于每一個i∈[1,n],Bob根據(jù)vi在全集Q中的序位li,在矩陣E(WU)第i行挑選第li列元素E(uili).并計算將C發(fā)送給Alice.

(3)Alice解密C,得到?=D(C)并輸出?.

協(xié)議1的正確性根據(jù)Paillier加密算法的加法同態(tài)性,在協(xié)議1第2步中,=E(),因此在第3步Alice對C解密后,結果為D(C)=.根據(jù)計算原理所述,這正是協(xié)議規(guī)定的輸出結果,因此協(xié)議1是正確的.

協(xié)議 1的安全性關于協(xié)議1的安全性,我們有下面的定理.

定理 1兩向量等分量數(shù)保密計算協(xié)議1在半誠實模型下是安全的.

證明:下面將應用多方保密計算中普遍接受的模擬范例方法嚴格證明定理1.

首先構造S1.S1接受到輸入(U,f1(U,V)=Φ(U,V))后,按如下方式運行:

在協(xié)議 1中由于Bob沒有利用云進行任何計算,即使Alice和云合謀也無法獲得Bob數(shù)據(jù)的任何額外信息.

下面構造S2.S2接受到輸入(V,f2(U,V)=Φ(U,V))后,按如下方式運行:

因此,協(xié)議1在半誠實模型下是安全的.

3.2 向量等分量數(shù)保密計算協(xié)議2

上節(jié)中討論了在數(shù)據(jù)范圍已知的情況下兩向量等分量數(shù)保密計算問題,但如果集合數(shù)據(jù)范圍不好確定(或范圍很大),這時將無法應用上節(jié)的協(xié)議進行計算(或應用上節(jié)協(xié)議計算復雜性將很高),因此需要在無全集限制條件下,構造兩向量等分量數(shù)保密計算協(xié)議.

計算原理將向量U,V的對應分量ui,vi,i∈[1,n]逐對進行大小比較,檢查其是否相等,并以Paillier加密算法為基礎實現(xiàn)保密計算.

協(xié)議 2:向量等分量數(shù)保密計算協(xié)議2.

輸入:Alice 輸入向量U=(u1,···,un),Bob 輸入向量V=(v1,···,vn).

輸出:滿足ui=vi,i∈[1,n]的分量數(shù)目?=Φ(U,V).

準備工作:Alice運行Paillier加密方案,生成加密的公鑰pk=(g,N)和對應的私鑰sk=ω(可取N足夠大使得

(1)Alice加密向量U,得到E(U)=(E(u1),···,E(un)),并將E(U),pk發(fā)送給 Bob.

(2)對于每一個i∈[1,n],Bob加密?vi,得到E(?vi),并選擇隨機數(shù)ri,0≤ri<計算ci=(E(ui)E(?vi))ri.將c=(c1,···,cn)中分量進行隨機置換 (將置換記為π),置換后得到=(cπ(1),···,cπ(n))(其中{π(1),···,π(n)}={1,···,n}),Bob將發(fā)送給Alice.

(3)對于每一個i∈[1,n],Alice解密ci得到明文di,將 (dπ(1),···,dπ(n))中取值為 0的分量數(shù)目記為?,并輸出?.

協(xié)議 2的正確性根據(jù)Paillier加密算法的加法同態(tài)性,對于任意i∈[1,n],ci=(E(ui)E(?vi))ri=E(ri(ui?vi)),解密后可得di=ri(ui?vi)modN,由于0≤ri,ui,vi<故?N

協(xié)議 2的安全性下面分別考慮Alice和Bob數(shù)據(jù)的安全性.

Alice數(shù)據(jù)的安全性.由于在協(xié)議執(zhí)行中,Bob僅接收到Alice發(fā)送的數(shù)據(jù)E(U),由于E(U)是Alice加密的密文,Bob沒有解密密鑰,根據(jù) Paillier加密算法的語義安全性,對 Bob來說從E(U)中得不到Alice數(shù)據(jù)的任何信息.因此Alice的數(shù)據(jù)是安全的.

Bob數(shù)據(jù)的安全性.由于在協(xié)議執(zhí)行中,Alice僅接收到Bob發(fā)送的密文數(shù)據(jù)ci=(E(ui)E(?vi))ri(i∈[1,n]).由于E(?vi)是Bob加密的密文,ri為Bob選擇的隨機數(shù),根據(jù)Paillier加密算法的語義安全性以及ri的隨機性,對Alice來說從ci(i∈[1,n])中得不到Bob數(shù)據(jù)的任何信息.雖然Alice有解密密鑰,解密后Alice僅獲得(dπ(1),···,dπ(n))中哪些分量為0,由于Alice不知道將c轉(zhuǎn)化為的隨機置換π,即Alice不知道π(i)和i的對應關系,因此Alice無法獲知對于具體哪些i∈[1,n],有ui=vi.而當uivi時,di=ri(ui?vi)modN,因ri是 Bob選擇的隨機數(shù),故Alice從協(xié)議 2的執(zhí)行中得不到Bob向量數(shù)據(jù)的任何額外信息.因此,Bob的數(shù)據(jù)是安全的.

類似于定理1,可以通過構造模擬器S1,S2嚴格證明協(xié)議2的安全性.僅敘述下面定理,證明從略.

定理 2兩向量對應分量相等個數(shù)保密計算協(xié)議2在半誠實模型下是安全的.

4 向量等分量數(shù)擴展問題

4.1 向量等分量數(shù)閾值問題

問題描述Alice和 Bob分別具有向量U=(u1,···,un)和V=(v1,···,vn),并事先商議好全集Q和閾值k(1≤k≤n),使得對于所有i∈[1,n],ui,vi∈Q.Alice和Bob希望保密判定兩向量分量相等個數(shù)?=Φ(U,V)與閾值k的大小關系,而不泄露關于集合U,V的任何額外信息.

計算原理Alice和Bob首先以協(xié)議1為基礎獲得函數(shù)值?的密文,這時不需要解密,進一步結合k的密文來保密判定Φ(U,V)與k的大小關系.

為敘述方便,定義謂詞:h=Hk(U,V):如果Φ(U,V)≥k,定義h=1,否則,定義h=0.為了構造本節(jié)的保密計算協(xié)議,我們需要解決兩個數(shù)大小的保密判定問題.首先證明下面命題.

命題 1假設 Paillier加密系統(tǒng)中私鑰為 sk,公鑰為 pk=(g,N),加解密算法分別為E,D.任意0≤u,vv當且僅當0N/2.

證明:按照Paillier加密算法的定義以及加法同態(tài)性,C=E(u)E(?v)=E(u?v),對C應用私鑰sk進行解密,解密結果為w=D(C)=(u?v)modN.

(a)當u=v時,得到w=D(C)=(u?v)modN=0.

(b)當u>v時,此時由于0

(c)當uN/2.

由于w=D(C)=(u?v)modN∈ZN,根據(jù)假設條件0≤u,v

命題 2對任意整數(shù)a,b,a≥b當且僅當2a+1>2b;a>b當且僅當2a>2b+1.

證明:若a≥b,則 2a≥2b,因此 2a+1>2b.反之,若 2a+1>2b,則必有 2a≥2b成立,即a≥b成立.綜上,a≥b當且僅當2a+1>2b.同理可得a>b當且僅當2a>2b+1.

下面給出具體協(xié)議.

協(xié)議 3:向量等分量數(shù)閾值問題保密判定協(xié)議.

輸入:Alice輸入向量U=(u1,···,un),Bob輸入向量V=(v1,···,vn),對于所有i∈[1,n],ui,vi∈Q.

輸出:向量等分量數(shù)Φ(U,V)與閾值k的大小關系h=Hk(U,V).

準備工作:協(xié)議3準備工作與協(xié)議1相同.

(1)Alice將公鑰pk=(g,N)以及E(WU)發(fā)送給Bob.

(2)對于每一個i∈[1,n],Bob根據(jù)vi在全集Q中的序位li,在矩陣E(WU)第i行挑選第li列元素E(uili).Bob選擇隨機數(shù)r滿足并將C發(fā)送給Alice.

(3)Alice解密C得到c,若,令h=1,否則令h=0.輸出h.

協(xié)議 3的正確性:協(xié)議3的準備工作和第(1)步與協(xié)議1完全相同.在協(xié)議3第(2)步,Bob首先計算得到?的密文:此后計算因此在第 (3)步中,解密結果c=r(2?+1?2k)modN,由于 0≤?,k≤n,r<,故可得 0≤r(2?+1),2rk2k,由命題2可得,?≥k,因此可得h=1,反之則h=0.綜上,協(xié)議3是正確的.

協(xié)議 3的安全性下面分別考慮Alice和Bob數(shù)據(jù)的安全性.

Alice數(shù)據(jù)的安全性.在協(xié)議執(zhí)行中,Alice僅給Bob發(fā)送了密文數(shù)據(jù)E(WU).由于Bob沒有密鑰,根據(jù)Paillier加密系統(tǒng)的語義安全性,Bob由E(WU)得不到Alice數(shù)據(jù)任何額外的信息,因此Alice數(shù)據(jù)是安全的.

Bob數(shù)據(jù)的安全性.在協(xié)議執(zhí)行中,Bob僅給Alice發(fā)送了密文由于r是Bob選擇的隨機數(shù),并且E(?2k)是Bob加密的密文,根據(jù)Paillier加密算法的語義安全性,對Alice來說從密文C中得不到Bob數(shù)據(jù)的任何信息.雖然Alice有解密密鑰,解密后Alice僅獲得h的值,該值是協(xié)議規(guī)定的輸出數(shù)據(jù),因此Bob數(shù)據(jù)是安全的.

類似于定理1,可以通過構造模擬器S1,S2嚴格證明協(xié)議3的安全性.僅敘述下面定理,證明從略.

定理 3向量等分量數(shù)閾值保密判定協(xié)議3在半誠實模型下是安全的.

4.2 向量優(yōu)勢及其閾值問題

在文獻 [23]中,通過對數(shù)據(jù)編碼研究向量優(yōu)勢問題,向量優(yōu)勢問題是指:Alice有向量U=(u1,···,un),Bob有向量V=(v1,···,vn).Alice和 Bob希望在不泄露各自向量信息的基礎上統(tǒng)計出滿足ui>vi,i∈[1,n]的分量個數(shù)T(U,V),而不泄露關于集合U,V的任何額外信息.

基本原理如下:Alice和 Bob事先商議好元素的全集Q,使得對于所有i∈[1,n],ui,vi∈Q.設向量U中的元素ui位于全集Q中的第ki位,向量V中的元素vi位于全集Q中的第li位.Alice對私有向量U進行編碼,得到矩陣 (SU)n×m,其中元素uit定義如下:當t≤ki時uit=0;當t>ki時uit=1(記該編碼方法為編碼方法2).對于i∈[1,n],Bob在SU的第i行中挑選第li位元素uili并相加,即得到

考慮到在一些應用場景下,僅僅統(tǒng)計優(yōu)勢分量數(shù)目并不能達到要求,為了進一步拓寬原有協(xié)議的應用范圍,下文中將向量優(yōu)勢統(tǒng)計與閾值進行結合,解決向量優(yōu)勢閾值統(tǒng)計問題.

問題描述Alice有向量U=(u1,···,un),Bob有向量V=(v1,···,vn),并事先商議好閾值k,1≤k≤n和全集Q,使得對于所有i∈[1,n],ui,vi∈Q.Alice和Bob希望在不泄露各自向量信息的基礎上統(tǒng)計出ui>vi,i∈[1,n]的個數(shù)T(U,V)與k的大小關系,而不泄露關于集合U,V的任何額外信息.

我們以上述計算原理及 Paillier加密算法為基礎,進一步討論向量優(yōu)勢閾值問題.首先計算T(U,V)的密文,進一步結合k的密文,根據(jù)命題1,2來保密判定T(U,V)與k的大小即可.為描述方便,定義謂詞:l=Lk(U,V):如果T(U,V)≥k,定義l=1,否則,定義l=0.具體協(xié)議設計如下:

協(xié)議 4:向量優(yōu)勢閾值問題保密判定協(xié)議.

輸入:Alice輸入向量U=(u1,···,un),Bob輸入向量V=(v1,···,vn),對于所有i∈[1,n],ui,vi∈Q.

輸出:滿足ui>vi,i∈[1,n]的元素個數(shù)T(U,V)與k的大小關系l=Lk(U,V).

準備工作:(a)Alice運行Paillier加密方案,生成私鑰sk和公鑰pk.

(b)Alice按照編碼方法2,對向量U進行編碼,得到編碼矩陣SU=(uij)n×m,借助云生成多個0,1的密文(其中0,1的密文不少于SU中0,1個數(shù)).并用云生成的數(shù)據(jù)本身對所有密文進行重隨機化(參看協(xié)議1準備工作),借助隨機化后的云生成的密文構造加密矩陣

(1)Alice將公鑰pk=(g,N)以及E(SU)發(fā)送給Bob.

(2)對于每一個i∈[1,n],Bob根據(jù)vi在全集Q中的序位li,在矩陣E(SU)第i行挑選第li列元素E(uili).Bob選擇隨機數(shù)r滿足r<,計算,并將C發(fā)送給Alice.

(3)Alice解密C得到c,若c<,令l=1,否則令l=0.輸出l.

協(xié)議 4的正確性與安全性協(xié)議 4是在文獻[23]計算結果的基礎上進一步應用命題 1判定T(U,V)與k的大小關系,其正確性與安全性證明與協(xié)議3類似,此處省略.

由于文獻[23]給出的協(xié)議要求向量分量在某個全集內(nèi)取值,且隨著全集的增大,協(xié)議的效率也隨之降低.因此需要設計在沒有全集限制情況下的計算協(xié)議.下文以命題1,2與協(xié)議2為基礎設計無全集限制情況下的向量優(yōu)勢統(tǒng)計協(xié)議.

協(xié)議 5:向量優(yōu)勢統(tǒng)計協(xié)議.

輸入:Alice輸入私密向量U,Bob輸入私密向量V.

輸出:滿足ui>vi,i∈[1,n]的元素個數(shù)t=T(X,Y).

準備工作:Alice計算xi=2ui,Bob計算yi=2vi+1.Alice運行 Paillier加密方案,生成公鑰pk=(g,N)與私鑰,并公布公鑰(可取N足夠大,使得所有

(1)Alice 加密向量X=(x1,···,xn)(逐項加密), 得到E(X)=(E(x1),E(x2),···,E(xn)), 將E(X)發(fā)送給Bob.

(2)(a)Bob 加密向量?Y=(?y1,···,?yn)(逐項加密), 得到E(?Y)=(E(?y1),E(?y2),···,E(?yn));

(b)Bob選擇隨機數(shù)ri

(c)Bob將W中元素進行隨機置換,得到=(wk1,wk2,···,wkn),并將發(fā)送給Alice.

協(xié)議5的正確性與安全性與協(xié)議2類似,不再具體論證.

5 協(xié)議效率分析與實驗數(shù)據(jù)分析

5.1 效率分析

本文協(xié)議效率分析本文所用的協(xié)議都是在Paillier加密算法的基礎上進行的,在進行計算復雜度分析時,為了便于比較,我們忽略模乘運算,只考慮最耗時的模指數(shù)運算.Paillier加密方案中加密1次需要2次模指數(shù)運算,解密1次需要進行1次模指數(shù)運算.記參與運算的向量維數(shù)為n,本文協(xié)議效率分析如下.

協(xié)議1為全集已知時的計算方法.在協(xié)議1中,因加密數(shù)據(jù)都為0,1,我們借助云外包生成所需要的0,1密文,于是協(xié)議的計算復雜度僅僅為1次解密與1次加密的復雜度,即3次模指數(shù)運算.協(xié)議2為全集未知時的計算方法.在協(xié)議2中,Alice進行n次加密和n次解密運算,Bob進行n次加密和n次模指數(shù)運算.因此協(xié)議2相當于進行6n次模指數(shù)運算.

通信復雜度一般由交換信息的通信比特數(shù)或者通信輪數(shù)來衡量,在安全多方計算中通常用輪數(shù)來衡量,每個參與者發(fā)送一次消息稱為一輪.協(xié)議2進行了1輪通信.協(xié)議1在執(zhí)行過程中借助云生成多個密文供參與者使用,因此其通信復雜性為 2輪,Alice和 Bob之間進行了1輪通信,Alice和云之間也進行了1輪通信.

綜上可得,在只考慮模指數(shù)運算的情況下,協(xié)議1的計算復雜性很低,但協(xié)議1的使用前提是元素范圍已知,且在執(zhí)行過程中借助了云進行計算,通信代價較高.而當向量中數(shù)據(jù)的范圍較大時,用協(xié)議2進行計算就更為方便.

協(xié)議3給出了向量等分量數(shù)閾值問題計算方法.在協(xié)議3中,前兩步和協(xié)議1相同,都為對0,1的加密,考慮外包時忽略其計算復雜度,在協(xié)議的后兩步,共進行了2次加密,2次模指數(shù)和1次解密運算,因此協(xié)議3相當于進行7次模指數(shù)運算.其通信復雜度也等同于協(xié)議1,共進行了2輪通信.

協(xié)議4解決的是向量優(yōu)勢閾值問題保密判定,是基于閾值的向量對應分量相等個數(shù)判定問題的推廣,與協(xié)議3相比僅改變了原始數(shù)據(jù)的編碼方法,其計算復雜性和通訊復雜性都等同于協(xié)議3.協(xié)議5將協(xié)議2進行擴展,計算無全集限制下的向量優(yōu)勢統(tǒng)計問題,其計算復雜性與通訊復雜性等同于協(xié)議2.故在此不作考慮.

與已有相關結果進行分析比較文獻 [24]中的 HDOT協(xié)議能夠解決字符串海明距離保密計算問題(執(zhí)行 HDOT協(xié)議的前兩步),如果將字符串中的各個字符看成向量的不同分量,則可應用文獻 [24]的HDOT協(xié)議解決本文的向量等分量數(shù)計算問題.下面主要對應用文獻[24]的HDOT協(xié)議解決向量等分量數(shù)問題時的計算效率進行分析,并與本文協(xié)議1,2的計算效率進行比較.

在應用文獻 [24]的 HDOT協(xié)議計算兩字符串的海明距離時 (僅需要執(zhí)行 HDOT的前兩步),如果將輸入的字符串中的每個字符數(shù)據(jù)所對應的二進制數(shù)據(jù)長度設為l,當輸入字符串所包含的字符個數(shù)為n時,協(xié)議需要調(diào)用n次binHDOT協(xié)議,每次調(diào)用 binHDOT的目的是判定兩個l長的比特字符串是否相等.根據(jù)文獻[24]中binHDOT協(xié)議,執(zhí)行一次l長的比特字符串相等判定(若兩字符串相等,輸出0,否則輸出1)需要進行l(wèi)次加密與1次解密運算,2l次模指數(shù)運算以及l(fā)ogl次不經(jīng)意傳輸.即是說,如果應用文獻[24]的HDOT協(xié)議(HDOT協(xié)議的前兩步)保密計算兩個n維向量的等分量數(shù)問題,需要進行n(4l+1)次模指數(shù)運算與nlogl次不經(jīng)意傳輸.協(xié)議的通信復雜性為O(nl)(這里l為向量分量數(shù)據(jù)在二進制表示下的數(shù)據(jù)長度).

表1給出了在解決兩個n維向量的等分量數(shù)保密計算問題時,應用本文協(xié)議 1,2與應用文獻[24]中的HDOT協(xié)議(HDOT的前兩步)的計算效率比較結果.

表1 協(xié)議效率分析Table 1 Analysis on efficiency

5.2 實驗數(shù)據(jù)分析

為進一步分析本文協(xié)議的執(zhí)行效率,我們設計模擬實驗來計算執(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).本文所做模擬實驗均在此環(huán)境下進行.

實驗方法:通過模擬實驗來測試本文協(xié)議所用時間,并通過協(xié)議執(zhí)行時間來驗證方案效率.假定本文協(xié)議1全集元素個數(shù)m=20.在向量維數(shù)n分別為6,7,8,···,20時,對n的每個設定值進行100次模擬實驗,并統(tǒng)計協(xié)議1,2執(zhí)行時間的平均值與文獻[24]中HDOT協(xié)議前兩步(僅考慮Paillier加密與解密所耗費的時間)的執(zhí)行時間的平均值.

由于協(xié)議1借助云來完成加密過程,協(xié)議復雜性較低,且隨著向量維數(shù)增加,協(xié)議運行時間基本不變.經(jīng)實驗,協(xié)議1平均一次運行時間為15 ms.協(xié)議2與文獻[24]中HDOT協(xié)議前兩步(在l=5時)的運行時間隨n的變化如圖1所示,在向量維數(shù)相同時,本文協(xié)議2的執(zhí)行時間遠小于文獻[24]的執(zhí)行時間.

6 向量分量相等個數(shù)的應用

6.1 點與區(qū)間關系保密計算問題

問題描述Alice 有區(qū)間列 [a1,b1],···,[an,bn],Bob 有數(shù)列v1,···,vn,其中ai,bi,vi,(i=1,2,···,n)為正整數(shù).Alice和 Bob希望在不泄露各自信息的條件下保密計算滿足vi∈[ai,bi](i=1,2,···,n)的區(qū)間個數(shù).

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

對上述問題設計安全高效的計算協(xié)議在實際中有廣泛應用.例如:(a)實際中如果需要保密判定一個整數(shù)點P(x,y,z)是否含于一個立方體V=[x1,x2]×[y1,y2]×[z1,z2]內(nèi).這個問題即可轉(zhuǎn)化為判定三個坐標值是否都分別屬于三個對應區(qū)間的問題.(b)某公司A希望考察一個公司B,看看能否成為合作伙伴,在確定是否可以合作之前,A需要通過一些指標對B進行考核評估,如考核其公司資產(chǎn),項目數(shù)量,生產(chǎn)能力等是否在要求范圍內(nèi).由于B的這些指標量屬于企業(yè)的機密信息,A的指標范圍也屬于商業(yè)機密,為了在保證各企業(yè)商業(yè)機密的前提下確定能否合作,就需要設計數(shù)與區(qū)間保密判定協(xié)議.(c)又如醫(yī)學上根據(jù)各項指標進行的疾病初步檢測,學校根據(jù)各科成績判定優(yōu)等生等問題,都可以抽象為多個點與區(qū)間的關系判定問題.

下面以向量等分量數(shù)計算協(xié)議為基礎,設計多個點與區(qū)間的關系判定問題的解決方案.

基本原理記mi=bi?ai,取一整數(shù)m>max{m1,m2,···,mn}.

(i)對于每一個區(qū)間 [ai,bi],將 [ai,bi]轉(zhuǎn)化為向量Ai=(ai,ai+1,ai+2,···,ai+m).

(ii)將Ai中大于bi的元素全替換為零,如此得到的向量記為Bi.將B1,···,Bn首尾相連得到一個n(m+1) 維向量B=(B1,B2,···,Bn)

(iii)記I是分量全為 1的m+1維向量,即I=(1,1,···,1).令Vi=viI,并將V1,···,Vn首尾相連得到一個n(m+1)維向量V=(V1,V2,···,Vn).

由向量B和V的構造過程容易證明:滿足vi∈[ai,bi](i=1,2,···,n)的區(qū)間個數(shù)即為兩向量B和V對應分量相等的分量數(shù)目.因此,Alice根據(jù)其私有區(qū)間序列構造相應的私密向量B,Bob根據(jù)其私有數(shù)列構造私密向量V.Alice和Bob再分別以向量B和V為輸入調(diào)用協(xié)議1,2即可.

注解 1對于i∈[1,n],以集合Xi={xi1,···,ximi}代替上面問題中的區(qū)間 [ai,bi](假設xi1,···,ximi單調(diào)遞增). 同樣選取m>max{m1,m2,···,mn},進一步定義Yi為m+1維向量:Yi=(xi1,···,ximi,0,···,0).再令Y=(Y1,···,Yn).完全類似地,通過計算向量Y與向量V等分量數(shù),可計算有多少個集合滿足vi∈Xi.

注解 2對于上述點與區(qū)間 (或集合)關系問題,也可以類似考慮其相應的閾值問題,而轉(zhuǎn)化為可以應用協(xié)議3解決的計算問題.

6.2 字符串匹配字符個數(shù)保密計算

字符串模式匹配[26]作為字符串的一項基本操作,在實際生活中有著重要作用.如果把某個地區(qū)信譽過低的人的名單整體看成一個字符串,某個居民的名字當作另一個字符串,判定此人信譽是否過低問題就轉(zhuǎn)化為判定兩個字符串是否模式匹配問題.顯然,信譽過低的人的名單在一些情況下不能直接公開,查詢者在查詢自己信譽是否過低時也不愿意泄露自己的名字.因此需要保密判定兩個字符串是否模式匹配.

問題描述Alice有目標字符串A=a1a2···,an,Bob有模式字符串B=b1b2···,bm(m≤n,m,n為公開值).在不泄露其他任何信息的情況下判斷A中是否存在一個子串與B相等,即判定在字符串A=a1a2···an中是否存在子串SA=aiai+1···ai+m?1=B.

基本原理將英文字母與數(shù)字做如下對應:

a→01,b→02,···,z→26

記ai,bi對應的數(shù)字分別為xi,yi,從而將字符串A,B轉(zhuǎn)化為數(shù)字串Sx=x1x2···xn,Sy=y1y2···ym.Alice 根據(jù)m將Sx分割為n?m+1 維向量X=(x1···xm,x2···xm+1,···,xn?m+1···xn),Bob 根據(jù)n將Sy轉(zhuǎn)變?yōu)閚?m+1 維向量Y=(y1···ym,y1···ym,···,y1···ym). 設置閾值k=1,通過協(xié)議3保密判定向量X,Y等分量數(shù)與閾值的大小關系即可得到結果:如果等分量數(shù)小于閾值,則說明A,B不能模式匹配,否則說明A,B能模式匹配.

7 結論

本文利用Paillier加密算法和對數(shù)據(jù)的編碼,根據(jù)全集是否已知設計了簡單的計算兩向量等分量數(shù)的協(xié)議,并證明了協(xié)議的正確性和安全性,分析了協(xié)議的效率.此外,我們將所設計的基礎協(xié)議進行延伸,解決了在考慮閾值的情況下的向量等分量數(shù)和向量優(yōu)勢統(tǒng)計問題,并設計了無全集限制的向量優(yōu)勢統(tǒng)計協(xié)議.同時,利用這些基礎協(xié)議解決了多個點與區(qū)間(集合)的關系判定問題和字符串匹配率計算問題.在后面的工作中,我們將探討惡意模型下的向量等分量數(shù)計算問題.