方樂笛,李順東,竇家維

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

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

1 引言

隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)和大數(shù)據(jù)技術(shù)的迅速發(fā)展與日益普及,隱私信息與機(jī)密信息極易泄露,這使得隱私保護(hù)變得尤為重要.安全多方計算(secure multiparty computation,SMC)作為隱私保護(hù)的核心技術(shù),成為了國際密碼學(xué)界的研究熱點[1].安全多方計算最初于1982年由Yao[2]以百萬富翁問題提出,它由兩個參與者組成,之后Ben-or和Goldwasser[3]將其擴(kuò)展到了多個參與者,學(xué)術(shù)界統(tǒng)稱為安全多方計算.安全多方計算的奇妙之處就在于可以使參與者在不泄露自己隱私數(shù)據(jù)的情況下,保密地使參與者利用自己的隱私數(shù)據(jù)聯(lián)合進(jìn)行某種運算,從而達(dá)到合作共贏的目的,也最大限度的平衡了參與者隱私性與合作性的需求.

安全多方計算的研究在計算科學(xué)領(lǐng)域、密碼學(xué)與信息安全中有著舉足輕重的作用,是信息社會隱私保護(hù)的核心技術(shù),其主要可分為以下幾類:(1)保密的科學(xué)計算問題[4–13];(2)保密的計算幾何問題[14–18];(3)保密的統(tǒng)計分析問題;(4)保密的數(shù)據(jù)挖掘問題[19];(5)保密的數(shù)據(jù)庫查詢問題;(6)其他安全多方計算問題.雖然人們已經(jīng)研究了很多安全多方計算問題,并提出了這些問題的解決方案,但這些方案的效率都亟待提高,此外還有很多新的問題需要研究,曼哈頓距離問題就是需要研究的新問題。

曼哈頓距離(Manhattan distance,MD)又稱出租車距離,是指兩個垂直方向上的距離之和.P(x1,y1)和Q(x2,y2)之間的曼哈頓距離MD=|x1?x2| +|y1?y2|.保密計算兩點間曼哈頓距離的問題是安全多方計算中一個很有趣的問題,它在保密科學(xué)計算、保密信息過濾,計算機(jī)圖形學(xué)的保密計算、保密生物信息學(xué)計算等方面有重要的應(yīng)用.

要保密計算曼哈頓距離MD,首先要保密計算|x1?x2|,即保密計算兩個數(shù)之差的絕對值.也可看做直線上的曼哈頓距離.然后再保密計算|x1?x2|+|y1?y2|.但根據(jù)安全多方計算的安全性要求,這個計算過程不能泄露|x1?x2|和|y1?y2| 的值,即不能分別保密計算|x1?x2|和|y1?y2| 的值后再相加,因為這將泄露|x1?x2|和|y1?y2| 的值.因此曼哈頓距離的保密計算不是絕對值保密計算的簡單推廣.

由于|x1?x2| 的安全多方計算和|x1?x2|+|y1?y2| 的安全多方計算都沒有見到報道,因此曼哈頓距離的安全多方計算是一個全新的問題,而且曼哈頓距離的保密計算不是絕對值保密計算的平凡推廣,實際上是兩個獨立的問題.保密計算兩點間曼哈頓距離的關(guān)鍵是雙方如何在經(jīng)過運算后直接得到兩點間的曼哈頓距離,而不是分別計算橫縱坐標(biāo)差的絕對值之和.本文便巧妙地解決了這一關(guān)鍵問題.我們首先設(shè)計了一種編碼方法,用這種編碼和Goldwasser-Micali 公鑰加密算法將原問題化為了保密計算兩個比特串的海明距離.我們的編碼方法也可以直接解決絕對值的保密計算問題,兩個比特串的海明距離問題,以及其他安全多方計算問題.

我們證明了這些協(xié)議在半誠實模型下是安全的,但是一個惡意的參與者可能會在關(guān)鍵的環(huán)節(jié)進(jìn)行欺騙.為了防止這種欺騙的發(fā)生,我們又設(shè)計了另一種編碼方法,這種編碼方法與Paillier 加密算法相結(jié)合可以保密計算兩點間曼哈頓距離問題,而且可以防止惡意參與者在關(guān)鍵環(huán)節(jié)進(jìn)行欺騙.當(dāng)然,這種編碼方法也可直接解決絕對值的保密計算問題.最后,我們對設(shè)計的協(xié)議進(jìn)行了理論分析與實驗仿真.通過理論分析和仿真表明,我們所設(shè)計的協(xié)議是高效的.

1.1 本文貢獻(xiàn)

(1)本文首次研究了關(guān)于保密計算兩點間曼哈頓距離的問題.這是一個全新的安全多方計算問題,它在保密科學(xué)計算、保密信息過濾、生物信息學(xué)保密計算等方面具有重要的理論意義與應(yīng)用價值.為了高效地解決此問題,設(shè)計了兩種新的編碼方法,將原本復(fù)雜而抽象的問題化為了簡單具體的問題.通過不同的編碼方法,參與者將自己的數(shù)據(jù)編碼成了一個向量,并且經(jīng)過運算后可直接得到兩點間的曼哈頓距離,避免了分別計算橫縱坐標(biāo)差的絕對值之和導(dǎo)致的信息泄露.

(2)結(jié)合Goldwasser-Micali 加密算法,將保密計算兩點間曼哈頓距離的問題化為保密計算兩向量海明距離的問題,設(shè)計出了協(xié)議1.我們的編碼方法也可以直接解決絕對值的保密計算問題,兩個比特串的海明距離問題,以及其他安全多方計算問題.

(3)我們又設(shè)計了另一種編碼方法,這種編碼方法與Paillier 加密算法相結(jié)合可以保密計算兩點間曼哈頓距離問題,設(shè)計出了協(xié)議2,而且結(jié)合數(shù)字承諾的思想可以防止惡意參與者在關(guān)鍵環(huán)節(jié)進(jìn)行欺騙.當(dāng)然,這種編碼方法也可直接解決絕對值的保密計算問題.

(4)將保密計算兩點間曼哈頓距離的問題應(yīng)用到了實際生活中,給出了保密計算兩點間曼哈頓距離的問題的應(yīng)用與擴(kuò)展.由于使用編碼方法,使得協(xié)議具有很高的效率,并通過理論分析與實驗數(shù)據(jù)證明了協(xié)議的高效性.

1.2 本文結(jié)構(gòu)

本文第2 節(jié)介紹預(yù)備知識; 第3–4 節(jié)分別設(shè)計了一個關(guān)于保密計算兩點間曼哈頓距離的協(xié)議,并用模擬范例證明了協(xié)議是安全的; 第5 節(jié)給出了曼哈頓距離的應(yīng)用及擴(kuò)展; 第6 節(jié)理論分析了協(xié)議的效率,并進(jìn)行了實驗仿真.第7 節(jié)為本文總結(jié)與展望.

2 預(yù)備知識

2.1 安全性定義

半誠實模型:所謂半誠實參與者是指參與者在協(xié)議執(zhí)行過程中將不折不扣地執(zhí)行協(xié)議,但他們會保留計算的中間結(jié)果,在協(xié)議結(jié)束后試圖推導(dǎo)出其他參與者的輸入.如果所有參與者都是半誠實參與者,這樣的模型稱為半誠實模型[20].

本文所設(shè)計的協(xié)議是在半誠實模型下安全的計算協(xié)議.

一些記號:假設(shè)參與保密計算的雙方分別為Alice和Bob,且Alice 擁有數(shù)據(jù)x,Bob 擁有數(shù)據(jù)y,他們希望在保證x,y隱私性的前提下,合作計算概率多項式時間函數(shù)f(x,y)=(f1(x,y),f2(x,y)).記π為計算f的協(xié)議,表示Alice 在執(zhí)行協(xié)議的過程中所得到的信息序列.其中r1表示Alice 所選隨機(jī)數(shù);表示Alice 收到的第i個信息.執(zhí)行協(xié)議π后,Alice 得到的輸出結(jié)果為f1(x,y).Bob 得到的信息序列可以類似定義[20].

定義1假設(shè)f(x,y)=(f1(x,y),f2(x,y))是一個兩方計算函數(shù),x(y)表示第一(二)方輸入的變量,f1(x,y)(f2(x,y))表示兩方各自獲得的函數(shù)值,π是計算f的一個兩方計算協(xié)議.如果存在概率多項式時間算法S1,S2使得:

則稱協(xié)議π保密地計算了函數(shù)f.其中表示計算不可區(qū)分.

2.2 Goldwasser-Micali 公鑰加密系統(tǒng)

Goldwasser-Micali 加密方案具體描述如下[21]:

密鑰生成:隨機(jī)選取大素數(shù)p,q,計算N=pq,并選取一個正整數(shù)則公鑰為(N,y),私鑰為(p,q).將加密算法記為E,解密算法記為D.

加密:對明文m∈{0,1},選擇隨機(jī)數(shù)r:1≤r≤N?1,計算得密文c=E(m)

解密:對密文c,按下面方式計算得明文m=D(c)

異或同態(tài)性:由于下面性質(zhì)成立

因此,Goldwasser-Micali 加密方案具有異或同態(tài)性.

2.3 Paillier 同態(tài)加密算法

Paillier 加密方案具體描述如下[22].

密鑰生成選取兩個大素數(shù)p,q,計算N=pq,λ=lcm(p?1,q?1).定義函數(shù)隨機(jī)選擇一個生成元使得gcd(L(gλmodN2),N)=1.則加密方案的公鑰為(g,N),私鑰為λ.

加密過程對于明文m

解密過程對密文c,計算得明文m=D(c)

加法同態(tài)性:由于下面性質(zhì)成立

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

2.4 單向散列函數(shù)

單向散列函數(shù)定義[23]:對于函數(shù)f,如果存在多項式時間算法A使得A(x)=f(x)但不存在多項式時間算法B使得B(y)=x′∧f(x′)=y,那么我們稱f是一個單向函數(shù).

如果一個單向函數(shù)f對于任意的|x1|=|x2|,都有|f(x1)|=|f(x2)|,我們就稱它為單向散列函數(shù).

單向散列函數(shù)具有下面的性質(zhì)[20]:(1)給定消息M,很容易計算h=hash(M);(2)給定h=hash(M),根據(jù)h計算其逆M=hash?1(h)很難;(3)給定M,要找到另一個消息M′,使得hash(M)=hash(M′)很難;(4)找出兩個隨機(jī)的消息M和M′,使得hash(M)=hash(M′)很難;(5)如果對x作微小改變,即使只改變一個比特,hash(x)的值也會發(fā)生驚人改變.

2.5 數(shù)字承諾

數(shù)字承諾[23],簡單地說,可以理解為一個有兩方參與的兩階段協(xié)議,這兩方分別為承諾者與接收者.第一個階段稱為承諾階段(commitment phase),第二個階段稱為承諾揭示階段(reveal phase 或open phase).通過這個協(xié)議承諾者能夠?qū)崿F(xiàn)自己與一個數(shù)字的綁定.這種綁定要滿足保密性(secrecy)與確定性(binding).所謂保密性是指承諾者作出承諾后,接收者無法獲得有關(guān)承諾者所承諾數(shù)字的任何知識; 所謂確定性是指,接收者只接受承諾者所發(fā)送的合法數(shù)字,若承諾者進(jìn)行欺騙,接收者可以發(fā)現(xiàn)并拒絕接收.

當(dāng)然,協(xié)議也應(yīng)該是可靠的(viable),即如果雙方都遵守協(xié)議,那么在協(xié)議的第二階段接收者應(yīng)該能夠獲得一個承諾者所承諾的唯一的數(shù)字.要求一個承諾方案必須保證承諾者在承諾階段不會向接收者泄露有關(guān)承諾值的任何信息,而且也使承諾者在承諾之后無法再改變自己的承諾值.而且還要保證這樣的協(xié)議應(yīng)該是可行的,即協(xié)議應(yīng)該能夠在概率多項式時間內(nèi)完成.而在揭示階段,承諾者可能需要向接收者提供很復(fù)雜的信息,也可能僅僅提供他自己的承諾的數(shù)值與在承諾階段所選擇的隨機(jī)數(shù)值供接收者驗證.只有利用相應(yīng)的承諾值與相應(yīng)的隨機(jī)數(shù)能夠?qū)С鲈诔兄Z階段接收者所收到的全部信息時.接收者才接受相應(yīng)的承諾值.

3 半誠實模型下曼哈頓距離協(xié)議

本節(jié)首先設(shè)計一種新的編碼方法,以此為基礎(chǔ),結(jié)合應(yīng)用Goldwasser-Micali 加密方案,設(shè)計構(gòu)造兩點間曼哈頓距離的保密計算協(xié)議.

問題描述:假設(shè)Alice和Bob 在平面上分別擁有私密點P(x1,y1)和Q(x2,y2),他們想保密計算兩點間的曼哈頓距離,即保密計算函數(shù)f(P,Q)=|x1?x2| +|y1?y2|.在下文中,我們也將點P(x1,y1),Q(x2,y2)看作兩個二維向量.

編碼方法1:為了保密計算曼哈頓距離,首先設(shè)計編碼方法如下:

給定全集U={u1,··· ,un},其中ui,i∈[1,n]={1,2,··· ,n} 為n個連續(xù)的整數(shù),滿足u1

以x1為例.根據(jù)x1和全集U構(gòu)造一個n維數(shù)組A1=(a11,··· ,a1n),構(gòu)造方法如下:假設(shè)x1=uk,則令a11=,··· ,=a1k=1,a1(k+1)=,··· ,=a1n=0.即數(shù)組的前k維元素為1,后n?k維元素0.對于y1以完全相同的方式構(gòu)造其對應(yīng)的數(shù)組,記為A2=(a21,··· ,a2n),那么定義P(x1,y1)在全集U之下對應(yīng)的編碼數(shù)組為

例1假設(shè)全集為U={?3,?2,··· ,4,5},對于點P(5,3),根據(jù)編碼方法1,將橫坐標(biāo)5 編碼為A1=(1,1,1,1,1,1,1,1,1).將縱坐標(biāo)3 編碼為A2=(1,1,1,1,1,1,1,0,0),進(jìn)而可得

類似地,對于點Q(?3,?2),根據(jù)編碼方法1 可得

計算原理1:在下面計算中,假設(shè)全集為U={u1,··· ,un},Alice和Bob 分別擁有點P(x1,y1)和Q(x2,y2),滿足x1,y1,x2,y2∈U,在全集U之下,點P(或Q)按照編碼方式1 對應(yīng)的向量記為

關(guān)于兩點P和Q之間的曼哈頓距離,有下面的結(jié)論.

命題1點P和Q間的曼哈頓距離可由下式計算:

證明:(i)我們首先證明

首先設(shè)x1≥x2,并記x1在全集U中的位置為k1,x2在全集U中的位置為s1,這時顯然有

按照編碼方式1 編碼后,x1對應(yīng)的向量為

x2編碼為

對A1和B1的對應(yīng)分量進(jìn)行異或,得到

顯然,將C1的各分量相加,得到

當(dāng)x2>x1時,完全類似得到

3.1 具體協(xié)議

以上面計算原理為基礎(chǔ),結(jié)合Goldwasser-Micali 加密算法,我們設(shè)計構(gòu)造兩點間曼哈頓距離的保密計算協(xié)議.

協(xié)議1半誠實模型下安全計算兩點間的曼哈頓距離

輸入Alice 輸入私密點P(x1,y1),Bob 輸入私密點Q(x2,y2).

輸出f1(P,Q)=f2(P,Q)=|x1?x2|+|y1?y2|.

準(zhǔn)備工作Alice 根據(jù)編碼方法1 構(gòu)造P對應(yīng)的向量A=(a11,··· ,a1n,a21,··· ,a2n); Bob 根據(jù)編碼方法1 得到Q對應(yīng)的向量B=(b11,··· ,b1n,b21,··· ,b2n).Alice 運行Goldwasser-Micali 加密方案,生成公鑰/私鑰對pk/sk,將公鑰pk 發(fā)送給Bob.

(1)Alice 用公鑰加密向量A(分別對每個分量加密),得到E(A)

并將E(A)發(fā)送給Bob.

(2)Bob 加密向量B的每個分量,并計算

再將R的n個分量進(jìn)行隨機(jī)置換,得到新的向量,記為,并將發(fā)送給Alice.

計算y=d11+···+d2n,并將y發(fā)給Bob.

(4)Alice和Bob 輸出y.

3.2 方案分析

正確性分析由協(xié)議的第(2)步,結(jié)合加密算法的異或同態(tài)性可知

根據(jù)前面的計算原理,即證得y=|x1?x2|+|y1?y2|.即協(xié)議1是正確性的.

安全性分析關(guān)于協(xié)議的安全性,我們有下面的結(jié)論.

定理1協(xié)議1能夠保密地計算兩點間的曼哈頓距離.

證明:通過構(gòu)造使式(1)和(2)成立的模擬器S1和S2證明本定理.

S1的模擬過程如下.

(1)接受輸入(P,f1(P,Q))后,S1隨機(jī)選擇使得f1(P,Q′)=f1(P,Q).并按照編碼方法1 對(P,Q′)進(jìn)行編碼,得到相應(yīng)的向量

(2)S1加密向量B′得到E(B′),并計算

再將R′的分量進(jìn)行隨機(jī)置換,得到.

(3)S1解密′,得到

(4)S1計算

類似地,S2的模擬過程如下.

(1)接受輸入(Q,f2(P,Q))后,S2隨機(jī)選擇使得f2(P′,Q)=f2(P′,Q).并按照編碼方法1 對(P′,Q)進(jìn)行編碼,得到相應(yīng)的向量

(2)S2加密向量A′得到E(A′),并計算

再將R′的分量進(jìn)行隨機(jī)置換,得到

(3)S2解密得到

(4)S2計算

由于E(A)是由Alice 加密得到的,Bob 沒有私鑰,根據(jù)加密算法的語義安全性,對于Bob 來說,E(A′),進(jìn)一步由于f2(P,Q)=f1(P′,Q),故有

因此,協(xié)議1能夠保密計算兩點間的曼哈頓距離.

4 增強(qiáng)的曼哈頓距離協(xié)議

眾所周知,雙方在半誠實模型下聯(lián)合計算的結(jié)果都會由擁有私鑰的一方(假設(shè)為Alice)進(jìn)行解密,之后再將解密結(jié)果發(fā)給另一方(假設(shè)為Bob).即Bob 所得最后結(jié)果完全是由Alice 單方面發(fā)來的.而之前雙方進(jìn)行聯(lián)合計算的目的也是為了得到這個最后結(jié)果.

我們設(shè)想,如果在協(xié)議1中,當(dāng)Alice 得到了兩點間的曼哈頓距離y以后,她可能因為自己的私利發(fā)送給Bob 一個不同于y的值,Bob 卻無法判斷得到的結(jié)果是否正確,這對Bob 顯然是不公平的.為了解決這個問題,我們將設(shè)計一個新的編碼方法,使一方參與者改用新的編碼方法編碼,如此可將計算兩點曼哈頓距離的問題轉(zhuǎn)化為兩個向量內(nèi)積問題,以此為基礎(chǔ),并結(jié)合Paillier 加密方案和數(shù)字承諾思想設(shè)計構(gòu)造防欺騙場景下的安全計算協(xié)議,保證兩個參與者獲得相同的計算結(jié)果(若有一方試圖欺騙,另一方即可發(fā)現(xiàn)).所謂的數(shù)字承諾,簡單地說,可以理解為一個有兩方參與的兩階段協(xié)議,這兩方分別為承諾者與接收者.通過這個協(xié)議承諾者能夠?qū)崿F(xiàn)自己與一個數(shù)字的綁定.這種綁定要滿足保密性與確定性.所謂保密性是指承諾者作出承諾后,接收者無法獲得有關(guān)承諾者所承諾數(shù)字的任何知識; 所謂確定性是指,接收者只接受承諾者所發(fā)送的合法數(shù)字,若承諾者有所欺騙,接收者可以發(fā)現(xiàn)并拒絕接收.

編碼方法2:與編碼方法1 類似,我們在全集U={u1,··· ,un} 之下構(gòu)造編碼方法,其中ui∈[1,n]具有與編碼方法1 中完全相同的性質(zhì).對于任一點P(x1,y1)∈U2,在全集U之下計新的編碼方法如下.

以x1為例.根據(jù)x1和全集U構(gòu)造n維數(shù)組V1=(v11,··· ,v1n),構(gòu)造方法如下:

假設(shè)x1=uk,則令v11=,··· ,=v1k=0,v1(k+1)=,··· ,=v1n=1.

即該數(shù)組的前k維元素為0,后n?k維元素為1.對于y1以完全相同的方式構(gòu)造其對應(yīng)的數(shù)組,記為V2=(u21,··· ,u2n),進(jìn)一步構(gòu)造向量

并稱V(P)為在全集U之下應(yīng)用編碼方法2 獲得的P(x1,y1)的對應(yīng)編碼向量.

例2假設(shè)全集為U={?3,?2,··· ,4,5},對于點P(?3,?2),應(yīng)用編碼方式2,將x1=?3 編碼為V1=(0,1,1,1,1,1,1,1,1),將y1=?2 編碼為V2=(0,0,1,1,1,1,1,1,1),并得到P(?3,?2)應(yīng)用編碼方法2 對應(yīng)的向量V(P)=(0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1).

計算原理 2:在下面計算中,總假設(shè)全集為U={u1,··· ,un},Alice和 Bob 分別擁有點P(x1,y1),Q(x2,y2),滿足x1,y1,x2,y2∈U,在全集U之下,對點P(或Q)先按照編碼方式1(或編碼方式2)進(jìn)行編碼,再按照編碼方式2(或編碼方式1)進(jìn)行編碼,對應(yīng)的向量記為

關(guān)于兩點P和Q間的曼哈頓距離,下面結(jié)論成立.

命題2點P和Q的曼哈頓距離等于向量A和V的內(nèi)積.即有下式成立

證明:(i)我們首先證明

首先假設(shè)x1≥x2,x1先按照編碼方式1 編碼,x2按照編碼方式2 編碼,記x1在全集U中的位置為在全集U中的位置為這時顯然有

按照編碼方式1 編碼后,x1對應(yīng)的向量為

按照編碼方式2 編碼后,x2編碼為

x1再按照編碼方式2 編碼,x2按照編碼方式1 編碼,并記x1在全集U中的位置為在全集U中的位置為這時顯然有

按照編碼方式2 編碼后,x1對應(yīng)的向量為

按照編碼方式2 編碼后,x2編碼為

當(dāng)x2>x1時,完全類似得到

4.1 具體協(xié)議

根據(jù)上面所述的計算原理,并結(jié)合應(yīng)用Paillier 加密方案和數(shù)字承諾思想可設(shè)計構(gòu)造防欺騙場景下計算兩點間曼哈頓距離的安全計算協(xié)議2.具體協(xié)議如下.

協(xié)議2防欺騙場景下安全計算兩點間的曼哈頓距離

輸入Alice 輸入私密點P(x1,y1),Bob 輸入私密點Q(x2,y2).

輸出f1(P,Q)=f2(P,Q)=|x1?x2|+|y1?y2|.

準(zhǔn)備工作Alice和Bob 根據(jù)上例分別按照編碼方法1 以及編碼方法2 對點P和Q進(jìn)行編碼,得到4n維向量A(P)=(a1,··· ,a4n)以及V(Q)=(v1,··· ,v4n),雙方再商定一個哈希函數(shù).在下面,將Paillier 加密及解密算法分別記為加密及解密算法分別記為以及

(1)Alice 加密向量A(P)(逐分量加密),得到

(2)Bob 選擇隨機(jī)數(shù)s,計算v=hash(s),利用Paillier 加密算法加密得到(s),進(jìn)一步計算

Bob 將v以及T發(fā)送給Alice.

(3)Alice 解密T得到并將發(fā)送給Bob.

(4)Bob 計算d=?s,并將d發(fā)給Alice.

4.2 方案分析

正確性分析由Paillier 加密算法的加法同態(tài)性,協(xié)議第(3)步Alice 解密可得到再由Bob 在第(4)步中計算可知,由命題2,正確性得證.

安全性分析完全類似于協(xié)議1的證明方法可知協(xié)議2 在半誠實模型下是安全的.在協(xié)議2中Alice 不再是最早得到計算結(jié)果的一方,從而避免了Alice 篡改結(jié)果的欺騙行為.計算結(jié)果是由Bob 在協(xié)議第(4)步率先得到,但為了防止Bob 的欺騙行為,在協(xié)議的第(2)步已經(jīng)將隨機(jī)數(shù)s的Hash 值v發(fā)給了Alice,從而對y進(jìn)行了承諾.根據(jù)不可能找到兩個不同的消息生成相同的單向散列函數(shù)值以及單向散列函數(shù)一個比特變化就會導(dǎo)致單向散列函數(shù)值約一半比特的比特發(fā)生變化的這兩個特殊性質(zhì),迫使Bob 最后只能公布真實的結(jié)果.若Bob 想修改結(jié)果,則Alice 在協(xié)議第(5)步驗證hash(?d)=v時就會發(fā)現(xiàn)Bob的欺騙行為.即Alice 將該值與原先收到的值和隨機(jī)數(shù)進(jìn)行匹配,如果匹配,則承諾有效; 反之,承諾無效,Alice 可以拒絕接受Bob 所發(fā)來的結(jié)果.本承諾的理論基礎(chǔ)就是根據(jù)單向散列函數(shù)這兩個特殊性質(zhì)決定的.故通過由Bob 選擇隨機(jī)數(shù)s及對s進(jìn)行Hash 運算這些技巧,既保證了協(xié)議2 的正確性以及安全性(在半誠實模型下),進(jìn)一步,當(dāng)Bob 把計算結(jié)果發(fā)送給Alice時,Alice 可以檢驗收到的結(jié)果是否為正確結(jié)果,從而保證了兩個參與者獲得相同的計算結(jié)果.

5 應(yīng)用及推廣

5.1 應(yīng)用

(1)中國象棋

眾所周知,在中國象棋中,卒在兩點間所行走的距離可以看做是計算兩點間的曼哈頓距離; 象在兩點間所行走的距離可以看做兩點間以斜對角(即斜45 度)為坐標(biāo)軸的曼哈頓距離.科學(xué)研究與工程實踐中的許多約束優(yōu)化問題可以抽象為中國象棋問題.在現(xiàn)實生活中,大多數(shù)實際問題是包含約束條件的.這使得約束優(yōu)化問題與實際生活息息相關(guān).但隨著網(wǎng)絡(luò)的迅速發(fā)展,人們越來越看重個人隱私,這使得隱私保護(hù)變得尤為重要,但如何在不降低安全性的前提下,保密地解決約束優(yōu)化的問題呢? 這就需要保密計算兩點間的曼哈頓距離.

(2)生物信息學(xué)

在生物信息學(xué)中,保密計算兩者間的曼哈頓距離可以評估離散頻率分布的差別.即RNA 拼接隨機(jī)引物的位置分布可以用曼哈頓距離表示.每一個位置分布可以用一個向量進(jìn)行表示,該向量的每一項代表了隨機(jī)引物在某一個核苷酸開始的概率.兩向量間的曼哈頓距離越大,則表明它們之間的分布差距越大; 兩向量間的曼哈頓距離越小,則表明它們之間就有相似的分布,從而對患病概率,新病種了解有著舉足輕重的作用.在現(xiàn)實生活中,患者并不想公開自己的患病信息,醫(yī)療機(jī)構(gòu)彼此之間也不想透漏自己的商業(yè)機(jī)密,這使得如何在不泄露私有信息的情況下保密地了解某種新的病種與已知病種間相似度的問題變得尤為重要.保密計算計算兩點間的曼哈頓距離便可以解決此問題.

5.2 推廣

(1)有理數(shù)域下保密計算兩點間的曼哈頓距離.

首先雙方商定精度,假設(shè)將有理數(shù)保留至小數(shù)點后一位.之后沿用思想1 或思想2,將全集按照0.1進(jìn)行劃分.利用同樣的方法便可保密計算有理數(shù)域下兩點間的曼哈頓距離.

(2)整數(shù)集下保密計算多點的曼哈頓距離.

問題描述Alice,Bob 分別在平面上擁有多個私密點(u1,u2),··· ,(ul?1,ul)和(v1,v2),··· ,(vl?1,vl),且這些私密點的全集已知,他們想保密求這些點間的曼哈頓距離,即保密計算(|u1?v1|+|u2?v2|)+···+(|ul?1?vl?1|+|ul?vl|)的值.

解決思路在多點對的情況下,我們同樣可以沿用協(xié)議1或者協(xié)議2的思想.以協(xié)議1思想為例,Alice,Bob 可以分別將自己l個私密點編碼,將其分別化為ln維向量L1,L2.之后再保密計算向量L1,L2間的海明距離即可.

(3)保密計算兩點間的切比雪夫距離.

問題描述Alice,Bob 分別在平面上擁有一個私有點(t1,t2)和(w1,w2),他們想保密求這兩點間的切比雪夫距離,即保密計算max{|t1?w1|,|t2?w2|},為了進(jìn)一步滿足安全性的需求,這里我們稍作改變,即輸出結(jié)果只輸出是橫坐標(biāo)差的絕對值大還是縱坐標(biāo)差的絕對值大,但不泄露具體數(shù)值.

解決思路將保密計算兩點間切比雪夫距離的問題化為保密計算兩向量內(nèi)積的問題.

雙方首先進(jìn)行編碼,雙方規(guī)則不同.Alice 先將自己的數(shù)據(jù)按照編碼方式1 進(jìn)行編碼,即該數(shù)及其之前的數(shù)均編為1,其余編為0.(或Bob 先將該數(shù)及其之前的數(shù)均編為0,其余編為1 或?1(對于橫坐標(biāo)編為1,縱坐標(biāo)標(biāo)為?1).)

例3假設(shè)Alice 擁有點(5,3); Bob 擁有點(?3,?2).全集為{?3,?2,··· ,4,5}.

Alice 將橫坐標(biāo)5 進(jìn)行編碼,得到向量T1=(1,1,1,1,1,1,1,1,1),將縱坐標(biāo)3 進(jìn)行編碼,得到向量T2=(1,1,1,1,1,1,1,0,0).進(jìn)而Alice 可以得到向量T′=(1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,0).

Bob 將橫坐標(biāo)?3 進(jìn)行編碼,得到向量W1=(0,1,1,1,1,1,1,1,1),再將縱坐標(biāo)?2 進(jìn)行編碼,得到向量W2=(0,0,?1,?1,?1,?1,?1,?1,?1).進(jìn)而 Bob 可以得到向量W′=(0,1,1,1,1,1,1,1,1,0,0,?1,?1,?1,?1,?1,?1,?1).

Alice 再將自己的數(shù)據(jù)按照編碼2 進(jìn)行編碼,即該數(shù)及其之前的數(shù)均編為0,其余編為1.(或Bob 先將該數(shù)及其之前的數(shù)均編為1,其余編為0.)

例4Alice 對橫坐標(biāo)5 進(jìn)行編碼,得到=(0,0,0,0,0,0,0,0,0),縱坐標(biāo)3 進(jìn)行編碼,得到=(0,0,0,0,0,0,0,1,1).從而可得向量T′′=(0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1).Bob 對橫坐標(biāo)?3進(jìn)行編碼,得到=(1,0,0,0,0,0,0,0,0),對縱坐標(biāo)?2 進(jìn)行編碼,得到=(1,1,0,0,0,0,0,0,0).從而可得向量=(1,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0).

至此,雙方分別得到向量

與

最后,雙方利用Paillier 同態(tài)加密算法保密求得T,W兩向量的內(nèi)積,即保密地將

與

6 協(xié)議的效率分析

6.1 計算復(fù)雜性與通信復(fù)雜性分析

計算復(fù)雜性由于目前沒有任何關(guān)于保密計算兩點間曼哈頓距離的協(xié)議,因此只對本文提出的協(xié)議進(jìn)行效率分析.協(xié)議1 中,Alice 加密了2n次(n為全集的勢),解密2n次; Bob 需要進(jìn)行2n次加密運算和2n次模乘運算.加密一次需要進(jìn)行2 次模乘運算,解密一次需要lgp次模乘運算,因此協(xié)議1 需進(jìn)行10n+2nlgp次模乘運算.協(xié)議2中,Alice 需加密4n次,解密1 次; Bob 最多需進(jìn)行4n次模乘運算,由于哈希運算速度極快,我們忽略哈希運算所進(jìn)行的時間,故協(xié)議2 最多需進(jìn)行2(6n+1)次模乘運算.

通信復(fù)雜性我們使用通信輪數(shù)來進(jìn)行分析.協(xié)議1和協(xié)議2均需要2 輪通信.具體分析見表1.

表1 協(xié)議性能比較Table 1 Protocol performance comparison

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

實驗測試環(huán)境:我們采用java 編程語言對協(xié)議進(jìn)行編程實現(xiàn).實驗測試環(huán)境如下:Windows 10 家庭中文版,處理器為Intel(R)Core(TM)i5-6600 3.30 GHz 3.31 GHz,內(nèi)存為8.00 GB.

實驗方法:隨機(jī)選取兩點X,Y,并設(shè)定全集的勢為n.對于n=5,··· ,23(間隔為2)的每個設(shè)定值進(jìn)行進(jìn)行1000 次實驗并取其平均時間.實驗所選取的Goldwasser-Micali 加密算法的加密密鑰為512 比特,Paillier 加密算法的加密密鑰為512 比特,選取隨機(jī)數(shù)長度為64 比特.圖1 描述了保密計算兩點間曼哈頓距離的時間隨著n值增長的變化規(guī)律.

圖1 協(xié)議執(zhí)行時間隨著n 值增長的變化規(guī)律Figure 1 Execution time of protocol varies with growth of n

實驗結(jié)果表明,保密計算兩點間曼哈頓距離的時間隨著n的增加大致呈線性增長.協(xié)議1與協(xié)議2均可以高效且安全地計算兩點間曼哈頓距離.

7 結(jié)論

保密計算兩點間的曼哈頓距離是密碼學(xué)中一個新的問題,在信息過濾,生物信息學(xué)方面有著重要的理論價值.本文用新的方法來解決這個新的問題,設(shè)計了兩種不同的編碼方法,利用該編碼和同態(tài)加密算法將原問題分別化為保密計算兩向量的海明距離與保密計算兩向量的內(nèi)積,經(jīng)過運算后可直接得到兩點間的曼哈頓距離,避免了分別計算橫縱坐標(biāo)差的絕對值之和導(dǎo)致的信息泄露,并用模擬器證明了協(xié)議是安全的.與此同時,我們將原問題擴(kuò)展至三個方面,形成了三個新問題(有理數(shù)域下保密求兩點間的曼哈頓距離; 整數(shù)集下保密計算多點的曼哈頓距離; 保密計算兩點間的切比雪夫距離).最后,通過理論分析和實驗顯示,我們的方案可以高效安全地計算兩點之間的曼哈頓距離.本文所設(shè)計的協(xié)議均是在半誠實模型下進(jìn)行的,在后面的工作中,我們將探討惡意模型下保密計算兩點間曼哈頓距離的問題.