差分隱私

差分隱私（英語：differential privacy）是一個數據共享手段，可以實現僅分享可以描述數據庫的一些統計特徵、而不公開具體到個人的信息。差分隱私背後的直觀想法是：如果隨機修改數據庫中的一個記錄造成的影響足夠小，求得的統計特徵就不能被用來反推出單一記錄的內容；這一特性可以被用來保護隱私。從另一個角度來理解差分隱私，可以將其視為用於公開統計數據庫統計特徵的算法的一個約束條件。該約束條件要求數據庫各記錄中的隱私信息不被公開。例如，差分隱私的算法被一些政府部門用於公開人口統計信息或其它統計數據，同時保證各被統計對象的回答的保密；又如，一些公司在收集用戶行為信息的時候可以籍此控制包括內部人員在內的訪問者可以看到的細節。

粗略地講，若觀察者無法分辨一個算法的輸出是否使用了某一特定個體的信息，這樣的算法就是差分隱私的。討論差分隱私時，經常會考量數據庫中的個體是否可以被分辨出來。儘管定義時沒有直接使用再識別攻擊的概念，差分隱私的算法通常可以抵禦此種攻擊。

差分隱私的概念最早由密碼學家提出，因此相關研究也經常與密碼學相關聯、使用大量密碼學術語。

歷史

官方的統計機構負責收集個人和組織機構的信息，並公開綜合數據以服務大眾。例如，1790年美國人口普查收集了居住在美國的個人的信息，並發布了基於性別、年齡、種族和勞役情況的統計表。很久以來，各統計機構在收集信息時都會承諾保密、保證數據只用於統計學用途，但公開發布的數據不可再被用於識別單一的個人或組織。為了實現這一要求，統計機構傳統上會在發布時隱去一部分信息。例如，在按照行業分類統計一個城市的各行業營業額情況的表格中，如果某一格的數據僅來自一家公司，則該格數據可能會被隱去，以保證該公司的真實營業額不會因此泄露。

1950到1960年代，各統計機構開始使用電子信息處理系統，大大加快了一個機構可以製作的統計表數量。如此一來，保密信息被不當公開的機會也因而增加了。例如，如果前述的公司被隱去的營業額數據也被統計進了該區域所有公司的總營業額，則用總數減去其他各行業的營業額，仍可得出該公司的真實營業額。更複雜的加減組合亦可能揭示更多信息。隨着公開發布的統計表格增加，需要檢查的計算方案呈指數增長。如果數據使用者可以在交互式系統中訪問統計數據庫，則需要檢查的計算方案數可能是無上限的。

1977年，托雷·達勒紐斯（Tore Dalenius）用數學語言描述了在表格中隱去一格數據的過程。

1979年，多蘿西·丹寧、彼得·丹寧和邁耶施瓦茨（Mayer D. Schwartz）正式提出了「追蹤者」的概念。這裡的追蹤者是指一個具有使用一系列查詢並記錄結果的能力、可以通過訪問統計數據庫來獲知保密內容的攻擊者。該研究及之後的研究分析了統計數據庫輸出的隱私性質：追蹤記錄每條查詢對數據庫中個體的隱私的影響是NP困難的。

2003年，科比·尼西姆和伊里特·迪努爾的研究顯示，對於一個統計數據庫，公開任意數量的查詢結果而不在此過程中泄露任何隱私信息是不可能的，且僅需進行很少次數的隨機查詢就可以完全揭示整個數據庫的每個記錄。這一現象被稱為信息恢復基本定律。由此可以推知，在絕大多數情況下，如不注入一定程度的噪聲，就無法確保隱私。這一結論引出了差分隱私的研究。

2006年，辛西婭·德沃克、弗蘭克·麥克雪麗、科比·尼西姆和亞當·D·史密斯的研究提出了確保隱私所需的噪聲，並提出一個添加噪聲的通用機制。 該研究贏得了2017年的哥德爾獎。

自此以來，後續研究進一步揭示了還有許多可以提供非常準確的統計數據、同時保證高程度隱私的方法。

動機

設想一個受信任的機構持有涉及眾多人的敏感個人信息（例如醫療記錄、觀看記錄或電子郵件統計）的數據庫，且想提供一個全局性的統計數據。這樣的系統被稱為統計數據庫。儘管表面看來，只有經過處理的統計特徵被發布，但這些統計結果也有可能揭示一些涉及個人的信息。例如，當研究人員同時使用兩個或多個分別進行過匿名化處理的數據庫時，個人信息的匿名化手段仍然可能失效。差分隱私就是為防護這類統計數據庫再識別技術而提出的一個概念。

網飛懸賞事件

2006年10月，網飛提出一筆100萬美元的獎金，以獎勵可將其推薦系統改進10%的參與者。為此，網飛發布了一個訓練數據集供開發者訓練其系統。在發布此數據集時，網飛提供了免責聲明：為保護客戶的隱私，可用於識別單個客戶的所有個人信息已被刪除，並且所有客戶ID已用隨機生產的ID替代。

然而，網飛不是網絡上唯一涉及電影評級的網站。其他很多網站，包括IMDb，亦提供類似的功能：用戶可以在IMDb上註冊和評價電影，且也可以選擇匿名自己的詳細資料。德克薩斯州大學奧斯汀分校的研究員阿爾文德·納拉亞南和維塔利·什馬蒂科夫（Vitaly Shmatikov）將網飛匿名化後的訓練數據庫與IMDb數據庫（根據用戶評價日期）相連，能夠重新識別網飛數據庫中的個人。這表明網飛採取的匿名化手段仍然可以泄露部分用戶的身份信息。

馬薩諸塞州集團保險委員會（GIC）醫療數據庫事件

麻省理工學院的拉坦亞·斯維尼將匿名化的GIC數據庫（包含每位患者的出生日期、性別和郵政編碼）與選民登記記錄相連後，可以找出馬薩諸塞州州長的病歷。

元數據與流動數據庫

MIT的德蒙喬耶（De Montjoye）等人引入了單一性（意為獨特性）概念，顯示出4個時空點、近似地點和時間就足以唯一性識別一個150萬人流動數據庫中的95%用戶。該研究進一步表明，即使數據集的分辨率較低，這些約束仍然存在，即粗糙或模糊的流動數據集和元數據也只提供很少的匿名性。

ε-差分隱私

2006年德沃克等人的文章提出了ε-差分隱私（英語：ε-differential privacy）的概念：用數學語言定義了統計數據庫的數據隱私損失。（這裡的「統計數據庫」是指在承諾保密的條件下收集的一組數據，這些數據僅用於產生統計數據，且在此過程中不損害數據提供者的隱私。）

這一定義背後的想法是：如果在統計數據公開的時候，如果一個人的數據不再數據庫里，那他的隱私就不會被泄露。因此，差分隱私旨在為每一個體提供與把對應數據移除可以帶來的隱私幾乎相同的隱私。也就是說，在這樣的數據庫上運行的統計函數（例如求和、求平均等）不能過於依賴任何個體的統計數據（即不能依賴任何單一記錄）。

當然，每個個體在統計結果中的貢獻取決於所使用的查詢請求了多少數據。如果一個數據庫只含有一個人的數據，那這個人的貢獻就是100%。如果數據庫里含有一百人的數據，則每個人可能只貢獻1%。差分隱私的關鍵在於，查詢請求的數據越少，就要添加越多的噪聲，以保證同等程度的隱私。正如2006年論文的標題所說的那樣：「在隱私數據分析中用靈敏度標定噪聲」。

在提出差分隱私的數學定義的同時，這篇論文還提出了一個基於添加拉普拉斯噪聲（即該噪聲服從拉普拉斯分布）的機制，該機制滿足差分隱私的定義。

定義

令ε為一正實數，而${\mathcal {A}}$ 為一隨機算法，以一數據庫為該算法的輸入。 令${\textrm {im}}\ {\mathcal {A}}$ 為算法${\mathcal {A}}$的像。若對所有的僅有一個記錄（例如一個人的數據）不同的兩個數據庫$D_{1}$和$D_{2}$，以及${\textrm {im}}\ {\mathcal {A}}$的所有子集$S$，

$\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp \left(\varepsilon \right)\cdot \Pr[{\mathcal {A}}(D_{2})\in S],$

則稱該算法${\mathcal {A}}$可以提供$\varepsilon$-差分隱私。其中，取概率的隨機性來自於算法${\mathcal {A}}$。

差分隱私的定義提供了模塊化設計和分析差分隱私機制的方法。差分隱私具有以下性質：可組合性、對後續過程的穩健性，以及在具有相關性的數據上可以自然地退化。

可組合性

可（自）組合性是指（有可能是按照特定順序排列的）多個差分隱私機制的輸出仍然是差分隱私的。

順序組合（串聯）：如果要查詢一個ε-差分隱私機制$t$次，而該機制對於多次查詢的隨機性是獨立的，則所有結果是$\varepsilon t$-差分隱私的。更一般地，若有$n$個獨立的機制${\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n}$，分別為$\varepsilon _{1},\dots ,\varepsilon _{n}$-差分隱私的，則任意一個它們的函數$g({\mathcal {M}}_{1},\dots ,{\mathcal {M}}_{n})$是$\left(\sum \limits _{i=1}^{n}\varepsilon _{i}\right)$-差分隱私的。

並行組合（並聯）：如果前述多個機制實施在一個數據庫的不相交的子集上，則函數$g$是$(\max _{i}\varepsilon _{i})$-差分隱私的。

對後續過程的穩健性

對任何定義在${\mathcal {A}}$的像上的確定或隨機的函數$F$，若${\mathcal {A}}$是ε-差分隱私的，則$F({\mathcal {A}})$也是。

可組合性和穩健性一同保證了差分隱私機制的模塊化設計和分析是可行的。這些性質也促成了「隱私損失預算」的概念。如果訪問敏感數據的一組機制各自都是差分隱私的，則它們的組合、外加任意的後續過程也都是差分隱私的。

組隱私

一般而言，ε-差分隱私可以保障兩個僅相差一個記錄的數據庫之間的隱私。也就是說，任何擁有任意外部信息的攻擊者都無法知道任何一個個體在數據庫中的信息。但這一定義也可以自然地擴展到兩個數據庫之間相差至多$c$個記錄的情況。組隱私希望保證任何擁有任意外部信息的攻擊者都無法知道$c$個個體是否在數據庫中有信息。這也是成立的，因為如果$c$個記錄不同，則概率擴張的上界是$\exp(\varepsilon c)$而不是$\exp(\varepsilon )$，也就是說，對於相差至多$c$個記錄的數據庫$D_{1}$和$D_{2}$：

$\Pr[{\mathcal {A}}(D_{1})\in S]\leq \exp(\varepsilon c)\cdot \Pr[{\mathcal {A}}(D_{2})\in S]\,\!$

因此，使用ε而非$\varepsilon /c$即可實現想要的效果（保護$c$個記錄）。也就是說，現在每$c$個條目都被ε-差分隱私的機制保護（而對於每一個條目而言，該機制則是$(\varepsilon /c)$-差分隱私的）。

滿足ε-差分隱私的機制

因為差分隱私是一個基於概率論的概念，任何差分隱私機制都是隨機的。其中一些，例如下述的拉普拉斯機制，依賴於在一個查詢需要計算的函數上添加一定的噪聲。其它機制，例如指數機制和後驗抽樣則使用一種由需求決定的概率分布來抽樣的方法。

靈敏度

令$d$為一正整數，${\mathcal {D}}$為一組數據庫，而$f\colon {\mathcal {D}}\rightarrow \mathbb {R} ^{d}$為一函數。把函數$f$的「靈敏度」 記作$\Delta f$，其定義是

$\Delta f=\max \lVert f(D_{1})-f(D_{2})\rVert _{1}$

其中最大值取在${\mathcal {D}}$ 中任意兩個相差至多一個條目的數據庫$D_{1}$和$D_{2}$上，而$\lVert \cdot \rVert _{1}$表示$\ell _{1}$範數。

在下面的醫療數據庫的例子裡，如果把$Q_{i}$作為函數$f$，則該函數的靈敏度是1，因為改變數據庫中任意一個記錄會使函數的值改變0或1。

有一些方法可以為低靈敏度的函數創建差分隱私的算法。

拉普拉斯機制

參見：添加噪聲機制

拉普拉斯機制添加拉普拉斯噪聲（即服從拉普拉斯分布的噪聲。該種噪聲可以用以下概率密度函數表示：${\text{noise}}(y)\propto \exp(-|y|/\lambda )\,\!$，其均值為0，標準差為${\sqrt {2}}\lambda \,\!$）。假設算法${\mathcal {A}}\,\!$可以看作一個實值函數，而${\mathcal {T}}_{\mathcal {A}}(x)=f(x)+Y\,\!$，其中$Y\sim {\text{Lap}}(\lambda )\,\!\,\!$，而$f\,\!$是原本要在數據庫上進行的一個查詢（也是一個實值函數）。${\mathcal {T}}_{\mathcal {A}}(x)\,\!$可以被視為一個連續隨機變量，其中

${\frac {\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{1}}(x)=t)}{\mathrm {pdf} ({\mathcal {T}}_{{\mathcal {A}},D_{2}}(x)=t)}}={\frac {{\text{noise}}(t-f(D_{1}))}{{\text{noise}}(t-f(D_{2}))}}\,\!$

且至多為$e^{\frac {|f(D_{1})-f(D_{2})|}{\lambda }}\leq e^{\frac {\Delta (f)}{\lambda }}\,\!$。把${\frac {\Delta (f)}{\lambda }}\,\!$作為隱私係數$\varepsilon \,\!$。這樣，${\mathcal {T}}\,\!$就是一個差分隱私的機制（參考前面的定義）。類似地，其它形式的噪聲，例如高斯噪聲等，也可以使用。使用其它噪聲時的隱私係數需要進行相應的推導。如果在下面的醫療數據庫例子裡使用拉普拉斯機制，根據前面的推導，若需使${\mathcal {A}}\,\!$滿足$\varepsilon \,\!$-差分隱私，則應令$\lambda =1/\varepsilon \,\!$。

根據這個定義，差分隱私可以看作是數據庫的統計數據公開機制（例如，負責發布統計查詢結果的程序）上的一個條件，而不是對數據庫本身的要求。直觀上說，這意味着對於任意兩個相近似的數據庫，一個差分隱私的算法在它們上的運算結果都會是大致相似的。這樣的定義也意味着單一記錄的存在與否不會大程度地影響算法的輸出。

例如，假設有一個醫療數據庫$D_{1}$，每條記錄是一個二元組(姓名, X)，其中$X$是一個布爾值，表示一個人是否患有糖尿病。

姓名	糖尿病（X）
張三	1
李四	1
王五	0
趙六	0
孫七	1
周八	0

假設一個惡意用戶（通常被稱作「敵手」）想要知道孫七有沒有糖尿病。假設他已經知道該數據庫里孫七位於第幾行。又假設用戶只能使用一個特定的查詢$Q_{i}$，該查詢只可以返回$X$這一列的前$i$行數值的和。為了找出趙六的具體數值，敵手可以執行$Q_{5}(D_{1})$和$Q_{4}(D_{1})$，然後查看兩個數值的差。在上例種，$Q_{5}(D_{1})=3$而$Q_{4}(D_{1})=2$，所以它們相差1。這意味孫七在着「糖尿病」這一列的數值一定是1。這個例子顯示了就算不能具體地查詢每一行的數值，統計數據庫還是有可能會泄露特定個體的信息。

繼續看這個例子。如果另有一個數據庫$D_{2}$，其中將(孫七, 1)改寫為(孫七, 0)，則該惡意用戶可以分辨出$D_{2}$和$D_{1}$是不同的數據庫，方法是對每個數據庫各進行一次$Q_{5}-Q_{4}$計算。但若敵手必須通過一個$\varepsilon$-差分隱私的算法來獲取$Q_{i}$的值，如果$\varepsilon$足夠小，該敵手就不能看出兩個數據庫有何差別，也就無法推斷出孫七在「糖尿病」一列的數值。

隨機化返回值

參見：本地差分隱私

舉一個簡單的例子，這樣的例子在社會科學中尤其常見，在統計調查中經常使用諸如「你是否滿足條件A？」這樣的問題。不直接記錄回答，而是使用如下方法：

1. 投一枚硬幣。
2. 如果正面朝上，則再投一次（忽略投出的結果）。然後如實地回答問題。
3. 如果反面朝上，則再投一次。如果正面朝上，就回答「是」；如果反面朝上，就回答「否」。

（註：第二次投擲看上去是多餘的。但該步驟實際上是為了防止以下情況出現：「投硬幣」這一動作本身可能會被人觀察到，就算投擲結果本身沒有被公開）有賴於可證偽性，這樣做可以提升每個人的回答的保密程度。

但總體上看，如果回答的數量足夠多，最終得到的數據仍然是可用的。因為回答被記錄為「是」的人里，可以期望有四分之一的人實際上不滿足「條件A」，而四分之三則實際上滿足。這樣，如果令$p$表示實際上滿足A的人的比例，則期望上，記錄中「是」所占的比例應當是$(1/4)(1-p)+(3/4)p=(1/4)+p/2$。因此，人們可以從統計結果中估計$p$的值。

這一方法的另一個好處是，如果「條件A」是指一個非法行為，則根據被記錄的回答「是」不能推斷回答者有罪，因為不管實際情況如何，所有人都有一定概率回答「是」。

在這樣的依賴隨機化回答的例子中，微觀數據庫（即完全公開每個人回答情況的數據庫）或許是可行的。但根據定義，差分隱私仍不允許微觀數據公開，只能通過查詢（即將多個回答合成為統計數據）進行，因為這樣的例子仍不符合差分隱私的要求：每個個體都無法否認自己參與了這一調查（即各記錄是否存在於數據庫里）。

對變換的穩定性

如果$T(A)$和$T(B)$之間的漢明距離至多是$c$倍的$A$與$B$之間的漢明距離，其中$A,B$是兩個數據庫，則稱一個變換$T$是$c$-穩定的。中的定理2表明，如果一個機制$M$是$\varepsilon$-差分隱私的，則組合$M\circ T$是 $(\varepsilon \times c)$-差分隱私的。

利用這一性質，可以將差分隱私一般化為組隱私，因為可以用$A$和$B$之間的漢明距離$h$來表示一組記錄的大小（其中$A$里包含這組記錄，而$B$不包含）。這時，$M\circ T$就是$(\varepsilon \times c\times h)$-差分隱私的。

其它定義

差分隱私的原始定義在一些實際應用中可能會太強或太弱，因此也有研究提出一些其它類似的定義。最常用的一種更弱的定義是(ε, δ)-差分隱私，該定義在ε指數倍概率的上界上再增加一個較小的數δ。

現實世界中對差分隱私的應用

至今為止，比較知名的採用差分隱私的應用如下：

• 2008年：美國普查局，應用差分隱私來發布通勤模式的統計數據。
• 2014年：谷歌的RAPPOR，用於監測功能，例如收集劫持用戶設置的惡意軟件的統計數據。
• 2015年：谷歌，發布歷史流量數據。
• 2016年：蘋果宣布計劃在iOS 10中使用差分隱私來改進其虛擬個人助理技術。
• 2017年：微軟，用於Windows中的監測功能。
• 2019年：Privitar Lens是一款應用差分隱私的API。
• 2020年：領英，用於廣告商的查詢。
• 在數據挖掘模型中使用差分隱私的實際表現已有一些初步研究。

參見

• 准標識符
• 指數機制
• k-匿名性

外部連結

• Privacy of Dynamic Data: Continual Observation and Pan Privacy （頁面存檔備份，存於網際網路檔案館） by Moni Naor, Institute for Advanced Study, November 2009
• Tutorial on Differential Privacy （頁面存檔備份，存於網際網路檔案館） by Katrina Ligett, California Institute of Technology, December 2013
• A Practical Beginner's Guide To Differential Privacy （頁面存檔備份，存於網際網路檔案館） by Christine Task, Purdue University, April 2012
• Private Map Maker v0.2 （頁面存檔備份，存於網際網路檔案館） on the Common Data Project blog
• Learning Statistics with Privacy, aided by the Flip of a Coin （頁面存檔備份，存於網際網路檔案館） by Úlfar Erlingsson, Google Research Blog, October 2014