保護(hù)位置隱私的效用優(yōu)化本地差分隱私機制

馮立剛,朱友文,2

(1.南京航空航天大學(xué)計算機科學(xué)與技術(shù)學(xué)院,江蘇 南京 211106;2.桂林電子科技大學(xué)廣西密碼學(xué)與信息安全重點實驗室,廣西 桂林 541010)

0 引 言

近年來移動智能設(shè)備已經(jīng)成為城市居民的一種標(biāo)準(zhǔn)配置，手機、平板和智能手表成為人們現(xiàn)代化生活不可或缺的一部分。用戶隨身攜帶智能設(shè)備，依據(jù)智能設(shè)備的傳感器獲取的數(shù)據(jù)，用戶能夠?qū)崟r確定自己的位置，然后使用它與基于位置的服務(wù)應(yīng)用進(jìn)行交互[1-2]。據(jù)此，用戶可以隨時隨地訪問各種服務(wù)，比如查詢附近的餐廳[3]、打車[4]、推薦[5]等。無論這些服務(wù)的確切性質(zhì)如何，這些服務(wù)都要求用戶披露他們的位置[6]，以使應(yīng)用程序可以按照預(yù)期方式進(jìn)行工作。然而，這種地理位置公開會導(dǎo)致用戶失去對其地理位置隱私的控制，因為有一些私密場所，比如家庭住址、禮拜場所等是人們不希望被泄露出去的。毫無疑問對于許多愿意了解更多用戶信息的公司來說，用戶的地理位置信息是一筆龐大的財富。許多應(yīng)用程序和公司將收集到的數(shù)據(jù)用于商業(yè)分析[7]、營銷、行為定位[8-11]，或者只是將這些信息出售給外部各方。此外，許多移動應(yīng)用程序會在征得或未經(jīng)用戶同意的情況下跟蹤和收集用戶的位置，因此，地理位置隱私保護(hù)是一個與生活緊密相關(guān)的重要問題。

為此，國內(nèi)外學(xué)者提出了許多地理位置隱私保護(hù)機制,如k匿名[12]、差分隱私[13]、啞元Dummy[14]和Mix-zone[15]等方法。他們的目標(biāo)是保護(hù)用戶的位置隱私，同時仍然允許他們使用地理定位服務(wù)。在所有隱私保護(hù)機制中，k匿名和差分隱私被廣泛采用，并成為大多數(shù)后續(xù)研究工作的基礎(chǔ)。學(xué)者們提出了通用的隱私保證，雖然這些保證最初并非用于地理位置隱私保護(hù)，但是后來被證明可以成功地應(yīng)用于位置隱私。傳統(tǒng)差分隱私技術(shù)通常假設(shè)數(shù)據(jù)收集者是可信任的，忽略了收集者泄露信息的潛在風(fēng)險。為了克服這一缺點，Google[16]和Apple公司采用本地差分隱私技術(shù)(Local Differential Privacy， LDP)[17]?，F(xiàn)有采用差分隱私的地理位置隱私保護(hù)機制大多數(shù)都是基于本地差分隱私。文獻(xiàn)[18-19]在地圖上構(gòu)建網(wǎng)格，將每個用戶的位置分配給網(wǎng)格中的單元格，然后根據(jù)隨機響應(yīng)方案發(fā)送網(wǎng)格中隨機一個單元格的數(shù)據(jù)，由于這些方法以相同的方式擾動同一單元中的不同位置，它們很難為每個位置提供一個優(yōu)化的方案。文獻(xiàn)[20]提出了平面拉普拉斯機制，在不需要劃分網(wǎng)格的情況下使用拉普拉斯噪聲完成位置擾動，但是該機制會產(chǎn)生較大的誤差。文獻(xiàn)[21]提出的分段機制利用有界噪聲分布擾動一個點，也可以在不使用網(wǎng)格的情況下收集地理位置數(shù)據(jù)。然而該機制將位置點在每個維度進(jìn)行獨立擾動，經(jīng)常會產(chǎn)生在一個維度中的值與原始位置相似，但在另一個維度中的值卻大不相同的擾動位置。因此，由該機制擾動獲得的位置其誤差往往很大。文獻(xiàn)[22]提出平方機制(Square Mechanism， SM)，擾動位置在原始位置附近的矩形中概率較高，其他位置概率較低，其主要目的是在減少單個擾動位置的擾動誤差。

然而現(xiàn)有的地理位置隱私保護(hù)機制并未考慮這樣一個事實，即地理位置的敏感程度是不同的，比起商場、游樂園等公共場所，家庭住址、工作地點顯然更加敏感，同時對于不同敏感度的地點，人們的保護(hù)意愿也是不同的，敏感地點需要有效保護(hù)，非敏感地點可能不需要加以保護(hù)，而現(xiàn)有的地理位置隱私保護(hù)機制對不同位置的隱私保護(hù)程度等同對待。效用優(yōu)化本地差分隱私(Utility-optimized Local Differential Privacy, ULDP)機制[23]考慮了數(shù)據(jù)集中包含不同隱私保護(hù)級別數(shù)據(jù)這一情況下的差分隱私，但是僅適用于類別型數(shù)據(jù)的頻率估計，在地理位置隱私保護(hù)方面沒有應(yīng)用。本文考慮ULDP機制下的地理位置隱私保護(hù)方案，對平方機制加以改造，提出效用優(yōu)化的平方機制(Utility-optimized Square Mechanism, USM)，該機制使得敏感地點擾動到自身周邊概率大，非敏感地點擾動到自身周邊概率加大。理論分析證明該機制對于敏感數(shù)據(jù)滿足本地差分隱私，同時在真實地理位置數(shù)據(jù)集上的實驗表明該機制具有較高的效用。

1 背景知識

1.1 本地差分隱私

差分隱私(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ù)進(jìn)行處理，這種方法被稱為中心化差分隱私。但是，實際生活中想要找到1個可信的第三方數(shù)據(jù)中心是十分困難的，因此，用戶自己處理個人數(shù)據(jù)從而達(dá)到差分隱私效果的方法應(yīng)運而生，該方法被稱為本地差分隱私。其定義如下:

定義1 對于輸入集合X，輸出集合Y，任意x，x′∈X，y∈Y，機制M有：

Pr[M(x)=y]≤eε·Pr[M(x′)=y]

(1)

則稱機制M滿足ε-LDP。

1.2 效用優(yōu)化本地差分隱私

效用優(yōu)化本地差分隱私是由Takao等人[23]提出的一種差分隱私機制，該機制針對數(shù)據(jù)之間隱私保護(hù)程度不同這一普遍事實，在本地差分隱私基礎(chǔ)上進(jìn)行了改進(jìn)，從而使隱私保護(hù)的效果得到優(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。

1.3 平方機制

平方機制是Hong等人[22]提出的一種能夠基于隱私預(yù)算和整體區(qū)域大小減少擾動位置誤差的地理位置隱私保護(hù)方法。該機制著眼于滿足本地差分隱私的個體用戶位置收集問題,文獻(xiàn)[22]中實驗表明其在現(xiàn)有使用差分隱私的地理位置隱私保護(hù)機制中效果最好。其方案設(shè)計如下：

問題設(shè)置為在一個給定的二維矩陣平面D=[-d1,d1]×[-d2,d2]上，對某一點p進(jìn)行擾動。

首先在平面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)

其具體計算過程見文獻(xiàn)[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)化進(jìn)行求值，在此不再詳述。

2 效用優(yōu)化的平方機制

在現(xiàn)有使用差分隱私的地理位置隱私保護(hù)機制中，大多數(shù)方法都將地理位置的隱私保護(hù)程度等同對待。本文將地理位置分為2個部分，敏感區(qū)域和非敏感區(qū)域，希望能夠?qū)γ舾袇^(qū)域加以更有效的保護(hù)，就像ULDP一樣。為此，本文基于ULDP機制對平方機制加以改造，設(shè)計一種新的機制，稱為效用優(yōu)化的平方機制。該機制對于敏感區(qū)域中的點，其擾動后只可能存在于敏感區(qū)域，非敏感區(qū)域中的點擾動后可能為自身也可能為敏感區(qū)域中的點。這種擾動方式可以在保證敏感區(qū)域的安全性的同時降低MSE和提高效用，即任意敏感區(qū)域中的點滿足LDP且擾動到自身周圍概率較大，非敏感區(qū)域中的點擾動到自身概率加大，整體MSE更小，效用更好。

2.1 機制設(shè)計

在一個給定的二維矩陣平面D=[-d1,d1]×[-d2,d2]中，敏感區(qū)域為A={A1,A2,…,An}，其面積為SA，非敏感區(qū)域為B，在D上對某一點p進(jìn)行擾動。機制設(shè)計步驟如下：

步驟1 預(yù)處理，根據(jù)平面邊長d1、d2和隱私預(yù)算設(shè)置下限，由COBYLA算法求出最大最優(yōu)邊長w′，并對每個敏感區(qū)域Aj?A，1≤j≤n進(jìn)行檢查更新，確保其邊長aj1、aj2滿足2·min(aj1,aj2)≥w′進(jìn)行修改調(diào)整，這是為保證機制滿足ULDP進(jìn)行的設(shè)置。

步驟2 與平方機制相同，根據(jù)平面邊長d1、d2和隱私預(yù)算ε，由COBYLA算法求出矩陣C*(p)和邊長w。

步驟3 若p∈B，不進(jìn)行矩陣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 理論分析

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效用好于平方機制。

3 實驗結(jié)果與分析

本文實驗環(huán)境設(shè)置如下：操作系統(tǒng)為Windows10，處理器為AMD Ryzen5 2600，內(nèi)存為16 GB，顯卡為RX580 8 GB。以下首先對機制中的預(yù)處理設(shè)置做簡要說明，然后在2種不同的真實地理位置數(shù)據(jù)集上進(jìn)行實驗，一種采用南京地圖作為數(shù)據(jù)，一種是Yelp數(shù)據(jù)集中Las Vegas數(shù)據(jù)，最后將USM與現(xiàn)有方案中效果最好的平方機制進(jìn)行對比。

3.1 預(yù)處理設(shè)置

預(yù)處理步驟確保USM符合ULDP，為此可能需要對敏感區(qū)域的邊長做一定修改。因為敏感區(qū)域可能為多個并且邊長不等，USM通過EU[MSE(p,p′)]求取w比較復(fù)雜，所以本文直接采用平方機制方法對w進(jìn)行求取。通過計算可以發(fā)現(xiàn)，在整體區(qū)域邊長給定且ε>1的情況下，ε越小，最優(yōu)邊長w越大，ES[MSE(p,p′)]越大，實用性越差。本文在d1=1000,d2=1000,ε={1,2,…,20}的條件下運行COBYLA算法，其實驗結(jié)果如圖2所示。實際使用時可以權(quán)衡隱私保護(hù)和效用自行設(shè)置ε下限。

圖2 ε-w關(guān)系圖

3.2 對比試驗

本文采用與平方機制相同的實驗設(shè)置，隱私預(yù)算ε設(shè)置為5～20。為了方便進(jìn)行對比，默認(rèn)設(shè)置敏感區(qū)域只有一個且位于中心點，其邊長為整體區(qū)域長度的1/2。將USM與平方機制進(jìn)行對比，圖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ū)域進(jìn)行重復(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ū)域的情況進(jìn)行實驗。本文分別設(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ù)集實驗對比

4 結(jié)束語

針對現(xiàn)有地理位置隱私保護(hù)機制忽略了地理位置敏感度不同這一問題，本文將效用優(yōu)化的本地差分隱私與平方機制相結(jié)合，提出了效用優(yōu)化的平方機制USM。理論和實驗證明，本文的機制相較于現(xiàn)有的機制在效用上有顯著的提高。

針對未來的工作，當(dāng)前的方法將地理位置分為敏感和非敏感2個部分，但是現(xiàn)實生活中仍有將敏感程度進(jìn)一步劃分的需求，目前沒有對不同數(shù)量的敏感地理位置等級進(jìn)行處理的機制，也沒有框架在不同數(shù)量的敏感等級下描述平方機制，因此可以沿著這個方向進(jìn)行深入探索，這一點可以參考可區(qū)分輸入的本地差分隱私機制(Min-ID LDP)[25]。同時，矩陣邊長w的求取方法也存在進(jìn)一步優(yōu)化的可能。最后，在連續(xù)軌跡隱私保護(hù)場景中，使用差分隱私的地理位置保護(hù)機制面臨隱私預(yù)算難以合理分配以及位置數(shù)據(jù)失真的挑戰(zhàn)，同時也缺乏對不同數(shù)量的敏感等級的研究，本文機制可以與一些連續(xù)軌跡隱私保護(hù)研究[26-28]相結(jié)合，探究連續(xù)位置隱私保護(hù)情境下不同敏感等級的保護(hù)機制。