張明武, 張依夢, 諶 剛

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

2. 密碼科學技術國家重點實驗室, 北京100878

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

1 引言

幾何位置關系的判定在實際中應用非常廣泛. 在軍事系統中, 兩雷達在不同范圍半徑進行位置探測,二者需要知道彼此探測區(qū)域的關系以判定是否彼此探測覆蓋; 另外, 在社交網絡中, 基于地理位置信息進行好友推薦, 并判斷用戶間的位置關系是社交網絡的重要因素[1]. 隨著大數據和人工智能等技術的發(fā)展,用戶彼此間交互的信息量急速增加, 這可能造成用戶信息的泄露[2,3]. 因此, 在參與多方有效判定各種位置關系的同時保護各自信息不被泄露是個不可忽視的問題[4].

安全多方計算(Secure Multi-party Computation, SMC)[5]為隱私保護的位置判定問題提供了有效的解決思路, 也為大多數學者的研究提供了一個重要方法. 安全統計分析[6,7]、安全幾何計算[8,9]以及安全科學計算[10]等是常見的安全多方計算問題, 而隱私保護的幾何位置關系判定問題, 是安全幾何計算問題的核心問題之一. 針對該問題, 提出了具體的點與圓(多邊形)[8,11–14]、點與直線[15,16]、及點與平面間[9,17]等位置判定的解決方案. Li 等人[14]提出隱私保護的點與凸(凹) 多邊形位置關系判定協議, 首先提出的安全兩方三角形面積計算協議, 然后通過判定三角形面積的符號位來解決凸多邊形中的點包含問題. 基于文獻[14] 中利用三角形面積判定的思想, Chen 等人[8]提出了點與凸多邊形位置判定協議, 基于內積協議解決安全兩方三角形面積計算問題, 然而該協議僅適用于解決凸多邊形點包含問題. 而Zhang等人[11]提出利用高效的叉積協議以解決點與多邊形的位置關系判定問題中, 其多邊形可為任意多邊形.文獻[13] 中提出隱私保護的判定點與圓、點與凸多邊形位置關系的協議, 用來秘密判定好友位置關系, 即用戶選擇任意范圍, 通過與朋友進行安全的聯合計算判斷朋友是否在自己所選范圍內, 且該協議采用安全兩方余弦值計算協議, 避免了復雜的密碼算法. 在解決隱私保護的點與直線間位置關系判定問題時, 利用安全內積協議來實現秘密點與秘密有向線間的位置判定由Yang 等人[15]提出, 而同態(tài)加密算法增加了其計算復雜度. Zhang 等人[16]提出保密判定點與線的位置關系協議, 該協議基于判定點是否為一個方程的解的思想并結合保密內積協議來解決該問題, 保密內積協議主要通過構造一個不可逆的矩陣來保護點與直線的隱私安全. 在解決隱私保護的平面間位置關系判定問題時, Li 等人[9]給出了隱私保護的判斷點與平面的距離、直線與平面、以及兩平面間的位置關系等問題的解決方案.

隱私保護的兩圓位置關系判定中, 參與兩方各自輸入秘密的圓的半徑和圓心等信息, 聯合判定二方的位置關系且不會泄露各自輸入的信息. 該類問題具有重要意義, 例如, 不同用戶的社交圈中, 在不泄露自身好友信息的情況下判定是否具有共同社會交集且實現各用戶社交信息的保密[18]. 為解決保密計算兩圓公切線問題, Wang 等人[19]提出了安全計算兩圓間的公切線協議, 并實現隱私保護的路徑規(guī)劃問題. Ye 等人[20]給出了計算兩秘密輸入的相交圓交點的協議. 文獻[21] 提出了隱私保護橢圓相交判定方案. Liu 等人[22]基于安全兩數和平方、安全兩實數關系判定和安全兩點距離計算等三個子協議提出安全兩方圓計算協議, 然而, 他們只解決兩圓相交、相離、外切三種關系的判定問題. 另外, 該協議需要多次調用子協議,所以這增加了系統的計算復雜度與通信開銷. 針對以上提出的問題, 本文提出了一種新的方案以解決隱私保護的兩圓間位置關系判定問題.

1.1 本文貢獻

基于對傳統的兩圓位置判定方法的改進, 本文設計一個隱私保護的兩方幾何圓位置關系判定協議以實現安全的求解兩圓間五種位置關系. 本文的主要貢獻如下:

(1) 給出了隱私保護的歐幾里德距離計算協議. 結合將Paillier 明文空間劃分的思想以實現對解密結果進行正確映射, 提出了隱私保護的歐幾里德距離計算協議, 提高了兩方的計算效率.

(2) 提出一個隱私保護的兩方幾何圓位置判定協議. 基于隱私保護的歐幾里德距離計算協議, 本文提出高效解決隱私保護的判定兩圓位置關系問題的方案, 與相關方案采用不經意傳輸和內積協議相比, 本文方案具有較低的計算復雜度和通信開銷.

(3) 支持判定兩圓的五種位置關系. 除判定兩圓相離、相切、相交三種位置, 本文協議還支持判定兩圓內切、內含等位置關系.

2 預備知識

2.1 符號定義

為便于讀者理解, 本節(jié)給出本文所用的基本符號.

κ: 系統安全參數

Pi: 協議參與方(i=a,b)

(pka,ska): Pa的Paillier 公私鑰對

[[m]]: 消息m 的密文

(Sa,Sb): 半誠實模型下Pa,Pb的模擬器

ci: Pi擁有的幾何圓

oi: ci的圓心

ri: ci的半徑

(xi,yi): 圓心oi

2.2 兩圓位置關系

(1) 相離: d>ra+rb;

(2) 外切: d=ra+rb;

(3) 相交: |ra?rb|

(4) 內切: d=|ra?rb|;

(5) 內含: d<|ra?rb|.

為方便比較, 本方案將轉化為計算d2=(xa?xb)2+(ya?yb)2.

2.3 安全模型

在安全多方計算協議中, 敵手模型主要分為半誠實敵手模型與惡意敵手模型[23]. 由于本協議的參與方是半誠實的, 本文只給出半誠實模型及安全性定義.

(1) 半誠實模型: 在半誠實模型下, 參與者能正確地執(zhí)行協議, 在協議執(zhí)行期間能得到所有中間結果,并試圖根據所得的中間結果得到額外信息.

圖1 兩圓位置關系Figure 1 Positional relationship of two circles

2.4 同態(tài)加密算法

Paillier 加密算法是一種常用的加法同態(tài)加密算法[24], 對于明文空間的任意兩個消息m1和m2的密文[[m1]] 和[[m2]], 以及隨機數α(α ∈Zn), 該算法滿足以下面性質:

Paillier 加密算法包括三部分, 具體描述如下:

? 密鑰生成算法(Gen): 給定安全參數為κ, 生成兩個大素數p 和q, |p| = |q| = κ, 且n = pq, 計算λ = lcm(p ?1,q ?1), 其中l(wèi)cm(a,b) 表示兩數a 和b 的最大公約數. 隨機選取a ∈Zn, 置g =1+an(modn2), 定義函數L(x)=(x ?1)/n. 置公鑰pk=(n,g) 和密鑰sk=λ.

定理1[25]Paillier 加密方案中不能直接對負數進行加密.

調用解密算法得到:

若要恢復出?m, 則需滿足1+λkmn=1(modn2).

由于gcd(λ,n)=1, 則要求n|λkm. 通常k=κp,k=κq, 所以當m=0(modn) 才能正確解密消息,這與m 為負數相矛盾.

本文采用以下方法實現Paillier 中的負數表示及加密: 設明文空間為[0,n], 將其劃分為兩等長區(qū)間[0,(n ?1)/2] 和[(n+1)/2,n], 將[0,(n ?1)/2] 內代表正數, [(n+1)/2,n] 內代表負數. 對于待加密明文范圍是[?(n ?1)/2,(n ?1)/2], 若待加密明文范圍是[?(n ?1)/2,0], 則轉化為加密?m+n=n ?m.

則加密過程表示為:

解密過程表示為:

2.5 隱私保護的歐幾里德距離計算協議

協議1 隱私保護的歐幾里德距離協議, 具體協議如圖2 所示.

在初始階段, Pa通過安全參數κ 產生一對Paillier 公私鑰對(pka,ska), 將公鑰pka發(fā)給Pb, 保留私鑰ska.

Pa方解密c 后的解密結果記為m′. 根據所述編碼方式, 判斷m′的取值范圍, 得到正確的解密結果m. 若m′∈[0,(n ?1)/2], 則m=m′; 反之, 若m′∈[(n+1)/2,n], 則m=m′?n.

進一步,

圖2 協議1: 隱私保護的歐幾里德距離計算協議Figure 2 Protocol 1: Privacy-preserving calculation protocol of Euclidean distance

3 隱私保護的兩圓間位置關系判定

本節(jié)在隱私保護的歐幾里德距離計算協議基礎上, 提出兩圓間位置關系的隱私保護條件下的判定協議.

3.1 問題描述

3.2 方案原理

3.3 具體方案

本節(jié)給出隱私保護的兩圓間位置關系判定協議具體實現過程, 該協議是基于2.4 節(jié)提到的隱私保護的歐幾里德距離計算協議.

協議2 隱私保護的兩圓間位置關系判定協議, 如圖3 所示.

圖3 協議2: 隱私保護的兩方幾何圓位置關系判定協議Figure 3 Protocol 2: Privacy-preserving positional determination protocol of two geometry circles

協議2 實現過程如下:

輸入: Pa輸入ca=, Pb輸入cb=.

輸出: Pa和Pb均知道ca和cb的位置關系, 但是不知道彼此額外的信息.

說明: 輸出結果記為flag, flag=1,2,3,4,5 分別表示兩圓相離、外切、相交、內切、內含的位置關系.

步驟1: Pa運行Paillier 密鑰生成算法, 生成一對公私鑰對(pka,ska), 將pka發(fā)送給Pb, 保留ska.

步驟2: 基于隱私保護的歐幾里德距離計算協議, Pa用pka加密ca的圓心(xa,ya), 計算如下:

將 發(fā)給Pb.

步驟3: Pb收到 后, 先用pka加密如下:

Pb利用自己坐標值(xb,yb) 在密文上計算下式:

Pb將 發(fā)送給Pa.

步驟4: Pa用ska解密c24, 解密結果記為m.

(1) 若f1>0, ca和cb相離, flag=1;

(2) 若f1=0, ca和cb外切, flag=2;

(3) 若f1<0, f2>0, ca和cb相交, flag=3;

(4) 若f2=0, ca和cb內切, flag=4;

(5) 否則, 若f2<0, ca和cb內含, flag=5.

Pb將flag 發(fā)送給Pa, Pa和Pb均得到判定結果.

4 正確性及安全性

4.1 協議正確性分析

為證明協議2 的正確性, 本文需要對以下兩點進行證明:Paillier 算法的加法同態(tài)性計算得到c24, 即

4.2 安全性分析

該協議安全性要求, 半誠實的兩方Pa和Pb在共同執(zhí)行完該協議后, Pa沒有泄露圓ca的信息, Pb沒有泄露圓cb的信息.

定理2 協議2 保密地實現圓ca與圓cb之間的位置關系.

證明: 由于該判定協議的輸出為f(ca,cb) = fa(ca,cb) = fb(ca,cb) = flag, fa(ca,cb) 和fb(ca,cb)分別為Pa和Pb執(zhí)行該協議后所得的結果, 這里分別構造Pa方的模擬器Sa和Pb方的模擬器Sb, 使其分別滿足式(1)和式(2).

1) 構造模擬器Sa來模擬Pa去執(zhí)行協議的過程如下:

(4) Pb計算后得到判斷結果, 記為flag?, 并發(fā)給Sa.

在協議執(zhí)行過程中, 我們得到:

又因為fb(ca,cb)=OUTPUTb(ca,cb), 故下式成立:

2) 構造模擬器Sb模擬Pb去執(zhí)行協議2, 過程如下:

又因為fa(ca,cb)=OUTPUTa(ca,cb), 故下式成立:

綜上, 由1) 和2) 可知, 協議2 在半誠實模型下是安全的.

5 性能分析

本文運用Paillier 同態(tài)加密技術提出隱私保護的歐幾里德距離計算協議, 對該協議進行擴展, 我們提出了隱私保護的兩方幾何位置判定協議(即協議2). 本節(jié)主要對協議2 進行性能分析.

協議2 設計安全兩方模型解決兩圓位置判定問題, 并運用Paillier 保證協議的安全性, 分析協議2 的計算復雜度時, 這里只考慮Paillier 算法加密操作、解密操作以及模冪操作的執(zhí)行次數. 由此, 協議2 中Pa方需要執(zhí)行2 次加密操作和1 次解密操作, Pb方需要執(zhí)行3 次加密操作和2 次模冪操作, 即協議2 需執(zhí)行5 次加密操作, 1 次解密操作以及2 次模冪操作.

通信開銷 協議2 需要進行2 輪通信, 且Pa方需要發(fā)送兩個密文和待比較數l0(明文空間內), Pb方需要發(fā)送一個密文和判斷結果flag. 若安全參數是512, 假設待比較數l0的長度為256 bits, 則執(zhí)行該協議的通信開銷為6400 bits.

實驗分析 協議2 解決了隱私保護的兩圓間位置關系判定問題, 所判定的相對位置關系為相離、外切、相交、內切和內含等五種, 為分析各種位置關系下協議2 的執(zhí)行情況, 本文對協議2 進行了仿真實驗. 仿真實驗的運行環(huán)境如下: Windows 10 64 位操作系統, 內存為8.00 GB, 處理器為Inter(R) Core(TM)i5-8250U CPU @1.60 GHz 1.80 GHz, 使用java 語言在IntelliJ IDEA 上運行的.

在實際情況中, 待判斷的兩圓可能距離很近也可能距離很遠, 且兩圓均有以下五種位置關系: 相離、外切、相交、內切與內含, 為充分分析協議2 在各種情況下的性能, 我們的仿真實驗分如下兩種情況進行: 情況一: 兩圓相距比較近; 情況二: 兩圓相距比較遠.

具體來說, 本實驗主要從兩個方面展開: 一是協議2 在情況一下兩圓位置分別為相離、外切、相交、內切以及內含時的性能; 二是協議2 在情況二下兩圓位置關系分別為以上五種時的性能. 為便于理解, 本文對情況一和情況二的參數分別設置為0500, 其中d 為兩圓間的歐幾里德距離.

本實驗所選取的Paillier 加密算法的安全參數為512, 表1 和表2 是兩種情況下各種相對位置關系仿真參數, 表中的第一列給出五種位置關系, 第二列給出每種位置關系下五組參數的實驗編號, 第三列中對于每組位置關系隨機選取5 組仿真參數, 這5 組參數是根據圓心距增大來進行選擇的, 其中表中的參數列表示: oa=<(xa,ya),ra> 和ob=<(xb,yb),rb>.

根據表1 和表2 中所給的參數, 我們對每組參數進行1000 次的仿真實驗, 并取其平均值, 實驗結果如圖4 和5 所示. 圖4 和圖5 從兩個方面進行比較, 一是對于相同組數據, 比較各種位置關系下的性能, 二是對于同種位置關系, 比較每組參數下的性能.

表1 的第一組參數到第五組參數中, 圓心距逐漸增大. 圖4 中顯示, 在情況一下, 隨著圓心距的增大,相對于位置關系為外切或相交時, 兩圓相離時協議2 的執(zhí)行時間波動不大, 并且當兩圓相距極近時(如第一組), 每種位置關系下的第一組時間未呈現最低值. 另外, 在同組仿真參數下, 位置關系為外切時的總時間總是大于相離時的總時間.

圖5 為情況二下五種位置關系是每組參數執(zhí)行的總時間. 從圖5 中看出,對于位置關系分別為相離、外切、相交、內切以及內含時, 第一組到第五組參數下執(zhí)行協議2 的總時間未呈線性增長, 同時兩圓相距較遠時(如第五組), 執(zhí)行總時間未呈現最大值, 且相同組參數在不同位置關系時執(zhí)行的總時間均相差不大.

圖6 給出了兩圓相隔較近以及相隔較遠兩個情況下, 五種位置關系時協議2 的總時間比較.

從表6 可看出, 在情況一與情況二下, 相對位置分別為相離、外切、相交、內切和內含時, 協議2 執(zhí)行時間相差較近, 且總時間均低于18 ms, 計算效率高.

綜上, 兩圓在相距較近和相距較遠的情況下, 改變兩圓相對位置關系均不會使協議2 的總時間呈線性增長. 圓心距相差較小時, 不同相對位置關系下協議2 執(zhí)行時間相差小; 在兩圓相距較近或相距較遠的情況下執(zhí)行協議2, 增大兩圓間的圓心距的同時保持兩圓相對位置關系不變, 協議2 的總時間未隨圓心距的

增大而增加. 由此, 協議2 在兩圓相距較近和相距較遠的情況下來解決兩圓相離、外切、相交、內切和內含等位置判定時均適用, 且執(zhí)行總時間不高.

表1 情況一下五種相對位置關系仿真參數表Table 1 Simulation parameters of five kinds position relationship in Case 1

圖4 情況一中五種位置關系時每組參數執(zhí)行總時間Figure 4 Running time of each group of parameters in five position relationships in Case 1

圖5 情況二中五種位置關系時每組參數執(zhí)行總時間Figure 5 Running time of each group of parameters in five position relationships in Case 2

表2 情況二下五種相對位置關系仿真參數表Table 2 Simulation parameters of five kinds position relationship in Case 2

6 結論

針對隱私保護的位置判定問題, 本文通過運用Paillier 同態(tài)加密技術, 并將Paillier 明文空間劃分為兩等長區(qū)間以實現對解密結果進行編碼的方法, 給出了隱私保護的歐幾里德距離計算協議. 基于該協議,我們提出一個隱私保護的兩方幾何圓的位置關系判定協議, 該協議避免圓心距分別與半徑和、半徑差間的直接比較, 將問題轉化為與一方半徑的比較. 另外, 與已有的保密判定兩圓位置關系協議比較, 除了判定兩圓相離、外切、相交外, 本文的協議還支持判定兩圓內切、內含等位置關系. 實驗分析表明, 在兩圓相距較近與相距較遠的兩個情況下判定以上五種位置關系, 本文的協議均適用, 并具有計算復雜度不高和通信開銷低等優(yōu)勢. 此外, 在后續(xù)的工作中, 本文的協議可擴展為解決隱私保護的兩球體間位置關系判定問題.