這是來自今天arXiv上面的一篇文章，標題為：Secure and Utility-Aware Data Collection with Condensed Local Differential Privacy。

摘要大致如下：當前LDP已經廣泛用於保護隱私的數據收集了，雖然當前基於LDP的方案在大數據樣本下能較高地保證數據有效性，但是在樣本量較小時LDP的表現就不太好了。而且當前缺乏對敘述序列和非敘述序列的擾動機制用於保護序列長度和內容。本文引入CLDP（Condensed Local Differential Privacy）用於小樣本數據手機問題，我們提出了一系列CLDP方案，這些方案都可以用於對樣本進行統計，並且數據有效性較高。我們的方案支持不同類型的客戶端數據，如有限空間的數據（惡意軟體感染的統計數據），序數以及非序數（OS版本，交易種類等）。數據集上的實驗表明與現有的LDP方法對比來看，CLDP能產生更高的效用。實際數據集的研究也表明方法的有效性。

本篇推送簡單掃一下這篇文章。談一談我理解的這篇文章的出發點。

在看CLDP概念之前，我們不妨看一下一篇CCS13年的文章，標題為：Geo-Indistinguishability: Differential Privacy for Location-Based Systems。這篇文章應該是將DP用到LBS中的鼻祖了。我們先來看一下理想中的LBS保護：需要同時提供數據有效性和隱私性。

以週一中午定外賣為例，假如我在紫荊15號樓。那我美團搜索的時候，會經歷這麼個流程：

  1. 美團獲取我的定位。
  2. 根據我的定位查詢1公里內的商家。
  3. 按照商家到我的距離排序告知我，讓我選擇。

當然，這個1公里是我瞎選的。好巧不巧，我老闆呢就能拿到美團的核心數據（當然，這是我杜撰的）。這時候我就擔心受怕了呀，這外賣要是一點，紫荊15號樓的定位一發，老闆就知道我沒去實驗室了。所以只能抱怨了，美團這對於用戶隱私也太不保護了。

美團：MMP, 你要我咋樣保護。

來來來，我們看看怎麼用DP來保護。

解決方案：運用多元回答下的Random Response，假定有N個地點，以較大的概率回答當前地點，以較小的概率回答其他地點，差不多就是這麼個方程：

operatorname{Pr}left[M(v)=y ight]=left{egin{array}{ll}{p=frac{e^{varepsilon}}{e^{varepsilon}+|mathcal{U}|-1}} & { ext { if } y=v} \ {q=frac{1}{e^{varepsilon}+|mathcal{U}|-1}} & { ext { if } y eq v}end{array} ight.

其中上面的概率表示真實回答的概率。那麼這個解決方案行不行呢？不行。為什麼呢？

  1. 因為假定不成立，這個世界並不是有N個地點。而是有無限個地點。當然，這個無限的問題是可以解決的，比如把地圖分為多少塊。
  2. 數據可用性保證不了啊，我在紫荊，你給我產生一個虛擬地點說我在塞納河畔。浪漫是浪漫，可我喫毛線呢。

但是，這之中有矛盾，想要保護位置，就一定要生成一個虛擬的位置報告給伺服器，產生虛擬位置就一定會有可能導致無法提供有效的服務（當然，可以認為所有的DP都有這個問題，因為單個數據是假的一定會導致數據有效性降低）。比如，查個天氣預報我在五道口你給我分到水立方我覺得問題都不打，定個外賣我在五道口你給我分到水立方的話外賣小哥要被氣死。

所以，我們轉換一下思路，地點之間是有一個潛在的相似性的，越靠近的地點，相似性就越高。所以，能否以較大的概率生成離我近的地方，以較小的概率生成較遠的地方呢？回到原來的例子，我在紫荊，你給我報告個三教，我也很美滋滋，畢竟根據這個機制，我在實驗室也很可能定位到三教去。

所以，引入了這個概念之後，用DP保護地理位置的機制可以濃縮成這個方程，這就是著名的Geo-indistinguishability:

K(x)(Z) leq e^{epsilon cdot dleft(x, x^{prime} ight)} Kleft(x^{prime} ight)(Z)

其中K(x)(Z)表示將地點x映射成Z的概率。這個和LDP有啥區別呢，就是多了個d(x,x)。理解上說，以較大的概率映射到離我近的地方，以較小的概率映射到更遠的地方。

這個公式講完了，就涉及到這篇文章中的東西了，這篇文章提了一個Condensed Local Differential Privacy，CLDP：

這個公式實際上和 Geo-indistinguishability 一模一樣的。

所以怎麼實現這個機制呢，首先這裡有個d(v1, v2)所以我麼肯定是需要一個距離矩陣的，在LDP下，每個元素之間沒有距離的概念，可以認為距離矩陣是一個全1的矩陣。

然後作者提車了基於CLDP的指數機制（EM, Exponential Mechanism）:

後面作者又基於這個概念提出了用於序數的機制等其他方面的機制，機制的設計和LDP下其實都是一樣的，不過需要考慮到一個距離矩陣。其實這中間有個問題，就是比如多元隨即響應，本來是沒有這個距離矩陣的概念的。

實驗結果對標基於LDP的方案，這是顯然存在問題的，從定義的角度來說，CLDP和LDP就不在同一個框架之下，就好比把LDP和k匿名去對比，怎麼對比都不公平。而且，顯然，CLDP要比LDP實驗效果好，畢竟LDP保證的是任何兩個數據都以相同的概率不可區分，而CLDP保證的是相近的數據比較遠的數據更不可區分。

不過在LDP中引入距離的概念，這個想法也挺interesting的。這篇文章的簡介就到這裡了，歡迎關注我的公眾號：差分隱私。


推薦閱讀：
相關文章