隱私保護的點與任意多邊形位置關系判定*

張明武,冷文韜,沈 華

1.湖北工業大學 計算機學院,武漢430068

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

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

1 引言

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

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

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

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

2 設計目標及安全性定義

2.1 安全性定義

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

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

其中|x|=|y|.

2.2 設計目標

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

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

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

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

3 預備知識

3.1 叉積

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

3.2 同態加密

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

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

3.3 點與直線位置關系

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

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

將點與直線的位置關系表示為:

3.4 點與任意多邊形的位置關系

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

定理1點與任意多邊形的位置關系等價于過判定點的任意射線與任意多邊形相交的點數,若相交點數為奇數則判定點在多邊形內,否則在多邊形外.

4 隱私保護的點與多邊形關系判定

4.1 問題描述和轉化

4.1.1 問題描述

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

4.1.2 問題轉化

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

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

基于同側點的概念,本文給出了實現問題轉化的定理.

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

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

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

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

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

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

基于定理2–4,點與任意多邊形位置關系的判定被轉化為任意一條過點的射線與多邊形相交點數的奇偶性判定.例如,圖2和圖3中的點p0和任意多邊形的相對位置可以通過統計點p0的同側點數并根據同側點的奇偶性得到.

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

圖3 點p0在多邊形內Figure 3 Example of a point inside a polygon

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

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

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

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

步驟3:根據叉積協議,計算得到判定點p0與相交邊的相對位置關系,從而獲得以判定點為頂點的同側點數,若同側點數為奇數則判定點p0在多邊形P的內部,若為偶數則判定點p0在多邊形P的外部.

4.2 具體方案

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

協議1隱私保護的點與直線位置關系判定

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

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

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

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

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

協議2隱私保護的點與任意多邊形位置關系判定

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

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

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

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

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

將所有滿足 Cross 條件的元素組對應點構成的直線構成的集合記為ICross),即ICross=其中1≤j

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

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

5 正確性及安全性證明

5.1 正確性

5.1.1 協議1正確性分析

協議1的目標是安全計算如下公式:

由加密同態性可得:

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

因此,協議1能夠得到正確的計算結果.

5.1.2 協議2正確性分析

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

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

5.2 安全性證明

5.2.1 協議1安全性證明

g1表示執行協議1后點的擁有者的結果,表示執行協議1后直線的擁有者的結果.

構造模擬器S1模擬直線的擁有者的協議執行過程,構造模擬器S1隨機選取使得

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

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

模擬結束.

顯然,我們可以得到:

構造模擬器S2模擬點的擁有者的執行過程.構造模擬器S2隨機選取其中使得

構造模擬器S2使用公鑰進行如下加密操作:

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

模擬結束.

顯然,可以得到

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

5.2.2 協議2的安全性證明

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

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

6 性能分析

6.1 協議1性能分析

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

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

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

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

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

6.2 協議2性能分析

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

表2 協議2的性能比較Table 2 Performance analysis of Protocol 2

7 結論

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