曼哈頓距離的保密計算*

方樂笛,李順東,竇家維

1.陜西師范大學 計算機科學學院,西安710119

2.陜西師范大學 數學與信息科學學院,西安710119

1 引言

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

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

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

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

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

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

1.1 本文貢獻

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

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

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

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

1.2 本文結構

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

2 預備知識

2.1 安全性定義

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

本文所設計的協議是在半誠實模型下安全的計算協議.

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

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

則稱協議π保密地計算了函數f.其中表示計算不可區分.

2.2 Goldwasser-Micali 公鑰加密系統

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

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

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

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

異或同態性:由于下面性質成立

因此,Goldwasser-Micali 加密方案具有異或同態性.

2.3 Paillier 同態加密算法

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

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

加密過程對于明文m

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

加法同態性:由于下面性質成立

因此,Paillier 加密算法具有加法同態性.

2.4 單向散列函數

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

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

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

2.5 數字承諾

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

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

3 半誠實模型下曼哈頓距離協議

本節首先設計一種新的編碼方法,以此為基礎,結合應用Goldwasser-Micali 加密方案,設計構造兩點間曼哈頓距離的保密計算協議.

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

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

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

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

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

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

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

關于兩點P和Q之間的曼哈頓距離,有下面的結論.

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

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

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

按照編碼方式1 編碼后,x1對應的向量為

x2編碼為

對A1和B1的對應分量進行異或,得到

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

當x2>x1時,完全類似得到

3.1 具體協議

以上面計算原理為基礎,結合Goldwasser-Micali 加密算法,我們設計構造兩點間曼哈頓距離的保密計算協議.

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

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

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

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

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

并將E(A)發送給Bob.

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

再將R的n個分量進行隨機置換,得到新的向量,記為,并將發送給Alice.

計算y=d11+···+d2n,并將y發給Bob.

(4)Alice和Bob 輸出y.

3.2 方案分析

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

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

安全性分析關于協議的安全性,我們有下面的結論.

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

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

S1的模擬過程如下.

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

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

再將R′的分量進行隨機置換,得到.

(3)S1解密′,得到

(4)S1計算

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

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

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

再將R′的分量進行隨機置換,得到

(3)S2解密得到

(4)S2計算

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

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

4 增強的曼哈頓距離協議

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

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

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

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

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

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

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

例2假設全集為U={?3,?2,··· ,4,5},對于點P(?3,?2),應用編碼方式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)應用編碼方法2 對應的向量V(P)=(0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1).

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

關于兩點P和Q間的曼哈頓距離,下面結論成立.

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

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

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

按照編碼方式1 編碼后,x1對應的向量為

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

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

按照編碼方式2 編碼后,x1對應的向量為

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

當x2>x1時,完全類似得到

4.1 具體協議

根據上面所述的計算原理,并結合應用Paillier 加密方案和數字承諾思想可設計構造防欺騙場景下計算兩點間曼哈頓距離的安全計算協議2.具體協議如下.

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

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

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

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

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

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

Bob 將v以及T發送給Alice.

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

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

4.2 方案分析

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

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

5 應用及推廣

5.1 應用

(1)中國象棋

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

(2)生物信息學

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

5.2 推廣

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

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

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

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

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

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

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

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

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

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

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

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

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

例4Alice 對橫坐標5 進行編碼,得到=(0,0,0,0,0,0,0,0,0),縱坐標3 進行編碼,得到=(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 對橫坐標?3進行編碼,得到=(1,0,0,0,0,0,0,0,0),對縱坐標?2 進行編碼,得到=(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,W兩向量的內積,即保密地將

與

6 協議的效率分析

6.1 計算復雜性與通信復雜性分析

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

通信復雜性我們使用通信輪數來進行分析.協議1和協議2均需要2 輪通信.具體分析見表1.

表1 協議性能比較Table 1 Protocol performance comparison

6.2 實驗數據分析

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

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

圖1 協議執行時間隨著n 值增長的變化規律Figure 1 Execution time of protocol varies with growth of n

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

7 結論

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