差分隱私

差分隱私是一個數據共享手段，可以實現僅分享可以描述資料庫的一些統計特徵、而不公開具體到個人的資訊。差分隱私背後的直觀想法是：如果隨機修改資料庫中的一個記錄造成的影響足夠小，求得的統計特徵就不能被用來反推出單一記錄的內容；這一特性可以被用來保護隱私。從另一個角度來理解差分隱私，可以將其視為用於公開統計特徵的演算法的一個約束條件。該約束條件要求資料庫各記錄中的隱私資訊不被公開。例如，差分隱私的演算法被一些政府部門用於公開人口統計資訊或其它統計資料，同時保證各被統計物件的回答的保密；又如，一些公司在收集使用者行為資訊的時候可以籍此控制包括內部人員在內的訪問者可以看到的細節。粗略地講，若觀察者無法分辨一個演算法的輸出是否使用了某一特定個體的資訊，這樣的演算法就是差分隱私的。討論差分隱私時，經常會考量資料庫中的個體是否可以被分辨出來。儘管定義時沒有直接使用攻擊的概念，差分隱私的演算法通常可以抵禦此種攻擊。差分隱私的概念最早由密碼學家提出，因此相關研究也經常與密碼學相關聯、使用大量密碼學術語。歷史.官方的統計機構負責收集個人和組織機構的資訊，並公開綜合資料以服務大眾。例如，收集了居住在美國的個人的資訊，併發布了基於性別、年齡、種族和勞役情況的統計表。很久以來，各統計機構在收集資訊時都會承諾保密、保證資料只用於統計學用途，但公開發布的資料不可再被用於試別單一的個人或組織。為了實現這一要求，統計機構傳統上會在釋出時隱去一部分資訊。例如，在按照行業分類統計一個城市的各行業營業額情況的表格中，如果某一格的資料僅來自一家公司，則該格資料可能會被隱去，以保證該公司的真實營業額不會因此洩露。1950到1960年代，各統計機構開始使用電子資訊處理系統，大大加快了一個機構可以製作的統計表數量。如此一來，保密資訊被不當公開的機會也因而增加了。例如，如果前述的公司被隱去的營業額資料也被統計進了該區域所有公司的總營業額，則用總數減去其他各行業的營業額，仍可得出該公司的真實營業額。更復雜的加減組合亦可能揭示更多資訊。隨著公開發布的統計表格增加，需要檢查的計算方案呈指數增長。如果資料使用者可以在互動式系統中訪問統計資料庫，則需要檢查的計算方案數可能是無上限的。1977年，託雷·達勒紐斯等人引入了概念，顯示出4個時空點、近似地點和時間就足以唯一性識別一個150萬人流動資料庫中的95%使用者。該研究進一步表明，即使資料集的解析度較低，這些約束仍然存在，即粗糙或模糊的流動資料集和元資料也只提供很少的匿名性。ε-差分隱私.2006年德沃克等人的文章提出了ε-差分隱私這一定義背後的想法是：如果在統計資料公開的時候，如果一個人的資料不再資料庫裡，那他的隱私就不會被洩露。因此，差分隱私旨在為每一個體提供與把對應資料移除可以帶來的隱私幾乎相同的隱私。也就是說，在這樣的資料庫上執行的統計函式。當然，每個個體在統計結果中的貢獻取決於所使用的查詢請求了多少資料。如果一個數據庫只含有一個人的資料，那這個人的貢獻就是100%。如果資料庫裡含有一百人的資料，則每個人可能只貢獻1%。差分隱私的關鍵在於，查詢請求的資料越少，就要新增越多的噪聲，以保證同等程度的隱私。正如2006年論文的標題所說的那樣：“在隱私資料分析中用靈敏度標定噪聲”。在提出差分隱私的數學定義的同時，這篇論文還提出了一個基於新增拉普拉斯噪聲的機制，該機制滿足差分隱私的定義。定義.令ε為一正實數，而formula_1 為一隨機演算法，以一資料庫為該演算法的輸入。令formula_2 為演算法formula_1的像。若對所有的僅有一個記錄不同的兩個資料庫formula_4和formula_5，以及formula_2的所有子集formula_7，formula_8則稱該演算法formula_1可以提供formula_10-差分隱私。其中，取機率的隨機性來自於演算法formula_1。差分隱私的定義提供了模組化設計和分析差分隱私機制的方法。差分隱私具有以下性質：可組合性、對後續過程的穩健性，以及在具有相關性的資料上可以自然地退化。可組合性.可多個差分隱私機制的輸出仍然是差分隱私的。順序組合：如果要查詢一個ε-差分隱私機制formula_12次，而該機制對於多次查詢的隨機性是獨立的，則所有結果是formula_13-差分隱私的。更一般地，若有formula_14個獨立的機制formula_15，分別為formula_16-差分隱私的，則任意一個它們的函式formula_17是formula_18-差分隱私的。並行組合：如果前述多個機制實施在一個數據庫的不相交的子集上，則函式formula_19是formula_20-差分隱私的。對後續過程的穩健性.對任何定義在formula_1的像上的確定或隨機的函式formula_22，若formula_1是ε-差分隱私的，則formula_24也是。可組合性和穩健性一同保證了差分隱私機制的模組化設計和分析是可行的。這些性質也促成了“隱私損失預算”的概念。如果訪問敏感資料的一組機制各自都是差分隱私的，則它們的組合、外加任意的後續過程也都是差分隱私的。組隱私.一般而言，ε-差分隱私可以保障兩個僅相差一個記錄的資料庫之間的隱私。也就是說，任何擁有任意外部資訊的攻擊者都無法知道任何一個個體在資料庫中的資訊。但這一定義也可以自然地擴充套件到兩個資料庫之間相差至多formula_25個記錄的情況。組隱私希望保證任何擁有任意外部資訊的攻擊者都無法知道formula_25個個體是否在資料庫中有資訊。這也是成立的，因為如果formula_25個記錄不同，則機率擴張的上界是formula_28而不是formula_29，也就是說，對於相差至多formula_25個記錄的資料庫formula_31和formula_32：formula_33因此，使用ε而非formula_34即可實現想要的效果。滿足ε-差分隱私的機制.因為差分隱私是一個基於機率論的概念，任何差分隱私機制都是隨機的。其中一些，例如下述的拉普拉斯機制，依賴於在一個查詢需要計算的函式上新增一定的噪聲。其它機制，例如和後驗抽樣則使用一種由需求決定的機率分佈來抽樣的方法。靈敏度.令formula_38為一正整數，formula_39為一組資料庫，而formula_40為一函式。把函式formula_41的“靈敏度” 記作formula_42，其定義是formula_43其中最大值取在formula_39 中任意兩個相差至多一個條目的資料庫formula_4和formula_5上，而formula_47表示formula_48範數。在下面的醫療資料庫的例子裡，如果把formula_49作為函式formula_41，則該函式的靈敏度是1，因為改變資料庫中任意一個記錄會使函式的值改變0或1。有一些方法可以為低靈敏度的函式建立差分隱私的演算法。拉普拉斯機制.拉普拉斯機制新增拉普拉斯噪聲。formula_57可以被視為一個連續隨機變數，其中formula_58且至多為formula_59。把formula_60作為隱私係數formula_61。這樣，formula_62就是一個差分隱私的機制。類似地，其它形式的噪聲，例如高斯噪聲等，也可以使用。使用其它噪聲時的隱私係數需要進行相應的推導。如果在下面的醫療資料庫例子裡使用拉普拉斯機制，根據前面的推導，若需使formula_53滿足formula_61-差分隱私，則應令formula_65。根據這個定義，差分隱私可以看作是資料庫的統計資料公開機制上的一個條件，而不是對資料庫本身的要求。直觀上說，這意味著對於任意兩個相近似的資料庫，一個差分隱私的演算法在它們上的運算結果都會是大致相似的。這樣的定義也意味著單一記錄的存在與否不會大程度地影響演算法的輸出。例如，假設有一個醫療資料庫formula_4，每條記錄是一個二元組(姓名, X)，其中formula_67是一個布林值，表示一個人是否患有糖尿病。假設一個惡意使用者想要知道孫七有沒有糖尿病。假設他已經知道該資料庫裡孫七位於第幾行。又假設使用者只能使用一個特定的查詢formula_49，該查詢只可以返回formula_67這一列的前formula_70行數值的和。為了找出趙六的具體數值，敵手可以執行formula_71和formula_72，然後檢視兩個數值的差。在上例種，formula_73而formula_74，所以它們相差1。這意味孫七在著“糖尿病”這一列的數值一定是1。這個例子顯示了就算不能具體地查詢每一行的數值，統計資料庫還是有可能會洩露特定個體的資訊。繼續看這個例子。如果另有一個數據庫formula_5，其中將(孫七, 1)改寫為(孫七, 0)，則該惡意使用者可以分辨出formula_5和formula_4是不同的資料庫，方法是對每個資料庫各進行一次formula_78計算。但若敵手必須透過一個formula_10-差分隱私的演算法來獲取formula_49的值，如果formula_10足夠小，該敵手就不能看出兩個資料庫有何差別，也就無法推斷出孫七在“糖尿病”一列的數值。隨機化返回值.舉一個簡單的例子，這樣的例子在社會科學中尤其常見，在統計調查中經常使用諸如“你是否滿足"條件A"？”這樣的問題。不直接記錄回答，而是使用如下方法：有賴於可證偽性，這樣做可以提升每個人的回答的保密程度。但總體上看，如果回答的數量足夠多，最終得到的資料仍然是可用的。因為回答被記錄為“是”的人裡，可以期望有四分之一的人實際上不滿足“條件A”，而四分之三則實際上滿足。這樣，如果令formula_82表示實際上滿足"A"的人的比例，則期望上，記錄中“是”所佔的比例應當是formula_83。因此，人們可以從統計結果中估計formula_82的值。這一方法的另一個好處是，如果“條件A”是指一個非法行為，則根據被記錄的回答“是”不能推斷回答者有罪，因為不管實際情況如何，所有人都有一定機率回答“是”。在這樣的依賴隨機化回答的例子中，。對變換的穩定性.如果formula_85和formula_86之間的漢明距離至多是formula_25倍的formula_88與formula_89之間的漢明距離，其中formula_90是兩個資料庫，則稱一個變換formula_91是formula_25-穩定的。中的定理2表明，如果一個機制formula_93是formula_10-差分隱私的，則組合formula_95是 formula_96-差分隱私的。利用這一性質，可以將差分隱私一般化為組隱私，因為可以用formula_88和formula_89之間的漢明距離formula_99來表示一組記錄的大小。這時，formula_95就是formula_103-差分隱私的。其它定義.差分隱私的原始定義在一些實際應用中可能會太強或太弱，因此也有研究提出一些其它類似的定義。最常用的一種更弱的定義是(ε, δ)-差分隱私，該定義在ε指數倍機率的上界上再增加一個較小的數δ。現實世界中對差分隱私的應用.至今為止，比較知名的採用差分隱私的應用如下：