馮立剛,朱友文,2
(1.南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院,江蘇 南京 211106;2.桂林電子科技大學(xué)廣西密碼學(xué)與信息安全重點實驗室,廣西 桂林 541010)
近年來移動智能設(shè)備已經(jīng)成為城市居民的一種標(biāo)準(zhǔn)配置,手機、平板和智能手表成為人們現(xiàn)代化生活不可或缺的一部分。用戶隨身攜帶智能設(shè)備,依據(jù)智能設(shè)備的傳感器獲取的數(shù)據(jù),用戶能夠?qū)崟r確定自己的位置,然后使用它與基于位置的服務(wù)應(yīng)用進行交互[1-2]。據(jù)此,用戶可以隨時隨地訪問各種服務(wù),比如查詢附近的餐廳[3]、打車[4]、推薦[5]等。無論這些服務(wù)的確切性質(zhì)如何,這些服務(wù)都要求用戶披露他們的位置[6],以使應(yīng)用程序可以按照預(yù)期方式進行工作。然而,這種地理位置公開會導(dǎo)致用戶失去對其地理位置隱私的控制,因為有一些私密場所,比如家庭住址、禮拜場所等是人們不希望被泄露出去的。毫無疑問對于許多愿意了解更多用戶信息的公司來說,用戶的地理位置信息是一筆龐大的財富。許多應(yīng)用程序和公司將收集到的數(shù)據(jù)用于商業(yè)分析[7]、營銷、行為定位[8-11],或者只是將這些信息出售給外部各方。此外,許多移動應(yīng)用程序會在征得或未經(jīng)用戶同意的情況下跟蹤和收集用戶的位置,因此,地理位置隱私保護是一個與生活緊密相關(guān)的重要問題。
為此,國內(nèi)外學(xué)者提出了許多地理位置隱私保護機制,如k匿名[12]、差分隱私[13]、啞元Dummy[14]和Mix-zone[15]等方法。他們的目標(biāo)是保護用戶的位置隱私,同時仍然允許他們使用地理定位服務(wù)。在所有隱私保護機制中,k匿名和差分隱私被廣泛采用,并成為大多數(shù)后續(xù)研究工作的基礎(chǔ)。學(xué)者們提出了通用的隱私保證,雖然這些保證最初并非用于地理位置隱私保護,但是后來被證明可以成功地應(yīng)用于位置隱私。傳統(tǒng)差分隱私技術(shù)通常假設(shè)數(shù)據(jù)收集者是可信任的,忽略了收集者泄露信息的潛在風(fēng)險。為了克服這一缺點,Google[16]和Apple公司采用本地差分隱私技術(shù)(Local Differential Privacy, LDP)[17]。現(xiàn)有采用差分隱私的地理位置隱私保護機制大多數(shù)都是基于本地差分隱私。文獻[18-19]在地圖上構(gòu)建網(wǎng)格,將每個用戶的位置分配給網(wǎng)格中的單元格,然后根據(jù)隨機響應(yīng)方案發(fā)送網(wǎng)格中隨機一個單元格的數(shù)據(jù),由于這些方法以相同的方式擾動同一單元中的不同位置,它們很難為每個位置提供一個優(yōu)化的方案。文獻[20]提出了平面拉普拉斯機制,在不需要劃分網(wǎng)格的情況下使用拉普拉斯噪聲完成位置擾動,但是該機制會產(chǎn)生較大的誤差。文獻[21]提出的分段機制利用有界噪聲分布擾動一個點,也可以在不使用網(wǎng)格的情況下收集地理位置數(shù)據(jù)。然而該機制將位置點在每個維度進行獨立擾動,經(jīng)常會產(chǎn)生在一個維度中的值與原始位置相似,但在另一個維度中的值卻大不相同的擾動位置。因此,由該機制擾動獲得的位置其誤差往往很大。文獻[22]提出平方機制(Square Mechanism, SM),擾動位置在原始位置附近的矩形中概率較高,其他位置概率較低,其主要目的是在減少單個擾動位置的擾動誤差。
然而現(xiàn)有的地理位置隱私保護機制并未考慮這樣一個事實,即地理位置的敏感程度是不同的,比起商場、游樂園等公共場所,家庭住址、工作地點顯然更加敏感,同時對于不同敏感度的地點,人們的保護意愿也是不同的,敏感地點需要有效保護,非敏感地點可能不需要加以保護,而現(xiàn)有的地理位置隱私保護機制對不同位置的隱私保護程度等同對待。效用優(yōu)化本地差分隱私(Utility-optimized Local Differential Privacy, ULDP)機制[23]考慮了數(shù)據(jù)集中包含不同隱私保護級別數(shù)據(jù)這一情況下的差分隱私,但是僅適用于類別型數(shù)據(jù)的頻率估計,在地理位置隱私保護方面沒有應(yīng)用。本文考慮ULDP機制下的地理位置隱私保護方案,對平方機制加以改造,提出效用優(yōu)化的平方機制(Utility-optimized Square Mechanism, USM),該機制使得敏感地點擾動到自身周邊概率大,非敏感地點擾動到自身周邊概率加大。理論分析證明該機制對于敏感數(shù)據(jù)滿足本地差分隱私,同時在真實地理位置數(shù)據(jù)集上的實驗表明該機制具有較高的效用。
差分隱私(Differential Privacy, DP)由Dwork[13]定義了正式且可證明的隱私保證。該機制的思想是,無論數(shù)據(jù)集中是否存在單個元素,對數(shù)據(jù)集計算的聚合結(jié)果都應(yīng)該幾乎相同。換句話說,添加或刪除單個元素不應(yīng)顯著改變聚合函數(shù)的任何結(jié)果的概率。傳統(tǒng)差分隱私機制是將數(shù)據(jù)集中到1個數(shù)據(jù)中心之后再對數(shù)據(jù)進行處理,這種方法被稱為中心化差分隱私。但是,實際生活中想要找到1個可信的第三方數(shù)據(jù)中心是十分困難的,因此,用戶自己處理個人數(shù)據(jù)從而達到差分隱私效果的方法應(yīng)運而生,該方法被稱為本地差分隱私。其定義如下:
定義1 對于輸入集合X,輸出集合Y,任意x,x′∈X,y∈Y,機制M有:
Pr[M(x)=y]≤eε·Pr[M(x′)=y]
(1)
則稱機制M滿足ε-LDP。
效用優(yōu)化本地差分隱私是由Takao等人[23]提出的一種差分隱私機制,該機制針對數(shù)據(jù)之間隱私保護程度不同這一普遍事實,在本地差分隱私基礎(chǔ)上進行了改進,從而使隱私保護的效果得到優(yōu)化。其定義如下:
定義2 對于輸入集合X,輸出集合Y,其中敏感輸入為Xs,非敏感輸入為Xn,敏感輸出為Yp,非敏感輸出為Yi,擾動機制M有:
1)對于任意輸出y∈Yi,存在輸入x∈Xn使得Pr[M(x)=y]>0并且任意x′≠x有Pr[M(x)=y]=0。
2)對于任意輸出y∈Yp,任意輸入x,x′∈X,有Pr[M(x)=y]≤eε·Pr[M(x′)=y]。
則稱擾動機制M滿足ε-ULDP。
平方機制是Hong等人[22]提出的一種能夠基于隱私預(yù)算和整體區(qū)域大小減少擾動位置誤差的地理位置隱私保護方法。該機制著眼于滿足本地差分隱私的個體用戶位置收集問題,文獻[22]中實驗表明其在現(xiàn)有使用差分隱私的地理位置隱私保護機制中效果最好。其方案設(shè)計如下:
問題設(shè)置為在一個給定的二維矩陣平面D=[-d1,d1]×[-d2,d2]上,對某一點p進行擾動。
首先在平面D內(nèi)找出一個矩陣C*(p),其邊長為w,中心點坐標(biāo)為c。中心點c需要在保證矩陣整體都在D內(nèi)的同時,盡可能貼合被擾動點p。對于靠近平面邊緣的點,平方機制會將其設(shè)置為最靠近點p同時滿足矩陣C*(p)整體處于D內(nèi)的點,即對于維度i有:
(2)
對于經(jīng)過平方機制S擾動后的點p′=S(p)有:
(3)
定義3 對于點p和擾動得到的點p′,定義MSE作為其效用指標(biāo),MSE越小效用越好。有:
(4)
則給定點p其擾動期望值為:
(5)
假設(shè)點p在D上是均勻分布的,則:
(6)
其具體計算過程見文獻[22]。因為隱私預(yù)算ε,整體區(qū)域邊長d1、d2都是預(yù)先給出的,所以ES[MSE(p,p′)]與w直接相關(guān)。那么選取w使得ES[MSE(p,p′)]盡可能小就變成了一個優(yōu)化問題,即:
subject to 0
(7)
平方機制依據(jù)經(jīng)典的COBYLA算法[24]選取最優(yōu)情況下的邊長,該算法使用線性逼近的約束優(yōu)化進行求值,在此不再詳述。
在現(xiàn)有使用差分隱私的地理位置隱私保護機制中,大多數(shù)方法都將地理位置的隱私保護程度等同對待。本文將地理位置分為2個部分,敏感區(qū)域和非敏感區(qū)域,希望能夠?qū)γ舾袇^(qū)域加以更有效的保護,就像ULDP一樣。為此,本文基于ULDP機制對平方機制加以改造,設(shè)計一種新的機制,稱為效用優(yōu)化的平方機制。該機制對于敏感區(qū)域中的點,其擾動后只可能存在于敏感區(qū)域,非敏感區(qū)域中的點擾動后可能為自身也可能為敏感區(qū)域中的點。這種擾動方式可以在保證敏感區(qū)域的安全性的同時降低MSE和提高效用,即任意敏感區(qū)域中的點滿足LDP且擾動到自身周圍概率較大,非敏感區(qū)域中的點擾動到自身概率加大,整體MSE更小,效用更好。
在一個給定的二維矩陣平面D=[-d1,d1]×[-d2,d2]中,敏感區(qū)域為A={A1,A2,…,An},其面積為SA,非敏感區(qū)域為B,在D上對某一點p進行擾動。機制設(shè)計步驟如下:
步驟1 預(yù)處理,根據(jù)平面邊長d1、d2和隱私預(yù)算設(shè)置下限,由COBYLA算法求出最大最優(yōu)邊長w′,并對每個敏感區(qū)域Aj?A,1≤j≤n進行檢查更新,確保其邊長aj1、aj2滿足2·min(aj1,aj2)≥w′進行修改調(diào)整,這是為保證機制滿足ULDP進行的設(shè)置。
步驟2 與平方機制相同,根據(jù)平面邊長d1、d2和隱私預(yù)算ε,由COBYLA算法求出矩陣C*(p)和邊長w。
步驟3 若p∈B,不進行矩陣C*(p)求取;若p∈Aj,則令矩陣C*(p)的中心點c對于維度i有:
(8)
即對于靠近敏感區(qū)域邊緣的點,USM會將其設(shè)置為最靠近點p同時滿足矩陣C*(p)整體處于敏感區(qū)域A內(nèi)的點,如圖1所示。
(a) 點p位于敏感區(qū)域內(nèi)部
(b) 點p位于敏感區(qū)域邊緣圖1 矩陣C*(p)位置示意圖
步驟4 USM擾動概率為:
當(dāng)p∈A:
(9)
當(dāng)p∈B:
(10)
2.2.1 安全性證明
首先證明該機制符合ULDP。
推論1 對于任意的p′∈A,x,x′∈D,有Pr[U(x)=p′]≤eε·Pr[U(x′)=p′]。
證明:
(11)
推論2 對于任意的p′∈B,存在點x∈B使得Pr[U(x)=p′]>0,且任意x′≠x有Pr[U(x′)=p′]=0。
證明:
對任意的p′∈B,當(dāng)x∈A,Pr[U(x)=p′]=0;
當(dāng)x∈B∩x≠p′,Pr[U(x)=p′]=0;
當(dāng)且僅當(dāng)x=p′,Pr[U(x)=p′]>0。
2.2.2 效用分析
下面證明USM效用好于平方機制,即同等條件下MSE更小。
首先給出USM的效用計算公式。同樣使用定義3作為標(biāo)準(zhǔn),當(dāng)p為敏感點,有:
(12)
當(dāng)p為非敏感點,有:
(13)
因為EU[MSE(p,p′)]與ES[MSE(p,p′)]中參數(shù)不同,本文無法直接比較,所以使用以下方法來證明:
推論3 同等條件EU[MSE(p,p′)]
證明:
對于EU[MSE(p,p′)]與ES[MSE(p,p′)]兩者w相等且固定,因為根據(jù)公式(7)可知,w與平面邊長d1、d2和隱私預(yù)算ε相關(guān),與敏感區(qū)域面積SA無關(guān)。當(dāng)敏感區(qū)域面積SA擴大,對于敏感點a∈A,其映射到周邊矩陣C*(p)概率α·eε減小,MSE增大,效用變差;對于非敏感點b∈B,其映射到自身的概率β減小,MSE增大,效用變差。整體而言,SA與MSE成正相關(guān),SA越大效用越差。當(dāng)敏感區(qū)域A等于整個平面區(qū)域D,此時有α=αw,USM退化為平方機制,兩者效用EU[MSE(p,p′)]與ES[MSE(p,p′)]相等。由此,可以證得USM效用好于平方機制。
本文實驗環(huán)境設(shè)置如下:操作系統(tǒng)為Windows10,處理器為AMD Ryzen5 2600,內(nèi)存為16 GB,顯卡為RX580 8 GB。以下首先對機制中的預(yù)處理設(shè)置做簡要說明,然后在2種不同的真實地理位置數(shù)據(jù)集上進行實驗,一種采用南京地圖作為數(shù)據(jù),一種是Yelp數(shù)據(jù)集中Las Vegas數(shù)據(jù),最后將USM與現(xiàn)有方案中效果最好的平方機制進行對比。
預(yù)處理步驟確保USM符合ULDP,為此可能需要對敏感區(qū)域的邊長做一定修改。因為敏感區(qū)域可能為多個并且邊長不等,USM通過EU[MSE(p,p′)]求取w比較復(fù)雜,所以本文直接采用平方機制方法對w進行求取。通過計算可以發(fā)現(xiàn),在整體區(qū)域邊長給定且ε>1的情況下,ε越小,最優(yōu)邊長w越大,ES[MSE(p,p′)]越大,實用性越差。本文在d1=1000,d2=1000,ε={1,2,…,20}的條件下運行COBYLA算法,其實驗結(jié)果如圖2所示。實際使用時可以權(quán)衡隱私保護和效用自行設(shè)置ε下限。
圖2 ε-w關(guān)系圖
本文采用與平方機制相同的實驗設(shè)置,隱私預(yù)算ε設(shè)置為5~20。為了方便進行對比,默認(rèn)設(shè)置敏感區(qū)域只有一個且位于中心點,其邊長為整體區(qū)域長度的1/2。將USM與平方機制進行對比,圖3為使用南京地圖數(shù)據(jù)集的實驗結(jié)果,圖4為使用Yelp Las Vegas數(shù)據(jù)集的實驗結(jié)果。通過圖3和圖4的實驗結(jié)果對比可以發(fā)現(xiàn)USM效果明顯好于平方機制。
圖3 南京地圖數(shù)據(jù)集實驗對比
圖4 Yelp數(shù)據(jù)集實驗對比
為了防止數(shù)據(jù)集帶來的偏差,本文使用不同的敏感區(qū)域進行重復(fù)實驗。圖5為使用南京地圖數(shù)據(jù)集中不同區(qū)域作為敏感區(qū)域,USM與平方機制的效用對比??梢钥闯鯱SM效果確實比平方機制有顯著提升。
(a) 敏感區(qū)域位于整體左下部分
(b) 敏感區(qū)域位于整體左上部分
(c) 敏感區(qū)域位于整體右下部分
(d) 敏感區(qū)域位于整體右上部分圖5 不同敏感區(qū)域位置南京數(shù)據(jù)集實驗對比
在現(xiàn)實地理位置平面中敏感區(qū)域通常為多個。為此,接下來針對二維平面區(qū)域內(nèi)存在多個敏感區(qū)域的情況進行實驗。本文分別設(shè)置敏感區(qū)域個數(shù)n為2/4/6,每個敏感區(qū)域邊長為整體區(qū)域邊長的1/8,敏感區(qū)域位置隨機分布,重復(fù)計算10次取平均值,為了防止最優(yōu)邊長過大導(dǎo)致預(yù)處理時發(fā)生敏感區(qū)域的合并,設(shè)置隱私預(yù)算ε范圍為10~20,在Yelp數(shù)據(jù)集上實驗結(jié)果如圖6所示,可見,在多敏感區(qū)域的情況下USM的效用仍然優(yōu)于平方機制。
(a) n=2時的Yelp實驗結(jié)果
(b) n=4時的Yelp實驗結(jié)果
(c) n=6時的Yelp實驗結(jié)果圖6 多敏感區(qū)域下Yelp數(shù)據(jù)集實驗對比
針對現(xiàn)有地理位置隱私保護機制忽略了地理位置敏感度不同這一問題,本文將效用優(yōu)化的本地差分隱私與平方機制相結(jié)合,提出了效用優(yōu)化的平方機制USM。理論和實驗證明,本文的機制相較于現(xiàn)有的機制在效用上有顯著的提高。
針對未來的工作,當(dāng)前的方法將地理位置分為敏感和非敏感2個部分,但是現(xiàn)實生活中仍有將敏感程度進一步劃分的需求,目前沒有對不同數(shù)量的敏感地理位置等級進行處理的機制,也沒有框架在不同數(shù)量的敏感等級下描述平方機制,因此可以沿著這個方向進行深入探索,這一點可以參考可區(qū)分輸入的本地差分隱私機制(Min-ID LDP)[25]。同時,矩陣邊長w的求取方法也存在進一步優(yōu)化的可能。最后,在連續(xù)軌跡隱私保護場景中,使用差分隱私的地理位置保護機制面臨隱私預(yù)算難以合理分配以及位置數(shù)據(jù)失真的挑戰(zhàn),同時也缺乏對不同數(shù)量的敏感等級的研究,本文機制可以與一些連續(xù)軌跡隱私保護研究[26-28]相結(jié)合,探究連續(xù)位置隱私保護情境下不同敏感等級的保護機制。