原標題:大數據時代下的隱私保護

百度安全實驗室

前言

本文介紹了學術界和工業界對於使用者隱私保護的努力成果,其中主要講到了k-anonymity(k-匿名化),l-diversity(l-多樣化),t-closeness 和 ε-differential privacy(差分隱私),並對它們的優缺點進行了分析。

數據v.s. 隱私

在大數據的時代,數據成為了科學研究的基石。我們在享受著推薦演算法、語音識別、圖像識別、無人車駕駛等智能的技術帶來的便利的同時,數據在背後擔任著驅動演算法不斷優化迭代的角色。在科學研究、產品開發、數據公開的過程中,演算法需要收集、使用使用者數據,在這過程中數據就不可避免的暴露在外。歷史上就有很多公開的數據暴露了使用者隱私的案例。

美國在線(AOL)是一家美國網際網路服務公司,也是美國最大的網際網路提供商之一。在2006 8月,為了學術研究,AOL 公開了匿名的搜索記錄,其中包括65 萬個使用者的數據,總共20M 條查詢記錄。在這些數據中,使用者的姓名被替換成了一個個匿名的ID,但是紐約時報通過這些搜索紀錄,找到了ID 匿名4417749的使用者在真實世界中對應的人。ID 4417749 的搜索記錄里有關於「60歲的老年人」的問題、「Lilburn地方的風景」、還有「Arnold的搜索字樣。通過上面幾條數據,紐約時報發現 Lilburn 只有14個人姓Arnold,最後經過直接聯繫這14個人確認 ID 4417749 是一位62歲名字叫 Thelma Arnold的老奶奶。最後AOL 緊急撤下數據,發表聲明致歉,但是已經太晚了。因為隱私泄露事件,AOL遭到了起訴,最終賠償受影響使用者總額高達五百萬美元。

同樣是2006年,美國最大的影視公司之一 Netflix,舉辦了一個預測演算法的比賽(Netflix Prize),比賽要求在公開數據上推測使用者的電影評分Netflix 把數據中唯一識別使用者的資訊抹去,認為這樣就能保證使用者的隱私。但是在2007 年來自The University of Texas at Austin 的兩位研究人員表示通過關聯 Netflix 公開的數據和 IMDb(網際網路電影資料庫)網站上公開的紀錄就能夠識別出匿名後使用者的身份。三年後,在2010年,Netflix 最後因為隱私原因宣布停止這項比賽,並因此受到高額罰款,賠償金額總計九百萬美元。

近幾年各大公司均持續關注使用者的隱私安全。例如蘋果2016 6 月份的WWDC 大會上就提出了一項名為Differential Privacy 的差分隱私技術。蘋果聲稱他能通過數據計算出使用者群體的行為模式,但是卻無法獲得每個使用者個體的數據。那麼差分隱私技術又是怎麼做的呢?

在大數據時代,如何才能保證我們的隱私呢?要回答這個問題,我們首先要知道什麼是隱私。

什麼是隱私?

我們經常談論到隱私泄漏、隱私保護,那麼什麼是隱私呢?舉個例子,居住在海淀區五道口的小明經常在網上購買電子產品,那小明的姓名購買偏好居住地址算不算是隱私呢?如果某購物網站統計了使用者的購物偏好並公開部分數據,公開的數據中顯示北京海淀區五道口的使用者更愛買電子產品,那麼小明的隱私是否被泄漏了呢?要弄清楚隱私保護,我們先要討論一下究竟什麼是隱私。

對於隱私這個詞,科學研究上普遍接受的定義是單個使用者的某一些屬性」,只要符合這一定義都可以被看做是隱私。我們在提隱私的時候,更加強調的是單個使用者。那麼,一群使用者的某一些屬性,可以認為不是隱私。我們拿剛才的例子來看,針對小明這個單個使用者,購買偏好居住地址就是隱私。如果公開的數據說住在五道口的小明愛買電子產品,那麼這顯然就是隱私泄漏了。但是如果數據中只包含一個區域的人的購買偏好,就沒有泄露使用者隱私。如果進一步講,大家都知道小明住在海淀區五道口,那麼是不是小明就愛買點此產品了呢?這種情況算不算事隱私泄漏呢?答案是不算,因為大家只是通過這個趨勢推測,數據並不顯示小明一定愛買電子產品。

所以,從隱私保護的角度來說,隱私是針對單個使用者的概念,公開群體使用者的資訊不算是隱私泄漏,但是如果能從數據中能準確推測出個體的資訊,那麼就算是隱私泄漏。

隱私保護的方法

從資訊時代開始,關於隱私保護的研究就開始了。隨著數據不斷地增長,人們對隱私越來越重視。我們在討論隱私保護的時候包括兩種情況。

第一種是公司為了學術研究和數據交流開放使用者數據,學術機構或者個人可以向資料庫發起查詢請求,公司返回對應的數據時需要保證使用者的隱私。

第二種情況是公司作為服務提供商,為了提高服務質量,主動收集使用者的數據,這些在客戶端上收集的數據也需要保證隱私性。學術界提出了多種保護隱私的方法和測量隱私是否泄露的工具,例如k-anonymityk-匿名化)、l-diversityl-多樣化)、t-closenessε-differentialprivacy(差分隱私)、同態加密(homomorphic encryption)、零知識證明(zero-knowledge proof)等等。今天主要介紹k-anonymityk-匿名化),l-diversityl-多樣化),t-closeness ε-differential privacy(差分隱私)。這些方法先從直觀的角度去衡量一個公開數據的隱私性,再到使用密碼學、統計學等工具保證數據的隱私性。

下面我們一一解讀這四種隱私保護的方法:

k-anonymityk-匿名化)

k-anonymity 是在1998 年由Latanya Sweeney Pierangela Samarati 提出的一種數據匿名化方法。

我們先看一下下面的這個表格:

大數據時代下的隱私保護

我們把要表格中的公開屬性分為以下三類:

Key attributes: 一般是個體的唯一標示,比如說姓名、地址、電話等等,這些內容需要在公開數據的時候刪掉。

Quasi-identifier: 類似郵編年齡、生日、性別等不是唯一的,但是能幫助研究人員關聯相關數據的標示。

Sensitive attributes: 敏感數據,比如說購買偏好、薪水等等,這些數據是研究人員最關心的,所以一般都直接公開。

簡單來說,k-anonymity 的目的是保證公開的數據中包含的個人資訊至少k-1 條不能通過其他個人資訊確定出來。也就是公開數據中的任意quasi-identifier資訊,相同的組合都需要出現至少k 次。

舉個例子,假設一個公開的數據進行了2-anonymity 保護。如果攻擊者想確認一個人(小明)的敏感資訊(購買偏好),通過查詢他的年齡、郵編和性別,攻擊者會發現數據里至少有兩個人是有相同的年齡、郵編和性別。這樣攻擊者就沒辦法區分這兩條數據到底哪個是小明了,從而也就保證了小明的隱私不會被泄露。

下面這個表就是2-anonymization 過的資訊:

大數據時代下的隱私保護

k-anonymity的方法主要有兩種,一種是刪除對應的數據列,用星號(*)代替。另外一種方法是用概括的方法使之無法區分,比如把年齡這個數字概括成一個年齡段。對於郵編這樣的數據,如果刪除所有郵編,研究人員會失去很多有意義的資訊,所以可以選擇刪除最後一位數字。

從這個表中,即使我們知道小明是男性、24歲、郵編是100083,卻仍然無法知道小明的購買偏好。而研究人員依然可以根據這些數據統計出一些有意義的結果,這樣既兼顧了個人的隱私,又能為研究提供有效的數據。

k-anonymity能保證以下三點:

1.攻擊者無法知道某個人是否在公開的數據中

2.給定一個人,攻擊者無法確認他是否有某項敏感屬性

3.攻擊者無法確認某條數據對應的是哪個人(這條假設攻擊者除了quasi-identifier 資訊之外對其他數據一無所知,舉個例子,如果所有使用者的偏好都是購買電子產品,那麼k-anonymity 也無法保證隱私沒有泄露

攻擊方法

未排序匹配攻擊(unsorted matching attack) 當公開的數據記錄和原始記錄的順序一樣的時候,攻擊者可以猜出匿名化的記錄是屬於誰。例如如果攻擊者知道在數據中小明是排在小白前面,那麼他就可以確認,小明的購買偏好是電子產品,小白是家用電器。解決方法也很簡單,在公開數據之前先打亂原始數據的順序就可以避免這類的攻擊。

補充數據攻擊(complementary release attack) 假如公開的數據有多種類型,如果它們的k-anonymity 方法不同,那麼攻擊者可以通過關聯多種數據推測使用者資訊。

除此之外,如果敏感屬性在同一類quasi-identifiers 中缺乏多樣性,或者攻擊者有其它的背景知識,k-anonymity 也無法避免隱私泄露。

大數據時代下的隱私保護

我們知道李雷的資訊,表中有兩條對應的數據,但是他們的購買偏好都是電子產品。因為這個敏感屬性缺乏多樣性,所以儘管是2-anonimity 匿名化的數據,我們依然能夠獲得李雷的敏感資訊。

大數據時代下的隱私保護

如果我們知道小紫的資訊,並且知道她不喜歡購買護膚品,那麼從表中,我們仍可以確認小紫的購買偏好是廚具。

l-diversityl-多樣化)

通過上面的例子,我們引出了多樣化的概念。簡單來說,在公開的數據中,對於那些quasi-identifier 相同的數據中,敏感屬性必須具有多樣性,這樣才能保證使用者的隱私不能通過背景知識等方法推測出來。

l-diversity 保證了相同類型數據中至少有l 種內容不同的敏感屬性。

大數據時代下的隱私保護

例如在上圖的例子中,有10 條相同的類型的數據,其中8 條的購買偏好是電子產品,其他兩條分別是圖書和家用電器。那麼在這個例子中,公開的數據就滿足3-diversity 的屬性。

除了以上介紹的簡單l-diversity 的定義,還有其他版本的l-diversity,引入了其他統計方法。比如說:

基於概率的l-diversity (probabilistic l-diversity): 在一個類型中出現頻率最高的值的概率不大於1/l

基於墒的l-diversity (entropy l-diversity): 在一個類型中敏感數據分佈的墒至少是log(l)

遞歸(c,l)-diversity (recursive (c, l)-diversity): 簡單來說就是保證最經常出現的值的出現頻率不要太高。

l-diversity 也有其局限性:

敏感屬性的性質決定即使保證了一定概率的diversity 也很容易泄露隱私。例如,醫院公開的艾滋病數據中,敏感屬性是艾滋病陽性(出現概率是1%)和艾滋病陰性(出現概率是99%),這兩種值的敏感性不同,造成的結果也不同。

有些情況下l-diversity 是沒有意義的:比如說艾滋病數據的例子中僅含有兩種不同的值,保證2-diversity 也是沒有意義的。

l-diversity 很難達成:例如,我們想在10000 條數據中保證2-diversity,那麼可能最多需要10000* 0.01 = 100 個相同的類型。這時可能通過之前介紹的k-anonymity的方法很難達到。

偏斜性攻擊(Skewness Attack)假如我們要保證在同一類型的數據中出現「艾滋病陽性」和出現「艾滋病陰性」的概率是相同的,我們雖然保證了diversity,但是我們泄露隱私的可能性會變大。因為l-diversity 並沒有考慮敏感屬性的總體的分佈。

l-diversity 沒有考慮敏感屬性的語義,比如說下面的例子,我們通過李雷的資訊從公開數據中關聯到了兩條資訊,通過這兩條資訊我們能得出兩個結論。第一,李雷的工資相對較低;第二,李雷喜歡買電子電器相關的產品。

大數據時代下的隱私保護

t-closeness

上面最後一個問題就引出了t-closeness 的概念,t-closeness 是為了保證在相同的quasi-identifier類型組中,敏感資訊的分佈情況與整個數據的敏感資訊分佈情況接近(close),不超過閾值t

如果剛才的那個數據保證了t-closeness 屬性,那麼通過李雷的資訊查詢出來的結果中,工資的分佈就和整體的分佈類似,進而很難推斷出李雷工資的高低。

最後,如果保證了k-anonymityl-diversity t-closeness,隱私就不會泄露了么?答案並不是這樣,我們看下面的例子:

大數據時代下的隱私保護

在這個例子中,我們保證了2- anonymity , 2-diversity , t-closeness(分佈近似),工資和購買偏好是敏感屬性。攻擊者通過李雷的個人資訊找到了四條數據,同時知道李雷有很多書,這樣就能很容易在四條數據中找到李雷的那一條,從而造成隱私泄露。可能有些讀者會有疑問,通過背景知識攻擊k-anonymity 的前提是不是假設了解 quasi-identifier ?並不是這樣,針對敏感屬性的背景攻擊對k-anonymity 也適用,所以無論經過哪些屬性保證,隱私泄露還是很難避免。

差分隱私(differential privacy

除了之前我們介紹的針對k-anonymity, l-diversity,t-closeness 三種隱私保護方法的攻擊之外,還有一種叫做差分攻擊( differential attack )。舉個例子,購物公司發布了購物偏好的數據,說我們有100 個人的購物偏好數據,其中有10 個人偏愛購買汽車用品,其他90 個偏愛購買電子產品。如果攻擊者知道其中99 個人是偏愛汽車用品還是電子產品,就可以知道第100 個人的購物偏好。這樣通過比較公開數據和既有的知識推測出個人隱私,就叫做差分攻擊。

2009 年,微軟研究院的Cynthia Dwork 提出差分隱私的概念,差分隱私就是為了防止差分攻擊,也就是說儘管攻擊者知道發布的100 個人的個人以資訊和其中99 個人的資訊,他也沒辦法通過比對這兩個資訊獲得第100 個人的資訊

簡單來說,差分隱私就是用一種方法使得查詢100 個資訊和查詢其中99 個的資訊得到的結果是相對一致的,那麼攻擊者就無法通過比較(差分)數據的不同找出第100 個人的資訊。這種方法就是加入隨機性,如果查詢100 個記錄和99 個記錄,輸出同樣的值的概率是一樣的,攻擊者就無法進行差分攻擊。進一步說,對於差別只有一條記錄的兩個數據集D D’ (neighboring datasets),查詢他們獲得結果相同的概率非常接近。注意,這裡並不能保證概率相同,如果一樣的話,數據就需要完全的隨機化,那樣公開數據也就沒有意義。所以,我們需要儘可能接近,保證在隱私和可用性之間找到一個平衡。

ε-差分隱私(ε-differential privacyε-DP) 可以用下面的定義來表示:

大數據時代下的隱私保護

其中 M 是在D 上做任意查詢操作,對查詢後的結果加入一定的隨機性,也就是給數據加噪音,兩個datasets加上同一隨機噪音之後查詢結果為C 的概率比小於一個特定的數。這樣就能保證使用者隱私泄露的概率有一個數學的上界,相比傳統的k-anonymity,差分隱私使隱私保護的模型更加清晰。

我們用一個例子解釋差分隱私的定義:

大數據時代下的隱私保護

上圖中D1 D2 是兩個neighboring datasets,他們只有一條記錄不一致,在攻擊者查詢「20-30歲之間有多少人偏好購買電子產品」的時候,對於這兩個資料庫得到的查詢結果是100 的概率分別是99% 98%,他們的比值小於某個數。如果對於任意的查詢,都能滿足這樣的條件,我們就可以說這種隨機方法是滿足ε-差分隱私的。因為D1 D2 是可以互換的,所以更加嚴格的講,他們的比值也要大於

無論查詢是什麼,兩個相鄰的資料庫返回的結果總是近似的。

要達到數據的差分隱私有四種方法:

1.輸出結果變換

2.輸入查詢變換

3.中間值變換

4.抽樣和聚合數據

本文接下來主要介紹輸出結果變換的方法,這種方法主要針對查詢結果是數值或者數值向量的情況,通過加入雜訊使輸出結果達到ε-DP

輸出結果變換:加入雜訊

在差分隱私中,防止隱私泄露的重要因素是在查詢結果中加噪音,對於數值的查詢結果,一種常見的方法就是對結果進行數值變換。要解釋如何加入噪音,我們先看一下下面的這個例子:

大數據時代下的隱私保護

假如某公司公開了數據,並且對外提供了查詢數據的介面f(x),針對不同的查詢x,伺服器都會輸出一個查詢結果f(x) + 雜訊,加入雜訊就是為了保證ε-差分隱私。

那麼如何選擇雜訊呢?

差分隱私方法中,作者巧妙的利用了拉普拉斯分佈的特性,找到了合適的雜訊方法。針對數值或向量的查詢輸出,M(x) = f(x) + 雜訊。我們能得出以下結論:

其中Lap 是拉普拉斯分佈,GS 表示global sensitivity

我們有了這個結論,想要對某個查詢介面f(x) 保證ε-DP 的話,只需要在查詢結果上加入Lap(GS/e) 的雜訊就可以了。

拉普拉斯分佈和其概率密度函數如下:

大數據時代下的隱私保護

(ε,δ)-differential privacy, (ε, δ)-DP

ε-DP 是一種嚴格的隱私保護保證,當在資料庫中添加和刪除一條數據時候,保證所有查詢的輸出都類似。但是(ε, δ)-DP ε-DP 的保證中允許了一定概率的錯誤發生,比如說,使用者在(ε, δ)-DP 的保護下會有δ 概率的隱私泄露。

大數據時代下的隱私保護

基於這些的概念,差分隱私在機器學習演算法中也能夠使用,常見的演算法,比如說PCAlogistic regressionSVM都有對應的差分隱私化演算法。

差分隱私在數據的實用性和隱私性之間達到了平衡,使用者可以通過設定自己的「隱私預算」(privacy budget)來調整數據的實用性和隱私性。但是差分隱私也不是萬能的,其中加入雜訊的很多演算法需要在大量的數據集上才實用。除此之外,什麼才是「隱私預算」的合理設定也是一個問題。這些都是差分隱私面臨的問題和挑戰。並且由於差分隱私對於「背景知識」的要求過於強,所以需要在結果中加入大量隨機化,導致數據的可用性(utility)急劇下降。但是差分隱私作為一個非常優雅的數學工具,是隱私保護的研究在未來的一個發展方向。差分隱私用嚴格的數學證明告訴人們一個匿名化的公開數據究竟能保護使用者多少的隱私。

k-匿名化與 ε-差分隱私的關係

我們前面分別單獨介紹了k-匿名化和 ε-差分隱私,k-匿名化相對比較容易理解和實踐,差分隱私更像是從理論上證明了隱私保護的邊界。雖然方法的分析角度完全不同,但是它們之間卻有著緊密的聯繫。普渡大學的Ninghui Li教授Provably PrivateData Anonymization: Or, k-Anonymity Meets Differential Privacy 文章中詳細分析了k-匿名化和ε-差分隱私之間的關係。文章證明了在使用k-匿名化「得當」的情況下,可以滿足一定條件的(ε, δ)-differentialprivacy。同時也提出了一種k-anonymity 的變形:β-Sampling+ Data-independent _Generalization + k-Suppression (k, β)-SDGS ,通過變形後的 k-anonymity 就可以使之滿足差分隱私。通過使用差分隱私這種工具,我們就能精確的衡量前人提出的 k-anonymity理論研究上具有重要意義。

實際案例

在實際應用中使用差分隱私時需要考慮的問題還有很多,我們在介紹差分隱私的時候假設所有的查詢操作都由可信的資料庫處理,資料庫里存儲著使用者的原始數據。那麼如果資料庫被攻擊了,包含使用者隱私的原始數據就泄露了。

如果不收集使用者的原始數據,在客戶端上先做差分隱私,再上傳給伺服器,這個問題就解決了。最近Google率先使用RAPPOR系統在Chrome 瀏覽器上通過這種方法收集使用者的使用情況數據。RAPPOR 基於「隨機應答」(randomized response)的方法保護使用者的原始數據不被泄露,隨機應答的流程如下:

1.當使用者需要上報個人數據的時候,首先「拋硬幣」決定是否上報真實數據。如果是正面,則上報真實數據。如果不是,就上報一個隨機的數據,再「拋一次硬幣」決定隨機數據的內容。

2.伺服器收到所有的數據後,因為知道「拋硬幣」是正面的概率,伺服器就能夠判斷返回的數據是正確的概率。

這種「隨機應答」的方法在理論上也被證明是服從ε-差分隱私的。對於使用者來說,隱私數據在上報給伺服器之前就已經加了雜訊,從而具有一定保證。對於公司來說,也能收集到有效的數據。

RAPPOR 使用「隨機應答」的方法克服了之前只能回答簡單查詢語句的限制,現在可以上報包含字元串這類更加複雜的回答。RAPPOR 在上報字元串資訊的時候首先使用「布隆過濾器」(bloom filter)演算法把字元串哈希到一個數組中,然後再加入雜訊傳給伺服器。布隆過濾器不需要存儲元素本身,並可以用於檢索一個元素是否在一個集合中。通過使用這種方法,就可以對字元串數據添加噪音,保護使用者的隱私。

蘋果在2016 年的世界開發者大會(WWDC)上也宣布使用差分隱私的方法收集使用者數據。雖然蘋果沒有透露具體的細節,我們從官方的描述中也可以推測出蘋果也使用了在客戶端上做匿名化再傳輸到伺服器的方法。

Differentialprivacy is a research topic in the areas of statistics and data analytics thatuses hashing, subsampling and noiseinjectionto enable…crowdsourced learning while keeping the data ofindividual users completely private. Apple has been doing some super-importantwork in this area to enable differential privacy to be deployed at scale.

我們剛才介紹的Google Apple 的模型都是先在本地做差分隱私,然後再上報給伺服器,我們把這種方法叫做本地模式(local mode)。這種差分隱私的做法在上報數據可以相互關聯的情況下還是存在隱私泄漏。Google的RAPPOR雖然解決了對同一個數據的多次上報的隱私泄露問題,但並沒有解決多個相關數據上報後產生的隱私泄露問題。對於這一問題,Apple也沒有給出詳細的解釋。

除了Google 和蘋果在內部產品中使用差分隱私方法,哈佛大學公開了一個名為PSI (Ψ) 的項目,提供了一個便捷的差分隱私工具。使用者通過上傳數據,調整差分隱私的參數,就可以獲得滿足差分隱私的數據集。

總結

本文介紹了學術界和工業界對於使用者隱私保護的努力成果。我們首先介紹了k-anonymity,即通過變換隱私數據,保證相同特性的使用者在資料庫出現的次數至少是k 次。然後,為了防止攻擊者通過隱私數據的背景知識推測使用者身份,提出使用l-diversity,保證相同特徵的使用者中,隱私數據相同的個數大於l。除此之外,我們也討論了t-closeness。最後我們詳細介紹了差分隱私的概念,以及實際應用中應如何使用差分隱私。

從最開始的k-anonymity, l-diversity , t-closeness 到現在的ε-差分隱私,都是為了既保證使用者的個人隱私,也能對實際應用和研究提供有價值的數據。在大數據的時代中,希望各公司在利用數據提供更好的服務的同時,能保護好使用者的個人隱私。這是法律的要求,也是安全行業的追求。我們相信隱私保護技術會越來越受到重視,並從學術理論迅速投入工業界實戰應用。

參考文章

https://www.cis.upenn.edu/~aaroth/Papers/privacybook.pdf

https://www.cs.cmu.edu/~yuxiangw/docs/Differential%20Privacy.pdf

https://blog.cryptographyengineering.com/2016/06/15/what-is-differential-privacy/

https://www.chromium.org/developers/design-documents/rappor

http://static.googleusercontent.com/media/research.google.com/en/us/pubs/archive/42852.pdf

Provably Private Data Anonymization: Or,k-Anonymity Meets Differential Privacy