方樂(lè)笛,李順東,竇家維

1.陜西師范大學(xué) 計(jì)算機(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ù)變得尤為重要.安全多方計(jì)算(secure multiparty computation,SMC)作為隱私保護(hù)的核心技術(shù),成為了國(guó)際密碼學(xué)界的研究熱點(diǎn)[1].安全多方計(jì)算最初于1982年由Yao[2]以百萬(wàn)富翁問(wèn)題提出,它由兩個(gè)參與者組成,之后Ben-or和Goldwasser[3]將其擴(kuò)展到了多個(gè)參與者,學(xué)術(shù)界統(tǒng)稱為安全多方計(jì)算.安全多方計(jì)算的奇妙之處就在于可以使參與者在不泄露自己隱私數(shù)據(jù)的情況下,保密地使參與者利用自己的隱私數(shù)據(jù)聯(lián)合進(jìn)行某種運(yùn)算,從而達(dá)到合作共贏的目的,也最大限度的平衡了參與者隱私性與合作性的需求.

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

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

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

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

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

1.1 本文貢獻(xiàn)

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

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

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

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

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

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

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

2.1 安全性定義

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

加密過(guò)程對(duì)于明文m

解密過(guò)程對(duì)密文c,計(jì)算得明文m=D(c)

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

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

2.4 單向散列函數(shù)

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

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

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

2.5 數(shù)字承諾

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

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

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

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

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

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

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

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

例1假設(shè)全集為U={?3,?2,··· ,4,5},對(duì)于點(diǎn)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)而可得

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

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

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

命題1點(diǎn)P和Q間的曼哈頓距離可由下式計(jì)算:

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

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

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

x2編碼為

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

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

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

3.1 具體協(xié)議

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

協(xié)議1半誠(chéng)實(shí)模型下安全計(jì)算兩點(diǎn)間的曼哈頓距離

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

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

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

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

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

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

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

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

(4)Alice和Bob 輸出y.

3.2 方案分析

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

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

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

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

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

S1的模擬過(guò)程如下.

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

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

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

(3)S1解密′,得到

(4)S1計(jì)算

類似地,S2的模擬過(guò)程如下.

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

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

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

(3)S2解密得到

(4)S2計(jì)算

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

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

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

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

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

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

以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.對(duì)于y1以完全相同的方式構(gòu)造其對(duì)應(yīng)的數(shù)組,記為V2=(u21,··· ,u2n),進(jìn)一步構(gòu)造向量

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

例2假設(shè)全集為U={?3,?2,··· ,4,5},對(duì)于點(diǎn)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 對(duì)應(yīng)的向量V(P)=(0,1,1,1,1,1,1,1,1,0,0,1,1,1,1,1,1,1).

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

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

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

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

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

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

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

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

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

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

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

4.1 具體協(xié)議

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

協(xié)議2防欺騙場(chǎng)景下安全計(jì)算兩點(diǎn)間的曼哈頓距離

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

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

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

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

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

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

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

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

4.2 方案分析

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

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

5 應(yīng)用及推廣

5.1 應(yīng)用

(1)中國(guó)象棋

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

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

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

5.2 推廣

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

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

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

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

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

(3)保密計(jì)算兩點(diǎn)間的切比雪夫距離.

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

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

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

例3假設(shè)Alice 擁有點(diǎn)(5,3); Bob 擁有點(diǎn)(?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 對(duì)橫坐標(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 對(duì)橫坐標(biāo)?3進(jìn)行編碼,得到=(1,0,0,0,0,0,0,0,0),對(duì)縱坐標(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 計(jì)算復(fù)雜性與通信復(fù)雜性分析

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

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

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

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

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

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

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

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

7 結(jié)論

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