于金霞，趙翠平，張 靜,2，湯永利+

1.河南理工大學 計算機科學與技術(shù)學院，河南 焦作 454000

2.北京交通大學 計算機與信息技術(shù)學院，北京 100044

安全多方空間兩平行直線間距離計算*

于金霞1，趙翠平1，張 靜1,2，湯永利1+

1.河南理工大學 計算機科學與技術(shù)學院，河南 焦作 454000

2.北京交通大學 計算機與信息技術(shù)學院，北京 100044

為提高三維空間兩平行直線間距離協(xié)議的計算效率，基于安全兩實數(shù)和平方（secure square of two real numbers sum，SSTS）計算協(xié)議與Paillier同態(tài)加密算法（Paillier homomorphic encryption algorithm，PHEA）分別提出了三維空間兩平行直線間的距離計算協(xié)議。SSTS協(xié)議利用空間任一點到直線的距離推導出三維空間兩平行直線間的距離，通過安全兩實數(shù)和平方計算協(xié)議構(gòu)造輔助數(shù)據(jù)來隱藏自己的具體數(shù)據(jù)；PHEA協(xié)議通過Paillier同態(tài)加密算法將自己直線方程的系數(shù)隱藏，能與對方進行交流計算，但不會泄露自己的具體數(shù)據(jù)；兩個協(xié)議均能保密地計算出三維空間兩平行直線間的距離。分別證明了兩個協(xié)議的正確性，并利用模擬范例證明了兩個協(xié)議的安全性。最后，對SSTS協(xié)議和PHEA協(xié)議與現(xiàn)有協(xié)議進行比較分析，結(jié)果表明，新協(xié)議有較低的計算復雜性和通信復雜性，比現(xiàn)有協(xié)議至少降低了50%。

隱私保護的計算幾何；空間距離；安全兩實數(shù)和平方；同態(tài)加密；模擬范例

1 引言

隨著互聯(lián)網(wǎng)的快速發(fā)展，陌生用戶之間的合作計算變得越來越重要，企業(yè)和組織機構(gòu)既要在合作計算交流信息的過程中保密自己的有價值數(shù)據(jù)，又要通過整合資源獲得利益，在此背景下安全多方計算應(yīng)運而生。安全多方計算最初是圖靈獎獲得者Yao[1]提出的，經(jīng)過了Goldreich等人的發(fā)展[2]，逐漸成為現(xiàn)代密碼學及電子商務(wù)等眾多應(yīng)用領(lǐng)域的重要研究課題之一。安全多方計算（secure multi-party computation，SMC）是信息社會隱私數(shù)據(jù)保護的核心技術(shù)，是指兩個或多個參與者在不泄露各自輸入的隱私數(shù)據(jù)情況下，能夠利用這些隱私數(shù)據(jù)參加保密計算，共同完成某項計算任務(wù)。安全多方計算在大數(shù)據(jù)安全與隱私保護[3-6]、基因序列[7-9]、數(shù)據(jù)挖掘[10]、密鑰分配、科學計算等方面得到應(yīng)用廣泛。

基于隱私保護的計算幾何是安全多方計算領(lǐng)域重要研究內(nèi)容之一，在商業(yè)、軍事和保密圖像處理等方面擁有廣泛的應(yīng)用前景[11]和潛在的應(yīng)用價值。目前已經(jīng)有一些重要的研究成果：在平面幾何方面，Du等人[12]利用置換協(xié)議和安全兩方點積協(xié)議不僅提出了平面上兩條直線的相交判定問題和凸包的相交問題，而且給出了解決此類問題有用的知識模塊，但是函數(shù)求值時可能產(chǎn)生信息泄露。文獻[13]針對Du的算法進行了修改，但當用戶輸入的隱私數(shù)據(jù)需要保護時，對傳統(tǒng)算法做簡單改進也不能滿足要求，對此提出半誠實模型下計算幾何中關(guān)于線段最核心的算法——叉積協(xié)議，此協(xié)議不僅可以用于解決保護私有信息的計算幾何問題，而且可以用于解決秘密比較等一般的安全多方計算問題，但對方可以惡意輸入虛假數(shù)據(jù)或者隨意終止協(xié)議運行。文獻[14]針對Du的兩線段相交計算復雜性高的問題提出一種高效的不經(jīng)意傳輸協(xié)議，并將高效不經(jīng)意傳輸協(xié)議擴展到判定兩個任意多邊形和兩個任意幾何圖形相交問題。文獻[15-18]研究了點包含問題，文獻[15]中的協(xié)議只使用于一些簡單多邊形域，文獻[16]中的協(xié)議只使用于圓域，文獻[17]研究了點與橢圓之間的關(guān)系，文獻[18]研究了點是否在一個凸多邊形內(nèi)。由于文獻[15-18]都具有局限性，文獻[19]基于角旋轉(zhuǎn)法提出了保護隱私的任意多邊形點包含兩方計算協(xié)議，并給出正確性和安全性證明，但此協(xié)議計算效率低。文獻[20]所提協(xié)議不僅可以判定點與任意多邊形的包含問題，而且比現(xiàn)有協(xié)議更加高效和安全，但是基于半誠實模型的，是不切實際的。文獻[15-18]研究的都是點包含問題，但在實際應(yīng)用中具有局限性。文獻[21]研究了點與曲線關(guān)系的隱私保護協(xié)議，解決了在不泄露任何信息的情況下和在不同情形下如何確定點與曲線位置關(guān)系的問題。文獻[22]研究了安全兩方圓計算協(xié)議，并利用這些協(xié)議解決了保護私有信息的圓與圓的位置關(guān)系和圓與直線的位置關(guān)系判定問題。以上研究僅局限于平面對象，對更為復雜的空間問題并未涉及。文獻[23]對平面線段相交問題進行了研究和擴展，利用點積協(xié)議和比較相等協(xié)議設(shè)計了保護私有信息的對應(yīng)成比例判定協(xié)議，解決了空間幾何對象相對位置判定問題，但此協(xié)議是在兩方安全環(huán)境下提出的，具有較高的計算復雜度；多數(shù)保護私有信息的幾何對象相對位置協(xié)議側(cè)重于定性研究，文獻[24]則定量對線、面之間的角度及線線之間的距離問題進行更深入的研究，構(gòu)建出三維空間線、面夾角協(xié)議和線、線距離協(xié)議，有效降低了計算復雜度，并且可用于解決更多的其他計算幾何問題，但協(xié)議是基于半誠實模型的，在惡意模型下對這些問題的協(xié)議分析和設(shè)計都非常復雜。文獻[11]研究了空間幾何中四面體的體積、點到平面的距離、直線與平面關(guān)系和兩平面關(guān)系的多方安全問題及其應(yīng)用，并利用模擬范例證明協(xié)議是安全的，但仍有許多計算幾何問題需要研究。文獻[25]研究了空間兩平行直線間的距離問題，但計算復雜度和通信復雜度很高。

本文針對三維空間兩平行直線間的距離問題提出了兩個新的安全計算協(xié)議：SSTS（secure square of two real numbers sum）協(xié)議基于安全兩實數(shù)和平方協(xié)議的方法解決了空間兩平行直線間距離問題的安全多方計算，PHEA（Paillier homomorphic encryption algorithm）協(xié)議基于Paillier的同態(tài)加密算法高效解決了空間兩平行直線間距離問題的安全多方計算。經(jīng)過理論分析，SSTS協(xié)議在計算復雜度和通信復雜度上比現(xiàn)有解決方案的復雜度至少降低了50%，并證明了其正確性和安全性。在SSTS協(xié)議的基礎(chǔ)上，進一步提出了更加安全高效的解決方案——PHEA協(xié)議。

2 預備知識

2.1 安全兩實數(shù)和平方計算協(xié)議

協(xié)議1安全兩實數(shù)和平方計算[22]。

Alice和Bob各有1個實數(shù)n1和n2,Alice和Bob希望在不泄露各自的私有輸入信息時，保密地計算(n1+n2)2。經(jīng)計算，Alice得到r1,Bob 得到r2,使得r1+r2=(n1+n2)2。

步驟2 Alice和Bob利用退化的一維安全兩方點積協(xié)議計算n1?n2：Alice得到R1，Bob 得到R2，使得R1+R2=n1?n2。

2.2 同態(tài)加密方案

同態(tài)加密方案[26]在云計算和安全多方計算中發(fā)揮著不可替代的作用，是公鑰加密方案中的一種。同態(tài)加密的特質(zhì)可以采用對密文進行運算代替對明文的某些運算并取得同樣的效果，而不影響明文數(shù)據(jù)的保密性。本文運用的是Paillier加密方案[27]的加法同態(tài)Ek(x)·Ek(y)=Ek(x+y),從加法同態(tài)性的性質(zhì)得E(x)m=E(mx)。

2.3 Paillier加密方案

密鑰產(chǎn)生：

（1）隨機選取兩個素數(shù)p和q，且滿足gcd(pq,(p-1)(q-1))=1。

（2）計算n=pq和λ=lcm(p-1,q-1)。

加密/解密：

對于明文m(m∈Zn)，選擇隨機數(shù)r(r∈Z?n)。

加密，c=gmrnmodn2。

解密，m=L(cλmodn2)umodn。

2.4 安全性

假設(shè)Alice與Bob都是半誠實的參與者，Alice擁有私有數(shù)據(jù)x，Bob擁有私有數(shù)據(jù)y，他們希望合作計算函數(shù)F∶(x,y)→ ( )f1(x,y),f2(x,y)而不泄露各自擁有的私有數(shù)據(jù)x和y。即Alice與Bob保證各自提供私有數(shù)據(jù)真實的前提下，嚴格按照協(xié)議的流程執(zhí)行，不會中途退出或更改協(xié)議執(zhí)行的步驟，但有可能會保留中間過程產(chǎn)生的結(jié)果用于推算對方的隱私數(shù)據(jù)。設(shè)P為計算函數(shù)F的協(xié)議，當輸入為(x,y)時,記為Alice（Bob）在執(zhí)行協(xié)議P的過程中所得到的消息序列，是,其中r1(r2)表示Alice（Bob）獨立的硬幣拋投結(jié)果；表示Alice（Bob）第i次收到的信息。記為Alice（Bob）得到的輸出結(jié)果。

定義1（半誠實參與者的保密性[28]）對于一個函數(shù)F，如果存在概率多項式時間算法S1與S2（也稱這樣的多項式時間算法為模擬器）使得：

則稱P保密地計算函數(shù)F（其中表示計算上不可區(qū)分）。

3 安全多方計算方案

3.1 空間兩平行直線間距離問題的解決方案1

文獻[25]雖然解決了空間兩條平行直線間的距離問題，但是因為利用不經(jīng)意傳輸協(xié)議，其計算復雜度和通信復雜度很高。本文根據(jù)幾何學知識和安全兩實數(shù)和平方計算協(xié)議理論提出了三維空間兩平行直線間的距離計算協(xié)議。首先，該協(xié)議是針對三維空間兩平行直線的標準式提出的；然后，根據(jù)三維空間點到直線的距離推導出三維空間兩條平行直線間的距離；最后，通過安全兩實數(shù)和平方協(xié)議計算出輔助數(shù)據(jù)，使Alice和Bob只知道他們隱私數(shù)據(jù)和的平方值，但永遠不可能知道對方數(shù)據(jù)的具體值。此協(xié)議在通信安全保密中的優(yōu)勢：文獻[25]空間兩平行直線間距離的保密計算協(xié)議共調(diào)用6次不經(jīng)意傳輸協(xié)議和6次點積協(xié)議，本文中SSTS協(xié)議只調(diào)用3次點積協(xié)議。文獻[25]計算復雜度是12(m+1)lgk,而SSTS協(xié)議的計算復雜度是6mlgk；文獻[25]通信復雜度是6(m+1)，而SSTS協(xié)議的通信復雜度是3m+1?？傊?，在計算復雜度和通信復雜度上，SSTS協(xié)議比文獻[25]至少降低了50%。由于SSTS協(xié)議使用了安全兩實數(shù)和平方計算協(xié)議，即點積協(xié)議，本協(xié)議的安全性主要依賴于點積協(xié)議。對于點積協(xié)議，在輸入階段，Alice和Bob分別通過隨機值來掩蓋其隱私向量；協(xié)議執(zhí)行后，Alice和Bob都只能獲得點積的計算值而無法得知對方的向量值。

假設(shè)空間有一點P1(x1,y1,z1)和一條直線，取直線t2上的一點M0(x2,y2,z2)，設(shè)M0P1與直線t2方向向量e=ai+bj+ck所成夾角為θ，則P1到直線e(t2)的距離應(yīng)為。如圖1所示，,則：

最外面“||”表示矢量取模。

對于三維空間兩平行直線t1、t2，取t1上點P1(x1,y1,z1)，P1到t2的距離即為三維空間兩條平行直線間的距離。

方案的主要思想是基于點到直線的距離保密地推導出三維空間兩條平行直線間的距離。假設(shè)Alice擁有一條保密直線t1，在t1上選擇一個保密的點P1(x1,y1,z1)，Bob擁有一條保密直線t2，他們分別利用安全兩實數(shù)和平方計算協(xié)議計算輔助數(shù)據(jù)，最后計算出三維空間兩條平行直線間的距離d。

協(xié)議2保密地計算出空間兩平行直線間的距離（此協(xié)議記為SSTS協(xié)議）。

Fig.1 Distance of pointP1to straight linet2圖1 點P1到直線t2的距離

輸出：Alice與Bob合作計算t1和t2間的距離d。

步驟1 Alice在t1上選擇一個保密的點P1(x1,y1,z1)，并計算(y1c-z1b)，Bob在t2上選擇一個保密的點P2(x2,y2,z2)，并計算(z2b-y2c)；Alice與Bob分別利用安全兩實數(shù)(y1c-z1b),(z2b-y2c)和平方計算協(xié)議，保密計算[(y1c-z1b)+(z2b-y2c)]2；經(jīng)計算，Alice得到，Bob得到，使得。

步驟2 Alice計算(z1a-x1c),Bob計算(x2c-z2a);Alice與Bob分別利用安全兩實數(shù)(z1a-x1c),(x2c-z2a)和平方計算協(xié)議，保密計算；經(jīng)計算，Alice得到，Bob得到，滿足。

步驟3 Alice計算(x1b-y1a)，Bob計算(y2a-x2b);Alice與Bob分別利用安全兩實數(shù)(x1b-y1a),(y2a-x2b)和平方計算協(xié)議，保密計算；經(jīng)計算，Alice得到，Bob得到，滿足。

步驟5 Bob計算F,并將F發(fā)送給Alice。

定理1 SSTS協(xié)議能正確計算出三維空間兩平行直線間的距離。

本文根據(jù)SSTS協(xié)議的具體驗算過程如下。

Alice和Bob合作計算后得到的信息分別為Alice：。

Alice計算：

Bob計算：

Alice收到Bob的信息，計算：

Alice計算得到d，但Alice無法從d這個式子中得到關(guān)于Bob的任何信息。整個過程中沒有泄露任何信息，并且完成了三維空間兩平行直線間的距離計算，正確性得以證明。

定理2 SSTS協(xié)議能安全計算出三維空間兩平行直線間的距離。

在SSTS協(xié)議中，首先假定參與的兩方Alice和Bob是半誠實的，在協(xié)議執(zhí)行后，Alice和Bob都只能獲得自己輔助數(shù)據(jù)的值，無法得知對方的具體值。

在輸入階段，Alice的輸入為保密直線l1，Bob的輸入為保密直線l2。步驟1～步驟3，Alice和Bob先分別選擇自己直線上一個保密的點；然后，分別計算出自己數(shù)據(jù)的值；最后，分別利用安全兩實數(shù)和平方計算協(xié)議得到各自輔助數(shù)據(jù)的值。但Alice無法從中得到Bob值，Bob也無法從中得到Alice的值。步驟4，Alice對自己得到的輔助數(shù)據(jù)進行計算。步驟5，Bob也對自己得到的輔助數(shù)據(jù)進行計算，并將計算結(jié)果發(fā)送給Alice。步驟6，Alice收到Bob的信息后，計算得到M=E+F,E+F是Alice與Bob輔助數(shù)據(jù)的總和?？傊?，SSTS協(xié)議每一步都是隱私保護的，下面利用模擬器進行具體證明。

證明 通過構(gòu)造出使式（1）和（2）成立的模擬器S1和S2來證明其安全性。

（1）首先構(gòu)造模擬器S1使得式（1）成立。在SSTS協(xié)議中,其中t1、t2分別是Alice與Bob的輸入。

S1的模擬過程如下：

步驟1S1接受( )t1,f1(t1,t2)作為Alice的輸入，根據(jù)f1(t1,t2)的值，任意選定直線t2′，滿足f1(t1,t2′)=f1(t1,t2)，記。

S1利用安全兩實數(shù)和平方計算協(xié)議分別計算出的值。

步驟2S1根據(jù)的值計算出,進而計算出M′=E+F′。根據(jù)構(gòu)造過程知道f1(t1,t2′)=f1(t1,t2)。

步驟3S1根據(jù)M′、G的值，計算出。

因為

（2）類似地，還可以構(gòu)造S2使下式成立：

根據(jù)定義1可知此協(xié)議是安全的。 □

3.2 空間兩平行直線間距離問題的解決方案2

SSTS協(xié)議解決了空間兩條平行直線標準式的距離問題。現(xiàn)在研究空間兩條平行直線交面式距離問題的解決方案，Alice擁有一條保密直線L1，Bob擁有一條保密直線L2,Alice與Bob希望在不泄露自己直線方程系數(shù)的情況下，保密計算出空間兩平行線間的距離d。該方案的思想是基于Paillier同態(tài)加密方案提出了三維空間兩平行直線間的距離計算協(xié)議。首先，該協(xié)議是針對三維空間兩平行直線的交面式提出的；然后，利用Paillier同態(tài)加密方案將Alice直線方程的系數(shù)進行加密后發(fā)送給Bob，Bob利用Paillier同態(tài)加密方案進行計算后發(fā)送給Alice；最后，Alice和Bob合作計算出三維空間兩平行直線間的距離。此協(xié)議在通信安全保密中的優(yōu)勢：由3.1節(jié)可知文獻[25]計算復雜度是12(m+1)lgk，大約進行180次模指數(shù)運算，SSTS協(xié)議的計算復雜度是6mlgk，大約進行90次模指數(shù)運算；Pailler一次加密需要2次模指數(shù)運算，一次解密需要1次模指數(shù)運算，而PHEA協(xié)議共進行25次模指數(shù)運算。由3.1節(jié)可知文獻[25]通信復雜度是6(m+1)，SSTS協(xié)議的通信復雜度是3m+1；而PHEA協(xié)議中通信輪數(shù)為3?？傊?，在計算復雜度和通信復雜度上，PHEA協(xié)議效率最優(yōu)。PHEA協(xié)議主要利用了Paillier同態(tài)加密算法：（1）同態(tài)加密的特質(zhì)可以用對密文進行運算代替對明文的某些運算并取得同樣的效果，而不影響明文數(shù)據(jù)的保密性。（2）Paillier同態(tài)加密算法是基于計算和判斷上的n次剩余問題的困難性，并給出了一種能夠驗證消息完整性的加密算法，在隨機預言模型下證明了該加密算法能夠抵抗適應(yīng)性攻擊。

協(xié)議3保密地計算空間兩平行直線間的距離（此協(xié)議記為PHEA協(xié)議）。

輸出：Alice與Bob合作計算L1和L2間的距離d。

步驟1設(shè)(G,E,D)是Paillier同態(tài)加密方案，k是設(shè)定的安全參數(shù)，Alice運行G(k)生成同態(tài)加密的公鑰和私鑰，Alice向Bob公布生成的公鑰。

步驟2 Alice計算M1=(a1b2+a2b1),M2=(a1c2+a2c1),M3=(a1d2+a2d1),M4=2b1b2,M5=(b1c2+b2c1),M6=(b1d2+b2d1),M7=2c1c2,M8=(c1d2+c2d1),M9=(b1c2-b2c1)2+(c1a2-c2a1)2+(a1b2-a2b1)2，對Mi(i=1,2,…,8)用公鑰進行加密，E(L)=E(Mi)，并將E(L)發(fā)送給Bob。

步驟3 Bob計算N1=(c3d4-c4d3),N2=(b3d4-b4d3),N3=(b3c4-c3b4),B=1/N23選 取 隨 機 數(shù)R1、R2、R3、R4、R5、R6、R7、R8、R9,然后分別利用 Paillier同態(tài)加密方案計算出：

并將B發(fā)送給Alice。

步驟4 Alice收到Bob的消息后用私鑰將Wi(i=1,2,…,9)進行解密，并計算出Q1、Q2、Q3。

利用解密得到的Wi(i=1,2,3,4,5,6,7,8,9)計算出Qi(i=1,2,3),其中，Q1=(W1-W2+W3)2,Q2=(W4-W5+W6)2,Q3=(W7-W8+W9)2,則,并將A發(fā)送給Bob。

定理3 PHEA協(xié)議能正確計算出三維空間兩平行直線間的距離。

證明（1）當a1b2-a2b1≠0時，空間兩平行直線間的距離公式：

（2）當a2c1-a1c2≠0時，空間兩平行直線間的距離公式：

（3）當b1c2-b2c1≠0時，空間兩平行直線間的距離公式：

A的代數(shù)余子式：

ni是平面πi的法向量。

下面根據(jù)PHEA協(xié)議以情況（3）為例進行具體驗算。

Alice直線的密文信息：

Bob收到Alice的密文信息，計算：

Alice收到Bob的信息后，解密得到：

并計算：

但Alice無法從d這個式子中得到關(guān)于Bob的任何信息。整個過程中沒有泄露任何信息，并且完成了三維空間兩平行直線間的距離計算，正確性得以證明。 □

定理4 PHEA協(xié)議能安全計算出三維空間兩平行直線間的距離。

為了能夠證明PHEA協(xié)議在半誠實模型下的保密性，只需要去驗證協(xié)議各方的輸入輸出，然后進行模擬分析。因為在PHEA協(xié)議中沒有可信的第三方，所以只需從Alice和Bob的視角來分析其輸入輸出，并作出相應(yīng)的保密性分析即可。

對于Alice，Alice的輸入為保密直線l1，Alice收到Bob的消息，用私鑰進行解密操作后，Alice得到的是一系列數(shù)字，但這些數(shù)字中并不包含Bob直線的任何信息值，僅僅是隨機數(shù)。因此，從Alice的角度來講滿足隱私性的要求。

對于Bob，Bob的輸入為保密直線l2，Alice對自己的隱私數(shù)據(jù)用公鑰進行加密后發(fā)送給Bob，但Bob并不知道Alice的私鑰，所以Bob無法獲取Alice直線的任何信息。因此，從Bob的角度來講滿足隱私性的要求。

總之，PHEA協(xié)議對于Alice和Bob都是隱私保護的，下面利用模擬器進行具體證明。

證明 通過構(gòu)造出使式（1）和（2）成立的模擬器S1和S2來證明其安全性。

（1）首先構(gòu)造模擬器S1使得式（1）成立。

在解決方案2中：

其中，L1、L2分別是Alice與Bob的輸入；E(L)是L的密文。

S1的模擬過程如下：

步驟1S1接受(L1,f1(L1,L2))作為Alice的輸入，根據(jù)f1(L1,L2)的值，任意選定直線L2′，滿足

S1分別計算出M1,M2,…,M9,B′的值。

步驟 2S1任意選取 9 個隨機數(shù)R1′,R2′,…,R9′，使得R3′=R2′-R1′,R6′=R5′-R4′,R9′=R8′-R7′,用同樣的方法加密Mi(i=1,2,…,8),并且分別計算出W1′,W2′,…,W9′,Q1′,Q2′,Q3′,A′的值。根據(jù)構(gòu)造過程知道f1(L1,L2′)=f1(L1,L2)。

步驟 3S1根據(jù)A′、B′的值，計算出d′=A′?B′,則為空間兩條平行直線間的距離。

（2）類似地，還可以構(gòu)造S2使下式成立：

4 復雜性分析

計算復雜性：文獻[25]空間兩平行直線間距離的保密計算協(xié)議共調(diào)用6次不經(jīng)意傳輸協(xié)議和6次點積協(xié)議。本文SSTS協(xié)議共調(diào)用3次點積協(xié)議，PHEA協(xié)議進行了8次加密運算，9次解密運算。假設(shè)安全參數(shù)為m，一次不經(jīng)意傳輸協(xié)議至少需要2lgk次模指數(shù)運算，一次點積協(xié)議至少需要2mlgk次模指數(shù)運算，文獻[25]共需12(m+1)lgk次模指數(shù)運算。一般情況下當m＞5,k＞8時才能達到基本的安全級別，故至少需要180次模指數(shù)運算。本文SSTS協(xié)議至少需要6mlgk次模指數(shù)運算，Pailler一次加密需要2次模指數(shù)運算，一次解密需要1次模指數(shù)運算，PHEA協(xié)議共進行25次模指數(shù)運算。

通信復雜性：衡量通信復雜性的指標可以采用協(xié)議交換的比特數(shù)或通信輪數(shù)，在安全多方計算研究中通常用通信輪數(shù)來衡量計算復雜性。文獻[25]通信輪數(shù)為6(m+1)次，本文SSTS協(xié)議通信輪數(shù)為3m+1次，PHEA協(xié)議通信輪數(shù)為3。各方案復雜性比較如表1所示。

Table1 Complexity comparison of schemes表1 各方案復雜性比較

因此本文協(xié)議計算效率和通信效率更高，適用范圍更廣。

5 結(jié)束語

在半誠實模型下，基于安全兩實數(shù)和平方計算協(xié)議和Paillier同態(tài)加密方案分別提出了計算空間兩平行直線間的SSTS和PHEA距離協(xié)議，有效降低了計算復雜度和通信復雜度，并且對SSTS和PHEA協(xié)議的正確性和安全性分別進行了證明。因為SSTS和PHEA協(xié)議都是基于半誠實模型的，當然還有不足之處，在惡意模型下對安全多方空間兩平行直線距離協(xié)議進行研究和分析會比較困難，所以未來將繼續(xù)對此進行探討并推廣到其他應(yīng)用領(lǐng)域。

[1]Yao A C C.Protocols for secure computations[C]//Proceedings of the 23rd Annual Symposium on Foundations of Computer Science,Chicago,USA,Nov 3-5,1982.Washington:IEEE Computer Society,1982:160-164.

[2]Goldreich O,Micali S,Wigderson A.How to play ANY mental game[C]//Proceedings of the 19th Annual ACM Symposium on Theory of Computing,New York,May 25-27,1987.New York:ACM,1987:218-229.

[3]Kaushik M,Jain A.Challenges to big data security and privacy[J].International Journal of Computer Science and Information Technologies,2014,5(3):3042-3043.

[4]Bertino E.Big data-security and privacy[C]//proceedings of the 2015 International Congress on Big Data,New York,Jun 27-Jul 2,2015.Washington:IEEE Computer Society,2015:757-761.

[5]Thuraisingham B M.Big data security and privacy[C]//Proceedings of the 5th Conference on Data and Application Security and Privacy,San Antonio,USA,Mar 2-4,2015.New York:ACM,2015:279-280.

[6]Patil H K,Seshadri R.Big data security and privacy issues in healthcare[C]//Proceedings of the 2014 International Congress on Big Data,Anchorage,USA,Jun 27-Jul 2,2014.Washington:IEEE Computer Society,2014:762-765.

[7]Erlich Y,Narayanan A.Routes for breaching and protecting genetic privacy[J].Nature Reviews Genetics,2014,15(6):409-421.

[8]Xie Wei,Kantarcioglu M,Bush W S,et al.SecureMA:protecting participant privacy in genetic association metaanalysis[J].Bioinformatics,2014,30(23):3334-3341.

[9]Sandfuchs B.Privacy nudges:an introduction[M]//Akrivopoulou C M.Protecting the Genetic Self from Biometric Threats:Autonomy,Identity,and Genetic Privacy.Hershey,USA:IGI Global,2015:256-264.

[10]Lindell Y,Pinkas B.Secure multiparty computation for privacy-preserving data mining[J].Journal of Privacy&Confidentiality,2008,25(2):761-766.

[11]Li Shundong,Wu Chunying,Wang Daoshun,et al.Secure multiparty computation of solid geometric problems and their applications[J].Information Sciences,2014,282:401-413.

[12]Du Wenliang,Atallah M J.Privacy-preserving cooperative scientific computations[C]//Proceedings of the 14th Computer Security Foundations Workshop,Cape Breton,Canada,Jun 11-13,2001.Washington:IEEE Computer Society,2001:273-294.

[13]Luo Yonglong,Huang Liusheng,Jing Weiwei,et al.Privacypreserving cross product protocol and its applications[J].Chinese Journal of Computers,2007,30(2):248-254.

[14]Li Shundong,Dai Yiqi,Wang Daoshun,et al.Secure multiparty computations of geometric intersections[J].Journal of Tsinghua University:Science and Technology,2007,47(10):1692-1695.

[15]Atallah M J,Du Wenliang.Secure multi-party computational geometry[C]//LNCS 2125:Proceedings of the 7th International Workshop on Algorithms and Data Structures,Providence,USA,Aug 8-10,2001.Berlin,Heidelberg:Springer,2001:165-179.

[16]Li Shundong,Dai Yiqi.Secure two-party computational geometry[J].Journal of Computer and Technology,2005,20(2):258-263.

[17]Luo Yonglong,Huang Liusheng,Zhong Hong.Secure twoparty point-circle inclusion problem[J].Journal of Computer and Technology,2007,22(1):88-91.

[18]Luo Yonglong,Huang Liusheng.A secure protocol for determining whether a point is insider a convex polygon[J].Chinese Journal of Electronics,2006,15(4):578-582.

[19]Chen Li,Lin Bogang.Privacy-preserving point-inclusion twoparty computation protocol[C]//Proceedings of the 4th International Conference on Computational and Information Sciences,Shiyan,China,Jun 21-23,2013.Washington:IEEE Computer Society,2013:257-260.

[20]Li Shundong,Wang Daoshun,Dai Yiqi.Efficient secure multiparty computational geometry[J].Chinese Journal of Electronics,2010,19(2E):324-328.

[21]Liu Liang,Wu Chunying,Li Shundong.Two privacy-preserving protocols for point-curve Relation[J].Journal of Electronics,2012,29(5):422-430.

[22]Liu Wen,Luo Shoushan,Yang Yixian,et al.A study of secure two-party circle computation problem[J].Journal of Beijing University of Posts and Telecommunications,2009,32(3):32-35.

[23]Luo Yonglong,Huang Liusheng,Jing Weiwei,et al.Privacy protection in the relative position determination for two spatial geometric objects[J].Journal of Computer Research and Development,2006,43(3):410-416.

[24]Zhong Hong,Sun Yanfei,Yan Feifei,et al.Privacy-preserving relative position calculation protocols for spatial geometric objects[J].Journal of Harbin Engineering University,2011,32(4):458-463.

[25]Xin Xin,Hao Lin,Tang Yu.Privacy-preserving computational protocol on minimum distance between two three-dimension parallel straight line[J].Application Research of Computers,2013,30(5):1530-1532.

[26]Frederick R.Core concept:homomorphic encryption[J].Proceedings of the National Academy of Sciences,2015,112(28):8515-8516.

[27]Wu Jiehong,Zhang Po,Shi Xiangbin.Research of MA protection based on addition-multiplication homomorphism and composite function technology[J].Journal of Chinese Computer Systems,2012,33(10):2223-2226.

[28]Reimer B,Fried R,Mehler B,et al.Brief report:examining driving behavior in young adults with high functioning autism spectrum disorders:a pilot study using a driving simulation paradigm[J].Journal of Autism&Developmental Disorders,2013,43(9):2211-2217.

附中文參考文獻：

[13]羅永龍,黃劉生,荊巍巍,等.保護私有信息的叉積協(xié)議及其應(yīng)用[J].計算機學報,2007,30(2):248-254.

[14]李順東,戴一奇,王道順,等.幾何相交問題的多方保密計算[J].清華大學學報:自然科學版,2007,47(10):1692-1695.

[22]劉文,羅守山,楊義先,等.安全兩方圓計算協(xié)議[J].北京郵電大學學報,2009,32(3):32-35.

[23]羅永龍,黃劉生,荊巍巍,等.空間幾何對象相對位置判定中的私有信息保護[J].計算機研究與發(fā)展,2006,43(3):410-416.

[24]仲紅,孫彥飛,燕飛飛,等.保護私有信息幾何對象的相對位置計算[J].哈爾濱工程大學學報,2011,32(4):458-463.

[25]辛欣,郝林,湯瑜.空間兩平行直線間距離的保密計算協(xié)議[J].計算機應(yīng)用研究,2013,30(5):1530-1532.

[27]吳杰宏,張坡,石祥濱.基于加乘同態(tài)與組合函數(shù)技術(shù)的MA保護研究[J].小型微型計算機系統(tǒng),2012,33(10):2223-2226.

2016-08,Accepted 2017-01.

Secure Multi-Party Computation on Spatial Distance Between Two Parallel Straight Lines*

YU Jinxia1,ZHAO Cuiping1,ZHANG Jing1,2,TANG Yongli1+
1.College of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China
2.School of Computer and Information Technology,Beijing Jiaotong University,Beijing 100044,China
+Corresponding author:E-mail:yltang@hpu.edu.cn

To improve the computational efficiency of the distance between two three-dimension parallel straight lines,this paper proposes two protocols of a secure square of two real numbers sum protocol(SSTS)and Paillier homomorphic encryption algorithm(PHEA).Firstly,SSTS is to derive the distance between two three-dimension parallel straight lines by the distance from a point to a straight line,and it constructs auxiliary data to hide their own specific data by a secure square of two real numbers sum protocol.Secondly,PHEA uses Paillier homomorphic encryption algorithm to hide linear equation coefficient.Parties can communicate with each other,but will not reveal their specific data.Two protocols are confidential to calculate the distance between two three-dimension parallel straight lines.In addition,this paper proves the validity of two protocols,and proves the security by the simulation example.Finally,this paper analyzes the computation complexity and communication complexity of SSTS and PHEA with the existing protocol.The results show that the new protocols are at least 50%less than that of the existing protocol.

privacy-preserving computational geometry;space distance;secure square of two real numbers sum;homomorphic encryption;simulation paradigm

10.3778/j.issn.1673-9418.1608069

*The National Natural Science Foundation of China under Grant No.61300216(國家自然科學基金);the International Science and Technology Cooperation Program of Science and Technology Office of Henan Province under Grant No.152102410048(河南省科技廳國際科技合作計劃);the Research of Basic and Advanced Technology of Henan Province under Grant No.142300410147(河南省基礎(chǔ)與前沿技術(shù)研究);the Natural Science Research Project of Education Department of Henan Province under Grant Nos.12A520021,16A520013(河南省教育廳自然科學研究項目).

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-01-05,http://www.cnki.net/kcms/detail/11.5602.TP.20170105.0828.002.html

YU Jinxia,ZHAO Cuiping,ZHANG Jing,et al.Secure multi-party computation on spatial distance between two parallel straight lines.Journal of Frontiers of Computer Science and Technology,2017,11(11)：1764-1774.

A

TP309

YU Jinxia was born in 1974.She received the Ph.D.degree in artificial intelligence from Central South University in 2007.Now she is a professor at Henan Polytechnic University.Her research interests include artificial intelligence and information security,etc.

于金霞（1974—)，女，河南博愛人，2007年于中南大學獲得博士學位，現(xiàn)為河南理工大學教授，主要研究領(lǐng)域為人工智能，信息安全等。

ZHAO Cuiping was born in 1989.She is an M.S.candidate at Henan Polytechnic University.Her research interests include information security and cryptology,etc.

趙翠平（1989—），女，河南商水人，河南理工大學碩士研究生，主要研究領(lǐng)域為信息安全，密碼學等。

ZHANG Jing was born in 1978.Now she is an associate professor at Henan Polytechnic University.Her research interests include network and information security,secure multi-party computation,etc.

張靜（1978—），女，河南焦作人，河南理工大學計算機科學與技術(shù)學院副教授，主要研究領(lǐng)域為網(wǎng)絡(luò)與信息安全，安全多方計算等。

TANG Yongli was born in 1972.He received the Ph.D.degree in cryptology from Beijing University of Posts and Telecommunications in 2008.Now he is an associate professor at Henan Polytechnic University.His research interests include information security and cryptology,etc.

湯永利（1972—），男，河南孟州人，2008年于北京郵電大學獲得博士學位，現(xiàn)為河南理工大學副教授，主要研究領(lǐng)域為信息安全，密碼學等。