空間平行直線距離的高效安全計(jì)算

蒲方圓，何明星，劉 陽

(西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院， 四川 成都 610039)

隨著現(xiàn)代網(wǎng)絡(luò)的迅速發(fā)展，多方合作的機(jī)會(huì)越來越多，如何保護(hù)各方隱私數(shù)據(jù)變得更加重要。安全多方計(jì)算是信息社會(huì)隱私保護(hù)的核心技術(shù)，是國(guó)際密碼學(xué)界近年來的研究熱點(diǎn)之一。安全多方計(jì)算的概念是由Yao[1]首先提出，是指在不泄露參與各方的輸入數(shù)據(jù)(隱私性)的條件下，能正確完成對(duì)輸入數(shù)據(jù)的函數(shù)計(jì)算(正確性)。它能夠讓人們最大程度地使用私有數(shù)據(jù)而不破環(huán)數(shù)據(jù)的私有性。正是因?yàn)榇诵再|(zhì)，它在數(shù)據(jù)隱私保護(hù)、電子商務(wù)、數(shù)據(jù)挖掘、保密存儲(chǔ)、計(jì)算外包、密鑰分配、入侵檢測(cè)等方面有著廣泛的應(yīng)用[2-8]。文獻(xiàn)[9-10]提出了通用的安全多方計(jì)算協(xié)議，即對(duì)任意的安全多方計(jì)算問題都轉(zhuǎn)化為通用的安全多方計(jì)算協(xié)議來解決，并引入了安全多方計(jì)算的安全性形式化定義與模擬范例，但是對(duì)于解決一些具體問題而言，如果轉(zhuǎn)化為通用的安全多方計(jì)算問題，計(jì)算復(fù)雜度和通信復(fù)雜度較高，使得效率較低，在實(shí)際中并不可行；所以具體問題應(yīng)該使用具體的協(xié)議。

安全幾何計(jì)算是安全多方計(jì)算的一個(gè)重要組成部分，它在商業(yè)、軍事等方面擁有廣泛的應(yīng)用前景[11]。文獻(xiàn)[11]提出了關(guān)于點(diǎn)面、線面、面面的位置關(guān)系判定協(xié)議。文獻(xiàn)[12]提出了空間中基于閾值的點(diǎn)與線段之間距離關(guān)系的保密判定協(xié)議。文獻(xiàn)[13]利用2組數(shù)據(jù)是否對(duì)應(yīng)成比例，解決了空間點(diǎn)、線、面的相對(duì)位置判定。文獻(xiàn)[14]提出了一個(gè)線段相交判定協(xié)議，同時(shí)研究了保護(hù)私有信息的多邊形相交的判定協(xié)議。文獻(xiàn)[15]提出了Paillier變體同態(tài)加密方案，并基于該方案提出了一種過私有2點(diǎn)保密計(jì)算出直線的協(xié)議。文獻(xiàn)[16]提出了一種判定凸多邊形的點(diǎn)包含協(xié)議，并進(jìn)一步研究了凹多邊形的點(diǎn)包含問題。文獻(xiàn)[17]提出了判定任意多邊形的點(diǎn)包含協(xié)議。文獻(xiàn)[18]將有理數(shù)看作過原點(diǎn)的直線斜率，將有理數(shù)的運(yùn)算轉(zhuǎn)化為整數(shù)的運(yùn)算，提出了有理數(shù)區(qū)間保密計(jì)算協(xié)議。

為了更加形象地說明本文要解決的問題，考慮以下場(chǎng)景，2家航空公司打算分別新開1條航線，已知這2條航線是相互平行的，為了保證飛機(jī)的飛行安全，現(xiàn)在要確定這2條航線的距離是否達(dá)到飛行的安全距離，如何在不泄露各自航線的基礎(chǔ)上求得這2條航線的距離。此問題就是安全計(jì)算空間平行直線的距離。文獻(xiàn)[19]提出了空間2平行直線間距離的保密計(jì)算協(xié)議，但是多次調(diào)用了不經(jīng)意傳輸協(xié)議[20]和保密點(diǎn)積協(xié)議，增加了計(jì)算的復(fù)雜度和通信復(fù)雜度。

本文基于Paillier同態(tài)加密，提出了2個(gè)求空間平行直線的距離協(xié)議。協(xié)議1：針對(duì)交面式空間2平行直線設(shè)計(jì)了一個(gè)高效求空間平行直線距離的協(xié)議。協(xié)議2：針對(duì)標(biāo)準(zhǔn)式空間2條平行直線設(shè)計(jì)了一種新的、安全的求解空間2平行直線距離的協(xié)議。與文獻(xiàn)[19]相比，協(xié)議1與協(xié)議2既不采用不經(jīng)意傳輸協(xié)議，也不采用保密點(diǎn)積協(xié)議，使得計(jì)算復(fù)雜度和通信復(fù)雜度較低。

1 相關(guān)知識(shí)

1.1 安全性定義

1) 半誠(chéng)實(shí)參與者[10]。假設(shè)所有的參與者都是半誠(chéng)實(shí)的參與者，在協(xié)議的執(zhí)行過程中，正確地按照協(xié)議的過程完成每一個(gè)步驟，不會(huì)隨意篡改輸入和輸出信息，但可能會(huì)保存協(xié)議執(zhí)行中關(guān)于其他參與者信息的中間結(jié)果，在協(xié)議結(jié)束后想要推導(dǎo)出其他參與者的私有信息。

定義如果存在概率多項(xiàng)式時(shí)間模擬器S1，S2使得以下2個(gè)等式同時(shí)成立

(1)

(2)

1.2 Paillier同態(tài)加密方案[21]

該加密方案由密鑰生成(Gen)、加密(Enc)和解密(Dec)這3個(gè)隨機(jī)算法組成。

Enc: 選擇隨機(jī)數(shù)r，r

Dec: 計(jì)算密文c的明文為

Paillier加密方案的同態(tài)性，為

E(m1)×E(m2)=E(m1+m2)

E(m)t=E(tm)

2 保密計(jì)算交面式的2條空間平行直線的距離

2.1 問題描述

設(shè)Alice和Bob分別擁有2條空間平行直線，其方程分別為

問題是如何保密計(jì)算2平行直線的距離d(考慮b1c2-b2c1≠0 的情況)。

當(dāng)b1c2-b2c1≠0時(shí)，空間2交面式平行直線間的距離為d。

(3)

式中n1，n2是l1對(duì)應(yīng)平面π1，π2的法向量。

2.2 保密計(jì)算交面式2條空間平行直線的距離(協(xié)議1)

輸入：Alice擁有1條保密直線

Bob擁有1條保密直線

輸出: Alice和Bob計(jì)算得到直線l1，l2之間的距離d。

1)基于Paillier的同態(tài)加密方案(G，D，E)，Alice運(yùn)行算法(Gen)生成同態(tài)加密的密鑰對(duì)(pk，sk)，并公布pk。

2)Alice用生成的公鑰對(duì)b1，c1，d1，b2，c2，d2進(jìn)行加密，得到E(b1)，E(c1)，E(d1)，E(b2)，E(c2)，E(d2)，并發(fā)送給Bob。

3)Bob選擇隨機(jī)數(shù)k1，k2，并計(jì)算E(k1)，E(k2)和Q1，Q2，將Q1，Q2發(fā)送給Alice(其中α=c3d4-c4d3，β=b4d3-b3d4，γ=b3c4-b4c3)。

Q1=E(b2)α×E(c2)β×E(d2)γ×E(k1)=E(b2α+c2β+d2γ+k1)

(4)

Q2=E(b1)α×E(c1)β×E(d1)γ×E(k2)=E(b1α+c1β+d1γ+k2)

(5)

4)Alice用私鑰解密Q1，Q2，得到q1，q2，并發(fā)送給Bob。

5)Bob得到q1，q2后，計(jì)算Aa1，Aa2，Q3，Q4。將Q3，Q4發(fā)送給Alice。

Aa1=q1-k1

(6)

Aa2=q2-k2

(7)

(8)

(9)

6)Alice計(jì)算d2，將結(jié)果d發(fā)送給Bob。

(10)

2.3 協(xié)議的正確性

定理1 協(xié)議1能正確計(jì)算出交面式的2條空間平行直線的距離。

證明Alice的密文信息為:

Bob的密文信息為

Bob根據(jù)密文信息計(jì)算Q1，D(Q1)，為

Q1=E(b2)α×E(c2)β×E(d2)γ×E(k1)=

[gb2α+c2β+d2γ+k1(r1r2r3r4)N]modN2

Bob按式(6)、式(8)計(jì)算出Q3，并發(fā)送給Alice。同理Alice可得到Q4，按式(10)計(jì)算平行直線距離的平方。

故有

由以上可知，協(xié)議1能夠正確地計(jì)算出2條空間平行直線的距離。在整個(gè)過程中，Alice和Bob沒有泄露各自的秘密信息，而且完成了平行直線的距離計(jì)算。

2.4 協(xié)議的安全性

定理2 在半誠(chéng)實(shí)模型下，協(xié)議1是安全的。

證明對(duì)Alice而言，Alice在協(xié)議過程中獲得

q1=b2α+c2β+d2γ+k1

q2=b1α+c1β+d1γ+k2

在這4個(gè)等式中，b1，b2，c1，c2，d1，d2是Alice的保密數(shù)，α，β，γ，k1，k2是5個(gè)未知變量，不能根據(jù)這4個(gè)等式來確定5個(gè)變量的值，并且α，β，γ與Bob的保密數(shù)b3，b4，c3，c4，d3，d4有這樣的關(guān)系:α=c3d4-c4d3，β=b4d3-b3d4，γ=b3c4-b4c3，因此Alice得不到關(guān)于Bob的任何私有信息。

對(duì)Bob而言，Bob在協(xié)議1的過程中獲得關(guān)于Alice的保密數(shù)E(b1)，E(c1)，E(d1)，E(b2)，E(c2)，E(d2)，由于Paillier加密方案的安全性，Bob在不知道Alice的私鑰的條件下不能得到Alice的保密數(shù)。Bob得到式(6)、式(7)和式(10)這3個(gè)等式，其中a1，a2，b1，b2，c1，c2，d1，d2是關(guān)于Alice的8個(gè)未知變量，根據(jù)數(shù)學(xué)知識(shí)，不能通過這3個(gè)等式來確定8個(gè)變量的值，則Bob得不到關(guān)于Alice的任何信息，因此協(xié)議1是安全的。

下面再通過構(gòu)造模擬器的方法進(jìn)行具體的安全性證明。

通過構(gòu)造滿足等式(1)和(2)的模擬器S1，S2來證明。

構(gòu)造S2對(duì)于輸入(l2，f2(l1，l2))，S2按以下方式運(yùn)行。

4)S2計(jì)算d2，則d為空間2條平行直線l1，l2間的距離。

令

由于在協(xié)議1的執(zhí)行過程中

同理，用類似的方法可以構(gòu)建模擬器S1使得

3 保密計(jì)算標(biāo)準(zhǔn)式空間2平行直線的距離

3.1 問題描述

問題是在Alice和Bob不泄露各自直線上的任何一點(diǎn)的情況下計(jì)算2直線的距離。

(11)

3.2 保密計(jì)算標(biāo)準(zhǔn)式2條空間平行直線的距離(協(xié)議2)

輸出:Alice和Bob計(jì)算得到2直線之間的距離d。

1)基于Paillier的同態(tài)加密方案， Alice生成密鑰對(duì)(pk，sk)，并公布pk。

2)Alice在直線l3選取保密點(diǎn)A(x1，y1，z1)，Bob在直線l4選取B(x2，y2，z2)。

3)Alice 計(jì)算:

e1=2(-x1c2-x1b2+y1ab+z1ac)

(12)

e2=2(x1ab-y1c2+y1a2+z1bc)

(13)

e3=2(x1ac+y1bc-z1a2-z1b2)

(14)

e4=(y1c-z1b)2+(z1a-x1c)2+(x1b-y1a)2

(15)

Alice用自己的公鑰對(duì)e1，e2，e3進(jìn)行加密得密文:E(e1)，E(e2)，E(e3)。Alice將密文發(fā)送給Bob。

4)Bob計(jì)算e5，用Alice公鑰加密e5得E(e5)，再計(jì)算M′并把M′發(fā)送給Alice。

e5=(z2b-y2c)2+(x2c-z2a)2+(y2a-x2b)2

(16)

M′=E(e1)x2×E(e2)y2×E(e3)z2×E(e5)

(17)

5)Alice解密M′得到m′，并計(jì)算m′+e4，進(jìn)而可得d，再將結(jié)果d發(fā)送給Bob。

(18)

3.3 協(xié)議的正確性

定理3 協(xié)議2能正確計(jì)算出標(biāo)準(zhǔn)式的2條空間平行直線的距離。

證明證明過程省略了初始化，Alice和Bob的密文信息分別為：

Alice的密文信息

Bob的密文信息

Bob根據(jù)密文信息計(jì)算M′。

(ge1x2+e2y2+e3z2+e5(r5r6r7r8)N)modN2

Bob將M′發(fā)送給Alice，Alice解密可得D(M′)。

然后根據(jù)公式(18)計(jì)算d，故有

由以上證明可知，協(xié)議2能夠正確地計(jì)算2條空間平行直線的距離。整個(gè)過程中，Alice和Bob沒有泄露各自的秘密信息，且完成了平行直線距離的計(jì)算。

3.4 協(xié)議的安全性

定理4 在半誠(chéng)實(shí)模型下，協(xié)議2是安全的。

證明首先考慮Alice的計(jì)算安全性，第3)步Alice將密文E(e1)，E(e2)，E(e3)發(fā)送給Bob，根據(jù)Paillier加密系統(tǒng)的語義安全，Bob沒有Alice的私鑰，則Bob不能得到Alice的信息。因此，Bob不能得到任何關(guān)于Alice的私有信息。

其次考慮Bob的計(jì)算安全性。第4)步， Bob發(fā)送給Alice密文M′，對(duì)M′解密得到m′，其中m′=e1x2+e2y2+e3z2+e5，但x2，y2，z2都是未知數(shù)，根據(jù)數(shù)學(xué)知識(shí)，不能根據(jù)這一個(gè)等式來確定這3個(gè)未知數(shù)的值，則Alice不能得到任何關(guān)于Bob的信息。所以，協(xié)議2的每一步都是隱私保護(hù)的。下面構(gòu)造模擬器進(jìn)行具體的證明。

構(gòu)造滿足等式(1)和(2)的模擬器S3，S4來證明協(xié)議2的安全性。

構(gòu)造S3對(duì)于輸入(l3，f3(l3，l4))，S3按以下方式運(yùn)行：

3)S3計(jì)算E(e1)，E(e2)，E(e3)；

4)S3計(jì)算M″

5)S3解密得到m″，并計(jì)算m″+e4。

同理，用類似的方法可以構(gòu)造模擬器S4使得

4 協(xié)議效率分析與比較

4.1 計(jì)算復(fù)雜度

上述文獻(xiàn)的協(xié)議中有的使用了公鑰加密算法，有的未使用公鑰加密算法。為了方便比較，將模指數(shù)運(yùn)算的次數(shù)作為衡量計(jì)算復(fù)雜度的指標(biāo)，忽略準(zhǔn)備工作和隨機(jī)數(shù)選擇的計(jì)算開銷。

Paillier同態(tài)加密算法中進(jìn)行1次加密運(yùn)算需要做2次模指數(shù)運(yùn)算，1次解密運(yùn)算需要做1次模指數(shù)運(yùn)算，每進(jìn)行1次密文模指數(shù)運(yùn)算為1次模指數(shù)運(yùn)算。為了方便計(jì)算，忽略準(zhǔn)備工作和隨機(jī)數(shù)選擇的計(jì)算開銷。

文獻(xiàn)[19]沒有明確表明使用哪個(gè)具體的不經(jīng)意傳輸協(xié)議和保密點(diǎn)積協(xié)議，所以本文在進(jìn)行算法比較時(shí)采用文獻(xiàn)[20]的不經(jīng)意傳輸協(xié)議，保密點(diǎn)積協(xié)議也采用該文獻(xiàn)的不經(jīng)意傳輸方法。1次保密點(diǎn)積協(xié)議需要調(diào)用m次1-out-of-k不經(jīng)意傳輸，1次1-out-of-k不經(jīng)意傳輸至少需要logk次1-out-of-2不經(jīng)意傳輸，1次1-out-of-2不經(jīng)意傳輸至少需要2次模指數(shù)運(yùn)算，那么1次不經(jīng)意傳輸協(xié)議至少需要2logk次模指數(shù)運(yùn)算，1次點(diǎn)積協(xié)議至少需要2mlogk次模指數(shù)運(yùn)算(其中m是安全參數(shù))。文獻(xiàn)[19]調(diào)用了6次不經(jīng)意傳輸協(xié)議和6次點(diǎn)積協(xié)議，則至少需要12(m+1)logk次模指數(shù)運(yùn)算。根據(jù)實(shí)際意義，只有當(dāng)m>5且k>8才能達(dá)到基本安全級(jí)別。在協(xié)議1中，Alice需要加密6次和解密2次， Bob需要加密2次和6次密文模指數(shù)運(yùn)算，需要進(jìn)行24次模指數(shù)運(yùn)算。在協(xié)議2中，Alice需要加密3次和解密1次，Bob需要加密1次和3次密文模指數(shù)運(yùn)算，需要進(jìn)行12次模指數(shù)運(yùn)算。

4.2 通信復(fù)雜度

通常情況下，衡量通信復(fù)雜度的方法是比較協(xié)議交換信息的比特?cái)?shù)或比較通信的輪數(shù)，本文使用通信輪數(shù)來衡量。文獻(xiàn)[19]協(xié)議通信輪數(shù)為 6(m+1)次，本文協(xié)議1通信輪數(shù)為5次，協(xié)議2通信輪數(shù)為3次。由于本文未使用不經(jīng)意傳輸協(xié)議和保密點(diǎn)積協(xié)議，所以沒有基礎(chǔ)協(xié)議的交互過程，通信次數(shù)大大減少。

表1 幾個(gè)協(xié)議的性能比較

從表1可以看出，本文不管是計(jì)算復(fù)雜度，還是通信復(fù)雜度均優(yōu)于文獻(xiàn)[19]的協(xié)議。

為了進(jìn)一步對(duì)協(xié)議進(jìn)行性能分析，使用Java編程語言對(duì)3種協(xié)議分別進(jìn)行了編程實(shí)現(xiàn)。計(jì)算機(jī)環(huán)境：操作系統(tǒng)為windows 7 企業(yè)版，處理器為Inter Core(TM)i5-2 450 M 2.50 GHz，內(nèi)存為4 GB。實(shí)驗(yàn)中設(shè)定Paillier加密算法中使用的大素?cái)?shù)p和q的位數(shù)為512 bits，其中k=9、m=6，保密數(shù)的范圍設(shè)定為[1，30]。并對(duì)每種協(xié)議的實(shí)驗(yàn)結(jié)果隨機(jī)抽取20組數(shù)據(jù)求時(shí)間平均值，其結(jié)果如表2所示。

表2 協(xié)議的運(yùn)算耗時(shí)對(duì)比

實(shí)驗(yàn)結(jié)果表明，文獻(xiàn)[19]中的協(xié)議需要的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)大于本文提出的2個(gè)協(xié)議。

5 結(jié)束語

本文在半誠(chéng)實(shí)模型下，在Paillier同態(tài)加密算法的基礎(chǔ)上，分別提出了標(biāo)準(zhǔn)式空間2平行直線距離和交面式空間2平行直線距離的安全計(jì)算協(xié)議，同時(shí)證明了協(xié)議的正確性和安全性。 在今后的工作中，將探討惡意模型下空間2平行直線距離的安全計(jì)算問題。另外，對(duì)于空間任意2條直線，將進(jìn)一步研究2條直線上點(diǎn)的最小距離的安全計(jì)算問題。