向量等分量數(shù)的兩方保密計(jì)算及推廣應(yīng)用*

王穎囡,竇家維,葛 雪

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

1 引言

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

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

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

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

本文主要貢獻(xiàn)如下:

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

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

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

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

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

2.1 安全性定義

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

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

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

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

如果存在概率多項(xiàng)式時(shí)間算法S1,S2,使得下面兩式成立

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

2.2 Paillier加密方案

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

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

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

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

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

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

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

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

問題描述:對于兩個(gè)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).

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

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

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

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

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

選擇方法對于每一個(gè)i∈[1,n],Bob在WU的第i行中選擇第li列元素uili,Bob再將所選擇的元素相加,得到?=u1l1+···+unln,?即為兩向量對應(yīng)分量相等的數(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進(jìn)行編碼得到矩陣

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

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

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

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

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

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

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

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

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

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

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

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

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

證明:下面將應(yīng)用多方保密計(jì)算中普遍接受的模擬范例方法嚴(yán)格證明定理1.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

(a)當(dāng)u=v時(shí),得到w=D(C)=(u?v)modN=0.

(b)當(dāng)u>v時(shí),此時(shí)由于0

(c)當(dāng)uN/2.

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

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

證明:若a≥b,則 2a≥2b,因此 2a+1>2b.反之,若 2a+1>2b,則必有 2a≥2b成立,即a≥b成立.綜上,a≥b當(dāng)且僅當(dāng)2a+1>2b.同理可得a>b當(dāng)且僅當(dāng)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的大小關(guān)系h=Hk(U,V).

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

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

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

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

協(xié)議 3的正確性:協(xié)議3的準(zhǔn)備工作和第(1)步與協(xié)議1完全相同.在協(xié)議3第(2)步,Bob首先計(jì)算得到?的密文:此后計(jì)算因此在第 (3)步中,解密結(jié)果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選擇的隨機(jī)數(shù),并且E(?2k)是Bob加密的密文,根據(jù)Paillier加密算法的語義安全性,對Alice來說從密文C中得不到Bob數(shù)據(jù)的任何信息.雖然Alice有解密密鑰,解密后Alice僅獲得h的值,該值是協(xié)議規(guī)定的輸出數(shù)據(jù),因此Bob數(shù)據(jù)是安全的.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.1 效率分析

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

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

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

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

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

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

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

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

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

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

5.2 實(shí)驗(yàn)數(shù)據(jù)分析

為進(jìn)一步分析本文協(xié)議的執(zhí)行效率,我們設(shè)計(jì)模擬實(shí)驗(yàn)來計(jì)算執(zhí)行協(xié)議所需時(shí)間.

實(shí)驗(yàn)測試環(huán)境:Windows 10 64位 (家庭版)操作系統(tǒng),處理器 Intel(R)Core(TM)i5-6600 CPU@3.30 GHz,內(nèi)存 8.00 GB,用 java語言在 MyEclipse上運(yùn)行實(shí)現(xiàn).本文所做模擬實(shí)驗(yàn)均在此環(huán)境下進(jìn)行.

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

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

6 向量分量相等個(gè)數(shù)的應(yīng)用

6.1 點(diǎn)與區(qū)間關(guān)系保密計(jì)算問題

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

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

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

下面以向量等分量數(shù)計(jì)算協(xié)議為基礎(chǔ),設(shè)計(jì)多個(gè)點(diǎn)與區(qū)間的關(guān)系判定問題的解決方案.

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

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

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

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

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

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

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

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

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

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

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

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

記ai,bi對應(yīng)的數(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). 設(shè)置閾值k=1,通過協(xié)議3保密判定向量X,Y等分量數(shù)與閾值的大小關(guān)系即可得到結(jié)果:如果等分量數(shù)小于閾值,則說明A,B不能模式匹配,否則說明A,B能模式匹配.

7 結(jié)論

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