基于極坐標的位置差分隱私保護方法

宋法根 劉佳

摘要：眾包作為一種新的工作模式，在實際生活中已經得到廣泛的應用。在基于位置的服務（location based service，LBS）應用中，眾包同樣取得了比較好應用效果。但是在LBS的應用中需要暴露用戶的位置信息，這給用戶的隱私帶來了很大的威脅。差分隱私可以很好地保護用戶的隱私，但是會影響眾包任務的分配。這篇文章中，結合差分隱私與極坐標變換設計了一種適用于眾包活動的位置隱私方法，一方面可以有效地保護用戶位置隱私，另一方面又不影響眾包任務的分配。

關鍵詞： 眾包;隱私保護;差分隱私;信息安全;網絡空間安全

中圖分類號：TP311.52? ? 文獻標識碼：A

文章編號：1009-3044（2021）09-0054-02

開放科學（資源服務）標識碼（OSID）：

位置信息是一種重要的信息，基于位置的服務（location based service，LBS）在日常生活中已經得到廣泛的應用，如在打車、導航、環境監測等領域均取得比較好的應用效果，取得很大的社會效益和經濟效益。隨著智能手機的普及以及導航系統的進一步完善，LBS必將發揮更大作用，創造更多的價值。但是這也為用戶的隱私安全帶來了很大的威脅。Wang S ， Sinnott R 等人在[1]中指出，一條軌跡上只需要4個準確的位置記錄，90%的軌跡能夠確定其對應的用戶。若沒有有效的隱私保護方法，位置信息被惡意用戶使用必然會給正常用戶的隱私安全帶來非常大的威脅。

差分隱私是一種有效的隱私保護方法，在隱私保護領域，差分隱私已成為隱私保護事實上標準之一。差分隱私對攻擊者的所掌握的背景信息不做假設，故而具有較強的隱私保護能力。其主要思想是通過添加噪聲，使得修改數據集中的任意一條記錄對查詢結果都不會有較大的影響，進而有效地保護用戶的隱私安全。但是在原始數據上添加噪聲，會對原始數據造成一定的破壞，進而影響數據的使用。本文提出一種在極坐標下進行添加噪聲的方法，該方法適合用于保護眾包活動中用戶的位置隱私。

1 眾包

眾包指的是一個機構把由員工執行的工作任務，外包給非特定的大眾志愿者的做法。目前已經廣泛應用于現實生活，并取得了很好的效果，創造了很大的經濟價值和社會價值。如滴滴打車每天有大量的用戶通過眾包打乘汽車出行，維基百科創建了通過眾包收集信息的典范。

目前眾包活動可以分成兩類，一類是基于自愿的，即不對完成眾包任務的用戶提供獎勵;如：導航軟件中，熱心的導航用戶會自發的上報道路上交通情況或交通事故情況。另一種是基于激勵機制的，如上文提到的滴滴打車，當用戶完成對應任務時會得到一定獎勵。一般獎勵的多少需要根據眾包用戶完成任務的情況，以及為完成任務時所付出的代價進行計算。對于某一任務其本身的情況是不變的，故在計算應付給用戶的報酬時，用戶完成任務所付出的代價對起著非常重要的作用，用戶付出的代價主要是用戶趕往確定地點的過程中所付出的代價，如旅行花費的時間，支付燃料的費用等。可見用戶與眾包任務的距離在報酬的計算過程中有很大的作用。要精確計算出眾包任務與用戶的距離，需要知道它們的精確位置，而如果用戶共享其精確的位置，勢必會泄露用戶的隱私。本文提出了一種基于極坐標的差分隱私變換方法，一方面可以保護用戶的位置信息不被泄露，另一方面又能夠相對精確地得到用戶與眾包任務的距離。

2 差分隱私

定義1 鄰居數據集： 如果數據集[D1]可以通過[D2] 修改、添加或刪除一個數據得到，則稱[D1]與[D2]為鄰居數據集。

定義2。差分隱私：? 算法[A]滿足差分隱私，對于[ε>0] ，當且僅當對于任意鄰居數據集，均滿足：

[?T?Rang（A）：Pr[A（D1）∈T]≤eεPr[A（D2∈T）]]? ? ? ?（1）

其中[Pr[A（D1）∈T]]表示算法[A]輸出[A（D1）∈T]的概率。

目前實現差分隱私的方法主要有拉普拉斯機制。拉普拉斯機制，是指在查詢結果上添加滿足拉普拉斯分布的噪聲。對于任意查詢請求[f]，得到其真實返回值[f（x）]，產生拉普拉斯噪聲[n]，最終返回[f（x）+n]，其實滿足差分隱私的，其證明過程已在[2]中詳細給出，這里不再贅述。

所采用的拉普拉斯噪聲[n]，一般位置參數為0，尺度參數為[?（f）/ε]，[n]的概率密度函數為

[p（x）=ε2Δ（f）e-|x|ε/Δ（f）]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

其中[Δ（f）] 為查詢函數[f]的敏感度，其描述了查詢在該數據集上的最大變化情況，其定義式為：[Δ（f）=maxD1，D2f（D1）-f（D2）1] ，其中[D1，D2]為鄰接數據集。

公式1中，ε稱為差分預算，ε值越小，隱私保護程度越高，需要加入噪聲越多。[Δ（f）]描述了，數據集修改一個元素后，對查詢結果的影響程度，其值越大，表明敏感度越高，要實現隱私保護，就需要添加更多的噪聲。

3 眾包位置保護方法

利用差分隱私保護用戶的位置隱私，如果直接在用戶所在位置的經緯度上添加噪聲，必然對用戶的位置造成比較大的擾動，進而影響眾包中任務與用戶之間距離的計算。本文首先以眾包任務為原點，建立極坐標系，然后在眾包用戶的極坐標上添加噪聲來實現差分隱私。極坐標中用戶與眾包任務之間的距離即為極徑。為了使得報酬計算的更加合理，在極徑上添加較少的噪聲，而在輻角上添加較多的噪聲，從而保護用戶的位置隱私。因為計算報酬時，只關心用戶為完成任務所旅行的距離，而不關心用戶是從哪個方向來的，所以本方法更適合于眾包活動中保護用戶的位置隱私。

對于一個眾包任務tl的坐標為（tlx，tly），某一worker（w）的坐標為（x，y） 。以點tl為原點，建立極坐標后，w的極坐標為[（ρ，α）]。

[r=（tlx-x）2+（tly-y）2]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

[α=arctan（tly-ytlx-x）]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（4）

對于每個眾包任務，進行差分隱私變換后，需要重新轉換為經常用的經緯度，具體轉換方法如公式（4）（5）所示。

[x=tlx+r·cosα]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（5）

[y=tly+r·sinα]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

為減少對眾包任務與用戶距離的擾動，在r上添加較少的噪聲，在輻角上添加較多的噪聲，從而保護用戶的隱私。具體過程如算法1所示：

算法1眾包位置隱私保護方法

輸入：眾包任務位置記錄[TL={tl′1，tl′2…tl′k}]，用戶位置記錄[WL={wl1，wl2…wln}]

輸出：對每個眾包任務得到其周圍噪聲處理后的用戶位置記錄[WL={WLtl′1，WLtl′2…WLtl′k}] 其中[WLtl′i]表示可以參與眾包任務[tli]的所有用戶的位置集合。

（1） 對于區域進行均勻劃分，計算各個網格中用戶的數量;

（2） For each [tl′i∈TL];

（3） 尋找[tl′i]所在單元格，根據單元格用戶的密度，估算可以參與總包活動的區域，及圓形區域的半徑;

（4） 根據公式（2，3）得到圓形區域內所有用戶的極坐標;

（5） 對區域內所有用戶的極坐標添加噪聲;

（6） 運用公式（4）（5）把添加噪聲后的極坐標還原經緯度，把[WLtl′i]加入[WL]

（7） Endfor

（8） Return [WL']

算分1中，首先對眾包區域進行網格劃分，主要是為了解在整個區域中，眾包用戶的分布情況。整個區域往往很大，并非所有的用戶都有參與該眾包任務的意愿，文獻[3]中研究發現，如果眾包任務和用戶的距離大于40km的話，那么用戶參與該眾包任務的意愿就非常低。故而沒有必要對整個區域中所有的用戶的位置進行變換。在第3行，根據任務所在網格的用戶的分布情況，以及完成任務所需要的用戶數，確定可能參與該眾包任務的用戶所在的區域。若任務tl周圍用戶的數量較少，顯然需要增大[r]，在更大的區域中對更多用戶的位置數據進行差分變換，并把變換后的數據發送給眾包服務器，以保證更高的任務分配成功率。在第5行，根據眾包任務的位置，把其周圍區域中用戶的坐標轉換為極坐標，分別極徑和輻角上添加噪聲。為了減少噪聲對計算眾包任務與用戶之間距離的影響，在極徑上添加相對較少的噪聲，而在輻角上添加較多的噪聲。第6行，把噪聲化的用戶的位置信息添加到[WLtl′i]，每一個眾包任務，返回一個用戶位置集合，最后對所有任務的用戶位置集合一起提交給眾包服務器，眾包服務器根據噪聲化后的數據進行任務分配。由于添加噪聲時，未對任務與用戶之間的距離造成較大的擾動，故而眾包服務器在根據用戶旅行距離確定報酬時更精確，更合理。

4 結論

本文基于差分隱私與極坐標變換提出了一種保護位置隱私的方法，本方法對眾包任務與用戶之間的距離擾動較少，故而眾包服務器可以更準確地計算出眾包任務與眾包用戶之間的距離，故而支付的報酬更合理。本文對于同一眾包任務需要多人協作完成的情況沒有考慮，對于需要多個用戶同時完成的眾包任務，可以當成幾個眾包任務同時進行分發。

參考文獻：

[1] Dwork C.Differential privacy：A survey of results[M]//Lecture Notes in Computer Science.Berlin，Heidelberg：Springer Berlin Heidelberg，：1-19.

[2] To H，Ghinita G，Fan L Y，et al.Differentially private location protection for worker datasets in spatial crowdsourcing[J].IEEE Transactions on Mobile Computing，2017，16（4）：934-949.

[3] 鄭袁平，賀嘉，陳珍文，等.關于大數據安全與隱私保護的研究[J].數字通信世界，2019（3）：166，241.

[4] 疏令.基于局部差分隱私的PCMS算法實現[J].電腦知識與技術，2019，15（22）：59-60.

[5] 王家波.基于位置服務的軌跡隱私保護技術研究[D].杭州：杭州電子科技大學，2014.

[6] 魏立斐，陳聰聰，張蕾，等.機器學習的安全問題及隱私保護[J].計算機研究與發展，2020，57（10）：2066-2085.

[7] 馮登國，張敏，葉宇桐.基于差分隱私模型的位置軌跡發布技術研究[J].電子與信息學報，2020，42（1）：74-88.

[8] 鄭袁平，賀嘉，陳珍文，等.關于大數據安全與隱私保護的研究[J].數字通信世界，2019（3）：166，241.

[9] 余智欣，黃天戍，楊乃擴，等.一種新型的分布式隱私保護計算模型及其應用[J].西安交通大學學報，2007，41（8）：954-958.

【通聯編輯：朱寶貴】