本地化差分隱私：如何面對非可信的世界
*本文作者：pingch，本文屬 FreeBuf 原創獎勵計劃，未經許可禁止轉載。
前言
近年來，隱私問題成為人們廣泛關注的熱點問題，隨著大資料時代的到來，每個人的行為軌跡都被廠商以不同形式儲存在雲端，產生了大量的隱私洩露問題。有研究者提出了差分隱私技術（Differential Privacy），它作為一種隱私模型，嚴格定義了隱私保護的強度，即任意一條記錄的新增或刪除，都不會影響最終的查詢結果。同時，該模型定義了極為嚴格的攻擊模型，其不關心攻擊者具有多少背景知識。
0×00 概述
傳統的差分隱私技術將原始資料集集中到一個資料中心，再有資料中心對使用者資料進行加工，使其符合差分隱私保護的要求，我們將其稱之為 中心化差分隱私 。在上一篇文章中我們簡單介紹了中心化差分隱私保護技術的拉普拉斯機制和指數機制。中心化差分隱私技術有一個很關鍵的假設，即資料中心/資料收集者是可信的，不會洩露使用者的隱私資訊。顯然這種前提僅存在於理論中，即使資料收集者主觀上沒有洩露使用者隱私的意願，但由於網路攻擊等外在因素，資料同樣可能被非法獲得。
在很多情況下，使用者往往面對的是大量的 非可信實體（untrusted entity） ，很多時候使用者甚至不希望廠商獲得自己的隱私資料。然而資料探勘又需要大量的使用者行為軌跡進行分析，從而獲得更精確的使用者畫像，提升使用者體驗（或是更精準的廣告投放）。如何讓企業在不侵犯使用者隱私的前提下，利用資料、挖掘資料的價值，是本文所要討論的問題。
既然一個真正可信的資料收集者很難找到，研究人員提出了本地化的差分隱私保護技術，直接在客戶端進行資料的隱私化處理，杜絕了資料中心/資料收集者洩露使用者隱私的可能。
0×01 隨機響應技術
在介紹本地化差分隱私技術之前，需要介紹的是 隨機響應技術（randomized response）。
首先，我們介紹一個使用隨機響應技術的典型場景：
假設有n個使用者，其中艾滋病患者的比例為π，我們希望對π進行統計。於是對目標使用者發起問卷調查：“你是否為艾滋病患者？”顯然，如果直接獲得使用者的相應資料進行統計，一旦資料洩露，那麼使用者隱私隨即洩露。因此，我們假設存在一枚非均勻的硬幣，其正面向上的概率為p，反面向上的概率為1-p。丟擲該硬幣，若正面向上，則回答真實答案，反面向上，則回答相反的答案。
顯然，理論上，Pr[Xi=“是”]=πp+(1-π)(1-p)，Pr[Xi=“否”]=(1-π)p+π(1-p)。直覺上，當n足夠大時，設回答“是”的人數為n1，回答“否”的人數為n2。Pr[Xi=“是”]=n1/n，Pr[Xi=“否”]=n2/n。求解下面的二次方程即可獲得π的值。
但是， 上述的結果並非真實比例的無偏估計 ，我們用極大似然估計(Max Likehood Estimation)對統計結果進行校正。
首先構建似然函式：
對數似然函式為：
令
求解可得π的極大似然估計：
通過進一步求解π的數學期望可驗證上述估計為π的無偏估計。
由此可得患有HIV的總人數：
0×02 本地化差分隱私定義
定義給定n個使用者，每個使用者對應一個隱私演算法M及其定義域Dom(M)和值域Ran(M)，若演算法M在任意兩條記錄t和t’(t, t’ ∈ Dom(M))上得到相同的輸出結果t ( t ⊆ Ran(M))滿足下列不等式，則M滿足ε-本地化差分隱私。
從上述定義可知，在實現本地化差分隱私保護的系統中，任意兩個使用者都可能輸出相同的結果，與中心化差分隱私技術相似，本地化差分隱私技術也是通過對資料加入擾動來實現任意兩條記錄之間的相似性。 0×01隨機響應技術 就是主流的資料擾動機制，由於擾動新增的流程被分配到客戶端，因此資料安全性的保證不再依賴於一個可信實體，降低了資料洩露的風險。通俗的說，本地化差分隱私就是讓各個資料提供者根據一定的概率對自身資料加入噪聲，而在資料聚合時，由於噪聲符合一定的概率分佈，因此不同記錄間的噪聲相互抵消，從而獲得基於大樣本的統計學特徵。
事實上，在 0×01隨機響應技術 的案例中即是實現了ε=ln(p/(1-p))的ε-本地化差分隱私，具體的證明步驟在此略去，可以參考相關文獻[2]。由於隨機響應技術僅適用於兩種取值的離散型變數，因此對於具有超過兩種取值的變數，主流的方案是對其進行二進位制編碼，使其分解為多個0-1變數，從而滿足隨機響應技術對二值變數的要求。另外，一些研究人員通過對隨機響應技術中的概率分佈進行改進，實現支援多種取值的差分隱私保護，例如文獻[3]中所提到的k-RR方法。
0×03 方案設計
在WWDC2016會議上，蘋果公司宣佈了他們將差分隱私技術應用在iOS10，儘管沒有開源相關技術，但是文獻[4]介紹了該技術實現的細節。如下圖所示，在蘋果對使用者Emoji表情使用頻數統計中，當一個Emoji表情使用事件發生時，首先對該事件使用ε-本地化差分隱私進行隱私化處理，然後將其暫存在裝置上，在經過一定時間後，系統根據規則對暫存的資料隨機抽樣，併發送至伺服器。
在iOS上，可以在[設定]-[隱私]-[分析]-[分析資料]中找到包含“DifferentialPrivacy”的實體【事實上，我並沒有在我的iOS裝置中找到相關條目】，下圖展示了使用差分隱私保護技術收集受歡迎的Emoji表情的例項，parameters欄位表示該差分隱私演算法中所使用引數的取值，records欄位表示一段由十六進位制編碼的隱私資料。
所有的隱私資料在處理前都會去除其IP地址，採集器（Ingestion）會一視同仁地將來自所有裝置和使用者的資料放在相同的環境中進行處理。在處理時，首先會刪除時間戳等元資料（metadata），然後根據各自的統計場景（例如Emoji表情受歡迎程度、系統偏好設定等）進行分類，最後隨機打亂各使用場景內部資料的順序，並傳輸至聚合器（Aggregation）。
聚合器從採集器獲得相關資料後，分別對不同統計場景，利用後續介紹的演算法生成該統計場景下的直方圖，這些統計結果會在蘋果內部的相關團隊中共享。
0×04 演算法
相比於Google的RAPPOR[2]，蘋果所提出的Private Count Mean Sketch（CMS）演算法顯然更易於理解。在這裡，我們將以CMS演算法為例，介紹如何在客戶端和服務端實現ε-本地化差分隱私保護。
客戶端
以統計使用者最常使用的Emoji表情為例。例如，根據客戶端的統計，某使用者最常瀏覽的Emoji表情為“【大笑】”。CMS演算法首先設計一組雜湊函式H={h1, h2, ···, hn}，並規定H中的函式能夠根據輸入的域名輸出一個大小為m的較小的值。假設，在該場景中CMS演算法選取雜湊函式h1，並且h1(“【大笑】”)=31。此時，我們首先初始化一個長度為m的one-hot向量B，並將第31位賦值為1，其他位置賦值為0，然後對該向量的每一位以概率p進行翻轉（即當Bi=1時，將Bi賦值為0；當Bi=0時，將Bi賦值為1），最後將翻轉後的向量B’和所選取的雜湊函式h1傳送至服務端。其中，p=1/(exp(ε/2)+1)，ε為該演算法的隱私保護預算。
對於服務端而言，由於獲得的向量經過混淆，無法根據客戶端傳送的向量來識別該使用者最常使用的Emoji表情。
服務端
在服務端，首先構建一個大小為n×m的矩陣M，即n列，m行。其中，n表示雜湊函式的數目，m表示向量B’的長度。當向量B’和雜湊函式h1被傳輸至服務端，則在M的第1行加上向量B’。當服務端獲得足夠多的樣本，矩陣M的規模足夠大，每一行就會提供每個元素的無偏估計。為了計算使用【大笑】表情的頻數，CMS演算法會通過讀取每一行M[j,hj(“【大笑】”)]的值，並計算這些估計的均值，從而獲得無偏估計。
例項：Emoji表情使用統計
蘋果採用了該技術用於獲得不同語言使用者的Emoji使用情況。在該統計場景中，共有2600個Emoji表情，此時CMS演算法的引數取值如下：m=1024，n=65536，ε=4。圖3的直方圖展示了英語使用者和法語使用者的Emoji表情使用情況。
RAPPOR：另一種可能
因為篇幅有限，這裡僅簡單介紹Google所提出的RAPPOR演算法的流程，不再介紹具體的擾動機制。
如下圖所示，RAPPOR首先使用Bloom Filter將字串編碼為長度為h的01向量B，同時記錄下字串與Bloom Filter的對映關係矩陣，然後利用隨機響應技術對向量B的每一位加入擾動，得到永久性隨機響應（Permanent Randomized Response，PRR）結果B’，然後在對B’的每一位進行第2次擾動，得到瞬時性隨機響應（Instantaneous Randomized Response，IRR）結果S。每個使用者得到擾動結果S後，將其傳送至服務端，服務端統計每一位上1出現的次數並進行校正，然後結合對映矩陣，通過Lasso迴歸方法完成使用者年齡頻數的統計。
熟悉Bloom Filter的人都知道，這個方法存在的一個很明顯的問題就是向量編碼值的衝突，即可能兩個不同的值可能會輸出相同的01向量編碼結果，對於這一點，RAPPOR通過調節對映矩陣的引數來避免。
0×05 總結
本文介紹了本地化差分隱私保護技術的系統架構和演算法，是前一篇文章 差分隱私保護 的細化和外延，相比於中心化差分隱私保護技術，本地化差分隱私保護技術打破了中心化差分隱私保護關於可信資料收集者的假設，直接在客戶端完成資料的隱私化處理，在工業實踐中具有更高的應用價值。
參考文獻
[1] 葉青青等. “本地化差分隱私研究綜述.” 軟體學報 7(2018).
[2] Erlingsson, Úlfar, Vasyl Pihur, and Aleksandra Korolova. “Rappor: Randomized aggregatable privacy-preserving ordinal response.” Proceedings of the 2014 ACM SIGSAC conference on computer and communications security. ACM, 2014.
[3] Kairouz, Peter, Sewoong Oh, and Pramod Viswanath. “Extremal mechanisms for local differential privacy.” Advances in neural information processing systems. 2014.
[4] Differential Privacy Team. “Learning with Privacy at Scale” Apple Machine Learning Journal
*本文作者：pingch，本文屬 FreeBuf 原創獎勵計劃，未經許可禁止轉載。