點(diǎn)包含問題的安全多方計(jì)算

楊曉藝，劉 新，亢 佳

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

點(diǎn)包含問題的安全多方計(jì)算

楊曉藝，劉 新，亢 佳

(陜西師范大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，陜西 西安 710119)

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

安全多方計(jì)算；保密計(jì)算幾何；點(diǎn)包含問題；線段相交問題

0 引 言

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

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

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

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

利用安全多方計(jì)算領(lǐng)域的兩個基礎(chǔ)協(xié)議-向量點(diǎn)積協(xié)議與姚式百萬富翁協(xié)議，在半誠實(shí)模型下，設(shè)計(jì)了一個可以保密地判斷一私有點(diǎn)與一私有多邊形的包含關(guān)系的協(xié)議，在很大程度上解決了現(xiàn)實(shí)生活中的某些實(shí)際問題。

1 預(yù)備知識

1.1 安全性定義

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

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

1.2 向量點(diǎn)積協(xié)議

1.3 姚式百萬富翁協(xié)議

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

1.4 向量叉積

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

兩個向量的叉積具有以下性質(zhì)：

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

定理1：若兩線段的端點(diǎn)分別在對方線段的兩側(cè)，則兩線段必相交。

2 問題描述及協(xié)議實(shí)現(xiàn)

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

2.1 線段相交問題的描述

協(xié)議1：線段相交問題的保密協(xié)議。

輸出：P與Q是否相交。

(3)Alice與Bob共同執(zhí)行向量點(diǎn)積協(xié)議。

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

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

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

u1>v1∧u2v3∧u4

u1v2∧u3v4

u1>v1∧u2v4

u1v2∧u3>v3∧u4

協(xié)議1的正確性：Alice與Bob構(gòu)造的向量做點(diǎn)積運(yùn)算得到：

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

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

2.2 點(diǎn)包含問題的描述

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

協(xié)議2：保密判斷點(diǎn)包含的協(xié)議。

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

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

(1)Bob選擇一個隨機(jī)大整數(shù)r，構(gòu)造一點(diǎn)P'=(r,yp)，令PP'近似看作一條射線；

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

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

協(xié)議2的正確性：由圖1可得協(xié)議2的正確性。

圖1 協(xié)議2的正確性說明

協(xié)議2的安全性：由協(xié)議1的安全性可知協(xié)議2在半誠實(shí)模型下是安全的。

3 結(jié)束語

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

[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].電子學(xué)報(bào),2005,33(5):769-773.

[7]ShenC，ZhangHG，F(xiàn)engDG，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] 羅永龍,黃劉生,荊巍巍,等.空間幾何對象相對位置判定中的私有信息保護(hù)[J].計(jì)算機(jī)研究與發(fā)展,2006,43(3):410-416.

[14] 羅永龍，黃劉生，荊巍巍，等.保護(hù)私有信息的叉積協(xié)議及其應(yīng)用[J].計(jì)算機(jī)學(xué)報(bào)，2007，30(2):248-254.

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

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

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

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

[19] 李順東,王道順,戴一奇,等.兩個集合相等的多方保密計(jì)算[J].中國科學(xué):信息科學(xué),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 網(wǎng)絡(luò)出版時間：2017-03-13

中央高校基本科研業(yè)務(wù)費(fèi)專項(xiàng)(GK20150417)；內(nèi)蒙古自治區(qū)包頭市科技計(jì)劃項(xiàng)目(2014S2004-2-1-15)

楊曉藝(1993-)，女，碩士研究生，研究方向?yàn)橛?jì)算機(jī)與網(wǎng)絡(luò)安全。

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