差分隱私之我見

從去年四月被師兄帶入差分隱私（differential privacy：DP）的大坑算起，一直到現在，也有快一年的時間了。這一年中自己一個人悶頭看論文，想 idea，碼實驗，寫論文，走了不少彎路，在大大小小的坑中摔了好幾次，最終寫完了一篇小論文，我也有點想告別差分隱私，去尋找其他的更具工程性和實驗性（empirical）的研究方向了。

在與差分隱私揮手告別之前，請允許我再回顧一下差分隱私在我心目中的形象吧～

總得來說，差分隱私是一個理論性很強的概念，他不像深度學習那麼 “黑盒”，也不像其他工程上的隱私保護機制（例如 Tor 網絡）那麼清晰直觀易懂，而是靠嚴格限定的模型和可證明的概率約束條件來實現隱私保護的。

Differential Privacy#

差分隱私所防範的是差分攻擊，其起源於數據庫領域，描述了一套攻擊者推斷數據庫中具體數據變化情況的過程。

Model#

考慮兩方：

數據庫維護者（curator）：他擁有完整的數據庫（例如關係型數據庫），其中每一條都是關於一個用戶的個人信息；他向第三方只提供聚合查詢接口（函數）$f$（例如 count，sum，max）。
攻擊者：基於已有的知識，嘗試通過 curator 提供的接口查詢得到數據庫中單個記錄的情況。

例如，有一張表記錄著用戶的姓名和性別，例如：<Alice, Female>。curator 提供查詢 Male 數量和 Female 數量的接口：

攻擊者查詢一次 Male 數量。
此時數據表發生了變動，添加了一條記錄為 <Bob, Male>，注意：假設攻擊者知道 Bob 被添加進了數據庫，但是不知道他的性別。攻擊者想要知道這個信息。
攻擊者再一次查詢 Male 數量，將兩次查詢得到的結果做差，就能夠判斷出 Bob 的性別。

知乎上的科普文 Differential Privacy 簡介舉了個相似的例子。

Definition#

對於隱私定義的看法是多樣的，其中一種常見的解釋是將具體的用戶 “hide in the crowd”，例如經典的 k - 匿名算法就要求一個集合內至少要有 k 條記錄具有相同的值。差分隱私的要求也是類似的，只是差分隱私要求的是隨機算法給定輸入和輸出的概率是相近的。

**（differential privacy）** 給定任意兩個相鄰數據集 $X$ 和 $X'$（相鄰可以指上文中假設的只插入一條用戶數據的情況，當然也有其他更加抽象的解釋），一個隨機算法 $\mathcal {M}$，當對於任意可能的結果 $y$，都有

\frac{\Pr[\mathcal{M}(X)=y]}{\Pr[\mathcal{M}(X')=y]}\leq e^\epsilon

那麼就稱隨機算法 $\mathcal {M}$ 滿足 $\epsilon$-differential privacy（$\epsilon$-DP）。一言蔽之，差分隱私要求返回相同結果的概率是相近的。顯然，上文提到的聚合函數 $f$（count，sum，max）對應於這裡的 $\mathcal {M}$，只是聚合函數給出的結果是確定的，不包含隨機性，因此是不滿足 $\epsilon$-DP 的。

和 k - 匿名類似，差分隱私給出了隱私定義，至於如何實現差分隱私，那就需要研究者來設計 $\mathcal {M}$ 的算法了。

Mechanism#

要對 $f$ 進行改造其實很簡單，只需要在函數進行計算的過程中添加一些隨機性。實際上，幾乎所有差分隱私保護機制 $\mathcal {M}$ 都是圍繞 “添加隨機性” 這一核心展開的。

常用的添加隨機性的方法主要有兩大類：

向變量添加隨機噪聲，例如 Laplacian 噪聲，高斯噪聲，即

\mathcal{M}(X)=f(X)+\eta,\ \eta\sim Laplacian(\frac{\Delta f}{\epsilon})

其中 $\Delta f$ 表示 $f$ 的敏感度，表示任意兩個不同的 $X$ 下 $f$ 的差值的最大值。

使用隨機響應（random response），即通過拋硬幣的方式決定程序運行流程，可以想象成一個隨機的 if 分支語句。

Properties#

差分隱私具有一些性質能夠方便人們在現有算法的基礎上進行組合和擴展，形成新的差分隱私擾動算法。

Properties

Local Differential Privacy#

Model#

要求用戶的隱私能夠得到差分隱私的保證，就需要這些 curator 對算法進行修改，添加隨機性。在現實生活中，數據庫持有者（curator）往往是那些提供服務的公司，要信任他們能夠保護用戶的隱私其實是不太現實的，他們沒有把完整數據打包賣給第三方就不錯了～

因此，研究者提出了更加嚴格的要求 —— 本地差分隱私（local differential privacy）。他將除自身之外的所有人都視作潛在的攻擊者，包括 curator。

**（local differential privacy）** 給定任意（arbitrary）兩個數據 $x$ 和 $x'$（這裡不再是兩個相鄰數據集了，應為單個用戶只對應一條記錄），一個隨機算法 $\mathcal {M}$，當對於任意可能的結果 $y$，都有

\frac{\Pr[\mathcal{M}(x)=y]}{\Pr[\mathcal{M}(x')=y]}\leq e^\epsilon

那麼就稱隨機算法 $\mathcal {M}$ 滿足 $\epsilon$-local differential privacy（$\epsilon$-LDP）。與 DP 最大的區別是，LDP 是對客戶端上的算法 $\mathcal {M}$ 提出了要求，在 DP 模型中，到達數據庫的是用戶的真實數據，而在 LDP 模型中，用戶發送的已經是經過 $\mathcal {M}$ 處理之後的假（pseudo）數據（也就是公式中的 $y$）了。

顯然，LDP 更能夠讓對隱私保護有要求的用戶感到滿意，因為整個宇宙中，除了他自己，沒有人知道真正的數據。

Privacy Utility Tradeoff#

隱私（privacy）和效用（utility）是兩個相對的概念，是天平的兩端。效用反映了數據所能夠提供的使用價值。當出於隱私保護的目的，對用戶的數據進行一定的修改後，數據就會產生偏差，從而影響服務質量。例如 Location based Service（LBS）應用中，用戶需要上傳地理位置來享受服務（外賣、網約車、路徑導航）。當服務方只能根據用戶上傳的假位置（pseudo location）來提供服務時，勢必會帶來一些麻煩（例如外賣送錯了地點）。

因此，既要保證 privacy 又不能損失太大的 utility 就顯得格外重要了，這也是研究隱私問題需要考慮的核心問題。在學術論文中，不僅要對隱私的收益和效用的損失做理論上的分析，還需要定義度量（metric）來對這二者的變化情況進行實驗評估（empirically）。

對於效用而言，具體的效用度量取決於對於數據的類型和使用方式。

數值數據
- 計算均值等統計量。
- 區間統計（直方圖）。
類別數據
- 頻次統計。
- 找到頻次最多類別（佔多數的類別）。
（其他）位置數據
- 附近 PoI（餐館、公園、酒店等）查詢。
- 定位服務。

對於不同的應用，效用損失的計算方式是不同的，需要具體情況具體分析。往往一個算法，能夠在保證隱私的情況下，確保一種特定應用場景下的效用損失不是太大，就已經很不錯了。當然這裡的衡量損失的大小不應該用絕對值，可以用多個不同算法的相對大小，也可以用倍率（類似漸進複雜度）的概念去衡量。

Application#

LDP 的應用是比較貼合移動互聯網時代的用戶體驗的。一般的用戶都會意識到服務方不太可信，因此保護措施如果在客戶端進行的話更安全一些，有一些專業技能的用戶則會去測試客戶端發出的到底是不是經過處理過的數據（例如抓包）。

Apple Emoji

一些軟件服務公司出於改進自身服務質量的目的，會收集用戶的使用數據，像一些較為規範的大廠會彈出 “是否允許收集匿名使用數據” 的對話框讓用戶進行選擇。這些數據會被用於分析出例如特定功能的使用頻率等信息。例如 Apple 會統計 Emoji 的使用頻率，並每年給出一份涵蓋所有用戶的使用報告，這個過程可以抽象成類別數據的統計過程。為了保證用戶使用 Emoji 的隱私得到差分隱私保護，Apple 會對數據在本地和服務端做一些非常複雜的處理。具體過程被發布在了 Learning with Privacy at Scale - Apple Machine Learning Research 一文中。

Apple

另外，Google 也發布了其應用 LDP 的方案 RAPPOR。

Rappor

這兩家大公司的 LDP 方案的客戶端部分很相似，可以總結為兩點：

先用 Hash 函數將原始數據編碼成二進制串。
用隨機響應翻轉每個二進制位。

當然，單條數據經過這些處理步驟之後，往往會變得 “面目全非”，但是當大量的面目全非的數據被服務器收集起來之後，服務端能夠通過一定的算法來得到相對於真實值（頻率、直方圖等）較為接近的估計值。

目前的研究文獻中，將 LDP 應用到生產環境中的之後 Google、Apple 和 Microsoft 這三家，這也是 LDP 的缺陷之一導致的 —— 要想獲得較好的效用，需要極大的數據量。

Location Privacy

Geo DP

另一個 LDP 常見的應用是地理位置服務，在 LBS 的框架下，LDP 要求任意兩個位置被混淆到相同位置的概率是相近的，但是要讓北京和倫敦的兩個位置被混淆到上海的概率相近，會造成巨大的效用損失，因此比較常用的做法如 Geo-Indistinguishability 一文所說：

\frac{f(z|x)}{f(z|x')}\le e^{\epsilon d(x,x')}

概率的相似性與兩個位置之間的距離直接關聯。這樣，以用戶真實位置為圓心，半徑為 r 的區域內的所有位置，可以看做一個等價類，這個等價類中的每個位置和用戶真實位置被混淆到相同位置的概率是接近的，也就是上圖所謂的” 模糊定位 “的範圍。

Inference Attack#

提到 DP 就不得不提推斷攻擊（inference attack），攻擊者基於已有的先驗知識 $\pi$，以及公開的混淆機制 $\mathcal {M}$，推斷出用戶真實數據可能的分布。值得注意的是，（L）DP 並不能阻止推斷攻擊，因為推斷攻擊假設攻擊者具有 $\pi$，而 DP 完全與 $\pi$ 無關，事實上，DP 的優勢就在於他對任意 $\pi$ 下都適用。假設攻擊者已經掌握了真實數據，即 $\pi (x_0)=1$，那麼即便 DP 的要求多麼苛刻，攻擊者也能給出正確答案。

DP 的作用在於，僅根據 $\mathcal {M}$ 本身，攻擊者無法得到任何額外的信息（information gain）。因為 $\mathcal {M}$ 對數據的混淆是帶有隨機性的，而這個隨機的概率又相當的 “均勻”，所以攻擊者僅憑 $\mathcal {M}$ 是無法準確地反推出真實數據的。但這不代表攻擊者利用其他信息也不能準確反推數據。

已有好幾篇論文對差分隱私的在具體應用場景下的局限性進行分析，如在地理位置隱私保護方面，存在：

不能抵抗推斷攻擊：如 PIVE。
隨機性帶來的效用損失極端情況：如 Back to the Drawing Board。

How to Water Paper#

根據我對 DP 相關學術研究的了解，DP 相關論文的難度如下依次遞減：

提出新的 DP 模型（scheme）或者基礎方法，如 shuffle model，amplification by resampling，vector DP 等，水這種論文需要很強的數學功底，需要推導出各種的上下界。
在挖掘到 DP 的缺陷之後，將 DP 與其他隱私保護概念結合。這類問題通常更考驗對 privacy 和 utility 的理解。
將 DP 引入到具體應用中，如 LBS，群智感知，聯邦學習等，將其作為優化問題的約束條件，或通過較為先進的 DP 模型來改進現有的工程實踐，輔以理論分析（套公式）。

Summary#

DP 是理論性很強的概念，他對數據處理過程 $\mathcal {M}$ 的隨機性提出了嚴格的約束，要求對於任意兩個輸入返回相同輸出的概率是接近的。比起其他隱私概念，DP 更難被用戶理解，要把隱私保護效果（包括隨參數的變化）給出一個清晰直觀的解釋是較為困難的。