摘要：基本思想上圖給出了差分隱私的一般性方法。定義一給出了差分隱私的數(shù)學(xué)表達(dá)。從定義可以看出差分隱私技術(shù)限制了任意一條記錄對(duì)算法輸出結(jié)果的影響。而基于不同噪音機(jī)制且滿(mǎn)足差分隱私的算法所需噪音大小與全局敏感性密切相關(guān)。

在2016 年6 月份的蘋(píng)果 WWDC 大會(huì)上蘋(píng)果公司負(fù)責(zé)軟件工程的高級(jí)副總裁克雷格?費(fèi)德里希(Craig Federighi)在WWDC上滿(mǎn)臉傲驕地說(shuō)「We believe you should havegreat features and great privacy」，那個(gè)瞬間特別像一個(gè)小孩子，自信滿(mǎn)滿(mǎn)地向世界宣告「我們就是能站著把錢(qián)賺了」。就這樣，差分隱私從研究論文一躍成為科技新聞?lì)^條。其實(shí) Google 也有嘗試過(guò)類(lèi)似的事情，在 GitHub 上開(kāi)源了一個(gè)名為RAPPOR(Randomized Aggregatable Privacy-Preserving Ordinal Response)的項(xiàng)目，從原理上來(lái)說(shuō)，也是向數(shù)據(jù)中注入可控的噪音元素的方式來(lái)保護(hù)用戶(hù)隱私，早在2014 年Google就以這項(xiàng)技術(shù)來(lái)收集用戶(hù)使用Chrome瀏覽器時(shí)的資料。不過(guò)DP主要是由微軟研究院的C. Dwork提出及發(fā)展，微軟也已經(jīng)在這個(gè)領(lǐng)域申請(qǐng)了不少的專(zhuān)利。遺憾的是，一如蘋(píng)果宣稱(chēng)的，蘋(píng)果是唯一一家將Differential Privacy作為標(biāo)準(zhǔn)大規(guī)模部署的公司。

過(guò)去幾十年，互聯(lián)網(wǎng)的發(fā)展徹底改變了我們的生活。網(wǎng)絡(luò)逐漸成為人們生活的中心——網(wǎng)購(gòu)、聊天、看新聞、查股票??，無(wú)不通過(guò)網(wǎng)絡(luò)進(jìn)行。日常生活的網(wǎng)絡(luò)化塑造了一個(gè)網(wǎng)絡(luò)時(shí)代和一大批與我們息息相關(guān)的互聯(lián)網(wǎng)公司。這些公司往往提供優(yōu)質(zhì)而免費(fèi)的服務(wù)，并擁有巨量用戶(hù)。不過(guò)，為了提供更好的服務(wù)，或者出于其他商業(yè)目的，幾乎所有的互聯(lián)網(wǎng)公司都在盡可能地記錄用戶(hù)的行為。這些用戶(hù)數(shù)據(jù)對(duì)互聯(lián)網(wǎng)公司來(lái)說(shuō)是珍貴的資源，因?yàn)樗麄兛梢酝ㄟ^(guò)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘從中獲得大量有用的信息。與此同時(shí)，用戶(hù)數(shù)據(jù)亦是危險(xiǎn)的“潘多拉之盒”：數(shù)據(jù)一旦泄漏，用戶(hù)的隱私將被侵犯，同時(shí)對(duì)公司的信譽(yù)也帶來(lái)莫大的傷害。近年來(lái)，我們已經(jīng)目睹了多起用戶(hù)隱私泄漏事件，幾家大公司深陷其中；而這些事件全都是由于數(shù)據(jù)擁有者分享數(shù)據(jù)不當(dāng)引起的。

20 世紀(jì)最著名的用戶(hù)隱私泄漏事件發(fā)生在美國(guó)馬薩諸塞州。90 年代中葉，該州團(tuán)體保險(xiǎn)委員會(huì)(Group Insurance Commis-sion)決定發(fā)布州政府雇員的“經(jīng)過(guò)匿名化處理的”醫(yī)療數(shù)據(jù)，以助公共醫(yī)學(xué)研究。在數(shù)據(jù)發(fā)布之前，委員會(huì)對(duì)潛在的隱私問(wèn)題已有所認(rèn)識(shí)，因此刪除了數(shù)據(jù)中所有的敏感信息，例如姓名、住址和社會(huì)安全號(hào)碼(social security number)。然而 1997 年，麻省理工學(xué)院博士生拉坦婭?斯威尼(Latanya Sweeney)(現(xiàn)任哈佛大學(xué)教授)成功破解了這份匿名數(shù)據(jù)，并找到了時(shí)任馬薩諸塞州州長(zhǎng)威廉?威爾德(William Weld)的醫(yī)療記錄，還將該記錄直接寄給了州長(zhǎng)本人。
2006 年8月4日，美國(guó)在線公司的研究部門(mén)在互聯(lián)網(wǎng)上發(fā)布了超過(guò)65萬(wàn)用戶(hù)在過(guò)去三個(gè)月的搜索關(guān)鍵字，以供公眾對(duì)搜索技術(shù)進(jìn)行研究。該公司對(duì)發(fā)布的數(shù)據(jù)進(jìn)行了匿名化處理，但僅僅是把用戶(hù)的賬號(hào)用一個(gè)隨機(jī)號(hào)碼代替，并沒(méi)有對(duì)用戶(hù)所提交的搜索關(guān)鍵字進(jìn)行任何處理。隨后，《紐約時(shí)報(bào)》成功將部分?jǐn)?shù)據(jù)去匿名化，并在經(jīng)過(guò)當(dāng)事人同意后，公開(kāi)了其中一位搜索用戶(hù)的真實(shí)身份。這起隱私泄漏事件引起了人們的廣泛關(guān)注，并導(dǎo)致美國(guó)在線公司首席技術(shù)官辭職。隨后，美國(guó)在線公司因?yàn)榇耸录诒奔又莸胤椒ㄔ罕黄鹪V。

網(wǎng)飛公司 (Netflix) 也曾深陷數(shù)據(jù)隱私泄漏的丑聞中。2006 年，網(wǎng)飛公司投資100萬(wàn)美元舉辦了一個(gè)為期三年的推薦系統(tǒng)算法競(jìng)賽，并發(fā)布了一些用戶(hù)的影評(píng)數(shù)據(jù)供參賽者測(cè)試。出于隱私保護(hù)，網(wǎng)飛公司在發(fā)布數(shù)據(jù)前將所有用戶(hù)的個(gè)人信息移除，僅保留了每個(gè)用戶(hù)對(duì)各個(gè)電影的評(píng)分以及評(píng)分的時(shí)間戳。然而，來(lái)自德州大學(xué)奧斯汀分校的兩位研究人員利用網(wǎng)飛用戶(hù)影評(píng)數(shù)據(jù)與公開(kāi)的互聯(lián)網(wǎng)電影數(shù)據(jù)庫(kù)(IMDB)用戶(hù)影評(píng)數(shù)據(jù)之間的相關(guān)性，將網(wǎng)飛公司的一部分匿名用戶(hù)與公開(kāi)的IMDB用戶(hù)進(jìn)行了一一對(duì)應(yīng)，由此獲得了IMDB用戶(hù)在網(wǎng)飛公司網(wǎng)站上的全部電影瀏覽信息（包括涉及敏感題材的電影）。為此，2009年，網(wǎng)飛公司遭到了4 位用戶(hù)的起訴，也不得不取消了原定于2010年舉行的第二屆算法競(jìng)賽。

隱私保護(hù)研究的目標(biāo)在于提出用以修改隱私數(shù)據(jù)的技術(shù)，使得修改后的數(shù)據(jù)可以安全發(fā)布(以供第三方進(jìn)行研究)，而不會(huì)遭受去匿名化等隱私攻擊。同時(shí)，修改后的數(shù)據(jù)要在保護(hù)隱私的前提下最大限度地保留原數(shù)據(jù)的整體信息，否則被發(fā)布的數(shù)據(jù)將毫無(wú)研究?jī)r(jià)值。具體來(lái)說(shuō)，當(dāng)前的研究熱點(diǎn)主要集中在兩個(gè)方面：
(1)隱私保護(hù)技術(shù)能提供何種強(qiáng)度的保護(hù)，或者說(shuō)能夠抵御何種強(qiáng)度的攻擊；
(2)如何在保護(hù)隱私的同時(shí)，最大限度地保留原數(shù)據(jù)中的有用信息。

針對(duì)層出不窮的隱私攻擊方式和現(xiàn)有隱私保護(hù)機(jī)制的缺陷，來(lái)自微軟研究院的德沃柯(Dwork) 等人于2006年提出了差分隱私模型。差分隱私具有兩個(gè)最重要的優(yōu)點(diǎn)：(1)差分隱私嚴(yán)格定義了攻擊者的背景知識(shí)：除了某一條記錄，攻擊者知曉原數(shù)據(jù)中的所有信息——這樣的攻擊者幾乎是最強(qiáng)大的，而差分隱私在這種情況下依然能有效保護(hù)隱私信息；(2)差分隱私擁有嚴(yán)謹(jǐn)?shù)慕y(tǒng)計(jì)學(xué)模型，極大地方便了數(shù)學(xué)工具的使用以及定量分析和證明。正是由于差分隱私的諸多優(yōu)勢(shì)，使其一出現(xiàn)便迅速取代了之前的隱私模型，成為隱私研究的核心，并引起理論計(jì)算機(jī)科學(xué)、數(shù)據(jù)庫(kù)與數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等多個(gè)領(lǐng)域的關(guān)注。

基本思想

上圖給出了差分隱私的一般性方法。當(dāng)用戶(hù)(也可能是潛藏的攻擊者)向數(shù)據(jù)提供者提交一個(gè)查詢(xún)請(qǐng)求時(shí)，如果數(shù)據(jù)提供者直接發(fā)布準(zhǔn)確的查詢(xún)結(jié)果，則可能導(dǎo)致隱私泄漏，因?yàn)橛脩?hù)可能會(huì)通過(guò)查詢(xún)結(jié)果來(lái)反推出隱私信息。為了避免這一問(wèn)題，差分隱私系統(tǒng)要求從數(shù)據(jù)庫(kù)中提煉出一個(gè)中間件，用特別設(shè)計(jì)的隨機(jī)算法對(duì)中間件注入適量的噪音，得到一個(gè)帶噪中間件；再由帶噪中間件推導(dǎo)出一個(gè)帶噪的查詢(xún)結(jié)果，并返回給用戶(hù)。這樣，即使攻擊者能夠從帶噪的結(jié)果反推得到帶噪中間件，他也不可能準(zhǔn)確推斷出無(wú)噪中間件，更不可能對(duì)原數(shù)據(jù)庫(kù)進(jìn)行推理，從而達(dá)到了保護(hù)隱私的目的。

定義及統(tǒng)計(jì)學(xué)模型

差分隱私的定義是建立在對(duì)隨機(jī)算法的約束之上的。約束的根本目的在于限制攻擊者在得到帶噪中間件后，對(duì)原數(shù)據(jù)庫(kù)的推導(dǎo)能力。定義一給出了差分隱私的數(shù)學(xué)表達(dá)。

差分隱私定義

隱私是指?jìng)€(gè)人、組織機(jī)構(gòu)等實(shí)體不愿意被外部知曉的信息。例如，個(gè)人的薪資、醫(yī)療記錄等。雖然出現(xiàn)了多種基于 -匿名和劃分隱私保護(hù)框架的保護(hù)方法，而差分隱私保護(hù)技術(shù)被公認(rèn)為比較嚴(yán)格和強(qiáng)健的保護(hù)模型。該保護(hù)模型的基本思想是對(duì)原始數(shù)據(jù)、對(duì)原始數(shù)據(jù)的轉(zhuǎn)換或者是對(duì)統(tǒng)計(jì)結(jié)果添加噪音來(lái)達(dá)到隱私保護(hù)效果。 該保護(hù)方法可以確保在某一數(shù)據(jù)集中插入或者刪除一條記錄的操作不會(huì)影響任何計(jì)算的輸出結(jié)果。另外，該保護(hù)模型不關(guān)心攻擊者所具有的背景知識(shí)，即使攻擊者已經(jīng)掌握除某一條記錄之外的所有記錄的信息，該記錄的隱私也無(wú)法被披露。差分隱私的形式化定義如下。

定義1:
給定數(shù)據(jù)集和，二者互相之間至多相差一條記錄，即。給定一個(gè)隱私算法，為的取值范圍，若算法在數(shù)據(jù)集和上任意輸出結(jié)果滿(mǎn)足下列不等式，則 滿(mǎn)足-差分隱私。

其中，概率由算法的隨機(jī)性控制，也表示隱私被披露的風(fēng)險(xiǎn)；隱私預(yù)算參數(shù)表示隱私保護(hù)程度， 越小隱私保護(hù)程度越高。從定義1可以看出差分隱私技術(shù)限制了任意一條記錄對(duì)算法輸出結(jié)果的影響。該定義是從理論角度確保算法滿(mǎn)足-差分隱私，而要實(shí)現(xiàn)差分隱私保護(hù)需要噪音機(jī)制的介入。

噪音機(jī)制

噪音機(jī)制是實(shí)現(xiàn)差分隱私保護(hù)的主要技術(shù)，常用的噪音添加機(jī)制分別為拉普拉斯機(jī)制與指數(shù)機(jī)制。而基于不同噪音機(jī)制且滿(mǎn)足差分隱私的算法所需噪音大小與全局敏感性(Global Sensitive)密切相關(guān)。
定義2:
對(duì)于任意一個(gè)函數(shù)，函數(shù)的全局敏感性為。其中，和至多相差一條記錄，表示所映射的實(shí)數(shù)空間，表示函數(shù)的查詢(xún)維度，表示度量使用的距離，通常使用來(lái)度量 。

拉普拉斯機(jī)制

該機(jī)制過(guò)拉普拉斯分布產(chǎn)生的噪音擾動(dòng)真實(shí)輸出值來(lái)實(shí)現(xiàn)差分隱私保護(hù)。

定理1：
對(duì)于任一個(gè)函數(shù)，若算法的輸出結(jié)果滿(mǎn)足下列等式，則滿(mǎn)足-差分隱私。

其中，是相互獨(dú)立的拉普拉斯變量，噪音量大小與成正比，與成反比。算法的全局敏感性越大，所需噪音越大 。從上式可知，中第個(gè)元素由拉普拉斯噪音引起的標(biāo)準(zhǔn)絕對(duì)誤差與方差分別為

指數(shù)機(jī)制

該機(jī)制主要是處理一些輸出結(jié)果為非數(shù)值型的算法，例如，分類(lèi)操作中分裂屬性的選擇問(wèn)題。該機(jī)制的關(guān)鍵技術(shù)是如何設(shè)計(jì)打分函數(shù)，其中表示從輸出域中所選擇的輸出項(xiàng)。

定理2：
給定一個(gè)打分函數(shù)，若算法
滿(mǎn)足下列等式，則滿(mǎn)足-差分隱私。

其中，為打分函數(shù)的全局敏感性。由上式可知，打分越高，被選擇輸出的概率越大。

差分隱私的組合特性

差分隱私保護(hù)技術(shù)本身蘊(yùn)含著序列組合性與并行組合性?xún)煞N重要的組合性質(zhì)。

性質(zhì)1.
給定數(shù)據(jù)庫(kù)與個(gè)隨機(jī)算法，且滿(mǎn)足-隱私，則在上的序列組合滿(mǎn)足-差分隱私，。

性質(zhì)2.
設(shè)為一個(gè)隱私數(shù)據(jù)庫(kù)，被劃分成個(gè)不相交的子集，,設(shè)為任一個(gè)隨機(jī)算法滿(mǎn)足-差分隱私。則算法在上的系列操作滿(mǎn)足-差分隱私。
這兩種性質(zhì)在證明算法是否滿(mǎn)足差分隱私以及在隱私預(yù)算分配過(guò)程中起著重要作用。

差分隱私保護(hù)方法的性能度量

滿(mǎn)足差分隱私的保護(hù)算法需要在保護(hù)隱私的同時(shí)，又要兼顧保護(hù)后數(shù)據(jù)的可用性以及隱私預(yù)算的分配策略是否合理。通常包括3個(gè)方面對(duì)隱私保護(hù)算法進(jìn)行度量。

(1)算法誤差。
常用的應(yīng)用型誤差度量方法包括相對(duì)誤差、絕對(duì)誤差、誤差的方差以及歐式距離等。此外，數(shù)據(jù)依賴(lài)情況下的操作，必須考慮信息缺損帶來(lái)的誤差。

(2)算法性能。
一般利用時(shí)間復(fù)雜度與漸近噪音誤差邊界對(duì)算法的性能進(jìn)行評(píng)估。

(3)的合理分配。
隱私預(yù)算代表著數(shù)據(jù)隱私保護(hù)程度。 一旦耗盡，將破壞差分隱私，算法本身也就失去了意義。因此，合理的預(yù)算分配策略要盡可能使的生命周期持續(xù)長(zhǎng)一些。常用的分配策略包括線性分配、均勻分配、指數(shù)分配、自適用性分配以及混合策略分配等。

參考文獻(xiàn)

張嘯劍, 孟小峰. 面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J]. 計(jì)算機(jī)學(xué)報(bào), 2014(4):927-949.
數(shù)據(jù)分享中的差分隱私保護(hù) 張俊