點包含問題的安全多方計算

楊曉藝，劉 新，亢 佳

(陜西師范大學 計算機科學學院，陜西 西安 710119)

點包含問題的安全多方計算

楊曉藝，劉 新，亢 佳

(陜西師范大學 計算機科學學院，陜西 西安 710119)

安全多方計算是近年來國際密碼學界研究的熱點問題，計算幾何的多方保密計算越來越受到重視，點包含問題的多方保密計算作為保密計算幾何中的一個重要問題也越來越受到關注。考慮到要保密地解決點包含的問題，基于安全多方計算的幾個基礎協議，即向量點積協議和姚式百萬富翁協議，設計了一個可以保密判斷線段是否相交的協議，基于此協議的核心思想同時聯系相關幾何知識，設計了可以保密判斷點包含問題的協議，理論分析結果表明所設計的協議在半誠實模型下是正確的和安全的。它們作為重要的安全多方計算基礎協議對解決保密計算幾何其他相關問題有著重要的實用價值，可以用來進一步解決兩個或多個圖形是否相交的問題、多個點是否包含在一個圖形中的問題等。

安全多方計算；保密計算幾何；點包含問題；線段相交問題

0 引 言

安全多方計算是近年來國際密碼學界的一個研究熱點。這一研究領域由Yao[1]在1982年提出，Goldreich等[2-3]豐富和發展了安全多方計算的理論。安全多方計算包含了密碼學中很多的基本模塊，具有很大的實用價值，因此受到了越來越多的關注。

安全多方計算的研究在密碼學研究中占有非常重要的地位。Goldwasser曾預言[4]，安全多方計算今天所處的地位正是公開密鑰密碼學10年前所處的地位，成為密碼學領域里一個極端重要的工具;豐富的理論將使它成為計算領域一個必不可少的組成部分；它在現實中的應用才剛剛開始，豐富的理論將使它成為計算科學中一個必不可少的組成部分。Goldwasser的這一預言激勵著密碼學者的不斷研究和探索。Goldreich的工作[2-3,5]奠定了安全多方計算的理論基礎，即一般的安全多方計算問題理論上都是可解的。但是Goldreich指出，應用一般條件下導出的通用解決方案解決具體問題是不切實際的-效率問題很難解決，因此對于具體問題需要研究具體的解決方案。

Goldwasser的預言和Goldreich的理論促進了具有實際應用背景的安全多方計算問題的研究，所研究的問題包括比較百萬富翁問題[1,6]、保密的計算幾何問題[7-8]、保密的數據挖掘問題[9]、保密拍賣問題[10]等等。

幾何是科學研究中一個非常重要的分支，現實中的許多問題都可以通過一定的方式轉成幾何問題進行恰當表達。計算幾何問題的保密計算是安全多方計算中一個新的研究方向，這些問題具有廣泛的應用背景[11]。Du等研究了保密的計算幾何問題中的兩線段相交問題并給出了解決方案[12]，Luo等研究了兩直線之間的位置關系的保密計算問題[13]。在Du的啟發下，很多研究人員也開始對保密計算幾何問題進行深入研究[13-18]。點包含問題就是計算幾何問題中的一個研究熱點，基于此問題的研究已有很多。

利用安全多方計算領域的兩個基礎協議-向量點積協議與姚式百萬富翁協議，在半誠實模型下，設計了一個可以保密地判斷一私有點與一私有多邊形的包含關系的協議，在很大程度上解決了現實生活中的某些實際問題。

1 預備知識

1.1 安全性定義

半誠實參與者[19]：每個參與者都是完全嚴格按照協議的規定執行協議的每一步，并且在協議執行過程中不會惡意輸入虛假數據，也不會中途退出協議。但是它們可能會通過分析和利用協議交互過程中自己所得到的信息來推斷其他參與方的相關私有輸入信息。

大部分安全多方計算的研究工作都是假設參與者是半誠實的，這是因為Goldreich曾經指出：只要能夠在半誠實參與者模型下設計出保密計算f的協議π，就可以通過位承諾方法將π轉換成惡意攻擊者參與的模型下保密計算f的協議[3]。在這個轉換協議中，一個惡意的參與者將被迫按照半誠實參與者的要求執行協議，否則將會被發現。簡單地說，半誠實參與者在協議執行過程中將完全按照協議要求執行協議，但他們可能會保留計算的中間結果試圖推導出其他參與者的輸入。半誠實模型不僅僅是一個重要的研究方法，而且為許多應用環境提供了一個很好的模型。

1.2 向量點積協議

1.3 姚式百萬富翁協議

問題描述：Alice有一個私有數據a，Bob有一個私有數據b，雙方希望在不泄露自身數據的情況下可以保密地比較兩個數據的大小，即得到a>b,a

1.4 向量叉積

兩個向量的叉積由下面的行列式確定：

兩個向量的叉積具有以下性質：

若叉積為正，那么v1在v2的順時針方向；若叉積為負，那么v1在v2的逆時針方向；若叉積為零，那么v1與v2共線。

定理1：若兩線段的端點分別在對方線段的兩側，則兩線段必相交。

2 問題描述及協議實現

基于預備知識中介紹的密碼學中的基本協議，對如何保密地判斷兩線段相交問題及點包含問題進行了描述，并對所提出協議的正確性和安全性進行了分析和討論。

2.1 線段相交問題的描述

協議1：線段相交問題的保密協議。

輸出：P與Q是否相交。

(3)Alice與Bob共同執行向量點積協議。

其中Alice得到u1,u3,v2,v4，Bob得到u2,u4,v1,v3。

(4)Alice與Bob共同執行4次姚式百萬富翁協議得到對應的ui,vi的大小。

(5)若下式中存在一個成立，則輸出P與Q是否相交，否則輸出不相交。

u1>v1∧u2v3∧u4

u1v2∧u3v4

u1>v1∧u2v4

u1v2∧u3>v3∧u4

協議1的正確性：Alice與Bob構造的向量做點積運算得到：

這正是一個叉積，因此可以根據叉積的正負也就是ui和vi的大小來判斷這兩向量的順逆時針。因此，若協議1步驟(5)中任一成立，則說明Alice的私有線段端點在Bob線段的兩側且Bob的私有線段端點在Alice線段的兩側，由定理1可知兩線段相交。

協議1的安全性：在協議1步驟(3)中，點積協議的結果分別是兩個人交叉得到，因此兩人無法根據一個結果推出對方線段的端點坐標信息。根據向量點積協議的安全性與姚式百萬富翁協議的安全性以及步驟(3)中的交叉處理可知，協議1在半誠實模型下是安全的。

2.2 點包含問題的描述

Alice有一個私有的多邊形Q，Q=(x1,y1),(x2,y2),…,(xn,yn)，其中每一對(xi,yi)表示多邊形各端點的坐標值。Bob有一個私有的點P，P=(xp,yp)。Alice與Bob想判斷點P是否在多邊形Q中，又不想泄露自己的私有信息，這一問題即為保密的判斷點包含的問題。

協議2：保密判斷點包含的協議。

輸入：Alice輸入多邊形Q=(x1,y1),(x2,y2),…,(xn,yn)，Bob輸入點P=(xp,yp)。

輸出：P在Q中或P不在Q中。

(1)Bob選擇一個隨機大整數r，構造一點P'=(r,yp)，令PP'近似看作一條射線；

(2)Alice與Bob共同執行協議1求得PP'與多邊形的各邊是否有交點(其中多邊形匯總的水平邊不參與計算)；

(3)若交點數為奇數，則輸出P在Q中，否則輸出P不在Q中。

協議2的正確性：由圖1可得協議2的正確性。

圖1 協議2的正確性說明

協議2的安全性：由協議1的安全性可知協議2在半誠實模型下是安全的。

3 結束語

保密計算幾何中的問題在現實生活的實際意義越來越重要，應用價值越來越高。通過利用向量點積協議、姚式百萬富翁協議以及其他一些相關幾何知識，提出了在半誠實模型下判斷兩線段是否相交問題和點包含問題的保密解決方案，同時分析和討論了這些協議的正確性和安全性。這兩個協議可以作為研究其他某些保密計算幾何問題的基礎協議，對于解決安全多方計算領域的其他相關問題也有重要的理論意義。在后面的工作中，將對協議的性能進行深入分析，進而提出更加安全、高效的解決方案，也會進一步研究多個點是否包含在一個圖形中的問題以及兩個或多個圖形是否相交的問題等。

[1]YaoA.Protocolsforsecurecomputations[C]//23rdannualsymposiumonfoundationsofcomputerscience.[s.l.]:IEEE,1982:160-164.

[2]GoldreichO，MicaliS，WigdersonA.Howtoplayanymentalgame[C]//ProceedingsofthenineteenthannualACMsymposiumontheoryofcomputing.[s.l.]:ACM,1987:218-229.

[3]GoldreichO.Foundationsofcryptography:volume2，basicapplications[M].[s.l.]:CambridgeUniversityPress，2004.

[4]GoldwasserS.Multipartycomputations:pastandpresent[C]//ProceedingsofthesixteenthannualACMsymposiumonprinciplesofdistributedcomputing.[s.l.]:ACM,1997:1-6.

[5]GoldreichO.Securemulti-partycomputation(workingdraft)[EB/OL].2002.http://www.wisdom.weizmann.ac.ilhomeodedpublic-htmlfoc.html.

[6] 李順東,戴一奇,游啟友.姚氏百萬富翁問題的高效解決方案[J].電子學報,2005,33(5):769-773.

[7]ShenC，ZhangHG，FengDG，etal.Surveyofinformationsecurity[J].ScienceinChinaSeriesF:InformationSciences，2007，50(3):273-298.

[8]CaoZ，ZhuH，LuR.Provablysecurerobustthresholdpartial

blindsignature[J].ScienceinChinaSeriesF:InformationSciences，2006，49(5):604-615.

[9]LindellY，PinkasB.Privacypreservingdatamining[J].JournalofCryptology，2002，15(3):177-206.

[10]CachinC.Efficientprivatebiddingandauctionswithanobliviousthirdparty[C]//Proceedingsofthe6thACMconferenceoncomputerandcommunicationssecurity.[s.l.]:ACM，1999:120-127.

[11]LiSD，WuCY，WangDS，etal.Securemultipartycomputationofsolidgeometricproblemsandtheirapplications[J].InformationSciences，2014，282:401-413.

[12]DuW，AtallahMJ.Securemulti-partycomputationproblemsandtheirapplications:areviewandopenproblems[C]//Proceedingsofnewsecurityparadigmsworkshop.NewYork:ACMPress，2001:13-22.

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

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

[15] 李順東,司天歌,戴一奇.集合包含與幾何包含的多方保密計算[J].計算機研究與發展,2005,42(10):1647-1653.

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

[17] 楊曉莉,李順東,左祥建.計算幾何問題的多方保密計算[J].密碼學報,2016,3(1):33-41.

[18] 羅永龍,黃劉生,徐維江,等.一個保護私有信息的多邊形相交判定協議[J].電子學報,2007,35(4):685-691.

[19] 李順東,王道順,戴一奇,等.兩個集合相等的多方保密計算[J].中國科學:信息科學,2009,39(3):305-310.

Secure Multi-party Computation for Point Inclusion Problems

YANG Xiao-yi，LIU Xin，KANG Jia

(School of Computer Science，Shaanxi Normal University，Xi’an 710119，China)

Secure multi-party computation is one of the hot spots in international cryptography research community in recent years，and more and more attention has been paid to the secure computational geometry.As an important problem of secure computational geometry,more interests have been paid on point-inclusion problem.A secure protocol for determining whether two segments are intersecting with several basic protocols,Scalar Product Protocol and Yao’s Millionaire’s Protocol,has been developed.Thus based on core of the protocol designed and related geometric knowledge,a secure protocol to solve the point-inclusion problem has been developed.Theoretical analysis results show that these two protocols are correct and secure under semi honest model.As a part of important secure multi-party computational protocols,they both imply important practical value in solving the problem of secure multi-party computational geometry and can be used to solve the problems,whether two or more graphics are intersected and whether multiple points are contained in a graphic etc..

secure multi-party computation;computational geometry;point-inclusion problem;segment-intersection problem

2016-06-17

2016-09-28 網絡出版時間：2017-03-13

中央高校基本科研業務費專項(GK20150417)；內蒙古自治區包頭市科技計劃項目(2014S2004-2-1-15)

楊曉藝(1993-)，女，碩士研究生，研究方向為計算機與網絡安全。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170313.1547.098.html

TP31

A

1673-629X(2017)05-0120-03

10.3969/j.issn.1673-629X.2017.05.025