轉(zhuǎn)自：http://www.freebuf.com/articles/database/146652.html

本文介紹了學(xué)術(shù)界和工業(yè)界對(duì)于用戶(hù)隱私保護(hù)的努力成果，其中主要講到了k-anonymity（k-匿名化）,l-diversity（l-多樣化）,t-closeness 和 ε-differential privacy（差分隱私），并對(duì)它們的優(yōu)缺點(diǎn)進(jìn)行了分析。

數(shù)據(jù)?v.s.?隱私

在大數(shù)據(jù)的時(shí)代，數(shù)據(jù)成為了科學(xué)研究的基石。我們?cè)谙硎苤扑]算法、語(yǔ)音識(shí)別、圖像識(shí)別、無(wú)人車(chē)駕駛等智能的技術(shù)帶來(lái)的便利的同時(shí)，數(shù)據(jù)在背后擔(dān)任著驅(qū)動(dòng)算法不斷優(yōu)化迭代的角色。在科學(xué)研究、產(chǎn)品開(kāi)發(fā)、數(shù)據(jù)公開(kāi)的過(guò)程中，算法需要收集、使用用戶(hù)數(shù)據(jù)，在這過(guò)程中數(shù)據(jù)就不可避免的暴露在外。歷史上就有很多公開(kāi)的數(shù)據(jù)暴露了用戶(hù)隱私的案例。

美國(guó)在線（AOL）是一家美國(guó)互聯(lián)網(wǎng)服務(wù)公司，也是美國(guó)最大的互聯(lián)網(wǎng)提供商之一。在 2006 ?年8月，為了學(xué)術(shù)研究，AOL 公開(kāi)了匿名的搜索記錄，其中包括 ?65 萬(wàn)個(gè)用戶(hù)的數(shù)據(jù)，總共 20M 條查詢(xún)記錄。在這些數(shù)據(jù)中，用戶(hù)的姓名被替換成了一個(gè)個(gè)匿名的 ?ID，但是紐約時(shí)報(bào)通過(guò)這些搜索紀(jì)錄，找到了 ID 匿名為 4417749的用戶(hù)在真實(shí)世界中對(duì)應(yīng)的人。ID 4417749 的搜索記錄里有關(guān)于“60歲的老年人”的問(wèn)題、“ Lilburn地方的風(fēng)景”、還有“Arnold” 的搜索字樣。通過(guò)上面幾條數(shù)據(jù)，紐約時(shí)報(bào)發(fā)現(xiàn) ?Lilburn 只有14個(gè)人姓Arnold，最后經(jīng)過(guò)直接聯(lián)系這 14個(gè)人確認(rèn) ID 4417749 是一位62歲名字叫 ?Thelma Arnold的老奶奶。最后 AOL 緊急撤下數(shù)據(jù)，發(fā)表聲明致歉，但是已經(jīng)太晚了。因?yàn)殡[私泄露事件，AOL遭到了起訴，最終賠償受影響用戶(hù)總額高達(dá)五百萬(wàn)美元。

同樣是 2006年，美國(guó)最大的影視公司之一 Netflix，舉辦了一個(gè)預(yù)測(cè)算法的比賽（ Netflix Prize），比賽要求在公開(kāi)數(shù)據(jù)上推測(cè)用戶(hù)的電影評(píng)分 。Netflix ?把數(shù)據(jù)中唯一識(shí)別用戶(hù)的信息抹去，認(rèn)為這樣就能保證用戶(hù)的隱私。但是在 2007 年來(lái)自The University of Texas at Austin ?的兩位研究人員表示通過(guò)關(guān)聯(lián) Netflix 公開(kāi)的數(shù)據(jù)和 IMDb（互聯(lián)網(wǎng)電影數(shù)據(jù)庫(kù)）網(wǎng)站上公開(kāi)的紀(jì)錄就能夠識(shí)別出匿名后用戶(hù)的身份。三年后，在2010年，Netflix 最后因?yàn)殡[私原因宣布停止這項(xiàng)比賽，并因此受到高額罰款，賠償金額總計(jì)九百萬(wàn)美元。

近幾年各大公司均持續(xù)關(guān)注用戶(hù)的隱私安全。例如蘋(píng)果 在2016 年 ?6 月份的WWDC 大會(huì)上就提出了一項(xiàng)名為 Differential Privacy 的差分隱私技術(shù)。蘋(píng)果聲稱(chēng)他能通過(guò)數(shù)據(jù)計(jì)算出用戶(hù)群體的行為模式，但是卻無(wú)法獲得每個(gè)用戶(hù)個(gè)體的數(shù)據(jù)。那么差分隱私技術(shù)又是怎么做的呢？

在大數(shù)據(jù)時(shí)代，如何才能保證我們的隱私呢？要回答這個(gè)問(wèn)題，我們首先要知道什么是隱私。

什么是隱私？

我們經(jīng)常談?wù)摰诫[私泄漏、隱私保護(hù)，那么什么是隱私呢？舉個(gè)例子，居住在海淀區(qū)五道口的小明經(jīng)常在網(wǎng)上購(gòu)買(mǎi)電子產(chǎn)品，那小明的姓名、購(gòu)買(mǎi)偏好和居住地址 算不算是隱私呢？如果某購(gòu)物網(wǎng)站統(tǒng)計(jì)了用戶(hù)的購(gòu)物偏好并公開(kāi)部分?jǐn)?shù)據(jù)，公開(kāi)的數(shù)據(jù)中顯示北京海淀區(qū)五道口的用戶(hù)更愛(ài)買(mǎi)電子產(chǎn)品，那么小明的隱私是否被泄漏了呢？要弄清楚隱私保護(hù)，我們先要討論一下究竟什么是隱私。

對(duì)于隱私這個(gè)詞，科學(xué)研究上普遍接受的定義是“單個(gè)用戶(hù)的某一些屬性”，只要符合這一定義都可以被看做是隱私。我們?cè)谔帷半[私”的時(shí)候，更加強(qiáng)調(diào)的是“單個(gè)用戶(hù)”。那么，一群用戶(hù)的某一些屬性，可以認(rèn)為不是隱私。我們拿剛才的例子來(lái)看，針對(duì)小明這個(gè)單個(gè)用戶(hù)，“購(gòu)買(mǎi)偏好”和“居住地址”就是隱私。如果公開(kāi)的數(shù)據(jù)說(shuō)住在五道口的小明愛(ài)買(mǎi)電子產(chǎn)品，那么這顯然就是隱私泄漏了。但是如果數(shù)據(jù)中只包含一個(gè)區(qū)域的人的購(gòu)買(mǎi)偏好，就沒(méi)有泄露用戶(hù)隱私。如果進(jìn)一步講，大家都知道小明住在海淀區(qū)五道口，那么是不是小明就愛(ài)買(mǎi)點(diǎn)此產(chǎn)品了呢？這種情況算不算事隱私泄漏呢？答案是不算，因?yàn)榇蠹抑皇峭ㄟ^(guò)這個(gè)趨勢(shì)推測(cè)，數(shù)據(jù)并不顯示小明一定愛(ài)買(mǎi)電子產(chǎn)品。

所以，從隱私保護(hù)的角度來(lái)說(shuō)，隱私是針對(duì)單個(gè)用戶(hù)的概念，公開(kāi)群體用戶(hù)的信息不算是隱私泄漏，但是如果能從數(shù)據(jù)中能準(zhǔn)確推測(cè)出個(gè)體的信息，那么就算是隱私泄漏。

隱私保護(hù)的方法

從信息時(shí)代開(kāi)始，關(guān)于隱私保護(hù)的研究就開(kāi)始了。隨著數(shù)據(jù)不斷地增長(zhǎng)，人們對(duì)隱私越來(lái)越重視。我們?cè)谟懻撾[私保護(hù)的時(shí)候包括兩種情況。

第一種是公司為了學(xué)術(shù)研究和數(shù)據(jù)交流開(kāi)放用戶(hù)數(shù)據(jù)，學(xué)術(shù)機(jī)構(gòu)或者個(gè)人可以向數(shù)據(jù)庫(kù)發(fā)起查詢(xún)請(qǐng)求，公司返回對(duì)應(yīng)的數(shù)據(jù)時(shí)需要保證用戶(hù)的隱私。

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

下面我們一一解讀這四種隱私保護(hù)的方法：

k-anonymity（k-匿名化）

k-anonymity?是在?1998?年由?Latanya Sweeney?和?Pierangela Samarati?提出的一種數(shù)據(jù)匿名化方法。

我們先看一下下面的這個(gè)表格：

我們把要表格中的公開(kāi)屬性分為以下三類(lèi)：

-? ??Key attributes:?一般是個(gè)體的唯一標(biāo)示，比如說(shuō)姓名、地址、電話(huà)等等，這些內(nèi)容需要在公開(kāi)數(shù)據(jù)的時(shí)候刪掉。

-? ??Quasi-identifier:?類(lèi)似郵編、年齡、生日、性別等不是唯一的，但是能幫助研究人員關(guān)聯(lián)相關(guān)數(shù)據(jù)的標(biāo)示。

-? ??Sensitive attributes:?敏感數(shù)據(jù)，比如說(shuō)購(gòu)買(mǎi)偏好、薪水等等，這些數(shù)據(jù)是研究人員最關(guān)心的，所以一般都直接公開(kāi)。

簡(jiǎn)單來(lái)說(shuō)，k-anonymity?的目的是保證公開(kāi)的數(shù)據(jù)中包含的個(gè)人信息至少?k-1?條不能通過(guò)其他個(gè)人信息確定出來(lái)。也就是公開(kāi)數(shù)據(jù)中的任意?quasi-identifier信息，相同的組合都需要出現(xiàn)至少?k?次。

舉個(gè)例子，假設(shè)一個(gè)公開(kāi)的數(shù)據(jù)進(jìn)行了?2-anonymity?保護(hù)。如果攻擊者想確認(rèn)一個(gè)人（小明）的敏感信息（購(gòu)買(mǎi)偏好），通過(guò)查詢(xún)他的年齡、郵編和性別，攻擊者會(huì)發(fā)現(xiàn)數(shù)據(jù)里至少有兩個(gè)人是有相同的年齡、郵編和性別。這樣攻擊者就沒(méi)辦法區(qū)分這兩條數(shù)據(jù)到底哪個(gè)是小明了，從而也就保證了小明的隱私不會(huì)被泄露。

下面這個(gè)表就是?2-anonymization?過(guò)的信息：

k-anonymity的方法主要有兩種，一種是刪除對(duì)應(yīng)的數(shù)據(jù)列，用星號(hào)（*）代替。另外一種方法是用概括的方法使之無(wú)法區(qū)分，比如把年齡這個(gè)數(shù)字概括成一個(gè)年齡段。對(duì)于郵編這樣的數(shù)據(jù)，如果刪除所有郵編，研究人員會(huì)失去很多有意義的信息，所以可以選擇刪除最后一位數(shù)字。

從這個(gè)表中，即使我們知道小明是男性、24歲、郵編是100083，卻仍然無(wú)法知道小明的購(gòu)買(mǎi)偏好。而研究人員依然可以根據(jù)這些數(shù)據(jù)統(tǒng)計(jì)出一些有意義的結(jié)果，這樣既兼顧了個(gè)人的隱私，又能為研究提供有效的數(shù)據(jù)。

k-anonymity能保證以下三點(diǎn)：

1.????攻擊者無(wú)法知道某個(gè)人是否在公開(kāi)的數(shù)據(jù)中

2.????給定一個(gè)人，攻擊者無(wú)法確認(rèn)他是否有某項(xiàng)敏感屬性

3.????攻擊者無(wú)法確認(rèn)某條數(shù)據(jù)對(duì)應(yīng)的是哪個(gè)人（這條假設(shè)攻擊者除了quasi-identifier信息之外對(duì)其他數(shù)據(jù)一無(wú)所知，舉個(gè)例子，如果所有用戶(hù)的偏好都是購(gòu)買(mǎi)電子產(chǎn)品，那么k-anonymity也無(wú)法保證隱私?jīng)]有泄露）

攻擊方法

未排序匹配攻擊?(unsorted matching attack)：當(dāng)公開(kāi)的數(shù)據(jù)記錄和原始記錄的順序一樣的時(shí)候，攻擊者可以猜出匿名化的記錄是屬于誰(shuí)。例如如果攻擊者知道在數(shù)據(jù)中小明是排在小白前面，那么他就可以確認(rèn)，小明的購(gòu)買(mǎi)偏好是電子產(chǎn)品，小白是家用電器。解決方法也很簡(jiǎn)單，在公開(kāi)數(shù)據(jù)之前先打亂原始數(shù)據(jù)的順序就可以避免這類(lèi)的攻擊。

補(bǔ)充數(shù)據(jù)攻擊?(complementary release attack)：假如公開(kāi)的數(shù)據(jù)有多種類(lèi)型，如果它們的?k-anonymity?方法不同，那么攻擊者可以通過(guò)關(guān)聯(lián)多種數(shù)據(jù)推測(cè)用戶(hù)信息。

除此之外，如果敏感屬性在同一類(lèi)?quasi-identifiers?中缺乏多樣性，或者攻擊者有其它的背景知識(shí)，k-anonymity?也無(wú)法避免隱私泄露。

我們知道李雷的信息，表中有兩條對(duì)應(yīng)的數(shù)據(jù)，但是他們的購(gòu)買(mǎi)偏好都是電子產(chǎn)品。因?yàn)檫@個(gè)敏感屬性缺乏多樣性，所以盡管是?2-anonimity?匿名化的數(shù)據(jù)，我們依然能夠獲得李雷的敏感信息。

如果我們知道小紫的信息，并且知道她不喜歡購(gòu)買(mǎi)護(hù)膚品，那么從表中，我們?nèi)钥梢源_認(rèn)小紫的購(gòu)買(mǎi)偏好是廚具。

l-diversity（l-多樣化）

通過(guò)上面的例子，我們引出了多樣化的概念。簡(jiǎn)單來(lái)說(shuō)，在公開(kāi)的數(shù)據(jù)中，對(duì)于那些quasi-identifier?相同的數(shù)據(jù)中，敏感屬性必須具有多樣性，這樣才能保證用戶(hù)的隱私不能通過(guò)背景知識(shí)等方法推測(cè)出來(lái)。

l-diversity?保證了相同類(lèi)型數(shù)據(jù)中至少有?l?種內(nèi)容不同的敏感屬性。

例如在上圖的例子中，有?10?條相同的類(lèi)型的數(shù)據(jù)，其中?8?條的購(gòu)買(mǎi)偏好是電子產(chǎn)品，其他兩條分別是圖書(shū)和家用電器。那么在這個(gè)例子中，公開(kāi)的數(shù)據(jù)就滿(mǎn)足3-diversity?的屬性。

除了以上介紹的簡(jiǎn)單?l-diversity?的定義，還有其他版本的?l-diversity，引入了其他統(tǒng)計(jì)方法。比如說(shuō)：

??????????基于概率的l-diversity (probabilistic l-diversity):?在一個(gè)類(lèi)型中出現(xiàn)頻率最高的值的概率不大于1/l。

??????????基于墑的l-diversity (entropy l-diversity):?在一個(gè)類(lèi)型中敏感數(shù)據(jù)分布的墑至少是?log(l)。

??????????遞歸?(c,l)-diversity (recursive (c, l)-diversity):?簡(jiǎn)單來(lái)說(shuō)就是保證最經(jīng)常出現(xiàn)的值的出現(xiàn)頻率不要太高。

l-diversity也有其局限性：

?敏感屬性的性質(zhì)決定即使保證了一定概率的?diversity?也很容易泄露隱私。例如，醫(yī)院公開(kāi)的艾滋病數(shù)據(jù)中，敏感屬性是“艾滋病陽(yáng)性”（出現(xiàn)概率是?1%）和“艾滋病陰性”（出現(xiàn)概率是?99%），這兩種值的敏感性不同，造成的結(jié)果也不同。

?有些情況下?l-diversity是沒(méi)有意義的：比如說(shuō)艾滋病數(shù)據(jù)的例子中僅含有兩種不同的值，保證2-diversity?也是沒(méi)有意義的。

?l-diversity很難達(dá)成：例如，我們想在?10000?條數(shù)據(jù)中保證?2-diversity，那么可能最多需要10000* 0.01 = 100?個(gè)相同的類(lèi)型。這時(shí)可能通過(guò)之前介紹的?k-anonymity的方法很難達(dá)到。

?偏斜性攻擊?(Skewness Attack)：假如我們要保證在同一類(lèi)型的數(shù)據(jù)中出現(xiàn)“艾滋病陽(yáng)性”和出現(xiàn)“艾滋病陰性”的概率是相同的，我們雖然保證了?diversity，但是我們泄露隱私的可能性會(huì)變大。因?yàn)閘-diversity?并沒(méi)有考慮敏感屬性的總體的分布。

?l-diversity沒(méi)有考慮敏感屬性的語(yǔ)義，比如說(shuō)下面的例子，我們通過(guò)李雷的信息從公開(kāi)數(shù)據(jù)中關(guān)聯(lián)到了兩條信息，通過(guò)這兩條信息我們能得出兩個(gè)結(jié)論。第一，李雷的工資相對(duì)較低；第二，李雷喜歡買(mǎi)電子電器相關(guān)的產(chǎn)品。

t-closeness

上面最后一個(gè)問(wèn)題就引出了?t-closeness?的概念，t-closeness?是為了保證在相同的quasi-identifier類(lèi)型組中，敏感信息的分布情況與整個(gè)數(shù)據(jù)的敏感信息分布情況接近(close)，不超過(guò)閾值?t。

如果剛才的那個(gè)數(shù)據(jù)保證了?t-closeness?屬性，那么通過(guò)李雷的信息查詢(xún)出來(lái)的結(jié)果中，工資的分布就和整體的分布類(lèi)似，進(jìn)而很難推斷出李雷工資的高低。

最后，如果保證了?k-anonymity，l-diversity?和?t-closeness，隱私就不會(huì)泄露了么？答案并不是這樣，我們看下面的例子：

在這個(gè)例子中，我們保證了?2- anonymity , 2-diversity , t-closeness（分布近似），工資和購(gòu)買(mǎi)偏好是敏感屬性。攻擊者通過(guò)李雷的個(gè)人信息找到了四條數(shù)據(jù)，同時(shí)知道李雷有很多書(shū)，這樣就能很容易在四條數(shù)據(jù)中找到李雷的那一條，從而造成隱私泄露。可能有些讀者會(huì)有疑問(wèn)，通過(guò)背景知識(shí)攻擊?k-anonymity 的前提是不是假設(shè)了解?quasi-identifier?？并不是這樣，針對(duì)敏感屬性的背景攻擊對(duì)?k-anonymity 也適用，所以無(wú)論經(jīng)過(guò)哪些屬性保證，隱私泄露還是很難避免。

差分隱私（differential privacy）

除了之前我們介紹的針對(duì)?k-anonymity, l-diversity,t-closeness?三種隱私保護(hù)方法的攻擊之外，還有一種叫做差分攻擊?( differential attack )。舉個(gè)例子，購(gòu)物公司發(fā)布了購(gòu)物偏好的數(shù)據(jù)，說(shuō)我們有?100?個(gè)人的購(gòu)物偏好數(shù)據(jù)，其中有?10?個(gè)人偏愛(ài)購(gòu)買(mǎi)汽車(chē)用品，其他?90?個(gè)偏愛(ài)購(gòu)買(mǎi)電子產(chǎn)品。如果攻擊者知道其中?99?個(gè)人是偏愛(ài)汽車(chē)用品還是電子產(chǎn)品，就可以知道第?100?個(gè)人的購(gòu)物偏好。這樣通過(guò)比較公開(kāi)數(shù)據(jù)和既有的知識(shí)推測(cè)出個(gè)人隱私，就叫做差分攻擊。

在?2009?年，微軟研究院的Cynthia Dwork?提出差分隱私的概念，差分隱私就是為了防止差分攻擊，也就是說(shuō)盡管攻擊者知道發(fā)布的100個(gè)人的個(gè)人以信息和其中?99個(gè)人的信息，他也沒(méi)辦法通過(guò)比對(duì)這兩個(gè)信息獲得第?100個(gè)人的信息。

簡(jiǎn)單來(lái)說(shuō)，差分隱私就是用一種方法使得查詢(xún)?100?個(gè)信息和查詢(xún)其中?99?個(gè)的信息得到的結(jié)果是相對(duì)一致的，那么攻擊者就無(wú)法通過(guò)比較（差分）數(shù)據(jù)的不同找出第100?個(gè)人的信息。這種方法就是加入隨機(jī)性，如果查詢(xún)?100?個(gè)記錄和?99?個(gè)記錄，輸出同樣的值的概率是一樣的，攻擊者就無(wú)法進(jìn)行差分攻擊。進(jìn)一步說(shuō)，對(duì)于差別只有一條記錄的兩個(gè)數(shù)據(jù)集?D?和?D’ (neighboring datasets)，查詢(xún)他們獲得結(jié)果相同的概率非常接近。注意，這里并不能保證概率相同，如果一樣的話(huà)，數(shù)據(jù)就需要完全的隨機(jī)化，那樣公開(kāi)數(shù)據(jù)也就沒(méi)有意義。所以，我們需要盡可能接近，保證在隱私和可用性之間找到一個(gè)平衡。

ε-差分隱私?(ε-differential privacy，?ε-DP)?可以用下面的定義來(lái)表示：

其中?M?是在?D?上做任意查詢(xún)操作，對(duì)查詢(xún)后的結(jié)果加入一定的隨機(jī)性，也就是給數(shù)據(jù)加噪音，兩個(gè)datasets加上同一隨機(jī)噪音之后查詢(xún)結(jié)果為?C?的概率比小于一個(gè)特定的數(shù)?。這樣就能保證用戶(hù)隱私泄露的概率有一個(gè)數(shù)學(xué)的上界，相比傳統(tǒng)的k-anonymity，差分隱私使隱私保護(hù)的模型更加清晰。

我們用一個(gè)例子解釋差分隱私的定義：

上圖中?D1?和D2是兩個(gè)neighboring datasets，他們只有一條記錄不一致，在攻擊者查詢(xún)“20-30歲之間有多少人偏好購(gòu)買(mǎi)電子產(chǎn)品”的時(shí)候，對(duì)于這兩個(gè)數(shù)據(jù)庫(kù)得到的查詢(xún)結(jié)果是?100?的概率分別是?99%和?98%，他們的比值小于某個(gè)數(shù)。如果對(duì)于任意的查詢(xún)，都能滿(mǎn)足這樣的條件，我們就可以說(shuō)這種隨機(jī)方法是滿(mǎn)足ε-差分隱私的。因?yàn)?D1?和?D2是可以互換的，所以更加嚴(yán)格的講，他們的比值也要大于。

無(wú)論查詢(xún)是什么，兩個(gè)相鄰的數(shù)據(jù)庫(kù)返回的結(jié)果總是近似的。

要達(dá)到數(shù)據(jù)的差分隱私有四種方法：

1.????輸出結(jié)果變換

2.????輸入查詢(xún)變換

3.????中間值變換

4.????抽樣和聚合數(shù)據(jù)

本文接下來(lái)主要介紹輸出結(jié)果變換的方法，這種方法主要針對(duì)查詢(xún)結(jié)果是數(shù)值或者數(shù)值向量的情況，通過(guò)加入噪聲使輸出結(jié)果達(dá)到?ε-DP。

輸出結(jié)果變換：加入噪聲

在差分隱私中，防止隱私泄露的重要因素是在查詢(xún)結(jié)果中加噪音，對(duì)于數(shù)值的查詢(xún)結(jié)果，一種常見(jiàn)的方法就是對(duì)結(jié)果進(jìn)行數(shù)值變換。要解釋如何加入噪音，我們先看一下下面的這個(gè)例子：

假如某公司公開(kāi)了數(shù)據(jù)，并且對(duì)外提供了查詢(xún)數(shù)據(jù)的接口?f(x)，針對(duì)不同的查詢(xún)?x，服務(wù)器都會(huì)輸出一個(gè)查詢(xún)結(jié)果f(x) +?噪聲，加入噪聲就是為了保證?ε-差分隱私。

那么如何選擇噪聲呢？

差分隱私方法中，作者巧妙的利用了拉普拉斯分布的特性，找到了合適的噪聲方法。針對(duì)數(shù)值或向量的查詢(xún)輸出，M(x) = f(x) +?噪聲。我們能得出以下結(jié)論：

其中?Lap?是拉普拉斯分布，GS?表示?global sensitivity：

詳細(xì)的證明可以參考差分隱私的相關(guān)文章。

我們有了這個(gè)結(jié)論，想要對(duì)某個(gè)查詢(xún)接口?f(x)?保證?ε-DP?的話(huà)，只需要在查詢(xún)結(jié)果上加入?Lap(GS/e)?的噪聲就可以了。

拉普拉斯分布和其概率密度函數(shù)如下：

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

ε-DP?是一種“嚴(yán)格”的隱私保護(hù)保證，當(dāng)在數(shù)據(jù)庫(kù)中添加和刪除一條數(shù)據(jù)時(shí)候，保證所有查詢(xún)的輸出都類(lèi)似。但是(ε, δ)-DP?在?ε-DP?的保證中允許了一定概率的錯(cuò)誤發(fā)生，比如說(shuō)，用戶(hù)在?(ε, δ)-DP?的保護(hù)下會(huì)有?δ?概率的隱私泄露。

基于這些的概念，差分隱私在機(jī)器學(xué)習(xí)算法中也能夠使用，常見(jiàn)的算法，比如說(shuō)?PCA、logistic regression、SVM都有對(duì)應(yīng)的差分隱私化算法。

差分隱私在數(shù)據(jù)的實(shí)用性和隱私性之間達(dá)到了平衡，使用者可以通過(guò)設(shè)定自己的“隱私預(yù)算”（privacy budget）來(lái)調(diào)整數(shù)據(jù)的實(shí)用性和隱私性。但是差分隱私也不是萬(wàn)能的，其中加入噪聲的很多算法需要在大量的數(shù)據(jù)集上才實(shí)用。除此之外，什么才是“隱私預(yù)算”的合理設(shè)定也是一個(gè)問(wèn)題。這些都是差分隱私面臨的問(wèn)題和挑戰(zhàn)。并且由于差分隱私對(duì)于“背景知識(shí)”的要求過(guò)于強(qiáng)，所以需要在結(jié)果中加入大量隨機(jī)化，導(dǎo)致數(shù)據(jù)的可用性（utility）急劇下降。但是差分隱私作為一個(gè)非常優(yōu)雅的數(shù)學(xué)工具，是隱私保護(hù)的研究在未來(lái)的一個(gè)發(fā)展方向。差分隱私用嚴(yán)格的數(shù)學(xué)證明告訴人們一個(gè)匿名化的公開(kāi)數(shù)據(jù)究竟能保護(hù)用戶(hù)多少的隱私。

k-匿名化與 ε-差分隱私的關(guān)系

我們前面分別單獨(dú)介紹了?k-匿名化和?ε-差分隱私，k-匿名化相對(duì)比較容易理解和實(shí)踐，差分隱私更像是從理論上證明了隱私保護(hù)的邊界。

雖然方法的分析角度完全不同，但是它們之間卻有著緊密的聯(lián)系。普渡大學(xué)的Ninghui Li教授在?Provably PrivateData Anonymization: Or, k-Anonymity Meets Differential Privacy?文章中詳細(xì)分析了?k-匿名化和?ε-差分隱私之間的關(guān)系。文章證明了在使用?k-匿名化“得當(dāng)”的情況下，可以滿(mǎn)足一定條件的?(ε, δ)-differentialprivacy。同時(shí)也提出了一種?k-anonymity?的變形：β-Sampling+ Data-independent _Generalization + k-Suppression (k, β)-SDGS，通過(guò)變形后的 k-anonymity 就可以使之滿(mǎn)足差分隱私。通過(guò)使用差分隱私這種工具，我們就能精確的衡量前人提出的 k-anonymity，在理論研究上具有重要意義。

實(shí)際案例

在實(shí)際應(yīng)用中使用差分隱私時(shí)需要考慮的問(wèn)題還有很多，我們?cè)诮榻B差分隱私的時(shí)候假設(shè)所有的查詢(xún)操作都由可信的數(shù)據(jù)庫(kù)處理，數(shù)據(jù)庫(kù)里存儲(chǔ)著用戶(hù)的原始數(shù)據(jù)。那么如果數(shù)據(jù)庫(kù)被攻擊了，包含用戶(hù)隱私的原始數(shù)據(jù)就泄露了。

如果不收集用戶(hù)的原始數(shù)據(jù)，在客戶(hù)端上先做差分隱私，再上傳給服務(wù)器，這個(gè)問(wèn)題就解決了。最近Google率先使用RAPPOR系統(tǒng)在?Chrome?瀏覽器上通過(guò)這種方法收集用戶(hù)的使用情況數(shù)據(jù)。RAPPOR?基于“隨機(jī)應(yīng)答”（randomized response）的方法保護(hù)用戶(hù)的原始數(shù)據(jù)不被泄露，隨機(jī)應(yīng)答的流程如下：

1.?????當(dāng)用戶(hù)需要上報(bào)個(gè)人數(shù)據(jù)的時(shí)候，首先“拋硬幣”決定是否上報(bào)真實(shí)數(shù)據(jù)。如果是正面，則上報(bào)真實(shí)數(shù)據(jù)。如果不是，就上報(bào)一個(gè)隨機(jī)的數(shù)據(jù)，再“拋一次硬幣”決定隨機(jī)數(shù)據(jù)的內(nèi)容。

2.?????服務(wù)器收到所有的數(shù)據(jù)后，因?yàn)橹馈皰佊矌拧笔钦娴母怕?，服?wù)器就能夠判斷返回的數(shù)據(jù)是正確的概率。

這種“隨機(jī)應(yīng)答”的方法在理論上也被證明是服從ε-差分隱私的。對(duì)于用戶(hù)來(lái)說(shuō)，隱私數(shù)據(jù)在上報(bào)給服務(wù)器之前就已經(jīng)加了噪聲，從而具有一定保證。對(duì)于公司來(lái)說(shuō)，也能收集到有效的數(shù)據(jù)。

RAPPOR?使用“隨機(jī)應(yīng)答”的方法克服了之前只能回答簡(jiǎn)單查詢(xún)語(yǔ)句的限制，現(xiàn)在可以上報(bào)包含字符串這類(lèi)更加復(fù)雜的回答。RAPPOR?在上報(bào)字符串信息的時(shí)候首先使用“布隆過(guò)濾器”（bloom filter）算法把字符串哈希到一個(gè)數(shù)組中，然后再加入噪聲傳給服務(wù)器。布隆過(guò)濾器不需要存儲(chǔ)元素本身，并可以用于檢索一個(gè)元素是否在一個(gè)集合中。通過(guò)使用這種方法，就可以對(duì)字符串?dāng)?shù)據(jù)添加噪音，保護(hù)用戶(hù)的隱私。

蘋(píng)果在?2016?年的世界開(kāi)發(fā)者大會(huì)（WWDC）上也宣布使用差分隱私的方法收集用戶(hù)數(shù)據(jù)。雖然蘋(píng)果沒(méi)有透露具體的細(xì)節(jié)，我們從官方的描述中也可以推測(cè)出蘋(píng)果也使用了在客戶(hù)端上做匿名化再傳輸?shù)椒?wù)器的方法。

Differentialprivacy is a research topic in the areas of statistics and data analytics thatuseshashing, 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?的模型都是先在本地做差分隱私，然后再上報(bào)給服務(wù)器，我們把這種方法叫做本地模式（local mode）。這種差分隱私的做法在上報(bào)數(shù)據(jù)可以相互關(guān)聯(lián)的情況下還是存在隱私泄漏。Google的RAPPOR雖然解決了對(duì)同一個(gè)數(shù)據(jù)的多次上報(bào)的隱私泄露問(wèn)題，但并沒(méi)有解決多個(gè)相關(guān)數(shù)據(jù)上報(bào)后產(chǎn)生的隱私泄露問(wèn)題。對(duì)于這一問(wèn)題，Apple也沒(méi)有給出詳細(xì)的解釋。

除了Google?和蘋(píng)果在內(nèi)部產(chǎn)品中使用差分隱私方法，哈佛大學(xué)公開(kāi)了一個(gè)名為PSI (Ψ)?的項(xiàng)目，提供了一個(gè)便捷的差分隱私工具。使用者通過(guò)上傳數(shù)據(jù)，調(diào)整差分隱私的參數(shù)，就可以獲得滿(mǎn)足差分隱私的數(shù)據(jù)集。

總結(jié)

本文介紹了學(xué)術(shù)界和工業(yè)界對(duì)于用戶(hù)隱私保護(hù)的努力成果。我們首先介紹了?k-anonymity，即通過(guò)變換隱私數(shù)據(jù)，保證相同特性的用戶(hù)在數(shù)據(jù)庫(kù)出現(xiàn)的次數(shù)至少是?k?次。然后，為了防止攻擊者通過(guò)隱私數(shù)據(jù)的背景知識(shí)推測(cè)用戶(hù)身份，提出使用?l-diversity，保證相同特征的用戶(hù)中，隱私數(shù)據(jù)相同的個(gè)數(shù)大于?l。除此之外，我們也討論了?t-closeness。最后我們?cè)敿?xì)介紹了差分隱私的概念，以及實(shí)際應(yīng)用中應(yīng)如何使用差分隱私。

從最開(kāi)始的?k-anonymity, l-diversity , t-closeness?到現(xiàn)在的?ε-差分隱私，都是為了既保證用戶(hù)的個(gè)人隱私，也能對(duì)實(shí)際應(yīng)用和研究提供有價(jià)值的數(shù)據(jù)。在大數(shù)據(jù)的時(shí)代中，希望各公司在利用數(shù)據(jù)提供更好的服務(wù)的同時(shí)，能保護(hù)好用戶(hù)的個(gè)人隱私。這是法律的要求，也是安全行業(yè)的追求。我們相信隱私保護(hù)技術(shù)會(huì)越來(lái)越受到重視，并從學(xué)術(shù)理論迅速投入工業(yè)界實(shí)戰(zhàn)應(yīng)用。

參考文章

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