空間平行直線距離的高效安全計算

蒲方圓，何明星，劉 陽

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

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

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

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

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

1 相關知識

1.1 安全性定義

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

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

(1)

(2)

1.2 Paillier同態加密方案[21]

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

Enc: 選擇隨機數r，r

Dec: 計算密文c的明文為

Paillier加密方案的同態性，為

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條空間平行直線的距離(協議1)

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

Bob擁有1條保密直線

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

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

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

3)Bob選擇隨機數k1，k2，并計算E(k1)，E(k2)和Q1，Q2，將Q1，Q2發送給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，并發送給Bob。

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

Aa1=q1-k1

(6)

Aa2=q2-k2

(7)

(8)

(9)

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

(10)

2.3 協議的正確性

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

證明Alice的密文信息為:

Bob的密文信息為

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

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

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

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

故有

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

2.4 協議的安全性

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

證明對Alice而言，Alice在協議過程中獲得

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

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

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

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

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

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

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

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

令

由于在協議1的執行過程中

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

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

3.1 問題描述

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

(11)

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

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

1)基于Paillier的同態加密方案， 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將密文發送給Bob。

4)Bob計算e5，用Alice公鑰加密e5得E(e5)，再計算M′并把M′發送給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發送給Bob。

(18)

3.3 協議的正確性

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

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

Alice的密文信息

Bob的密文信息

Bob根據密文信息計算M′。

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

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

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

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

3.4 協議的安全性

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

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

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

構造滿足等式(1)和(2)的模擬器S3，S4來證明協議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 協議效率分析與比較

4.1 計算復雜度

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

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

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

4.2 通信復雜度

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

表1 幾個協議的性能比較

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

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

表2 協議的運算耗時對比

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

5 結束語

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