蒲方圓，何明星，劉 陽

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

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

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

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

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

1 相關知識

1.1 安全性定義

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

定義如果存在概率多項式時間模擬器S1，S2使得以下2個等式同時成立

(1)

(2)

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

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

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

Dec: 計算密文c的明文為

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

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

E(m)t=E(tm)

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

2.1 問題描述

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

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

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

(3)

式中n1，n2是l1對應平面π1，π2的法向量。

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

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

Bob擁有1條保密直線

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

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

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

3)Bob選擇隨機數(shù)k1，k2，并計算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后，計算Aa1，Aa2，Q3，Q4。將Q3，Q4發(fā)送給Alice。

Aa1=q1-k1

(6)

Aa2=q2-k2

(7)

(8)

(9)

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

(10)

2.3 協(xié)議的正確性

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

證明Alice的密文信息為:

Bob的密文信息為

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

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

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

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

故有

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

2.4 協(xié)議的安全性

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

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

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

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

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

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

下面再通過構造模擬器的方法進行具體的安全性證明。

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

構造S2對于輸入(l2，f2(l1，l2))，S2按以下方式運行。

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

令

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

同理，用類似的方法可以構建模擬器S1使得

3 保密計算標準式空間2平行直線的距離

3.1 問題描述

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

(11)

3.2 保密計算標準式2條空間平行直線的距離(協(xié)議2)

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

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

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

3)Alice 計算:

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用自己的公鑰對e1，e2，e3進行加密得密文:E(e1)，E(e2)，E(e3)。Alice將密文發(fā)送給Bob。

4)Bob計算e5，用Alice公鑰加密e5得E(e5)，再計算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′，并計算m′+e4，進而可得d，再將結果d發(fā)送給Bob。

(18)

3.3 協(xié)議的正確性

定理3 協(xié)議2能正確計算出標準式的2條空間平行直線的距離。

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

Alice的密文信息

Bob的密文信息

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

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

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

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

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

3.4 協(xié)議的安全性

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

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

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

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

構造S3對于輸入(l3，f3(l3，l4))，S3按以下方式運行：

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

4)S3計算M″

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

同理，用類似的方法可以構造模擬器S4使得

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

4.1 計算復雜度

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

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

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

4.2 通信復雜度

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

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

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

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

表2 協(xié)議的運算耗時對比

實驗結果表明，文獻[19]中的協(xié)議需要的運行時間遠遠大于本文提出的2個協(xié)議。

5 結束語

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