保護位置隱私的效用優化本地差分隱私機制

馮立剛,朱友文,2

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

0 引 言

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

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

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

1 背景知識

1.1 本地差分隱私

差分隱私(Differential Privacy, DP)由Dwork[13]定義了正式且可證明的隱私保證。該機制的思想是，無論數據集中是否存在單個元素，對數據集計算的聚合結果都應該幾乎相同。換句話說，添加或刪除單個元素不應顯著改變聚合函數的任何結果的概率。傳統差分隱私機制是將數據集中到1個數據中心之后再對數據進行處理，這種方法被稱為中心化差分隱私。但是，實際生活中想要找到1個可信的第三方數據中心是十分困難的，因此，用戶自己處理個人數據從而達到差分隱私效果的方法應運而生，該方法被稱為本地差分隱私。其定義如下:

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

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

(1)

則稱機制M滿足ε-LDP。

1.2 效用優化本地差分隱私

效用優化本地差分隱私是由Takao等人[23]提出的一種差分隱私機制，該機制針對數據之間隱私保護程度不同這一普遍事實，在本地差分隱私基礎上進行了改進，從而使隱私保護的效果得到優化。其定義如下:

定義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]提出的一種能夠基于隱私預算和整體區域大小減少擾動位置誤差的地理位置隱私保護方法。該機制著眼于滿足本地差分隱私的個體用戶位置收集問題,文獻[22]中實驗表明其在現有使用差分隱私的地理位置隱私保護機制中效果最好。其方案設計如下：

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

首先在平面D內找出一個矩陣C*(p)，其邊長為w，中心點坐標為c。中心點c需要在保證矩陣整體都在D內的同時，盡可能貼合被擾動點p。對于靠近平面邊緣的點，平方機制會將其設置為最靠近點p同時滿足矩陣C*(p)整體處于D內的點，即對于維度i有:

(2)

對于經過平方機制S擾動后的點p′=S(p)有:

(3)

定義3 對于點p和擾動得到的點p′，定義MSE作為其效用指標，MSE越小效用越好。有：

(4)

則給定點p其擾動期望值為：

(5)

假設點p在D上是均勻分布的，則：

(6)

其具體計算過程見文獻[22]。因為隱私預算ε，整體區域邊長d1、d2都是預先給出的，所以ES[MSE(p,p′)]與w直接相關。那么選取w使得ES[MSE(p,p′)]盡可能小就變成了一個優化問題，即：

subject to 0

(7)

平方機制依據經典的COBYLA算法[24]選取最優情況下的邊長，該算法使用線性逼近的約束優化進行求值，在此不再詳述。

2 效用優化的平方機制

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

2.1 機制設計

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

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

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

步驟3 若p∈B，不進行矩陣C*(p)求取;若p∈Aj，則令矩陣C*(p)的中心點c對于維度i有:

(8)

即對于靠近敏感區域邊緣的點，USM會將其設置為最靠近點p同時滿足矩陣C*(p)整體處于敏感區域A內的點，如圖1所示。

(a) 點p位于敏感區域內部

(b) 點p位于敏感區域邊緣圖1 矩陣C*(p)位置示意圖

步驟4 USM擾動概率為:

當p∈A:

(9)

當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，當x∈A,Pr[U(x)=p′]=0;

當x∈B∩x≠p′，Pr[U(x)=p′]=0;

當且僅當x=p′，Pr[U(x)=p′]>0。

2.2.2 效用分析

下面證明USM效用好于平方機制，即同等條件下MSE更小。

首先給出USM的效用計算公式。同樣使用定義3作為標準，當p為敏感點，有：

(12)

當p為非敏感點，有:

(13)

因為EU[MSE(p,p′)]與ES[MSE(p,p′)]中參數不同，本文無法直接比較，所以使用以下方法來證明：

推論3 同等條件EU[MSE(p,p′)]

證明:

對于EU[MSE(p,p′)]與ES[MSE(p,p′)]兩者w相等且固定，因為根據公式(7)可知，w與平面邊長d1、d2和隱私預算ε相關，與敏感區域面積SA無關。當敏感區域面積SA擴大，對于敏感點a∈A，其映射到周邊矩陣C*(p)概率α·eε減小，MSE增大，效用變差;對于非敏感點b∈B，其映射到自身的概率β減小，MSE增大，效用變差。整體而言，SA與MSE成正相關，SA越大效用越差。當敏感區域A等于整個平面區域D，此時有α=αw，USM退化為平方機制，兩者效用EU[MSE(p,p′)]與ES[MSE(p,p′)]相等。由此，可以證得USM效用好于平方機制。

3 實驗結果與分析

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

3.1 預處理設置

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

圖2 ε-w關系圖

3.2 對比試驗

本文采用與平方機制相同的實驗設置，隱私預算ε設置為5～20。為了方便進行對比，默認設置敏感區域只有一個且位于中心點，其邊長為整體區域長度的1/2。將USM與平方機制進行對比，圖3為使用南京地圖數據集的實驗結果，圖4為使用Yelp Las Vegas數據集的實驗結果。通過圖3和圖4的實驗結果對比可以發現USM效果明顯好于平方機制。

圖3 南京地圖數據集實驗對比

圖4 Yelp數據集實驗對比

為了防止數據集帶來的偏差，本文使用不同的敏感區域進行重復實驗。圖5為使用南京地圖數據集中不同區域作為敏感區域，USM與平方機制的效用對比?？梢钥闯鯱SM效果確實比平方機制有顯著提升。

(a) 敏感區域位于整體左下部分

(b) 敏感區域位于整體左上部分

(c) 敏感區域位于整體右下部分

(d) 敏感區域位于整體右上部分圖5 不同敏感區域位置南京數據集實驗對比

在現實地理位置平面中敏感區域通常為多個。為此，接下來針對二維平面區域內存在多個敏感區域的情況進行實驗。本文分別設置敏感區域個數n為2/4/6，每個敏感區域邊長為整體區域邊長的1/8，敏感區域位置隨機分布，重復計算10次取平均值，為了防止最優邊長過大導致預處理時發生敏感區域的合并，設置隱私預算ε范圍為10～20，在Yelp數據集上實驗結果如圖6所示，可見，在多敏感區域的情況下USM的效用仍然優于平方機制。

(a) n=2時的Yelp實驗結果

(b) n=4時的Yelp實驗結果

(c) n=6時的Yelp實驗結果圖6 多敏感區域下Yelp數據集實驗對比

4 結束語

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

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