來源| OSCHINA 社區(qū)

作者 |PrimiHub開源

原文鏈接：https://my.oschina.net/u/6662337/blog/10087905

在 2016 年 6 月份的蘋果 WWDC 大會上提到了一項差分隱私技術（Differential Privacy），其作用是對用戶的數(shù)據(jù)進行擾動，然后上傳到蘋果服務器。蘋果能通過這些擾動過的數(shù)據(jù)計算出用戶群體的行為模式，但是對每個用戶個體的數(shù)據(jù)卻無法解析。

蘋果通過采用差分隱私技術，實現(xiàn)了在不得到用戶原始數(shù)據(jù)的前提下，學習用戶行為。如果你想知道 “數(shù)據(jù)可用不可見” 背后的技術，就跟著我們一起來學習下蘋果的差分隱私技術背后的原理吧！

一、簡介

差分隱私是一種數(shù)據(jù)隱私保護技術，它通過在數(shù)據(jù)中引入隨機化擾動的手段來保護隱私。簡單來說，擾動后的數(shù)據(jù)是無法精確地推斷出其原始值。同時，它允許對隨機化后數(shù)據(jù)進行統(tǒng)計分析，保證了數(shù)據(jù)的有用性。差分隱私提供了衡量隱私的嚴格數(shù)學定義，是近些年來業(yè)界常見的一種隱私保護技術。

1.1 差分隱私應用場景

蘋果使用本地化差分隱私（Local Differential Privacy）技術來收集用戶設備上的信息，其部署的產品見下表 [1, 2]。

1.2 本地化差分隱私

在本地化差分隱私框架中，用戶在上傳的原始數(shù)據(jù)中添加噪聲（擾動），服務器則無法知道用戶的真實數(shù)據(jù)。這項技術最早是由 Warner 提出的隨機響應（Randomized response）[3]。



本地化差分隱私技術可用于聯(lián)合統(tǒng)計，比如計算平均數(shù)、中位數(shù)、頻率直方圖等。其算法框架（E-R-A-P）一般分為四個步驟：

編碼（Encoding,E）

隨機化（Randomizing,R）

聚合（Aggregation,A）

后處理（Post-processing,P）

用戶端進行編碼與隨機化，保證傳輸?shù)臄?shù)據(jù)是擾動后的；服務器端進行聚合與后處理，得到相應的統(tǒng)計量。

二、蘋果的方案

蘋果的本地化差分隱私方案參見 [2, 4, 5]，其中 [4, 5] 是專利。這里介紹 [2] 中方案的簡易版本，以統(tǒng)計表情包的頻率直方圖為例。

2.1 用戶端

依照上面提到的 算法框架（E-R-A-P），用戶端需要在上傳數(shù)據(jù)之前對做原始數(shù)據(jù)做編碼 (E)和隨機化 (R)。 編碼 (E)：編碼是為了后續(xù)的隨機化和聚合步驟。蘋果的編碼采用哈希表的方式，初始表中的元素均為 “-1”。然后通過哈希函數(shù)hh將元素dd（使用頻率最高的表情包）映射到位置h(d)h(d)，并標記 “1”。假設哈希表的長度為mm（聚合時會用到該參數(shù)）。



2.2 服務器端

依照上面提到的 算法框架（E-R-A-P），服務器端需要在接收到數(shù)據(jù)后對做 “擾動” 后的數(shù)據(jù)做聚合 (A)和后處理 (P)。



后處理 (P)：在不同應用場景中，計算的統(tǒng)計量可能有先驗知識，比如取值范圍的限制（如大于 0），或者保持加和不變（如統(tǒng)計個數(shù)），這時就需要進行后處理操作。差分隱私的性質使得任何后處理操作均不影響其結果的隱私性。

2.3 其他技術

數(shù)據(jù)隱私保護需要考慮的方面很多，僅使用差分隱私技術無法解決所有的問題。蘋果在方案中還使用了其他技術來保護數(shù)據(jù)隱私，例如數(shù)據(jù)脫敏、通信加密、訪問控制等。

用戶上傳的數(shù)據(jù)已移除設備標識符、時間戳等信息

用戶與服務器通信使用 TLS 協(xié)議，即數(shù)據(jù)加密傳輸

服務器收到用戶數(shù)據(jù)后首先移除 IP、地址、時間戳等 meta 信息，并將數(shù)據(jù)順序打亂（shuffle）

數(shù)據(jù)聚合在受限訪問環(huán)境中執(zhí)行

數(shù)據(jù)只在蘋果內部流通，且蘋果的員工不能隨意訪問數(shù)據(jù)

2.4 隱私預算

看到這里大家應該明白了，差分隱私是通過在增加噪聲（擾動）來實現(xiàn)隱私保護，但由于擾動增加，聚合的結果會變得不精確（統(tǒng)計量的方差增大）。所以下面介紹平衡算法的隱私性和實用性的隱私預算??。



而且，雖然數(shù)據(jù)添加了差分隱私擾動，但同一用戶會不斷地上傳新數(shù)據(jù)，根據(jù)差分隱私的串型組合定理，隱私預算??會隨著時間累積逐步增加。因此，蘋果限制了用戶每天上傳數(shù)據(jù)的最大次數(shù)，并表示數(shù)據(jù)最多只會留存三個月。

有研究 [6] 指出，蘋果應該解釋是如何設置隱私預算??的取值的，告知用戶并將其透明化。例如，雖然 Emoji 產品中宣稱的隱私預算??取值為 1，但通過代碼逆向工程后發(fā)現(xiàn)其取值為 2（iOS 10.1.1 和 MacOS 10.12.3 版本的數(shù)據(jù)）。而且，隱私預算隨時間累積也是其方案存在的一個重要問題。

三、方案優(yōu)化

第 2 節(jié)中描述的是方案的簡易版，而蘋果的方案針對通信、統(tǒng)計量的精確性、場景適配等均做了優(yōu)化 [2] 如下：

為了減少哈希碰撞的影響，實際有kk個哈希函數(shù)，每個用戶在編碼時隨機選擇一個，并將選擇的哈希函數(shù)告訴服務器。服務器則構建kk個哈希表，然后進行聚合計算。

為了降低通信量，蘋果的方案中對編碼后的數(shù)據(jù)進行了阿達馬變換（Hadamard transform），并通過采樣的方式，隨機選擇 1 比特的數(shù)據(jù)發(fā)送到服務器。這樣不僅可以降低通信量，而且不會增加統(tǒng)計值的方差。

表情包的數(shù)據(jù)一般是固定的，但在一些場景下，用戶數(shù)據(jù)是無法預知的。比如學習熱門新詞匯，統(tǒng)計網站。蘋果對此采用了 Sequence Fragment Puzzle 技術，并設計了本地化差分隱私的方案。

四、無偏估計證明

這里依舊是按照 算法框架（E-R-A-P）順序進行講解，證明f~(d)f~(d)是f(d)f(d)的無偏估計。



4.1 編碼



4.2 隨機化



4.3 聚合



統(tǒng)計量的方差小才意味著估計的精確性高。 以上通過公式推導的方式證明了蘋果采用的「差分隱私」算法的準確性，可以實現(xiàn)在 “數(shù)據(jù)可用不可見” 的情況下實現(xiàn)統(tǒng)計計算。

五、最后

看似 “高不可攀” 的差分隱私技術，其實早已走進了我們的日常生活和工作中，為我們的個人隱私保駕護航。 本文通過通俗易懂的圖文和嚴謹?shù)墓酵茖Вv解了蘋果的差分隱私技術原理，希望能夠勾起你對隱私計算技術的興趣。

審核編輯：劉清