隱私保護(hù)的點(diǎn)與任意多邊形位置關(guān)系判定*

張明武,冷文韜,沈 華

1.湖北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院,武漢430068

2.桂林電子科技大學(xué) 計(jì)算機(jī)與信息安全學(xué)院,桂林541004

3.智能地學(xué)信息處理湖北省重點(diǎn)實(shí)驗(yàn)室,武漢430074

1 引言

隨著移動(dòng)互聯(lián)網(wǎng)和大數(shù)據(jù)相關(guān)技術(shù)的不斷發(fā)展,人類社會(huì)的信息量越來越多,隱私問題日益突出.例如,為了讓企業(yè)領(lǐng)導(dǎo)者了解員工是否到達(dá)指定的工作區(qū)域,員工需要報(bào)告自己的具體坐標(biāo)位置,同時(shí)員工也被告知工作區(qū)域的具體信息.員工的具體坐標(biāo)位置屬于員工的個(gè)人隱私信息,工作區(qū)域的具體信息屬于企業(yè)的隱私信息,因此,上述應(yīng)用場景中存在隱私泄漏問題.如何在不泄漏員工隱私信息和企業(yè)隱私信息的條件下企業(yè)領(lǐng)導(dǎo)者可以了解掌握員工到達(dá)指定工作區(qū)域的情況,是一個(gè)亟待解決的問題.在另外一個(gè)應(yīng)用場景中,某個(gè)調(diào)查機(jī)構(gòu)需要調(diào)查統(tǒng)計(jì)指定區(qū)域的車流量情況,為了保證調(diào)查的有效性該調(diào)查機(jī)構(gòu)必須保密被調(diào)查區(qū)域的信息同時(shí)利用車輛的位置信息得到統(tǒng)計(jì)結(jié)果.車輛的位置信息屬于車輛使用者的隱私信息,因此,該應(yīng)用場景中也存在隱私泄漏問題.如何在不泄漏車輛位置信息和被調(diào)查區(qū)域信息的條件下調(diào)查機(jī)構(gòu)獲得該區(qū)域的車流量情況,也是一個(gè)值得研究的問題.上述這些問題可以被抽象為具有具有隱私保護(hù)的點(diǎn)與多邊形關(guān)系判定問題,該問題主要涉及到具有隱私保護(hù)的多方幾何計(jì)算.具有隱私保護(hù)的多方幾何計(jì)算屬于安全多方計(jì)算(secure multi-party computation,SMC)[1–3]研究領(lǐng)域.SMC 實(shí)現(xiàn)了在分布式環(huán)境下,多個(gè)互不信任的參與者在不泄漏自己輸入的前提下協(xié)作完成指定的計(jì)算.SMC 的具體應(yīng)用領(lǐng)域主要有:數(shù)據(jù)挖掘[4]、計(jì)算幾何[5]、比特幣交易[6]等.

點(diǎn)與多邊形的位置關(guān)系判定[7](point-in-polygon problem,PIPP)是計(jì)算幾何中的常見問題.解決該問題的方法有射線法[8]和面積法以及夾角法[9]等.其中射線法是指,通過判定點(diǎn)引出一條射線,計(jì)算該射線與多邊形的交點(diǎn)數(shù),若交點(diǎn)的數(shù)為奇數(shù),則坐標(biāo)點(diǎn)在多邊形內(nèi)部,否則坐標(biāo)點(diǎn)在多邊形外[8].在具有隱私保護(hù)的點(diǎn)與多邊形關(guān)系判定問題中,參與雙方中的一方擁有一個(gè)點(diǎn)另一方擁有一個(gè)構(gòu)成多邊形的頂點(diǎn)集合,在不泄漏各自輸入信息的前提下,雙方協(xié)作完成點(diǎn)與多邊形的位置關(guān)系判定,并且雙方也無法從判定結(jié)果中推測出對方的輸入.文獻(xiàn)[2]基于Monte Carlo 方法和Cantor 編碼設(shè)計(jì)了點(diǎn)包含與圖形包含問題的近似解決方案,該方案將問題轉(zhuǎn)化為集合包含問題,利用了可交換加密,是一種近似求解問題的方法,其精度與復(fù)雜度成正比,存在一定誤差.點(diǎn)包含問題是指,判斷判定點(diǎn)是否位于指定區(qū)域內(nèi).點(diǎn)包含問題是點(diǎn)與多邊形位置關(guān)系中的一種.文獻(xiàn)[5]基于安全兩方點(diǎn)積協(xié)議和向量控制協(xié)議,首次解決了安全兩方點(diǎn)包含問題,該方案調(diào)用了數(shù)次百萬富翁協(xié)議,導(dǎo)致協(xié)議的復(fù)雜度較高.文獻(xiàn)[10]將點(diǎn)包含問題轉(zhuǎn)化為三角形面積問題,并基于內(nèi)積協(xié)議給出解決三角形面積問題的方案.該方案受制于問題轉(zhuǎn)化方法的局限性并不適用于凹多邊形的情況.文獻(xiàn)[11]提出了一種茫然安全點(diǎn)線位置關(guān)系判斷協(xié)議,并利用該協(xié)議解決了點(diǎn)包含問題,該方法基于茫然傳輸和百萬富翁協(xié)議,其效率不高,并且無法適用于復(fù)雜的任意多邊形.文獻(xiàn)[12]基于內(nèi)積協(xié)議設(shè)計(jì)了一種具有隱私保護(hù)的點(diǎn)與直線距離的計(jì)算協(xié)議,解決了隱私保護(hù)的直線與圓圈的相交問題.文獻(xiàn)[13]提出了安全的兩方向量叉積協(xié)議以及安全的點(diǎn)與線叉積協(xié)議,協(xié)議必須調(diào)用百萬富翁協(xié)議,其復(fù)雜度與多邊形的邊數(shù)有關(guān),且僅支持普通凸多邊形.文獻(xiàn)[14]在云外包環(huán)境下將點(diǎn)與面的位置關(guān)系等轉(zhuǎn)化為夾角問題,并設(shè)計(jì)了基于云外包條件的內(nèi)積協(xié)議,但該協(xié)議無法適用于任意多邊形情況.文獻(xiàn)[15]使用角度旋轉(zhuǎn)法解決了點(diǎn)與多邊形的關(guān)系判定問題,該方案雖然解決了點(diǎn)與任意多邊形的關(guān)系判定,然而其計(jì)算復(fù)雜度較高.由于實(shí)際應(yīng)用中人們往往面臨的是點(diǎn)與凹凸多邊形結(jié)合的復(fù)雜圖形的位置關(guān)系判定,因此,研究和設(shè)計(jì)點(diǎn)與任意多邊形的位置關(guān)系判定協(xié)議具有很重要的應(yīng)用價(jià)值.但目前缺少高效安全地求解點(diǎn)與任意多邊形關(guān)系判定問題的方案.

針對上述問題,本文首先基于文獻(xiàn)[12]提出的編碼方式設(shè)計(jì)了一種精簡高效的叉積協(xié)議,該協(xié)議實(shí)現(xiàn)了具有隱私保護(hù)的點(diǎn)與直線相對位置的判定,然后在該叉積協(xié)議的基礎(chǔ)之上本文結(jié)合射線法提出了一種具有隱私保護(hù)的點(diǎn)與任意多邊形關(guān)系判定方案.

本文的主要貢獻(xiàn)有:(1)提出了一種具有隱私保護(hù)的點(diǎn)與任意多邊形關(guān)系判定的方案,該方案同時(shí)適用于凸多邊形與凹多邊形的情況.(2)設(shè)計(jì)了一種高效的叉積協(xié)議,該協(xié)議基于明文空間數(shù)域劃分的思想實(shí)現(xiàn)了支持負(fù)數(shù)的叉積運(yùn)算,提升了判定方案的效率.(3)提出了一種高效的轉(zhuǎn)化方法,將點(diǎn)與任意多邊形位置關(guān)系的判定問題轉(zhuǎn)化為任意一條過點(diǎn)的射線與多邊形相交的點(diǎn)數(shù)奇偶性的判定問題.

2 設(shè)計(jì)目標(biāo)及安全性定義

2.1 安全性定義

本文的安全目標(biāo)是,參與計(jì)算的兩方均無法獲得對方的輸入信息.本文在半誠實(shí)參與者安全模型下達(dá)到該安全目標(biāo).半誠實(shí)參與者是指能夠嚴(yán)格遵守協(xié)議的執(zhí)行指令,在協(xié)議的執(zhí)行過程中記錄所有得到的中間結(jié)果并企圖根據(jù)自己獲得的信息推測出額外信息的參與者.基于該安全模型,如果參與者可以利用自己的輸入和協(xié)議的輸出單獨(dú)模擬整個(gè)協(xié)議的執(zhí)行過程并且在此過程中得不到任何額外的信息,那么該協(xié)議就能保證參與者輸入的安全性.上述安全性的形式化定義如下:

假設(shè)兩個(gè)參與者要計(jì)算函數(shù)f:{0,1}?×{0,1}?→{0,1}?×{0,1}?,其中f1(x,y)和f2(x,y)分別代表f的第一個(gè)元素和第二個(gè)元素;π表示計(jì)算f的協(xié)議;S1和S2是兩個(gè)多項(xiàng)式時(shí)間算法,它們作為模擬器模擬協(xié)議的執(zhí)行過程.Si(x,f(x,y))表示模擬器以第i個(gè)參與者的輸入和協(xié)議的輸出作為參數(shù)模擬協(xié)議的執(zhí)行過程,表示第i個(gè)參與者的視圖表示第i個(gè)參與者執(zhí)行協(xié)議得到的結(jié)果,其中i=1,2.對于確定性功能函數(shù)f,我們稱協(xié)議π在半誠實(shí)模型下秘密的計(jì)算f當(dāng)且僅當(dāng)S1和S2是使得

其中|x|=|y|.

2.2 設(shè)計(jì)目標(biāo)

基于上述安全模型,本文設(shè)計(jì)目標(biāo)是提出一種具有隱私保護(hù)的、高效的點(diǎn)與任意多邊形關(guān)系判定方案.具體來說,提出的方案需要達(dá)到下述設(shè)計(jì)目標(biāo):

(1)安全性.通過執(zhí)行方案,雙方在不知道對方輸入信息的情況下協(xié)作完成點(diǎn)與多邊形的位置關(guān)系判定,并且雙方也無法從判定結(jié)果中推測出對方的輸入,即方案必須滿足2.1節(jié)提出的安全性要求.

(2)正確性.對在凸多邊形內(nèi)或外的任何點(diǎn),方案都能得到正確的判定結(jié)果; 對在凹多邊形內(nèi)或外的任何點(diǎn),方案都能得到正確的判定結(jié)果.即,針對任意多邊形,方案都能夠正確判定點(diǎn)和多邊形的位置關(guān)系.

(3)高效性.為更具實(shí)用性,方案應(yīng)有效減少參與雙方之間的通信開銷和每個(gè)參與方的計(jì)算開銷.

3 預(yù)備知識

3.1 叉積

圖1 叉積定義Figure 1 Definition of cross product

3.2 同態(tài)加密

同態(tài)加密是一種允許對密文進(jìn)行計(jì)算的一類加密算法.在將明文加密后,對密文進(jìn)行有限的加法或乘法運(yùn)算后仍可以解密,解密后的結(jié)果與對明文的操作是一致的,從而達(dá)到對密文數(shù)據(jù)計(jì)算的目的.Paillier公鑰密碼系統(tǒng)[17]是一種常見的同態(tài)加密算法,其主要包括三個(gè)算法:密鑰產(chǎn)生算法(Gen)、加密算法(Enc)和解密算法(Dec).該加密算法的同態(tài)性主要體現(xiàn)在以下方面:

其中m1和m2是消息空間中的兩個(gè)消息,r1和r2是兩個(gè)隨機(jī)數(shù).

3.3 點(diǎn)與直線位置關(guān)系

文獻(xiàn)[16]已證明點(diǎn)與直線的位置關(guān)系等價(jià)于求點(diǎn)與直線的叉積,可以通過求點(diǎn)與直線的叉積來判斷點(diǎn)與直線的位置關(guān)系.點(diǎn)p0=(x0,y0)與直線的關(guān)系(其中p1=(x1,y1),p2=(x2,y2))定義如下.

定義1(點(diǎn)與直線的關(guān)系)計(jì)算點(diǎn)p0與直線的叉積

將點(diǎn)與直線的位置關(guān)系表示為:

3.4 點(diǎn)與任意多邊形的位置關(guān)系

文獻(xiàn)[18]給出并證明了關(guān)于點(diǎn)與任意多邊形位置關(guān)系的如下定理.

定理1點(diǎn)與任意多邊形的位置關(guān)系等價(jià)于過判定點(diǎn)的任意射線與任意多邊形相交的點(diǎn)數(shù),若相交點(diǎn)數(shù)為奇數(shù)則判定點(diǎn)在多邊形內(nèi),否則在多邊形外.

4 隱私保護(hù)的點(diǎn)與多邊形關(guān)系判定

4.1 問題描述和轉(zhuǎn)化

4.1.1 問題描述

設(shè)Alice 擁有一個(gè)點(diǎn)p0=(x0,y0),Bob 擁有一個(gè)由n個(gè)頂點(diǎn){p1=(x1,y1),p2=(x2,y2),··· ,pn=(xn,yn)} 構(gòu)成的任意多邊形P,在不泄漏雙方各自信息的情況下,Alice和Bob 協(xié)作判斷Alice 擁有的點(diǎn)p0是否在Bob 的任意多邊形P內(nèi).

4.1.2 問題轉(zhuǎn)化

本文基于模擬射線法的思路將點(diǎn)與任意多邊形位置關(guān)系的判定問題轉(zhuǎn)化為任意一條過點(diǎn)的射線與多邊形相交點(diǎn)數(shù)的奇偶性判定問題.為了便于描述,本文提出了同側(cè)點(diǎn)的概念,其定義如下.

定義2(同側(cè)點(diǎn))經(jīng)過點(diǎn)的直線等價(jià)于兩條以該點(diǎn)為頂點(diǎn)并且方向相反的射線,其中同一條射線上的點(diǎn)稱作該點(diǎn)的同側(cè)點(diǎn).

基于同側(cè)點(diǎn)的概念,本文給出了實(shí)現(xiàn)問題轉(zhuǎn)化的定理.

定理2過判定點(diǎn)作直線,直線與多邊形的交點(diǎn)中同側(cè)點(diǎn)的數(shù)量等價(jià)于過判定點(diǎn)射線與多邊形的交點(diǎn)數(shù),若交點(diǎn)數(shù)為奇數(shù)則判定點(diǎn)在多邊形內(nèi),否則判定點(diǎn)在多邊形外.

證明:已知一條直線可被判定點(diǎn)劃分為兩條方向相反的射線,若直線與多邊形相交,顯然這些交點(diǎn)分別存在于兩條方向相反的射線上,因此可統(tǒng)計(jì)得到判定點(diǎn)的同側(cè)點(diǎn)數(shù),由定理1結(jié)論可知定理2成立.

定理3若多邊形的頂點(diǎn)全部位于直線的同一側(cè),則直線與多邊形不相交.

證明:假設(shè)直線與多邊形相交,那么必定存在一個(gè)頂點(diǎn)在直線上或在直線的另一側(cè),命題得證.

定理4過判定點(diǎn)做任意一條直線,若直線與多邊形不相交,則判定點(diǎn)必定在多邊形外.

證明:假設(shè)判定點(diǎn)在多邊形內(nèi),過判定點(diǎn)任意做一條直線,由于直線的性質(zhì)其必定會(huì)與多邊形相交,因此假設(shè)不成立,命題得證.

基于定理2–4,點(diǎn)與任意多邊形位置關(guān)系的判定被轉(zhuǎn)化為任意一條過點(diǎn)的射線與多邊形相交點(diǎn)數(shù)的奇偶性判定.例如,圖2和圖3中的點(diǎn)p0和任意多邊形的相對位置可以通過統(tǒng)計(jì)點(diǎn)p0的同側(cè)點(diǎn)數(shù)并根據(jù)同側(cè)點(diǎn)的奇偶性得到.

圖2 點(diǎn)p0在多邊形外Figure 2 Example of a point outside a polygon

圖3 點(diǎn)p0在多邊形內(nèi)Figure 3 Example of a point inside a polygon

為了方便表達(dá),定義如下謂詞:

根據(jù)定義1可知叉積協(xié)議是一種用來解決點(diǎn)與直線位置關(guān)系判定的工具,文獻(xiàn)[16]中提出的具有隱私保護(hù)的叉積協(xié)議雖然能保密的判定點(diǎn)與直線的位置關(guān)系,但是其需要調(diào)用復(fù)雜度較高的密碼學(xué)原語.本文設(shè)計(jì)了一個(gè)輕量級的叉積協(xié)議用于判定點(diǎn)與直線的位置關(guān)系.針對任意一條過點(diǎn)的射線與多邊形相交點(diǎn)數(shù)的奇偶性判定問題,基于該輕量級叉積協(xié)議,本文給出的判定方案包括3 個(gè)步驟.

步驟1:首先任取一點(diǎn)p′與判定點(diǎn)p0組成一條直線

步驟2:根據(jù)叉積協(xié)議,計(jì)算得到多邊形P的頂點(diǎn)與直線的相對位置關(guān)系,從而找出多邊形與直線相交的所有邊;

步驟3:根據(jù)叉積協(xié)議,計(jì)算得到判定點(diǎn)p0與相交邊的相對位置關(guān)系,從而獲得以判定點(diǎn)為頂點(diǎn)的同側(cè)點(diǎn)數(shù),若同側(cè)點(diǎn)數(shù)為奇數(shù)則判定點(diǎn)p0在多邊形P的內(nèi)部,若為偶數(shù)則判定點(diǎn)p0在多邊形P的外部.

4.2 具體方案

本文提出的具有隱私保護(hù)的點(diǎn)與任意多邊形位置關(guān)系的判定方案包括兩個(gè)協(xié)議:具有隱私保護(hù)的點(diǎn)與直線位置關(guān)系判定協(xié)議和具有隱私保護(hù)的點(diǎn)與任意多邊形位置關(guān)系的判定協(xié)議.首先由Alice和Bob分別根據(jù)安全參數(shù)生成各自的Paillier 加密算法的公私鑰對(PKA,SKA)和PKB,SKB,然后Alice和Bob 執(zhí)行具有隱私保護(hù)的點(diǎn)與任意多邊形位置關(guān)系的判定協(xié)議,使得Alice和Bob 在保證自己的輸入信息不被泄漏的情況下均知道點(diǎn)p0是否在多邊形P中.在執(zhí)行點(diǎn)與任意多邊形位置關(guān)系的判定協(xié)議的過程中,具有隱私保護(hù)的點(diǎn)與直線位置關(guān)系判定協(xié)議將被調(diào)用以協(xié)助完成點(diǎn)與任意多邊形位置關(guān)系的判定.本文使用文獻(xiàn)[12]中支持符號位的編碼方式,對于明文空間{0,1,··· ,T},設(shè)L=?logT?+1,將明文空間中的元素表示成長度為L的二進(jìn)制數(shù),將其中的第L位視為符號位.根據(jù)符號位的值,本文將明文空間分成正負(fù)兩個(gè)部分.L為1 的元素構(gòu)成明文空間的負(fù)數(shù)空間,L為0 的元素構(gòu)成明文空間的正數(shù)空間.點(diǎn)的坐標(biāo)范圍為[?T/2,T/2].當(dāng)點(diǎn)坐標(biāo)落在范圍[0,T/2]內(nèi)時(shí),將該坐標(biāo)映射到明文空間的正數(shù)空間,此時(shí)只需直接映射即可; 當(dāng)點(diǎn)坐標(biāo)落在范圍[?T/2,0)內(nèi)時(shí),將該坐標(biāo)映射到明文空間的負(fù)數(shù)空間,此時(shí)通過將坐標(biāo)值加上T進(jìn)行映射.協(xié)議的具體內(nèi)容描述如下.

協(xié)議1隱私保護(hù)的點(diǎn)與直線位置關(guān)系判定

步驟1.點(diǎn)的擁有者基于自己公鑰利用加密算法Enc 對點(diǎn)進(jìn)行加密,得密文集合

步驟2.點(diǎn)的擁有者將發(fā)送給直線的擁有者,直線的擁有者選取隨機(jī)數(shù)r并做如下計(jì)算:

并將計(jì)算結(jié)果(M,W,K)發(fā)送給點(diǎn)的擁有者.

步驟3.點(diǎn)的擁有者接收到(M,W,K)后做如下計(jì)算.

步驟4.點(diǎn)的擁有者將結(jié)果告訴直線的擁有者.

協(xié)議2隱私保護(hù)的點(diǎn)與任意多邊形位置關(guān)系判定

輸入:Alice 擁有點(diǎn)p0(x0,y0),Bob 擁有多邊形P={pj(xj,yj),j∈(1,··· ,n)}.

輸出:Alice和Bob 均得到點(diǎn)p0(x0,y0)與多邊形P的位置關(guān)系.

步驟1.Alice 隨機(jī)選取點(diǎn)p′(x′,y′),構(gòu)造直線

步驟 2.以直線和多邊形的頂點(diǎn)pj(xj,yj)作為輸入,使用Bob 的公鑰執(zhí)行協(xié)議1,即其中j=1,2,··· ,n,協(xié)議被執(zhí)行了n次,將n次執(zhí)行得到的結(jié)果記為

步驟3.Bob 在R中篩選出滿足下述Cross 條件的元素組其中1≤j

將所有滿足 Cross 條件的元素組對應(yīng)點(diǎn)構(gòu)成的直線構(gòu)成的集合記為ICross),即ICross=其中1≤j

步驟 4.以點(diǎn)p0和線段∈ICross作為輸入,使用 Alice 的公鑰執(zhí)行協(xié)議1,即協(xié)議被執(zhí)行了|ICross| 次,將|ICross| 次執(zhí)行得到的結(jié)果記為R′=若?0 ∈R′,則點(diǎn)p0在多邊形P內(nèi),即f(p0,P)=1; 若R′中–1或1 的個(gè)數(shù)為奇數(shù),則p0點(diǎn)在多邊形P內(nèi),即f(p0,P)=1; 若R′中–1 或1 的個(gè)數(shù)為偶數(shù),則p0點(diǎn)在多邊形P外,即f(p0,P)=0.

步驟5.Alice 將結(jié)果f(p0,P)發(fā)送給Bob.

5 正確性及安全性證明

5.1 正確性

5.1.1 協(xié)議1正確性分析

協(xié)議1的目標(biāo)是安全計(jì)算如下公式:

由加密同態(tài)性可得:

顯然,當(dāng)把負(fù)值映射到明文空間的負(fù)值空間后,對其進(jìn)行同態(tài)運(yùn)算會(huì)導(dǎo)致明文數(shù)值上的偏移.協(xié)議1將公式(13)中的減法運(yùn)算均安排在解密之后進(jìn)行,保證加密過程中的明文為正數(shù).

因此,協(xié)議1能夠得到正確的計(jì)算結(jié)果.

5.1.2 協(xié)議2正確性分析

將點(diǎn)p0與隨機(jī)選取的點(diǎn)p′確定的直線與多邊形P的頂點(diǎn)作為輸入,執(zhí)行協(xié)議1得到多邊形P的各個(gè)頂點(diǎn)與直線的位置關(guān)系,即集合R.基于5.1.1的證明可以保證集合R的正確性.若R中的元素全部為1 或–1,則意味著多邊形P的全部頂點(diǎn)均位于直線的同一側(cè),說明直線與多邊形P不相交,p0在多邊形P的外部,協(xié)議結(jié)束.若R中的元素不全部為1 或–1,則說明直線與多邊形相交,即|ICross|=0.ICross中的直線與直線相交,以點(diǎn)p0和ICross中的直線作為輸入執(zhí)行協(xié)議1,根據(jù)執(zhí)行結(jié)果可以推測出直線與多邊形P相交的點(diǎn)數(shù),即點(diǎn)p0的同側(cè)點(diǎn)的個(gè)數(shù).基于5.1.1的證明可以保證該同側(cè)點(diǎn)的個(gè)數(shù)的正確性.根據(jù)獲得的同側(cè)點(diǎn)的個(gè)數(shù),基于定理1可以推斷出點(diǎn)p0是在多邊形P的內(nèi)部還是外部.同側(cè)點(diǎn)個(gè)數(shù)的正確性及文獻(xiàn)[18]對定理1的證明可以保證推斷結(jié)論的正確性.

下面討論點(diǎn)在多邊形上的特殊情況,點(diǎn)在多邊形任意一條邊上被認(rèn)定為點(diǎn)在多邊形內(nèi).不妨假設(shè)點(diǎn)p0位于直線∈ICross上,根據(jù)定義1可知=0,以點(diǎn)p0與直線為輸入執(zhí)行協(xié)議1,基于5.1.1的證明可知協(xié)議1的輸出結(jié)果為0,根據(jù)協(xié)議2,因?yàn)?0 ∈R′,所以點(diǎn)p0在多邊形P內(nèi),協(xié)議2的輸出結(jié)果是正確的.

5.2 安全性證明

5.2.1 協(xié)議1安全性證明

g1表示執(zhí)行協(xié)議1后點(diǎn)的擁有者的結(jié)果,表示執(zhí)行協(xié)議1后直線的擁有者的結(jié)果.

構(gòu)造模擬器S1模擬直線的擁有者的協(xié)議執(zhí)行過程,構(gòu)造模擬器S1隨機(jī)選取使得

構(gòu)造模擬器S1使用自己的公鑰進(jìn)行如下加密操作:

構(gòu)造模擬器S1選擇隨機(jī)數(shù)r′(r′=0,1),進(jìn)行如下計(jì)算:

模擬結(jié)束.

顯然,我們可以得到:

構(gòu)造模擬器S2模擬點(diǎn)的擁有者的執(zhí)行過程.構(gòu)造模擬器S2隨機(jī)選取其中使得

構(gòu)造模擬器S2使用公鑰進(jìn)行如下加密操作:

構(gòu)造模擬器S2選擇隨機(jī)數(shù)r?(r?=0,1),計(jì)算:

模擬結(jié)束.

顯然,可以得到

上述證明過程說明協(xié)議1是隱私保護(hù)安全的.

5.2.2 協(xié)議2的安全性證明

協(xié)議2安全性要求,Alice和Bob 執(zhí)行完協(xié)議2后,Alice 在不泄漏自己擁有的點(diǎn)p0信息和Bob 在不泄漏自己擁有多邊形P的信息的情況下,Alice和Bob 均知道點(diǎn)p0與多邊形P的相對位置關(guān)系.協(xié)議2的安全性依賴協(xié)議1.協(xié)議2的輸出結(jié)果為f(p0,P)=f1(p0,P)=f2(p0,P),其中f1(p0,P)表示執(zhí)行協(xié)議2后Alice 得到的結(jié)果,f2(p0,P)表示執(zhí)行協(xié)議2后Bob 得到的結(jié)果.構(gòu)造模擬器S3模擬Bob 執(zhí)行協(xié)議2的過程,模擬器S3隨機(jī)選取一個(gè)點(diǎn)依次以直線和多邊形P的每個(gè)頂點(diǎn)為輸入執(zhí)行協(xié)議1,得到P的每個(gè)頂點(diǎn)與直線的位置關(guān)系集合R?.根據(jù)R?中的結(jié)果計(jì)算出使用中的線段執(zhí)行協(xié)議1,得到結(jié)果

同理對Alice 也可以構(gòu)造模擬器S4證明view4(p0,P)與S4(p?0,P)不可區(qū)分.上述證明過程說明協(xié)議保證了雙方輸入信息的安全.

6 性能分析

6.1 協(xié)議1性能分析

制約安全多方計(jì)算協(xié)議性能的主要因素是協(xié)議的通信復(fù)雜度和計(jì)算復(fù)雜度.本文將從上述兩個(gè)方面對協(xié)議1和文獻(xiàn)[14]提出的協(xié)議進(jìn)行分析比較.為了便于敘述,本文分別用符號Tenc、Tdec、Tmult和Tpow表示1 次加密操作、1 次解密操作、1 次密文乘法運(yùn)算和1 次模冪運(yùn)算的時(shí)間.

執(zhí)行1 次協(xié)議1需要進(jìn)行7 次加密操作、3 次解密操作、3 次密文乘法運(yùn)算和4 次模冪運(yùn)算,故執(zhí)行1 次協(xié)議1的計(jì)算開銷為:7Tenc+3Tdec+3Tmult+4Tpow.

文獻(xiàn)[14]利用云環(huán)境中的點(diǎn)積協(xié)議設(shè)計(jì)了一種點(diǎn)與直線關(guān)系的判定協(xié)議,在計(jì)算內(nèi)積時(shí)文獻(xiàn)[14]利用了BGN 的乘法同態(tài),需要執(zhí)行多次雙線性對運(yùn)算,因此本文提出的協(xié)議在計(jì)算性能方面優(yōu)于文獻(xiàn)[14]提出的協(xié)議.為了證實(shí)這一分析結(jié)果,我們給出了仿真實(shí)驗(yàn).實(shí)驗(yàn)環(huán)境為Windows 7 64 位操作系統(tǒng)、內(nèi)存4 G、Intel(R)Pentium(R)CPU G3220@ 3.00 GHz,基于JPBC[19]的庫函數(shù),實(shí)驗(yàn)?zāi)M了協(xié)議1的執(zhí)行,在模擬的過程中我們忽略了通信消耗的時(shí)間并取τ為160 bit,實(shí)驗(yàn)數(shù)據(jù)如表1 所示.

表1 協(xié)議1計(jì)算性能比較的實(shí)驗(yàn)數(shù)據(jù)(單位:ms)Table 1 Experimental data of computation performance comparison of Protocol 1(ms)

上述實(shí)驗(yàn)仿真數(shù)據(jù)說明本文提出的協(xié)議1的計(jì)算性能優(yōu)于文獻(xiàn)[14]提出的協(xié)議.值得注意的是,文獻(xiàn)[20]使用的是仰角比較協(xié)議,文獻(xiàn)[13]使用的是安全叉積協(xié)議,文獻(xiàn)[21]使用的是極角比較協(xié)議,文獻(xiàn)[22]使用的是角度旋轉(zhuǎn)協(xié)議.協(xié)議1對比其他文獻(xiàn),協(xié)議1在設(shè)計(jì)上避免使用復(fù)雜的密碼原語從而降低了計(jì)算開銷,更加精簡.

6.2 協(xié)議2性能分析

協(xié)議2的計(jì)算開銷依賴于協(xié)議1的計(jì)算開銷、多邊形P的頂點(diǎn)數(shù)n以及多邊形P與直線相交的邊數(shù)|ICross|

表2 協(xié)議2的性能比較Table 2 Performance analysis of Protocol 2

7 結(jié)論

隱私保護(hù)的點(diǎn)與任意多邊形關(guān)系的判定問題,具有較高的研究意義.解決該問題的方法一般從問題本身出發(fā)尋找突破口,然后結(jié)合隱私保護(hù)相關(guān)技術(shù)設(shè)計(jì)具體的解決方案.本文基于支持符號位的編碼和同態(tài)加密算法設(shè)計(jì)了高效的點(diǎn)與直線關(guān)系判定協(xié)議,然后利用模擬射線法的轉(zhuǎn)化方法將點(diǎn)與任意多邊形位置關(guān)系的判定問題轉(zhuǎn)化為任意一條過點(diǎn)的射線與多邊形相交點(diǎn)數(shù)的奇偶性判定問題,最后給出了具有隱私保護(hù)的點(diǎn)與任意多邊形關(guān)系判定方案.本文研究的問題是基于半誠實(shí)模型下兩個(gè)參與者的二維空間安全幾何計(jì)算問題.但是如何實(shí)現(xiàn)三維空間下多個(gè)參與者以及惡意模型下的具有隱私保護(hù)的幾何計(jì)算問題還有待進(jìn)一步的研究.