張明武,冷文韜,沈 華

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

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

3.智能地學(xué)信息處理湖北省重點實驗室,武漢430074

1 引言

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

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

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

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

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

2.1 安全性定義

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

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

其中|x|=|y|.

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

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

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

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

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

3 預(yù)備知識

3.1 叉積

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

3.2 同態(tài)加密

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

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

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

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

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

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

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

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

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

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

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

4.1.1 問題描述

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

4.1.2 問題轉(zhuǎn)化

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

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

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

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

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

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

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

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

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

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

圖2 點p0在多邊形外Figure 2 Example of a point outside a polygon

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

為了方便表達,定義如下謂詞:

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

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

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

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

4.2 具體方案

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

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

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

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

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

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

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

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

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

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

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

步驟 2.以直線和多邊形的頂點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)點構(gòu)成的直線構(gòu)成的集合記為ICross),即ICross=其中1≤j

步驟 4.以點p0和線段∈ICross作為輸入,使用 Alice 的公鑰執(zhí)行協(xié)議1,即協(xié)議被執(zhí)行了|ICross| 次,將|ICross| 次執(zhí)行得到的結(jié)果記為R′=若?0 ∈R′,則點p0在多邊形P內(nèi),即f(p0,P)=1; 若R′中–1或1 的個數(shù)為奇數(shù),則p0點在多邊形P內(nèi),即f(p0,P)=1; 若R′中–1 或1 的個數(shù)為偶數(shù),則p0點在多邊形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)是安全計算如下公式:

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

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

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

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

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

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

5.2 安全性證明

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

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

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

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

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

模擬結(jié)束.

顯然,我們可以得到:

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

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

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

模擬結(jié)束.

顯然,可以得到

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

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

協(xié)議2安全性要求,Alice和Bob 執(zhí)行完協(xié)議2后,Alice 在不泄漏自己擁有的點p0信息和Bob 在不泄漏自己擁有多邊形P的信息的情況下,Alice和Bob 均知道點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隨機選取一個點依次以直線和多邊形P的每個頂點為輸入執(zhí)行協(xié)議1,得到P的每個頂點與直線的位置關(guān)系集合R?.根據(jù)R?中的結(jié)果計算出使用中的線段執(zhí)行協(xié)議1,得到結(jié)果

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

6 性能分析

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

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

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

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

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

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

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

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

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

7 結(jié)論

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