空間位置關系的安全多方計算及其應用

張衛國 孫 嫚 陳振華 陳 娓

?

空間位置關系的安全多方計算及其應用

張衛國 孫 嫚*陳振華 陳 娓

(西安科技大學 西安 710054 )

空間位置關系的保密計算屬于安全多方計算中的空間幾何問題，在機密性商業、工程、軍事等方面有著重要的意義。但目前大多數空間幾何問題都是通過轉化為距離或數據對應成比例問題解決的，計算復雜性較高，且應用范圍受限。針對這些問題，該文先將原問題轉化為一個點是否為一個方程的解，再利用一種簡單高效的內積協議一次性解決了點線、點面、線線、線面、面面等5種空間位置關系的判定，并利用模擬范例證明了協議的安全性。該文方案并沒有利用任何公鑰加密算法，取得了信息論安全；并且由于問題的巧妙轉化，使得能解決的問題更加廣泛，效率也相對較高。

安全多方計算；位置關系；空間幾何；內積協議

1 引言

安全多方計算最早由文獻[1]提出，是指在不泄漏各方的輸入數據(隱私性)的條件下，能正確完成輸入數據的函數計算(正確性)。安全多方計算的特點使得人們能夠最大限度地利用私有數據完成所需的計算任務而不破壞數據的隱私性。因此它在統計分析[2]、保密關聯規則挖掘[3]、隱私保護聚類挖掘[4,5]、保密的幾何問題等方面有著廣泛的應用。

文獻[9]曾預言安全多方計算所處的地位就如同公鑰密碼學10年前所處的地位一樣重要，它是計算科學一個極其重要的工具，而實際應用才剛起步。因此豐富其理論將使它成為計算科學和現實應用中一個必不可少的工具。1987年，文獻[10]提出了一個通用方案來解決所有的安全多方計算問題。該文獻還指出，在大多數參與者是誠實的情況下，所有的安全多方計算問題均存在解決方案。這一完備性結論為以后的安全多方計算協議的研究提供了動力，也為安全多方計算的應用指出了樂觀的前景。后來，在文獻[11]中系統地總結了安全多方計算的研究成果，包括安全性定義、敵手模型的定義以及通用解決方案的描述。文獻[11]的工作成為大部分安全多方計算問題解決方案的理論基礎，其貢獻對整個密碼學領域都具有重大的影響。

文獻[12]在前人工作的基礎上，進一步研究了一些具體的安全多方計算問題及其應用，包括科學計算、幾何計算、統計分析等問題?？臻g幾何問題的保密計算也是安全多方計算中一個很重要的組成部分。針對于此，文獻[13]研究了安全兩方多邊形相交等問題。文獻[14]研究了點與平行線位置關系等問題。而位置關系問題的安全計算是空間幾何中的一個重要分支，在現實生活中應用廣泛。比如以下的場景：

為了摧毀一顆老化的氣象衛星，A, B兩國想合作在太空發射兩顆導彈來擊毀，但是在發射的過程中就有可能進行干擾或碰撞。但是為了各自利益都不愿意告訴對方自己所在的位置信息，那么A, B兩國如何在不泄露各自私有信息的前提下完成合作？

以上場景屬于保密軍事問題，轉化成數學模型就是判斷空間兩條直線是否相交，屬于安全多方計算中的空間保密位置判定問題，但目前這方面的研究文獻并不多。由于現實中很多問題都可以歸結為此問題。因此研究其理論意義對現實問題有著重要的應用價值。

針對點、線、面等空間位置關系的安全計算問題，以往的學者們提出了一些解決方案。文獻[15]利用四面體的體積將問題轉化為距離來判定點面、線面、面面的位置關系，但是若用該方法研究點線、線線的位置關系，我們無法在該條線上取3個不共線的點，繼而也不能構造一個四面體，那么就無法把四面體的體積轉化為距離來判定點線、線線的位置關系。因此該方法研究范圍受限。2006年，文獻[16]利用法向量與方向向量的關系，解決了線線、線面、面面位置關系的問題。該方案用到了多種基本協議：比較相等協議、點積協議，又利用了數據對應成比例協議；此外，又利用求距離的方法研究了點線、點面的位置關系。因此計算十分繁瑣。

以上方案由于轉化方法的問題，要不所解決的空間位置關系較少，研究范圍受限；要不，計算十分繁瑣，復雜性較高。針對此問題，本文首先將空間位置關系問題轉化為一個點是否為一個方程的解。避免了多次求距離或數據對應成比例的方法，從而提高了應用范圍和效率；其次，在將原問題轉化成該問題的基礎上，共設計了5個協議：(1)利用內積設計了點線位置關系的協議1、點面位置關系的協議2。(2)在協議1和協議2的基礎上，又設計了線與線位置關系的協議3、線與面位置關系的協議4、面與面位置關系的協議5；最后，文中5個協議都沒有利用任何公鑰加密算法，安全性級別較高，取得了信息論安全。

2 預備知識

2.1安全多方計算的安全性定義

(1)半誠實參與者：安全多方計算的協議運行環境分為半誠實參與者模型和惡意攻擊者模型[10, 17]，半誠實參與者指協議方將誠實地執行協議，不會篡改輸入和輸出信息，但可能會保留計算的中間結果，試圖推導出協議之外的信息或者他人的信息。

(2)半誠實模型下的安全性定義：文獻[10,17]利用比特承諾和零知識證明理論設計了一個編譯器，這個編譯器可以將在半誠實參與者條件下保密計算函數的協議自動生成在惡意參與者條件下也能保密計算的協議。新的協議可以迫使惡意參與者以半誠實方式參與協議的執行，否則就會被發現。因此大多數情況下，我們只設計半誠實模型下的協議。當我們設計出所需要的半誠實模型下的安全多方協議時，只要按照文獻[10,17]的通用轉化方法就可以將原協議轉化為惡意模型下的新協議?；谶@一結論，本文也只給出半誠實模型下的協議和相應的安全性模擬范例。

(2)

此定義說明了任何一方參與者視圖中的信息只能從自己輸入和所獲得的輸出中得到，即說明任何一方參與者視圖中不包含額外的信息，這樣就保證了在協議執行過程中，任何一方得不到其他方的私有信息。因此要證明一個兩方計算協議是保密的，就必須構造使得式(1)和式(2)成立的模擬器與。

2.2一個基本的保密內積協議

下面給出文獻[18]設計的一個信息論安全的保密內積協議(表1)。

表1信息安全保密內積協議

該協議通過構造一個不可逆的矩陣進行計算，由于沒有利用任何公鑰加密算法取得隱私保護，因此安全性級別較高，達到了信息論安全。

2.3 本文研究的問題

本文研究以下5個問題：

問題1 安全計算空間點與空間直線的位置關系：Alice有一個秘密的空間點, Bob有一條秘密的空間直線。Alice和Bob兩人想在不泄露給對方信息的條件下來判定點和直線的位置關系。

問題2 安全計算空間點與空間平面的位置關系：Alice有一個秘密的空間點, Bob有一個秘密的空間平面。Alice和Bob兩人想在不泄露給對方信息的條件下來判定點和平面的位置關系。

問題3 安全計算空間直線與空間直線的位置關系：Alice有一條秘密的空間直線, Bob也有一條秘密的空間直線。Alice和Bob兩人想在不泄露給對方信息的條件下來判定直線與直線的位置關系。

問題4 安全計算空間直線與空間平面的位置關系：Alice有一條秘密的空間直線, Bob有一個秘密的空間平面。Alice和Bob兩人想在不泄露給對方信息的條件下來判定直線與平面的位置關系。

問題5 安全計算空間平面與空間平面的位置關系：Alice有一個秘密的空間平面, Bob也有一個秘密的空間平面。Alice和Bob兩人想在不泄露給對方信息的條件下來判定平面與平面的位置關系。

3 解決方案

3.1問題的轉化和解決

本文把點與線、點與面的位置關系轉化為一個點是否為一個方程的解，進而提出一種高效的方法來保密判定點與線、點與面的位置關系。

以下協議假設所有的參與者都是在半誠實模型下，網絡之間傳輸都是公開信道。

3.2兩個具體的協議

協議1 安全計算點與線的位置關系

(2)Alice和Bob執行兩次2.2節的保密內積協議，可計算出向量與向量的內積和向量與向量的內積。

(3)如果兩次保密求內積的值都為零，則點在線上，否則其他情況都在線外。

分析：在協議1中，調用2.2節的內積協議。首先Alice和Bob一起生成不可逆矩陣，接著由于Alice隨機生成一個維的向量，所以即使Alice發送給Bob, Bob也得不到Alice的任何信息。其次，Bob用Alice發來的和向量計算內積，然后再生成階矩陣。由于矩陣是不可逆的，所以Bob把和發送給Alice, Alice也得不到Bob的任何信息。最后，Alice生成一個減法因子，進而求出所需的內積。因此，在整個協議中即保護了Alice的隱私性又保護了Bob的隱私性。

協議2 安全計算點與面的位置關系

(2) Alice和Bob執行一次2.2節的保密內積協議，可計算出向量與向量的內積。

(3) 如果保密求內積的值為零，則點在面上，否則點在面外。

分析：在協議2中，隱私安全性和協議1相同，不同的是在協議2中我們只進行一次保密內積協議，比協議1更簡潔更高效。

4 應用

本節將協議1和協議2作為基礎子協議，進一步判定了線與線、線與面、面與面的位置關系。

4.1問題的轉化

有別于前人方案利用距離的解決方法，本文是在其中一條直線上任取兩個點，然后把原問題轉化為這兩個點是否都屬于一個方程的解。進而保密判定了線與線、線與面、面與面的位置關系。

以下協議假設所有的參與者都是在半誠實模型下，網絡之間傳輸都是公開信道。

4.2具體協議

協議3 安全計算線與線的位置關系

步驟3 Alice和Bob執行4次2.2節的保密內積協議，即向量與向量的內積，向量與向量的內積，向量與向量的內積，向量與向量的內積。

步驟5 Alice用自己任意選取的這兩點表示這條直線所在方向向量, Bob取直線上的方向向量，根據2.2節的的保密內積協議，Alice可以得到，記該數的絕對值為。Bob可以得知，記該數的絕對值為。根據夾角公式，利用Hash函數判斷與是否相等，若，則，說明，即直線與直線平行，否則相交。

分析：在協議3中，我們首先用的是內積協議，隱私安全性和以上協議完全相同。不同的是在步驟5我們引進夾角公式和Hash函數。由內積協議我們可以知道，最終是Alice計算的值，只要Alice不告訴Bob的值，那么Alice的隱私性就可以保證。Bob也是如此。Hash函數是一個單向陷門函數，所以即使最后兩人知道的值，也不可能得知,的值。因此各自的隱私性都得到保護，所以協議安全。

協議4安全計算線與面的位置關系

步驟3 Alice和Bob執行兩次2.2節保密內積協議，即計算向量與向量的內積、向量與向量的內積。如果向量與向量和向量與向量的內積結果都為零，則直線在平面上，即重合；否則就是相交或者平行。如果是后者，轉入第4步。

步驟4 Alice用自己任意選取的這兩點表示這條直線所在方向向量, Bob取平面上任取一個向量，根據2.2節的的保密內積協議，Alice可以得到，記該數的絕對值為。Bob可以得知，記該數的絕對值為。根據夾角公式，利用Hash函數判斷與是否相等，若，則，說明，即直線與平面平行，否則相交。

分析：在協議4中，隱私安全性和協議3相同。

協議5 安全計算面與面的位置關系

步驟3 Alice和Bob執行3次保密內積協議，即計算向量與向量的內積，向量與向量的內積，向量與向量的內積。

步驟4 如果3次保密求內積的結果都為零，那么平面與平面重合；如果有其中一個或兩個不為零，那么平面與平面相交；如果都不為零，則轉為步驟5。

分析：在協議5中，隱私安全性和協議3、協議4相同。

5 安全性分析

在本節，應用2.1節的安全性模擬范例給出本文5個協議的安全性證明，由于協議1~協議5證明過程相似，而且協議2~協議5都是以協議1為基礎協議設計得到。安全性依賴于協議1保障。為了節省篇幅，我們以證明協議1安全性為主，而對于協議2~協議5，只給出安全性結論。

定理1 協議1保密判定點與線的位置關系。

用類似的方法可以證明協議2~協議5的安全性，這里不再一一贅述。

6 效率分析與比較

本節將本文的方案和文獻[15]、文獻[16]的方案在效率以及性能方面做一個分析和比較。

(1)計算復雜度：由于這些方案有的使用公鑰加密算法，有的未使用公鑰加密算法，而且在運算過程中都使用了多項式數乘運算，因此，把方案的加解密次數與數乘運算的個數作為衡量計算復雜性的指標。除了點線、線線外，本文與參考文獻共同研究的是點面、線面、面面3種空間位置關系。因此為了給出一個橫向比較，統一用本文方案(協議2、協議4、協議5)與文獻[15]文獻[16]中同類點面、線面、面面3種協議進行比較。

點面協議：文獻[15]進行數乘計算18次，加解密次數0次；文獻[16]進行數乘運算16次，加解密次數12次；而本文的協議2進行數乘運算4次，加解密次數0次。

線面協議：文獻[15]進行數乘計算9次，加解密次數0次；文獻[16]進行數乘運算21次，加解密次數21次；而本文的協議4進行數乘運算12次，加解密次數0次。

面面協議：文獻[15]進行數乘計算12次；加解密次數0次；文獻[16]進行數乘計算20次，加解密次數63次，而本文的協議5進行數乘計算16次，加解密次數0次。

(2)通信復雜度：衡量通信復雜度的指標用協議交換信息的比特數，或者用通信輪數，在多方保密計算研究中通常用輪數(round)。

(3)性能：以方案所能解決的問題以及安全性級別作為衡量性能的指標。

綜合以上分析，本文與現有文獻[15]文獻[16]在點面、線面、面面的效率對比如表2；本文與現有文獻[15]文獻[16]的性能對比如表3。

表2本文方案與現有方案的效率比較

表3本文方案與現有方案的性能比較

從表2可以看出，無論是從數乘個數、加解密次數還是通信復雜度方面做比較，本文所設計的3個協議都比文獻[16]中同類的各個協議的計算量少；而對于文獻[15]而言，雖然本文的協議4、協議5在數乘個數方面比其多，但是相差不大，且加解密次數相同，同時本文的協議2在各個方面都比其同類協議計算量少，因此，本文的效率相對較高。

從表3可以看出，文獻[15]解決空間中的點面、線面、面面3種位置關系；文獻[16]雖然研究了空間中的點線、點面、線面等5種位置關系，但是空間中的點線、點面協議并未使用作者新提出的方法，而是另外一種方法。而本文用同一種方法一次性解決了空間中的點線、點面、線面等5種位置關系。因此，本文的方法能解決的問題范圍更廣。

綜合以上，以往的方案或者計算復雜性較高，或者研究問題的范圍受限。而本文的方案在和信息論安全的參考文獻相比，在保持同樣安全性級別的情況下，我們能判斷的位置關系更多，即解決的問題范圍更廣；在和計算性安全的參考文獻相比，我們的方法具有通用性，可以一次性判斷空間多種位置關系，效率更高。

7 結論

空間位置關系的保密計算屬于安全多方計算中的空間幾何問題，現實中很多問題都能歸結于此。而已存在的方案大多把原問題轉化為距離或數據對應成比例問題來解決，計算復雜性較高，且應用范圍受限。本文首先將原問題轉化成一個點是否屬于一個方程的解，然后基于密碼學和數學中的知識解決了此問題。本文設計的5個協議，并沒有利用任何公鑰加密算法，取得了信息論安全；并且由于問題的巧妙轉化，使得本文方案能解決的問題更廣，效率也相對較高。

[1] YAO A C. Protocols for secure computations[C]. Proceedings of 23rd IEEE Symposiumon Foundations of Computer Science, Chicago, IL, USA, 1982: 160-164. doi: 10.1109/ SFCS.1982.38.

[2] KAMM L. Privacy-preserving statistical analysis using secure multi-party computation[D]. [Ph.D. dissertation], University of TARTU, 2015: 50-54.

[3] 劉峰, 薛安榮, 王偉. 一種隱私保護關聯規則挖掘的混合算法[J]. 計算機應用研究, 2012, 29(3): 1108-1109. doi: 10.3969/ j.issn.1001-3695.2012.03.084.

LIU Feng, XUE Anrong, and WANG Wei. Hybrid algorithm for privacy preserving association rules mining[J]., 2012, 29(3): 1108-1109. doi: 10.3969/ j.issn.1001-3695.2012.03.084.

[4] ROY B. Performance analysis of clustering in privacy preserving data mining[J].&, 2014, 5(4): 35-39.

[5] 崇志宏, 倪巍偉, 劉騰騰, 等. 一種面向聚類的隱私保護數據發布方法[J]. 計算機研究與發展, 2010, 47(12): 2083-2089.

CHONG Zhihong, NI Weiwei, LIU Tengteng,. A privacy-preserving data publishing algorithm for clustering application[J]., 2010, 47(12): 2083-2089.

[6] LI C and LIN B G. Privacy-preserving point-inclusion two-party computation protocol [C]. 2013 IEEE Fifth International Conferenceon on Computational and Information Sciences (ICCIS), Hubei, China, 2013: 257-260. doi: 10.1109/ICCIS.2013.75.

[7] 王珽, 羅文俊. 安全多方計算在空間幾何問題中的應用[J]. 計算機系統應用, 2015, 24(1): 156-160. doi: 10.3969/j.issn. 1003-3254.2015.01.029.

WANG Ting and LUO Wenjun. Applications of secure multi-party computation in spacegeometry problems[J].&, 2015, 24(1): 156-160. doi: 10.3969/j.issn.1003-3254.2015.01.029.

[8] QIN Jing, DUAN Hongwei, ZHAO Huawei,. A new lagrange solution to the privacy-preserving general geometric intersection problem[J]., 2014, 46(1): 94-99. doi:10.1016/j.jnca.2014. 08.004.

[9] GOLDWASSER S. Multi-party computations: Past and present[C]. Proceedings of the 16thAnnual ACM Symposium on Principles of Distributed Computing, New York, USA, 1997: 1-6. doi: 10.1145/259380.259405.

[10] GOLDRE O, MICALI S, and WIGDERSON A. How to play any mental game[C].Proceedings of the 19th Annual ACM Conference on Theory of Computing, New York,USA, 1987: 218-229.

[11] GOLDREICH O. Secure multi-party computation(draft)[OL].http://www.wisdow.weizmann.ac.il/~oded/pp.html,1998.

[12] DU W L and ATALLAH M J. Secure multi-party computation problems and their applications: A review and open problems[C]. Proceedings of the 2001 Workshop on New Security Paradigms, New York, USA, 2001: 11-22.

[13] 荊巍巍. 安全多方計算中若干基礎協議及應用的研究[D]. [博士論文], 中國科學技術大學, 2008. doi: 10.7666/d.y1270516.

JING Weiwei. Research on several basic protocols and application of secure multi-party, computation[D]. [Ph.D. dissertation], University of Science and Technology of China, 2008. doi: 10.7666/d.y1270516.

[14] 王珽, 羅文俊. 基于閾值的點線距離與位置關系保密判定協議[J]. 計算機工程與應用,2010, 46(13): 87-89. doi: 10.3778/ j.issn.1002-8331/.2010.13.026.

WANG Ting and LUO Wenjun. Privacy-preserving determination protocol for point-line distance and position relation based on threshold[J]., 2010, 46(13): 87-89. doi: 10.3778/j.issn. 1002-8331/.2010.13.026.

[15] LI Shundong, WU Chunying, WANG Daoshun,. Secure multiparty computation of solidgeometric problems and their applications[J]., 2014, 282(10):401-413. doi: 10.1016/j.ins.2014.04.004.

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

LUO Yonglong, HUANG Liusheng, JING Weiwei,. Privacy protection in the relativeposition determination for two spatial geometric objects[J]., 2006, 43(3): 410-416.

[17] GOLDREICH O. Foundations of Cryptography: Basic Applications[M]. London: CambridgeUniversity Press, 2004: 599-729.

[18] CLIFTON C, KANTARCIOGLU M, VAIDYA J,. Tools for privacy preserving distributed datamining[J]., 2002, 4(2): 28-34.

Secure Multi-party Computation of Spatial Relationship and Its Application

ZHANG Weiguo SUN Man CHEN Zhenhua CHEN Wei

(Xi’an University of Science and Technology, Xi’an 710054, China)

Privacy-preserving determination of spatial relationship belongs to spatial geometry problem in secure multiparty computation, which is significant to confidential business, engineering, military,. However, most existing schemes transform the original problem into the distance problem or the correspondingly proportional data problem, which makes the computation complexity high and the application range being limited. To deal with these problems, first, the original problem is transformed into whether a point is the solution of equation. Based on the technique, a simple and efficient scalar product protocol is adopted to determine five spatial relationships all at once: point and line, point and plane, line and line, line and plane, and plane and plane. In addition, the security of the proposed protocol is proved with simulation paradigm. The proposed scheme does not employ any public key encryption algorithm so as to achieve the information security. The analysis indicates the trick transformation makes the proposed scheme higher efficient and more applicable than the known schemes.

Secure multi-party computation; Position relationship; Spatial geometry; Scalar product protocol

TP309

A

1009-5896(2016)09-2294-07

10.11999/JEIT160102

2016-06-15；

2016-08-09

國家自然科學基金(U1261114)

The National Natural Science Foundation of China (U1261114)

孫嫚 sunman_xust@163.com

張衛國： 男，1964年生，教授，研究方向為信息安全與安全多方計算.

孫 嫚： 女，1990年生，碩士生，研究方向為安全多方計算.

陳振華： 女，1976年生，副教授，研究方向為秘密共享與安全多方計算.

陳 娓： 女，1992年生，碩士生，研究方向為安全多方計算.