基于本地差分隱私的眾包隱私保護方法

趙 龍,龍士工,2

(1.貴州大學計算機科學與技術學院,貴州 貴陽 550025; 2.貴州大學公共大數據國家重點實驗室,貴州 貴陽 550025)

0 引 言

隨著互聯網的飛速發(fā)展，眾包工作模式已經成為了一種廣泛使用的任務執(zhí)行模式，通過高效協同群智資源來匯聚群體智慧從而有效地解決問題，特別是針對那些單獨使用計算機難以完成但是對于個人來說相對簡單的任務。由于位置服務的普及，個人位置信息就很輕易地被獲取從而進行位置數據挖掘分析。攻擊者甚至可以推測出個人的喜好、生活習慣等更為敏感[1-3]的信息。

在目前的研究工作中，文獻[4]和文獻[5]提供了一種產生虛假位置的保護隱私的方法，用戶是在發(fā)送個人真實位置的同時，發(fā)送產生的假位置進行混雜;文獻[6]和文獻[7]則是將目前流行的差分隱私技術應用到位置隱私保護領域之中，其工作內容為將可控噪聲引入隨機機制中，在數據發(fā)布環(huán)節(jié)中，已經證明是可用且有效的?，F有的關于位置數據隱私保護的研究工作中，大部分是直接將差分隱私技術應用到位置數據信息發(fā)布環(huán)節(jié)上。文獻[8]采用了差分隱私擾動方法在數據發(fā)布上進行保護,文獻[9]是利用k-匿名技術來保護位置隱私。

在上述位置數據采集模式中，都是用戶直接將個人真實的地理位置發(fā)送給數據采集者，由數據采集方來進行相關的擾動操作，這樣有2個前提：1)數據采集方對于移動用戶來說是可信的，并且采集方不會故意泄露甚至販賣用戶的數據信息；2)移動用戶愿意將自己的真實位置提供給數據采集方。首先，由于大量的采集方是不可信的，社會上出現很多服務提供商販賣移動用戶的個人數據，導致隱私數據泄露問題普遍存在；其次，由于人們不愿意將自己的精確位置數據暴露在外，因此很難獲取其真實數據。根據上述分析，本地化差分隱私技術是處理該情況最好的方法。在本地化差分隱私模型之中，用戶的真實數據在流出客戶端之前通過滿足差分隱私機制進行擾動處理生成近似數據，將近似數據發(fā)送給數據收集方。文獻[10]采用維諾圖方式對路網空間進行劃分，客戶端對于用戶位置數據信息進行差分隱私保護之后發(fā)送給服務器，這樣便保護了移動用戶的位置數據隱私。如果簡單地將差分隱私運用到位置數據之中，會有這個問題[11-12]，對于位置數據集來說，由于其敏感度的測量與位置距離有關，如果簡單將傳統的差分隱私方法用來計算其敏感度，則會涉及位置數據集中最遠距離，出現敏感度較大的問題，導致數據的可用性降低。

地理不可區(qū)分性[13-14]，是對差分隱私應用在幾何空間中的擴展。地理不可區(qū)分性引入了距離這一概念，即在用戶指定的范圍之中，用戶的真實位置和產生的近似位置是不能區(qū)分的。該機制是將可控的噪聲添加到用戶的精準位置數據上從而產生出虛假位置。在半徑為r的圓形區(qū)域范圍之中，虛假位置和真實位置之間相似度極高，導致攻擊者無法區(qū)分兩者區(qū)別。

本文的主要研究內容是：基于本地化差分隱私技術在眾包中的位置數據上的理論與實現，具體來說，本文的主要工作如下：

提出一種地理不可區(qū)分性算法應用在眾包位置數據保護方法。在不暴露用戶的真實位置的情況下，服務器端可以在近似位置上進行空間范圍查詢，達到其相同的效應同時保護用戶的位置數據信息。

提出一種對于網格劃分上以工人計數為衡量標準的隱私預算自適應方法，通過各個子網格上的工人計數占比合理分配隱私預算，從而提高隱私預算的利用率。

提出一種二級區(qū)域網格劃分方法，將差分隱私機制應用在網格劃分的人數計數保護上，在數據發(fā)布環(huán)節(jié)中保護地理區(qū)域位置計數隱私。

通過實驗對本文提出的方法進行驗證，表明該方法在數據精確度上具有優(yōu)勢。

1 預備知識

1.1 系統結構

在某一時刻下，移動用戶設備擁有一條由該移動設備所生成的位置數據信息，由于前文提到的隱私泄露的問題，用戶往往不會發(fā)送自己的真實位置給數據采集方，而是先將自己的真實位置進行算法擾動得到近似位置，再將近似位置發(fā)送給服務器。服務器通過得到的數據以某種計算方法獲取其統計結果。

本文研究的問題系統結構如圖1所示。客戶端生成擾動位置后發(fā)送給服務器端。服務器內包含了地圖網格劃分、網格人數擾動以及查詢結果返回3個模塊。

圖1 差分隱私的眾包位置數據保護系統結構

1.2 本地化差分隱私

本地化差分隱私[15-20](Local Differential Privacy, LDP)與傳統差分隱私(Differential Privacy, DP)之間是有區(qū)別的，移動用戶的位置數據在移動用戶設備流出數據之前就已經被擾動過。

定義1 本地化差分隱私(LDP)[9]。隨機算法F滿足ε-LDP，當且僅當對于a，a1∈A，任意的B?Range(A)：

P[F(a)∈B]≤eε×P[F(a1)∈B]

(1)

其中，A、Range(A)分別為函數F的定義域與值域。

定義2 拉普拉斯機制。在點c周圍生成噪音點c1的概率隨著兩者之間的距離為指數遞減，其概率密度函數f為：

(2)

性質1 差分隱私的并行性。若2個A1、A2分別是滿足ε1、ε2的差分隱私算法，并且應用在獨立的數據集上，則組合算法是滿足max{ε1，ε2}-差分隱私。

1.3 地理不可區(qū)分性

定義3 隱私級別。對任意半徑r大于0的范圍空間，若該機制滿足ε-地理不可區(qū)分性[13]，其中ε為差分隱私中的隱私預算，則用戶在半徑為r的圓形區(qū)域內擁有εr-隱私，其中εr為該區(qū)域內位置點之間的隱私級別l。

定義4 地理不可區(qū)分性。當x，x1∈X，Y是X通過機制G的輸出結果，若機制G滿足ε-地理不可區(qū)分性,則對所有歐氏距離d(x,x1)≤r，其中r為上述機制保護的范圍，報告位置點y∈Y，有：

G(x)(y)≤eεd(x,x1)G(x1)(y)

(3)

其中，G(x)(y)表示在該位置點x報告y的概率。式(3)中表示當輸入為x與x1時，將得到相同的輸出y的概率在eεd(x,x1)范圍內。

由于差分隱私的Laplace機制是應用在一維數據之中，而位置坐標卻是二維數據，所以首先需要定義一個連續(xù)的機制，滿足連續(xù)平面的地理不可區(qū)分性。

定義5 平面拉普拉斯分布[13]。對指定ε∈R2,實際位置x∈R2,對于任意一個進行該機制生成的虛假位置y∈R2，該概率密度函數為：

(4)

公式(5)是以x為中心點的平面Laplace分布。在極坐標下，原點為x的概率密度函數為：

(5)

由于真實情況下，往往都是用離散坐標表示位置點。通過將其離散化，使地理不可區(qū)分性機制可以使用到離散的笛卡兒坐標系中。

移動用戶真實位置x,向極坐標中的x添加可控噪聲(r,θ)，根據離散化操作，獲得其近似位置Y={y1,y2,y3,…,yn}，機制的查詢函數G(x)(y)作為x點的概率累計函數。由于極坐標映射到笛卡兒坐標系上所產生的不規(guī)則性，為保持其數據可用性程度，通過調整隱私參數，滿足其地理不可區(qū)分性。

令rmax

(6)

其中，u為笛卡兒坐標網格步長單元，σr、σθ為機器繪制坐標中半徑和角度的精確度[21]。在直徑為rmax的范圍內，Gε′滿足ε-地理不可區(qū)分性，即對d(x,y),d(x′,y)≤r時查詢函數G有：

Gε′(x)(y)≤eεd(x,x′)Gε′(x′)(y)

(7)

其中G(x)(y)是在點x報告點y的概率。

2 本地化差分隱私的位置眾包流程

滿足本地化差分隱私的位置數據保護算法的流程如下：1)用戶得到其移動設備所產生的真實位置x，然后通過滿足地理不可區(qū)分性機制來產生近似位置y，并且發(fā)送給服務器；2)服務器收到位置y后對位置數據集進行二級區(qū)域劃分，得到其每個子區(qū)域內的人數計數N；3)服務器將每個子區(qū)域內人數進行滿足差分隱私的加噪擾動得到擾動數據N1并發(fā)布。

數據流向如圖2所示。

圖2 數據流向

2.1 滿足地理不可區(qū)分性的位置數據擾動

移動用戶獲得真實位置數據信息后，由于ε1-地理不可區(qū)分性的隱私保護等級限制，需要調整參數ε1的方式保證其可用性。針對個人的真實位置，角度θ和半徑r由擾動機制來決定，最后，在需要生成虛假位置的范圍內，通過將噪聲(r,θ)添加在真實位置上，得到虛假位置y[21]。

2.2 地圖劃分網格

本文將得到的位置數據集做成一個大型區(qū)域網格圖[22]，然后均分為4份一級子區(qū)域，得到其每個一級子區(qū)域內的網格人數統計M，根據每個一級子區(qū)域內的網格人數排序，按照人數多少依次劃分為3×3、2×3、2×2、2×1的二級子區(qū)域網格。分割步驟如圖3所示，實際效果如圖4和圖5所示。

圖3 區(qū)域網格圖劃分

圖4 一級網格劃分

圖5 二級網格劃分

結合上述內容，滿足本地化差分隱私的數據保護算法如算法1所示。

算法1ε-Geo算法

輸入：實際位置x，隱私預算ε1、ε2,參數u、q、σr、σθ；

輸出：近似位置y，網路圖W(Nj,Y)

Step1//位置擾動

For each 用戶ui

生成真實位置數據x;

生成虛假位置y;

將虛假位置報告給服務器;

End for

Step2//計數加噪

服務器得到用戶報告位置;

將位置數據進行區(qū)域二級劃分得到W(Ni,Y);

計算每個二級子區(qū)域占比Pi;

將每個區(qū)域內計數Ni添加對應Laplace噪聲生成Nj;

將區(qū)域信息W(Nj,Y)發(fā)布;

End

3 實驗分析

為了驗證本文所采用的算法的可行性，本實驗采用真實的公共位置數據集Gowalla。共有10163名用戶合計456967條用戶位置簽到數據。為了直觀地表現出ε-Geo算法對于位置點的影響，實驗采用文獻[23]提出的相對誤差來判定其算法精確度，用A(f)表示在真實數據集上執(zhí)行查詢f的結果，B(f)表示在擾動后數據集上執(zhí)行查詢f的結果。

(8)

其中，s是一個常數，本實驗中，s=0.001×|D|,|D|表示數據集中的位置數據數目。

在位置數據集中隨機選取一個用戶位置點，對該位置點分別進行以保護范圍為200 m、700 m的程度進行算法加噪后以得到的近似位置為中心點0.5 km、1 km、1.5 km范圍內的位置點的查詢，每次查詢執(zhí)行10次，取其平均相對誤差。如圖6所示。

ε=0.2

ε=0.5

ε=1

從圖6可以看出，隨著查詢范圍的增加，真實位置與近似位置的相對誤差會越來越小，在近似位置上查詢的結果會更加接近真實結果。當查詢范圍減小時，誤差率會有提升。

本文將ε-DP算法與ε-Geo算法以保護范圍為200 m加噪后產生的位置點以1 km為范圍作查詢的相對誤差進行對比，如表1所示。

表1 2種算法相對誤差對比

從表1和圖7可以看出，對于同范圍檢索查詢的情況下，ε-Geo算法誤差率更小，查詢精確度提高了至少2.7%。

圖7 以1 km為范圍查詢誤差對比

本文將ε-Geo算法對于區(qū)域計數加噪的精確度與equal分配隱私預算后計數加噪進行對比，選擇區(qū)域為一個子區(qū)域內擁有過大計數C5和2個二級子區(qū)域擁有計數較少C19、C20的區(qū)域。從表2和圖8可以看出，對于計數區(qū)域較小的情況下，ε-Geo算法誤差率更小，精確度提高了至少4.62個百分點，對于計數區(qū)域較大的情況，ε-Geo算法也同樣提高了精確度。

表2 隱私保護強度對比

圖8 3個區(qū)域的計數精確率對比

4 結束語

根據現在大量的位置數據信息的使用，人們對于自己的個人位置隱私越來越重視，在數據流出移動設備之前就進行差分隱私保護這一方式更加安全。本文提出了一種基于本地化差分隱私的眾包隱私保護方法。在用戶的真實位置上進行滿足差分隱私機制的地理不可區(qū)分性加噪方式得到近似位置，發(fā)送給服務器方，服務器根據獲得的近似位置生成二級網格區(qū)域圖，并將每個子區(qū)域內的人數計數添加滿足拉普拉斯機制的噪聲得到近似人數，最后進行發(fā)布。通過實驗可以看出，傳統的差分隱私對于地理位置的加噪方式，該算法所使用的地理不可區(qū)分性的方式能夠降低其查詢結果的誤差度，并且在近似位置對于與真實位置較遠距離的查詢和在真實位置上進行查詢結果較為接近。研究如何保護眾包地理位置隱私的技術具有廣闊的研究意義和實際作用，目前將地理不可區(qū)分性運用在此方面上的有關研究還比較少，今后筆者將繼續(xù)研究該方向，提出更佳的算法。