來源| OSCHINA 社區(qū)

作者 |PrimiHub開源

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

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

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

一、簡(jiǎn)介

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

1.1 差分隱私應(yīng)用場(chǎng)景

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

1.2 本地化差分隱私

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



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

編碼（Encoding,E）

隨機(jī)化（Randomizing,R）

聚合（Aggregation,A）

后處理（Post-processing,P）

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

二、蘋果的方案

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

2.1 用戶端

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



2.2 服務(wù)器端

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



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

2.3 其他技術(shù)

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

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

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

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

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

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

2.4 隱私預(yù)算

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



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

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

三、方案優(yōu)化

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

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

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

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

四、無偏估計(jì)證明

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



4.1 編碼



4.2 隨機(jī)化



4.3 聚合



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

五、最后

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

審核編輯：劉清