蘋果的 Differential Privacy 差分隱私技術是什麼原理？

12-27

在 2016 年 6 月份的蘋果 WWDC 大會上提到了一項 Differential Privacy 差分隱私技術，其作用是能夠通過密碼學演算法對用戶的數據進行「加密」上傳到蘋果伺服器。蘋果能通過這些「加密」過的數據計算出用戶群體的行為模式，但是對每個用戶個體的數據卻無法解析。

蘋果這項技術的實現原理是什麼？

正好最近在寫一篇DP方向的論文，來答一下：
DP是為了允許研究者（蘋果）在不泄露個體信息（用戶隱私）的前提下對一個數據集的整體（用戶行為）進行分析而研究出的加密手段。

舉個例子：之前netflix辦了個機器學習的比賽，旨在提升自己推薦系統的準確度。netflix公布了一個數據集，裡面包含了它的真實用戶的瀏覽數據，為了保護用戶隱私，netflix把用戶ID和識別碼一類的可以唯一識別用戶的信息都抹去了。netflix聲稱這樣我們就保護了用戶的隱私。然而，事實上在這個數據集發布一個月後，兩個學者就利用一種叫做record linkage的技術，挖掘出了這個數據集中某些記錄對應的用戶是誰。原理很簡單，我從網上挖掘一些包含用戶信息的電影瀏覽記錄（比如IMDB），然後把這些記錄和netflix數據集里的瀏覽記錄進行匹配，就可以反向推理出在netflix數據集中的個體對應的是哪些人，於是這些人在netflix中的購買記錄等隱私就泄露了。

這個事件告訴我們一個道理，就是如果你要公布一個數據集，那麼僅僅移除其中的ID這類信息是完全不足以保護隱私的。於是2006年（正好也是netflix數據泄露事件發生那年），微軟的C. Dwork提出了一個概念，叫做Differential Privacy。

它的思路就是，假如我現在想公布一個數據集，給大眾做數據分析，但我又想保護裡面每一個個體的信息不泄露，那麼一種可行的手段就是給這個數據集注入一些噪音或者說擾動。當然這個擾動不能隨便加，否則數據就喪失了可用性。然而擾動也不能太小，否則就起不到保護隱私的作用了。C. Dwork在他的論文中提出了一個數學上的描述，來測量一個擾動機制究竟能夠帶來多大程度上的保密性。簡單來說就是，你給我一個數據集A，假如我有一個擾動機制，可以讓我先對A做一個擾動得到A"，再從原數據集A里隨意拿掉一行記錄得到B，對這個數據集B做擾動得到B『，如果得到的A"和B』幾乎是一模一樣的（這個一模一樣有數學上的定義），那麼我就認為這個擾動機制可以保護隱私。因為在這個擾動機制下，A裡面任何單獨一行數據存在或不存在都幾乎不影響結果。具體的數學公式可以在C. Dwork的論文(http://www.msr-waypoint.com/pubs/64346/dwork.pdf）里找到。

通俗來講，這個機制保證了一個數據集的每個個體都不被泄露，但數據集整體的統計學信息（比如均值，方差）卻可以被外界了解。因此，比如一個醫療機構要公布患者的疾病數據給外界以供研究，就可以先對這個數據集做一個滿足DP的擾動，再公布出去。

DP現在在業界很火，很多人都在搞這一塊，因為DP僅僅是一個定義，並沒有給出具體的擾動方法，所以大家就都在研究怎樣加密能在保證DP保密性的前提下，最大化一個數據集的可用性。

有興趣可以移步Havard的Differential Privacy實驗室，他們做了一個DP的原型實現，你可以傳一個數據集上去，得到一個加密過的新數據集：Differentially Private Curator
Apple實現的應該就是類似東西。

原以為差分隱私是個好小眾的話題，沒想到zhihu上的討論還這麼熱烈。這是我最重要的研究方向，想盡我所能把這個學術問題說的大家都能聽懂。

1. 什麼是隱私？

講差分隱私前，我想說一下什麼是隱私

其實隱私這個定義，各家有各家的說法，而且各人有各人不同的考量。目前普遍比較接受的是：「單個用戶的某一些屬性」可以被看做是隱私。這個說法里所強調的是：單個用戶。也就是說，如果是一群用戶的某一些屬性，那麼可以不看做隱私。

舉個例子：醫院說，抽煙的人有更高的幾率會得肺癌。這個不泄露任何隱私。但是如果醫院說，張三因為抽煙，所以有了肺癌。那麼這個就是隱私泄露了。好，那麼進一步，雖然醫院發布的是趨勢，說抽煙的人更高几率得肺癌。然後大家都知道張三抽煙，那麼是不是張三就會有肺癌呢？那麼這算不算隱私泄露呢？結論是不算，因為張三不一定有肺癌，大家只是通過一個趨勢猜測的。

所以，從隱私保護的角度來說，隱私的主體是單個用戶，只有牽涉到某個特定用戶的才叫隱私泄露，發布群體用戶的信息（一般叫聚集信息）不算泄露隱私。記得高德地圖發過一張圖，大意是開凱迪拉克的群體喜歡去洗浴中心.......很多人說暴露隱私, 其實從學術定義上來說，這個不算隱私泄露，因為沒有牽涉到任何個體。

那麼我們是不是可以任意發布聚集信息呢？倒是未必。我們設想這樣一種情況：醫院發布了一系列信息，說我們醫院這個月有100個病人，其中有10個感染HIV。假如攻擊者知道另外99個人是否有HIV的信息，那麼他只需要把他知道的99個人的信息和醫院發布的信息比對，就可以知道第100個人是否感染HIV。這種對隱私的攻擊行為就是差分攻擊。

2. 差分隱私

差分隱私顧名思義就是防止差分攻擊了，它想做的事情就是即使你小子知道我發布的100個人的信息，以及另外99個人的信息，你也絕對沒辦法把這兩個信息比對之後獲取第100個人的信息。怎麼才能做到這一點呢？差分隱私於是定義：如果你能找出一種方法讓攻擊者用某種方式查詢100個信息和查詢那99個信息得到的結果是一致的，那攻擊者就沒辦法找出那第100個人的信息了。但這個「一致」怎麼做到呢？那就加入隨機性吧。如果查詢100個記錄和查詢99個記錄，輸出同樣值的概率是一樣的，攻擊者就無法進行差分攻擊。這裡我們就得到了差分隱私的核心思想：對於差別只有一條記錄的兩個數據集，查詢它們獲得相同值的概率非常非常的接近。Wait，不是說一致的么？為什麼變成了非常接近了？這是因為，如果概率一樣，就表示數據集需要完全隨機化，那數據的可用性就沒有了，隱私保護也沒有意義了。所以，我們儘可能的把概率做的接近，而不是一致，以期在隱私和可用性之間找一個平衡。

上面這張圖描述了差分隱私的基本思想，對於兩個只相差一個記錄的數據集D和D"來說，查詢M的輸出結果S概率應該非常接近。

3. 如何做到差分隱私

其實就是在查詢結果里加入隨機性。

任何一種方法，只要用在數據集上能滿足差分隱私的核心思想，那這個方法就是滿足差分隱私的。所以最常用的方法是在結果上加滿足某種分布的噪音，使查詢結果隨機化。

目前常用的有兩種方法，一個是Laplace機制，在查詢結果里加入Laplace分布的噪音，適用於數值型輸出。例如：zhihu里有多少人是985大學畢業的？假如結果是2000人，那麼每一次查詢得到的結果都會稍稍有些區別，比如有很高的概率輸出2001，也有較高概率輸出2010，較低概率輸出1990，等等。

另外一個是指數機制，在查詢結果里用指數分布來調整概率，適用於非數值型輸出。例如：中國top 3大學是哪一所。很高概率輸出浙江大學，較高概率輸出上海交大，較低概率輸出武漢大學，很低概率輸出藍翔技校，等等。

4. 差分隱私應用

這麼說吧，任何需要保護隱私的演算法里都可以使用差分隱私。差分隱私最美麗的一點在於只要你的演算法每一個步驟都滿足差分隱私的要求，那麼它可以保證這個演算法的最終輸出結果滿足差分隱私，換句話說，即使攻擊者具有足夠多的背景知識，也無法在最終的輸出中找出單個人的某項屬性。

目前在學術上，差分隱私可以被應用在推薦系統，社交網路，基於位置的服務，當然，也包括了蘋果的輸入系統。

5. 差分隱私的弱點

差分隱私的弱點其實很明顯：由於對於背景知識的假設過於強，需要在查詢結果中加入大量的隨機化，導致數據的可用性急劇下降。特別對於那些複雜的查詢，有時候隨機化結果幾乎掩蓋了真實結果。這也是導致目前應用不多的一個原因。

但差分隱私作為一個非常漂亮的數學工具，為隱私研究指明了一個發展的方向。在早期，人們很難證明我的方法保護了隱私，更無法證明究竟保護了多少隱私。現在差分隱私用嚴格的數學證明告訴人們，只要你按照我的做，我就保證你的隱私不會泄露。

更有意思的是，Dwork團隊2015年提出應用差分隱私的想法可以解決機器學習的over-fitting問題，一步從隱私界跨到了AI界，開始搶機器學習的飯碗了。她們的論文發表在了2015年的Science上，有志於搶AI飯碗的同學可以瞄一下。

The reusable holdout: Preserving validity in adaptive data analysis

7. 最後，放一篇我在2017年寫的有關差分隱私的前世今生，很學術，有興趣研究這個方向的同學可以讀讀。

Differentially Private Data Publishing and Analysis: a Survey

寫過相關paper，Differential Privacy原理很簡單。

說個例子吧，醫院為了促進流行病研究，允許公眾查詢流感病人數量。
表面看起來，醫院沒有公布病人姓名，保護了隱私。
然而在存在額外訊息(side channel)的情況下，病人的隱私會暴露。
比如說，我今早查詢了一下，流感病人500人。我朋友A早上去醫院看病。下午我一查，流感病人501人，那麼我推測A很大可能患病。

另一個著名例子就是其他答案提到的通過IMBD數據破解Netflix數據。
所以要真正保護病人隱私，醫院不能每次都公布準確數字，而應該在準確數字上加個雜訊。

Differential Privacy (DP)的嚴格定義如下：

考慮兩個相似的資料庫 $D,D$ ，其中只有一個用戶的數據不同。
對於任意參數 $epsilon>0$ ，一個查詢函數 $q$ 滿足 $epsilon$ -differential privacy，那麼兩個資料庫 $D,D$ 的查詢結果在概率上應該接近。
嚴格的說，對於任意的查詢結果集合 $S$ ，
$P[q(D)in S] leq e^epsilon P[q(D$

由於一個用戶改變數據對於查詢結果的影響不大，所以從查詢結果反推用戶數據就變得困難。
參數 $epsilon$ 接近0時， $e^epsilon$ 接近1，兩個概率接近相等，保密程度高。
$epsilon$ 越大，越沒隱私，但查詢結果可以更精確。

回到上面的流感問題，要讓這個查詢滿足DP，只要：
醫院公布的流感人數=精確人數+Laplace雜訊（拉普拉斯分布_百度百科）。

這種加Lapace雜訊的辦法叫Laplace mechanism，是最常用的保證DP的辦法。
此外還有 exponential mechanism, Gaussian mechanism，大同小異。

我個人本來不太看好DP。
資料庫小的時候，DP的代價是查詢誤差極大。
資料庫大的時候，非DP的傳統方法（k-annonimity, l-diversity）也能基本保證privacy，同時查詢誤差為0。
一直覺得DP就是研究和騙funding的噱頭，沒想到還真實用了。

差分隱私是一種標準也是一種技術。通過引入雜訊，對源數據進行干擾後，數據能夠滿足一定的標準，防止數據被推測。差分隱私的標準是這樣描述的：知道數據中的一點（one element）內容，整個數據的信息熵（不確定性）幾乎沒有改變。簡單的說也就是你獲取到的部分數據內容對於推測出更多的數據內容幾乎沒有用處。差分隱私是一種比較強的隱私保護技術，滿足差分隱私的數據集能夠抵抗任何對隱私數據的分析，因為它具有資訊理論意義上的安全性。其實現原理主要是通過匿名、擾亂、混淆等方式為數據添加雜訊，相關研究已經有十年之久，但是，具體實現方法商且沒有比較通用的手段，往往數據試下差分隱私之後，數據的可用性大大折扣，使得這種技術離應用還有差距。
至於蘋果推出的差分隱私技術，不知道技術細節公布沒有，但是目前對於差分隱私技術的研究離實用尚有差距（13年之前的研究，14年之後沒有了解）。附錄是比較老的一個綜述，比較有意思的是，這篇文章是微軟研究院人寫的，但是微軟尚未推出相關產品。不知道近些年還有綜述沒有，大家看一下，了解一下差分隱私是什麼回事，最新的研究進展還是希望在此領域有研究的同學繼續努力，因為差分隱私是在隱私保護領域，除了加密之外，
Dwork, Cynthia. "Differential privacy: A survey of results." Theory and applications of models of computation. Springer Berlin Heidelberg, 2008. 1-19.

我不認為DP是一種加密技術。雖然都是隨機化，但區別在於隨機化後密文的分布。對於加密，希望以均勻分布把明文映射到密文空間，也就是說明文加密後，以完全相同的概率有可能是密文空間中的任何一個密文，是均勻分布，這也是香農對perfect security的定義。但對於DP，隨機化後的結果不可能是均勻分布，那樣發布的結果就完全沒意義了，所以它是Laplace分布或者高斯分布，也就是說雖然隨機化了，但趨近真實值的概率高，而遠離真實值的概率小。加密是要徹底破壞密文的可用性，它的可用性必須通過解密出明文來實現。但DP沒有逆過程，它必須在一定程度上保證隨機化後結果的可用性。

佔個坑，其實原理不算複雜。
有生之年看到真的有公司大規模的用DP還是挺…奇怪的……，畢竟這個技術雖然近些年在學術界很熱，各個領域都要插上一腳，但還是有很多問題沒解決，並不成熟。

DP是一種安全標準很高的隱私保密標準。這種標準要求對某個隱私資料庫任意增刪一條信息並不會顯著改變該資料庫的信息熵（差別為exp(e),其中e為某個預定義的小量），從而保證了對所有隱私信息的保護。DP的主要困難在於設計出能處理大規模數據的高效演算法，但蘋果既然已經商業化了，想必已經解決了這個問題。

不過DP主要是由微軟研究院的C. Dwork提出及發展，微軟也已經在這個領域申請了不少的專利，所以蘋果想要完全繞開微軟基本不可能。這下恐怕只能解釋為兩大巨頭在私下達成了戰略合作，微軟又搞了個大新聞啊。

今年的 WWDC 蘋果給出了答案：Differential Privacy。沒錯，也許魚和熊掌，是可以兼得的。利用這項新的隱私保護技術，蘋果會在鍵盤輸入預測、相冊、Spotlight 內容推薦、備忘錄智能標註等各處，向用戶提供機器學習的結果。

要理解蘋果為什麼需要等這麼久，這期間蘋果到底在試圖解決什麼問題，其實並不難。現在人們已經習慣了自己的資料存儲在雲端，並且相當一部份人已經並不介意，如果自己的數據被放在一個全局的視角中被觀察，想想朋友圈那些熱轉的大數據分析，很多時候你就是其中的那一個分母。

但是，這並不意味著你不能從整體中被揪出來，想一想，也許你對人們在京東上都在買什麼東西感興趣，但如果你自己的購物清單，被公諸於眾呢？類似的案例曾經發生過，2007 年，Netflix（就是紙牌屋製作方）曾設立了一項 100 萬美金的獎勵計劃，鼓勵人們幫助它改進其內容推薦系統。為此，它放出了一個資料庫，裡面包含了其用戶對各個電影電視劇的評分，但抹去了姓名等隱私信息。不料，有人將 Netflix 放出的資料庫與網路上最大的影視數據平台 IMDB（類似中國的豆瓣電影）做了交叉對比，從而還原出了 Netflix 數據中用戶的真實身份。

如果把電影名字也去掉，只留下電影的類別呢？也不一定完全可靠，比如只要有用戶的評價打分時間，很可能用戶會在兩個平台同時完成打分操作，交叉匹配這部分數據，同樣有可能暴露出用戶的真實身份。

而蘋果的 Differential Privacy，其實並不是蘋果自創的一項技術，更具體地說，它在理論界已經被廣泛地討論，只是沒有真正地實施應用到具體的業務中，而其實 Differential Privacy 也不是具體指某一項技術，而是指一系列技術的綜合運用，從而最終達到這個目的：有沒有辦法，從總體 A 中去掉某一個樣本後得到 A"，而在統計分析上，兩者在數學上是無差別的。

要做到這一點，Craig Federighi 在 WWDC 上提到蘋果做了幾件事情：

局部抽樣：與其上傳用戶的整體資料，蘋果很可能是以某一頻率，局部採集一部分用戶的數據；
哈希加密：例如用戶的鍵盤輸入記錄，可以先用布隆過濾器哈希一遍，這樣就可以在保護用戶隱私的前提下，得知用戶是否使用某些固定的表達；
注入噪音：在採集用戶的數據前，向其中隨機地注入一些噪音，只要被注入的噪音抽樣是正態分布的，那麼回到整體來看，這些噪音最終將相互抵消；

你會發現，蘋果做的這些工作，都是為了避免在全局中暴露個人的信息，在蘋果手上，永遠只有加密的、部分的、甚至含有隨機錯誤的信息。但也正是如此，蘋果沒有針對單個用戶建立 User Profile。事實上，為什麼我們需要針對單個用戶建立 User Profile 呢？這裡有一個悖論，如果你的行為和屬性屬於某一個群體，那麼 Group Profile 的精度就已經足夠了，在需要 User Profile 的場景下，比如說預測你下一個字會打什麼，即使機器學習再先進，憑什麼認為它比你還了解你自己？

Craig Federighi 在 WWDC 上滿臉傲驕地說「We believe you should have great features and great privacy」，那個瞬間特別像一個小孩子，自信滿滿地向世界宣告「我們就是能站著把錢賺了」。

其實 Google 也有嘗試過類似的事情，在 GitHub 上開源了一個名為 RAPPOR(Randomized Aggregatable Privacy-Preserving Ordinal Response) 的項目，從原理上來說，也是向數據中注入可控的噪音元素的方式來保護用戶隱私，早在 2014 年 Google 就以這項技術來收集用戶使用 Chrome 瀏覽器時的資料。遺憾的是，一如蘋果宣稱的，蘋果是唯一一家將 Differential Privacy 作為標準大規模部署的公司。

本文由【子不語】原創，歡迎搜一搜微信公眾號【子不語】關註：ZiChat。

準確地說，dp不是一種保護技術。dp指的是一種攻擊。攻擊者可以利用dp去攻擊某些類型的資料庫，去獲得用戶的隱私信息，即使這個資料庫是脫敏保存的。

那麼蘋果的意思就是說，蘋果保存和使用用戶數據，是可以防止差分攻擊。

怎麼說的呢？其實如果拋開具體的數學定義和具體的技術細節，differential privacy非常好理解。它提供了一種最強大的隱私保護：
敵人根本不知道我在不在這個數據集里。

這為什麼是最強大的保護呢？畢竟如果你不在這個數據集里的話，你的數據自然就不會泄露咯。DP的提出者在我們學校給talk時也提到了：不管你怎麼定義privacy,基本都會最終走到dp的這條路上來。

Apple具體的技術實現細節就不知道了，也不知其是否達到了理論上DP的要求。

差分隱私是06年由Dwork提出的一種隱私保護機制，主要通過對原始數據進行隨機擾動，而達到隱私保護的目的。

首先，我們需要了解差分攻擊的含義。例如，一個資料庫中包含4個人分別的月工資，另一個資料庫包含前3個人的月工資。若攻擊者得知這兩個資料庫的工資總數，則通過S(D2)-S(D1)則可以得到第四個人精確的月工資。

為了避免這種個人隱私的泄露，我們可以通過在每個人的工資上加入一定量的雜訊。這樣，即使採用差分攻擊，也不能得到該人精確的工資數值。

我是因為是一名 iOS 開發者，才關注到 Apple 的 Differetial Privacy，同時也很想學習演算法領域的東西。看了很多人的回答，大致了解了 DP 的理論原理，從概念上並不難理解，但是實現似乎有比較大的難度。所以，Apple 在 WWDC 2016 上提出的 DP 是較傳統意義上弱化了的，還是說 Apple 真的有技術能力實現了真正意義上的 DP（個人覺得 Apple 還是這個技術能力的）。關注了，期望能得到更多更深入的回答。

兩句話就能解釋一堆人講一堆，
如果說能在一定條件下無限檢索資料庫，那麼理論上我可以還原這個資料庫。差分隱私就是無論你怎麼檢索，都無法還原一個準確、完整的資料庫。

其實Apple提了Differetial Privacy和No User Profiling，我來做一個他們結合的吧

剛上了這個課，教授也講到了Apple 的 DP巴拉巴拉，但是我聽著似乎就是呵呵呵騙我沒文化呢... 然後Google的DP也將到了聽著就像呵呵呵看你表現還不錯＝＝

見圖Apple

見圖Google

通俗點說，就是對原數據進行干擾，使得某條數據的存在與否取值如何對最終輸出結果的概率分布影響不大。
干擾方式有多種，加噪音（如laplace噪音和gaussian噪音）是最直接的方式，也有根據數據分布或演算法特性構造出的不加噪音的干擾方式。