差分私隱

差分私隱（英語：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