差分隱私

4 人贊了文章

差分隱私

英文名Differential privacy

1 概要

? 原則和實例

2 正式的定義和應用示例

? 靈敏度

? 準確性與隱私的均衡

? 差分隱私的其他概念

3 差分隱私機制

? 拉普拉斯機制

4 組合性

? 順序組成

? 平行構圖

5 群體隱私

? 穩定變形

6 採用差分隱私的實際應用

概要

差分隱私Differential privacy[1] 是對通過演算法消除的個人隱私的數學定義。當個人信息用於創建數據產品時通過某種方法可以消除特定的個人隱私信息。該術語由Cynthia Dwork於2006年創造[2] ，但更早的定義實際上來源於Dwork，Frank McSherry，Kobbi Nissim和Adam D. Smith 的文章[3] 。差分隱私的概念部分基於Nissim和Irit Dinur 的工作[4] ，他們的研究表明，即使通過大量統計發布的數據，也一定會泄露個人信息；而且通過少數查詢就可以獲取整個資料庫的信息。

Dinur和Nissim的「資料庫重建」工作的是人們認識到使用隱私的語義定義為統計資料庫提供隱私保護的方法是不可行的。而且隨著私人數據在統計數據中的增長，需要新的科技幫助人們控制隱私泄露的風險。後續研究工作的結果是技術的發展使得在許多情況下可以從資料庫提供非常準確的統計數據，同時仍然確保高度的隱私性。[2]

原則和實例

差分機密性是將隨機性引入數據的過程。

一個社會學簡單的例子，[6] 根據以下流程要求被提問者回答「你擁有屬性A？」的問題，對方的回複流程是：

1. 扔一枚硬幣。

2. 如果正面朝上，然後誠實回答。

3. 如果反面朝上，然後再扔硬幣，如果正面回答「是」，如果反面回答「否」。

保密性來源於個人答覆的可糾正性。

但總的來說，這些有很多答案的數據是非常重要的，因為沒有屬性A的人給予四分之一的肯定答案，實際擁有屬性A的人給出四分之三的肯定答案。如果p是A的真實比例，那麼我們期望得到（1/4）（1-p）+（3/4）p =（1/4）+ p / 2的肯定答案。因此可以估計p。

特別是如果屬性A可能意味著非法行為，因為無論是否違法的具體個人都有可能給出「是」的答案回應，那麼回答「是」不會獲罪。

雖然受隨機響應啟發的這個例子可能適用於微數據（即釋放單獨響應的數據集），但根據定義，差分隱私排除了微數據發布，並且僅適用於查詢（即，將單個響應合併為一個結果）。微數據發布因為可以抵賴個人數據的存在性而不符合差分隱私的定義。[7-8]

正式的定義和應用示例

假設

是一個正實數，A是一個隨機演算法，它將數據集作為輸入（表示信任方擁有的數據）。imA表示A的映射。對於在非單個元素（即，一個人的數據）的所有數據集D1和D2以及imA的所有子集S，演算法A是

-差分隱私，其中概率取決於演算法的隨機性。

例如, 假設我們有一個醫療記錄資料庫 D1 在那裡每條記錄是一對 (名字, x), 其中 X 是一個布爾值表示一個人是否瘓有糖尿病。例如:

姓名

有糖尿病

Ross

是1

Monica

是1

Joey

否0

Phoebe

否0

Chandler

是1

現在假設一個惡意用戶 (通常被稱為攻擊者) 想知道Chandler是否有糖尿病。假設他知道Chandler在資料庫的哪一行。現在攻擊者只能使用特定形式的查詢Qi返回資料庫中前i行中第一列 X 的部分總和。攻擊者為了獲取Chandler是否有糖尿病的信息。只需要執行兩個查詢 Q5（D1）和Q4（D1），分別計算前五行和前四行的總和，然後計算兩個查詢的差別。在本例中Q5（D1）=3，Q4（D1）=2，差是1。攻擊者在知道Chandler在第5行的情況下，就會知道他的糖尿病狀況是1（有糖尿病）。這個例子顯示了即使在沒有明確查詢特定個人信息的情況下, 個人信息如何被泄露。

繼續這個例子，如果我們用（Chandler，0）代替（Chandler，1）構造D2，那麼這個惡意攻擊者將能夠通過計算每個數據集的Q5-Q4來區分D2和D1。 如果攻擊者被要求通過

-差分隱私演算法接收Qi值，對於足夠小的

，則他將不能區分這兩個數據集。

靈敏度

d為正整數，D為一個數據集的集合，

為函數。

代表的函數的靈敏度[9] 由下式定義:

其中最大值是D中的所有對數據集對應的D1和D2中最差別最大的一對，

表示曼哈頓距離。

在上面醫學資料庫的例子中，如果我們認為f是函數Qi，那麼函數的靈敏度就是1，因為改變資料庫中的任何一個條目都會導致函數的輸出改變0或 1。

有一些技術（如下所述），我們可以使用這些技術建立低靈敏度差分隱私演算法。

準確性與隱私的均衡

通過差分隱私加擾的結果，要在統計數據的準確性和隱私參數之間有權衡.[10-13] 這種均衡也必須考慮到ε參數乘以查詢數量(包括預計的查詢數量)。

差分隱私的其他概念

對很多應用而言, 差分隱私被認為過於嚴格, 因此建議了許多被弱化的版本。這些包括 (ε, δ)-差分隱私,[14] 隨機差分隱私, [15]以及特定標度的隱私。[16]

差分隱私機制

由於差分隱私是一個概率概念，任何差分隱私機制必然是隨機的。 下面描述的拉普拉斯機制就依賴於我們對結果添加的受控雜訊。 其他的像指數機制[17] 和後驗抽樣[18] 依賴於問題的分布族。

拉普拉斯機制

許多差分隱私方法以添加受控噪音實現降低查詢結果的靈敏度[9] 。拉普拉斯機制增加了拉普拉斯雜訊（即符合拉普拉斯分布的雜訊，其可以用概率密度函數

表示，其均值為0和標準偏差是

）。 現在在我們的例子中，我們將的輸出函數定義為實值函數（稱為

的輸出副本）為

，其中

和f是我們計劃在資料庫上執行的原始實值查詢/函數。現在很明顯，

可以被認為是一個連續的隨機變數，其中

，最多為

.我們可以認為是隱私因子

.

因此，

遵循不同的隱私機制（從上面的定義可以看出）。 如果我們試圖在我們的糖尿病例子中使用這個概念，那麼從上面推導出的事實可以看出，為了讓

作為

-差分隱私演算法，我們需要

。 雖然我們在這裡使用了拉普拉斯雜訊，但也可以使用其他形式的雜訊，例如高斯雜訊，但這樣可能需要略微放寬差分隱私的定義[19] 。

組合性

順序組成

如果我們查詢一個ε差分隱私機制t次，並且該機制的隨機化是

-差分隱私。 在更通用的情況下，如果有n個獨立的機制：

，其隱私係數分別為

，那麼它們的任意函數g即

是：

-差分隱私。[20]

平行構圖

此外，如果以前的機制是在私有資料庫的不相交子集上計算的，那麼函數g將是

- 差分隱私。[20]

群體隱私

通常，ε-差分隱私被設計用於保護相鄰資料庫中僅在一行中的隱私數據。 這意味著有任意輔助信息的攻擊者無法知道一個特定參與者是否提交了他的信息。如果我們想要保護c行數據，這種情況也是可擴展的。使用任意輔助信息的攻擊者有可能知道特定c個參與者是否提交了他們的信息，這種攻擊可以實現，因為如果c項改變，隨機噪音的概率是以

而不是

為界[19] ，即D1和D2在c個項目上不同：

將ε設定為

可以達到所需的結果（保護c個項目）。 不是每個項目ε-差分隱私保護，現在每一組c個項目是ε-差分隱私（並且每個項目都是

-差分隱私）。

穩定變形

對於任何兩個資料庫A，B，如果T（A）和T（B）之間的漢明距離最多為A和B之間的漢明距離的c倍，則變換T是c階穩定的。 [20] 中的定理2斷言如果存在

-差分隱私機制M，那麼複合機制

是

-差分隱私。

這可以推廣到群體隱私，因為群體大小可以被認為是A和B之間的漢明距離h（其中A包含群組而B不包含）。 在這種情況下，

是

-差分隱私。

採用差分隱私的實際應用

迄今已知的微分隱私的幾個應用：

美國人口普查局為顯示交通狀況[21]

谷歌的RAPPOR[22]

谷歌，共享歷史流量統計[23]

2016年6月13日，蘋果宣布打算在iOS 10中使用差分隱私[24]

在數據分析和反欺詐中，差分隱私的一些初步研究[25] 。