差分隱私綜述

李效光, 李 暉, 李鳳華, 朱 輝

西安電子科技大學(xué)網(wǎng)絡(luò)與信息安全學(xué)院, 陜西 西安 710071

1 引言

在進(jìn)入21世紀(jì)以來(lái), 互聯(lián)網(wǎng)行業(yè)發(fā)展十分的迅速, 隨之而來(lái)的是人們通訊與數(shù)據(jù)共享的便利與快捷。然而, 由此引發(fā)的隱私泄露風(fēng)險(xiǎn)也隨之日益增長(zhǎng)。近年來(lái), 隱私泄露事件時(shí)有發(fā)生, 另外, 隨著計(jì)算機(jī)技術(shù)的發(fā)展與網(wǎng)絡(luò)攻擊手段的不斷豐富, 保護(hù)隱私數(shù)據(jù)已遠(yuǎn)遠(yuǎn)不再是隱藏?cái)?shù)據(jù)中敏感屬性這么簡(jiǎn)單。例如, 在 2015年, 俄羅斯約會(huì)網(wǎng)站 Topface有

2000萬(wàn)訪客的用戶名和電子郵件地址被盜, 黑客可以使用這些賬號(hào)來(lái)嘗試獲取銀行、病例或其他敏感數(shù)據(jù)信息。另外, 在 2015年, 美國(guó)大型醫(yī)療保險(xiǎn)商

CareFirst表示, 該公司去年六月發(fā)現(xiàn)有黑客入侵, 約有110萬(wàn)醫(yī)療保險(xiǎn)客戶的個(gè)人信息遭泄露, 攻擊者竊取了客戶姓名、生日、郵箱地址、醫(yī)療保險(xiǎn)號(hào)碼等信息。這些事實(shí)說(shuō)明, 隱私的泄露原因可能是多樣的,因此, 隱私保護(hù)理論和技術(shù)需要能夠針對(duì)不同的攻擊手段提供保護(hù)。更為嚴(yán)峻的是, 隨著進(jìn)幾年來(lái)數(shù)據(jù)挖掘等數(shù)據(jù)分析技術(shù)的快速發(fā)展, 使得攻擊者可以從海量數(shù)據(jù)中發(fā)掘出與用戶隱私相關(guān)的信息, 這又對(duì)隱私保護(hù)提出了新的挑戰(zhàn)。因?yàn)楣粽呖梢詰?yīng)用數(shù)據(jù)挖掘技術(shù)對(duì)海量的數(shù)據(jù)進(jìn)行分析, 從而得到數(shù)據(jù)中深層蘊(yùn)含的用戶信息, 而不是通過(guò)訪問數(shù)據(jù)直接獲取。因此, 傳統(tǒng)的加密, 訪問控制等技術(shù)對(duì)這樣的攻擊方式并沒有太好的效果。因此, 隱私保護(hù)是一門結(jié)合多個(gè)學(xué)科和領(lǐng)域的交叉技術(shù)。

要對(duì)隱私進(jìn)行保護(hù), 首先需要對(duì)隱私信息進(jìn)行定義和度量。李鳳華等人[1]提出了隱私信息的全生命周期模型, 如圖1所示, 其中包括9個(gè)部分。分別為:隱私信息產(chǎn)生, 隱私感知, 隱私保護(hù), 隱私發(fā)布, 隱私信息存儲(chǔ), 隱私交換, 隱私分析, 隱私銷毀, 隱私接收者。該模型如圖 1所示。隱私保護(hù)所研究的問題, 主要在隱私保護(hù), 隱私發(fā)布/存儲(chǔ)/交換, 隱私分析這3個(gè)部分。

隱私保護(hù)的方式主要分為以下三種: 數(shù)據(jù)失真,加密, 以及訪問控制。而目前很多隱私保護(hù)技術(shù)結(jié)合其中多種技術(shù)。k-匿名[2-3]是由 Latanya Sweeney和Pierangela Samarati在1998提出的一種匿名化數(shù)據(jù)的技術(shù), 它通過(guò)混淆數(shù)據(jù)的屬性, 解決了“給定一個(gè)原始數(shù)據(jù)集, 生成一個(gè)匿名化的數(shù)據(jù)集, 它可以在保證數(shù)據(jù)的實(shí)驗(yàn)可用性的條件下, 保證其中的個(gè)體身份不會(huì)被恢復(fù)出來(lái)”。k-匿名對(duì)數(shù)據(jù)集提供了一個(gè)良好的性質(zhì), 它可以使得包含在匿名化數(shù)據(jù)集中的每一個(gè)個(gè)體信息都不能從其他 k-1個(gè)個(gè)體信息中區(qū)分開。但是, k-匿名中不包含任何的隨機(jī)化屬性, 所以攻擊者依然可以從滿足 k-匿名性質(zhì)的數(shù)據(jù)集中推斷出與個(gè)體有關(guān)的隱私信息。另外, k-匿名還容易遭受到一致性攻擊與背景知識(shí)攻擊[4], 一致性攻擊主要是指, 在數(shù)據(jù)集中, 如果有 k個(gè)相同屬性的敏感值,那么即使數(shù)據(jù)集符合k-匿名的要求, 那么這k個(gè)敏感屬性也可能被推斷出來(lái)。而背景知識(shí)攻擊是指攻擊者可以通過(guò)找出一個(gè)或多個(gè)準(zhǔn)身份信息屬性和敏感屬性之前的關(guān)聯(lián), 以此來(lái)縮小對(duì)敏感屬性猜測(cè)的范圍。由于k-匿名存在以上缺陷, Machanavajjhala等人[5]在2007對(duì)k-匿名提出了一個(gè)改進(jìn)的方案, l-多樣性。l-多樣性是指, 一個(gè)等價(jià)類中最少有 l個(gè)可以很好代替的敏感屬性的值, 對(duì)于數(shù)據(jù)表來(lái)說(shuō), 則需要每一個(gè)等價(jià)類中都滿足l-多樣性。但是, l-多樣性也并不能完全的保護(hù)用戶隱私不被泄露, 因?yàn)樵谝粋€(gè)真實(shí)的數(shù)據(jù)集中, 屬性值很有可能是偏斜的或者語(yǔ)義相近的, 而l-多樣性只保證了多樣性, 沒有認(rèn)識(shí)到在屬性值上語(yǔ)義相近的情況。因此l-多樣性會(huì)受到相似性攻擊[6]。李寧輝等人[7]在提出的t-closeness方案彌補(bǔ)了l-多樣性, t-closeness指一個(gè)等價(jià)類中的屬性分布和整個(gè)表中的屬性分布之間的距離不超過(guò)門限t。如果一個(gè)數(shù)據(jù)表中的每個(gè)等價(jià)類都滿足 t-closeness,則稱這個(gè)數(shù)據(jù)表滿足t-closeness。

雖然已有的隱私保護(hù)方案層出不窮, 但是它們有一個(gè)共同的缺點(diǎn), 都依賴于攻擊者的背景知識(shí),沒有對(duì)攻擊模型做出合理的假設(shè)。

圖1 隱私信息的全生命周期Figure 1 The full life cycle of privacy information

而2006年Dwork等人提出的差分隱私[8-14]模型解決了這個(gè)問題, 差分隱私的概念來(lái)自于密碼學(xué)中語(yǔ)義安全的概念, 即攻擊者無(wú)法區(qū)分出不同明文的加密結(jié)果。在差分隱私中, 要求攻擊者無(wú)法根據(jù)發(fā)布后的結(jié)果推測(cè)出哪一條結(jié)果對(duì)應(yīng)于那一個(gè)數(shù)據(jù)集。該模型通過(guò)加入隨機(jī)噪聲的方法來(lái)確保公開的輸出結(jié)果不會(huì)因?yàn)橐粋€(gè)個(gè)體是否在數(shù)據(jù)集中而產(chǎn)生明顯的變化, 并對(duì)隱私泄露程度給出了定量化的模型。因?yàn)橐粋€(gè)個(gè)體的變化不會(huì)對(duì)數(shù)據(jù)查詢結(jié)果有顯著的影響, 所以攻擊者無(wú)法以明顯的優(yōu)勢(shì)通過(guò)公開發(fā)布的結(jié)果推斷出個(gè)體樣本的隱私信息, 所以差分隱私模型不需要依賴于攻擊者所擁有多少背景知識(shí), 而且對(duì)隱私信息提供了更高級(jí)別的語(yǔ)義安全, 因此被作為一種新型的隱私保護(hù)模型而廣泛使用。私, 而是對(duì)數(shù)據(jù)集中的每個(gè)個(gè)體的隱私提供保護(hù)。它的概念要求每一個(gè)單一元素在數(shù)據(jù)集中對(duì)輸出的影響都是有限的。從而使得攻擊者在觀察查詢結(jié)果后無(wú)法推斷是哪一個(gè)個(gè)體在數(shù)據(jù)集中的影響使得查詢返回這樣的結(jié)果, 因此, 也就無(wú)法從查詢結(jié)果中推斷有關(guān)個(gè)體隱私的信息。換言之, 攻擊者無(wú)法得知某一個(gè)個(gè)體是否存在于這樣的一個(gè)數(shù)據(jù)集中。

定義 1. 差分隱私. 對(duì)于一個(gè)隨機(jī)算法M,mP為算法M可以輸出的所有值的集合。如果對(duì)于任意的一對(duì)相鄰數(shù)據(jù)集D和D′,mP的任意子集mS, 算法M滿足:

則稱算法M滿足∈-差分隱私, 其中參數(shù)∈為隱私保護(hù)預(yù)算。

從上式中可以看出, 當(dāng)參數(shù)∈越小時(shí), 作用在一對(duì)相鄰數(shù)據(jù)集上的差分隱私算法返回的查詢結(jié)果的概率分布越相似, 攻擊者就越難以區(qū)分這一對(duì)相鄰

2 差分隱私基礎(chǔ)

差分隱私并不是要求保證數(shù)據(jù)集的整體性的隱數(shù)據(jù)集, 保護(hù)程度就越高, 極端情況下, 當(dāng)0=∈時(shí),攻擊者無(wú)法區(qū)分這一對(duì)相鄰數(shù)據(jù)集保護(hù)程度最高。反之, 參數(shù)∈越大時(shí), 保護(hù)程度越低。

圖2說(shuō)明了差分隱私概念的性質(zhì)。差分隱私機(jī)制將一個(gè)正常的查詢函數(shù) ()f.的查詢結(jié)果, 映射到一個(gè)隨機(jī)化的值域上, 并以一定的概率分布來(lái)給用戶返回一個(gè)查詢結(jié)果。通過(guò)參數(shù)∈來(lái)控制一對(duì)相鄰數(shù)據(jù)集上的概率分布的接近程度, 達(dá)到在一對(duì)相鄰數(shù)據(jù)集上, 輸出結(jié)果幾乎一致的目的。從而使得攻擊者無(wú)法區(qū)分這一對(duì)相鄰數(shù)據(jù)集, 實(shí)現(xiàn)保護(hù)數(shù)據(jù)集中個(gè)體隱私信息的目的。

圖2 差分隱私算法在鄰近數(shù)據(jù)集上的輸出概率Figure 2 Output probability of DP algorithm on neighbor dataset

McSherry等人[15]在 2010年又對(duì)差分隱私提出了 2個(gè)重要的性質(zhì)。分別為順序合成性質(zhì)和平行合成性質(zhì)。

性質(zhì) 1. 順序合成. 對(duì)于任意 k個(gè)算法, 分別滿足∈1-差分隱私, ∈2-差分隱私, …, ∈k-差分隱私。將他們作用于同一個(gè)數(shù)據(jù)集上時(shí), 滿足隱私。

這個(gè)性質(zhì)說(shuō)明了, 當(dāng)有一個(gè)算法序列同時(shí)作用在一個(gè)數(shù)據(jù)集上時(shí), 最終的差分隱私預(yù)算等價(jià)于算法序列中所有算法的預(yù)算的和。

性質(zhì)2. 平行合成. 把一個(gè)數(shù)據(jù)集D分成k個(gè)集合, 分別為D1,D2, …,Dk, 令A(yù)1,A2,… ,Ak是k個(gè)分別 滿 足 ∈1,∈2, … ,∈k的 差 分 隱 私 算 法, 則分隱私。

這個(gè)性質(zhì)說(shuō)明了, 當(dāng)有多個(gè)算法序列分別作用在一個(gè)數(shù)據(jù)集上多個(gè)不同子集上時(shí), 最終的差分隱私預(yù)算等價(jià)于算法序列中所有算法預(yù)算的最大值。

這兩個(gè)性質(zhì)在設(shè)計(jì)差分隱私機(jī)制時(shí)有重要的作用, 它們可以被用來(lái)控制一個(gè)差分隱私機(jī)制在使用中所需要的隱私預(yù)算?？刂齐[私預(yù)算的目的在于, 如果在一個(gè)較低隱私預(yù)算參數(shù)∈的情況下, 攻擊者對(duì)一個(gè)數(shù)據(jù)集進(jìn)行了多次查詢, 那么根據(jù)性質(zhì) 1, 攻擊者實(shí)際上獲得的隱私預(yù)算就相當(dāng)于獲得了多次查詢的隱私預(yù)算的和, 而這就破壞了原本設(shè)定的隱私預(yù)算。所以需要控制隱私預(yù)算的上限, 來(lái)通過(guò)上述的性質(zhì)來(lái)計(jì)算合適的隱私預(yù)算上限。

另外, Daniel Kifer等人[16]在2010年對(duì)差分隱私又提出了另外2個(gè)性質(zhì)。

性質(zhì) 3. 變換不變性. 給定任意一個(gè)算法A1滿足∈-差分隱私, 對(duì)于任意算法A2(A2不一定是滿足差分隱私的算法), 則有A(.) =A2(A1(.))滿足∈-差分隱私。

這個(gè)性質(zhì)說(shuō)明了差分隱私對(duì)于后處理算法具有免疫性, 如果一個(gè)算法的結(jié)果滿足∈-差分隱私, 那么在這個(gè)結(jié)果上進(jìn)行的任何處理都不會(huì)對(duì)隱私保護(hù)有所影響。

性質(zhì) 4. 中凸性. 給定 2個(gè)算法A1和A2滿足∈-差分隱私。對(duì)于任意的概率p∈ [ 0,1], 用符號(hào)Ap表示為一種機(jī)制, 它以p的概率使用A1算法, 以1 -p的概率使用A2算法, 則Ap機(jī)制滿足∈-差分隱私。

這個(gè)性質(zhì)說(shuō)明, 如果有 2個(gè)不同的差分隱私算法, 都提供了足夠的不確定性來(lái)保護(hù)隱私, 那么可以通過(guò)選擇任意的算法來(lái)應(yīng)用到數(shù)據(jù)上實(shí)現(xiàn)對(duì)數(shù)據(jù)的隱私保護(hù), 只要選擇的算法和數(shù)據(jù)是獨(dú)立的。

3 差分隱私模型

差分隱私可以通過(guò)在查詢結(jié)果上加入噪聲來(lái)實(shí)現(xiàn)對(duì)用戶隱私信息的保護(hù), 而噪聲量的大小是一個(gè)關(guān)鍵的量, 要使加入的噪聲既能保護(hù)用戶隱私, 又不能使數(shù)據(jù)因?yàn)榧尤脒^(guò)多的噪聲而導(dǎo)致數(shù)據(jù)不可用。函數(shù)敏感度是控制噪聲的重要參數(shù)。Dwork等人[17]在2006年, 提出了全局敏感度以及拉普拉斯機(jī)制的概念, 通過(guò)全局敏感度來(lái)控制生成的噪聲大小,可以實(shí)現(xiàn)滿足差分隱私要求的隱私保護(hù)機(jī)制。

定義 2. 全局敏感度. 對(duì)于一個(gè)查詢函數(shù)f, 它的形式為:f:D→R, 其中D為一數(shù)據(jù)集,R是查詢函數(shù)的返回結(jié)果。在一對(duì)任意的相鄰數(shù)據(jù)集D和D′上, 它的全局敏感度定義如下:

其中, | |f(D) -f(D′)||1是f(D)與f(D′)之間的曼哈頓距離。

全局敏感度反映了一個(gè)查詢函數(shù)在一對(duì)相鄰數(shù)據(jù)集上進(jìn)行查詢時(shí)變化的最大范圍。它與數(shù)據(jù)集無(wú)關(guān), 只由查詢函數(shù)本身決定。

拉普拉斯機(jī)制是一種簡(jiǎn)單, 而且廣泛用于數(shù)值型查詢的隱私保護(hù)機(jī)制。對(duì)于數(shù)值型的查詢結(jié)果, 拉普拉斯機(jī)制通過(guò)在返回一個(gè)在查詢結(jié)果上加入一個(gè)分布的噪聲的結(jié)果來(lái)實(shí)現(xiàn)差分隱私保護(hù)。即R(D) =f(D) +x, 其中f為查詢函數(shù),x為滿足拉普拉斯分布的噪聲。另外, 所加入的拉普拉斯噪聲的均值要求為0, 這樣輸出的R(D)才是f(D)的無(wú)偏估計(jì)。

圖 3展示了不同參數(shù)∈下的拉普拉斯噪聲的概率密度函數(shù)。從圖中可以看出, ∈越小, 所加入的拉普拉斯噪聲的概率密度越平均, 所加入的噪聲為 0的概率就越小, 對(duì)輸出的混淆程度就越大, 保護(hù)程度也就越高。

但是當(dāng)全局敏感度較大時(shí), 根據(jù)全局敏感度生成的噪聲往往會(huì)對(duì)數(shù)據(jù)提供過(guò)度的保護(hù), 針對(duì)這一問題, Nissim 等人[18]提出了一個(gè)局部敏感度以及平滑敏感度等新的概念來(lái)解決這一問題。

圖3 不同∈的拉普拉斯噪聲的概率密度Figure 3 Probability density of Laplace noise with different ∈

定義 3. 局部敏感度. 對(duì)于一個(gè)查詢函數(shù)f, 它的形式為:f:D→R, 其中D為一數(shù)據(jù)集,R是查詢函數(shù)的返回結(jié)果。在一給定的數(shù)據(jù)集D和與它相鄰的任意數(shù)據(jù)集D′上, 它的局部敏感度定義如下:

其中, | |f(D) -f(D′)||1是f(D)與f(D′)之間的曼哈頓距離。

與全局敏感度不同, 局部敏感度是由查詢函數(shù)和給定的數(shù)據(jù)集共同決定, 因?yàn)榫植棵舾卸戎皇菍?duì)于一個(gè)數(shù)據(jù)集做變化。

因?yàn)榫植棵舾卸认拗屏艘粚?duì)相鄰數(shù)據(jù)集中的一個(gè)數(shù)據(jù)集, 所以如果在局部敏感度中, 給定的數(shù)據(jù)集和全局敏感度中使 ||f(D) -f(D′)||1達(dá)到最大的數(shù)據(jù)集相同時(shí), 局部敏感度等于全局敏感度。所以, 局部敏感度和全局敏感度的關(guān)系可以表示為:

因?yàn)楦鶕?jù)局部敏感度所產(chǎn)生的噪聲和數(shù)據(jù)集本身相關(guān), 所以直接使用局部敏感度生成噪聲會(huì)泄露數(shù)據(jù)集信息, Nissim等人[18]提出了根據(jù)平滑敏感度來(lái)生成噪聲的方案, 它們首先提出了平滑上界的概念。

定義4. 平滑上界. 給定一個(gè)β＞0, 對(duì)于一個(gè)函數(shù)F:D→R, 在查詢函數(shù)f上, 如果它滿足如下條件:

則稱函數(shù)F是一個(gè)在查詢函數(shù)f上的β-平滑上界。

定義8. 平滑敏感度. 對(duì)于一個(gè)β＞0, 一個(gè)查詢函數(shù)f的β-平滑敏感度為:

其中,y是和給定數(shù)據(jù)集D維度相同的任意數(shù)據(jù)集,函數(shù)d返回?cái)?shù)據(jù)集D和y中的不同元素的個(gè)數(shù)。實(shí)際上, 平滑敏感度就是可以滿足平滑上界條件的最小函數(shù)。

根據(jù)這一方案, Nissim等人[18]還提出了Sample-Aggregate框架, 對(duì)原有的隱私保護(hù)框架做出了改進(jìn),在 Sample-Aggregate框架中, 所添加的噪聲不僅僅和查詢函數(shù)有關(guān), 還和數(shù)據(jù)集本身有關(guān)。而使用平滑敏感度, 保證了添加的噪聲雖然與數(shù)據(jù)集有關(guān), 但不會(huì)泄露有關(guān)數(shù)據(jù)集的相關(guān)信息。對(duì)于很多查詢函數(shù)來(lái)說(shuō), 它的平滑敏感度可能是難以有效計(jì)算的,甚至是NP-困難的, 而且對(duì)于不同的查詢函數(shù), 平滑敏感度的計(jì)算不能自動(dòng)進(jìn)行。Sample-Aggregate框架很好的解決了這一問題, 它可以自動(dòng)的進(jìn)行, 并且對(duì)于大多數(shù)查詢函數(shù)都適用, 而且不需要精確的計(jì)算出查詢函數(shù)的平滑敏感度。Sample-Aggregate框架通過(guò)把一個(gè)查詢函數(shù)f轉(zhuǎn)化為一個(gè)平滑敏感度較低相關(guān)函數(shù), 再加入合適的噪聲來(lái)作為查詢結(jié)果。圖4說(shuō)明了Sample-Aggregate框架的結(jié)構(gòu)。

圖4 Sample-Aggregate框架Figure 4 Framework of Sample-Aggregate

Sample-Aggregate框架首先將一個(gè)數(shù)據(jù)集隨機(jī)取樣劃分為m個(gè)小子集, m是框架中設(shè)定好的參數(shù),然后對(duì)每個(gè)子集上執(zhí)行查詢函數(shù)f來(lái)生成一個(gè)在f的輸出空間上的值z(mì)k, 最后通過(guò)聚合函數(shù)生成來(lái)替代原始查詢函數(shù)f, 加入校正至平滑敏感度的噪聲來(lái)得到查詢結(jié)果。

對(duì)于批量線性查詢的問題, Li等人[19]提出了一種矩陣機(jī)制, 優(yōu)化了大量線性查詢中噪聲量過(guò)大的問題。該方案通過(guò)將批量的線性查詢轉(zhuǎn)化為一查詢負(fù)載W, 該W矩陣中包含了一系列不同的線性查詢。該方案使用一個(gè)不同的矩陣A來(lái)進(jìn)行查詢, 矩陣A稱為查詢策略。在這里, 我們把可以線性表示查詢負(fù)載的矩陣A稱為查詢負(fù)載W的查詢策略。嚴(yán)格的說(shuō), 即存在解矩陣X, 使得W=XA成立。矩陣機(jī)制通過(guò)在查詢策略上加入合適的噪聲來(lái)實(shí)現(xiàn)差分隱私保護(hù)。Li等人[19]對(duì)矩陣機(jī)制Mk,A(W,x)給出了如下定義:

其中K(A,x)為作用于數(shù)據(jù)集x和查詢策略A的差分隱私機(jī)制,A+為查詢策略A的廣義逆矩陣。對(duì)于矩陣機(jī)制中使用的差分隱私機(jī)制K(A,x), 可以使用拉普拉斯機(jī)制來(lái)實(shí)現(xiàn)。具體來(lái)說(shuō),K(A,x) =Ax+b~A, 其中Ax是在查詢策略下的查詢結(jié)果,b~A是一個(gè)噪聲向量, 用來(lái)提供滿足拉普拉斯分布的噪聲。圖5說(shuō)明了矩陣機(jī)制的模型結(jié)構(gòu)。

但是矩陣機(jī)制的缺點(diǎn)在于, 當(dāng)給定一個(gè)查詢負(fù)載時(shí), 求解其最優(yōu)的查詢策略是一個(gè)半正定最優(yōu)問題, 當(dāng)查詢負(fù)載在一個(gè)有m個(gè)數(shù)據(jù)格的直方圖上時(shí),求解該問題的復(fù)雜度為O(m6), 這使得矩陣機(jī)制對(duì)于大型的數(shù)據(jù)是難以使用的。

由于拉普拉斯機(jī)制只能針對(duì)數(shù)值型數(shù)據(jù)進(jìn)行隱私保護(hù), 對(duì)于非數(shù)值型數(shù)據(jù), 例如實(shí)體對(duì)象,McSherry等人[20]提出了指數(shù)機(jī)制。

假設(shè)所有可能的輸出集合為O, 指數(shù)機(jī)制的目的是使輸出結(jié)果滿足一定的概率分布。用可用性函數(shù)q來(lái)衡量每一個(gè)輸出項(xiàng)的價(jià)值。q定義為q:(D×o) →R, 其中D和o為輸入的數(shù)據(jù)集和可能的輸出集合中的項(xiàng), 函數(shù)q返回一個(gè)實(shí)數(shù)用來(lái)表示這一項(xiàng)的價(jià)值。當(dāng)q的值越高時(shí), 這一項(xiàng)的價(jià)值越大,被輸出的概率也就越大。

定義 9. 指數(shù)機(jī)制. 對(duì)于任意一個(gè)可用性函數(shù)q和一個(gè)差分隱私預(yù)算∈, 如果隨機(jī)算法M以正比于的概率輸出一個(gè)o∈O作為結(jié)果, 其中Δq為可用性函數(shù)q的全局敏感度, 則隨機(jī)算法M滿足∈-差分隱私。

指數(shù)機(jī)制的意義在于防止了攻擊者對(duì)數(shù)據(jù)集中個(gè)體的投票情況的推測(cè)。例如在一次投票活動(dòng)中, 一共有3個(gè)候選人(用編號(hào)1到3表示), 10位選民, 攻擊者控制了除了選民A以外的其他9個(gè)選民(B, C, …, J),現(xiàn)在他的目的是推斷選民 A的投票情況。假設(shè)在 A沒有投票時(shí), 每個(gè)候選人的得票數(shù)都為 3, 也就是說(shuō)B, C, …, J分別給每個(gè)候選人各投了一票, 那么如果攻擊者想要推斷A的投票情況, 就可以通過(guò)最終的選舉結(jié)果看哪位候選人勝出來(lái)判斷A的投票結(jié)果。但是,如果加入指數(shù)機(jī)制, 就可以抵御這種攻擊。

圖5 矩陣機(jī)制模型Figure 5 Matrix mechanism

在指數(shù)機(jī)制中, 參數(shù)∈越小, 每一項(xiàng)輸出的概率就越接近, 相應(yīng)的, 輸出三個(gè)候選人的概率也就越平均, 從而讓攻擊者難以判斷A的投票情況。當(dāng)參數(shù)∈選擇為0時(shí), 隱私保護(hù)級(jí)別最高, 攻擊者完全無(wú)法判斷A的投票情況。表1以一個(gè)圖表說(shuō)明了指數(shù)機(jī)制如何抵御這種攻擊。

表1 投票數(shù)據(jù)集及公布結(jié)果概率分布Table 1 ballot dataset and probability distribution

另外, Blum 等人[21]提出了網(wǎng)絡(luò)機(jī)制, 可以計(jì)算比較可能的新數(shù)據(jù)集與原始數(shù)據(jù)集的誤差來(lái)最優(yōu)的生成新數(shù)據(jù)集來(lái)實(shí)現(xiàn)差分隱私。Hardt等人[22]提出了隱私乘法權(quán)重調(diào)整機(jī)制, 可以動(dòng)態(tài)地調(diào)整數(shù)據(jù)集真實(shí)分布與人為猜測(cè)分布間的誤差使其滿足差分隱私。

綜上所述, 在一個(gè)隱私信息的全生命周期內(nèi),Sample-Aggregate框架和矩陣機(jī)制主要被設(shè)計(jì)為交互式的模型應(yīng)用于隱私保護(hù)和隱私發(fā)布/存儲(chǔ)/交換的部分, 而拉普拉斯機(jī)制和指數(shù)機(jī)制是差分隱私方法的基礎(chǔ)模型, 由這 4種機(jī)制設(shè)計(jì)的其他差分隱私方案被廣泛的用于隱私信息的全生命周期內(nèi)的隱私保護(hù), 隱私發(fā)布/存儲(chǔ)/交換以及隱私分析部分。

4 差分隱私在數(shù)據(jù)發(fā)布中的應(yīng)用

由于差分隱私在隱私信息保護(hù)方面的諸多性質(zhì),使得差分隱私被用于了各個(gè)數(shù)據(jù)發(fā)布的技術(shù)領(lǐng)域。直方圖是一種常用的數(shù)據(jù)分布的表示形式, 經(jīng)常被用于數(shù)據(jù)發(fā)布上, 在各個(gè)領(lǐng)域都有廣泛的應(yīng)用。除了矩陣機(jī)制, 差分隱私還在直方圖上有廣泛的應(yīng)用。

Dwork等人[23]將設(shè)計(jì)的拉普拉斯機(jī)制應(yīng)用在了直方圖發(fā)布上, 他設(shè)計(jì)了一種簡(jiǎn)單的機(jī)制。

因?yàn)樵跀?shù)據(jù)集對(duì)應(yīng)的直方圖中, 每一個(gè)數(shù)據(jù)集中元素的變化最多影響直方圖中一個(gè)數(shù)據(jù)格上一個(gè)元素的變化, 所以該方法使用拉普拉斯機(jī)制, 在每個(gè)數(shù)據(jù)格上添加服從分布的噪聲。Dwork 指出, 在這種機(jī)制下, 對(duì)直方圖進(jìn)行范圍查詢的 MSE為范圍查詢的長(zhǎng)度。Dwork還提出, 對(duì)于各種范圍的查詢, 這種方案的平均 MSE為其中N為數(shù)據(jù)格數(shù)。

對(duì)于提高范圍查詢精度的問題, Qardaji等人[24]提出了一種基于分層的差分隱私方法。該方法將直方圖轉(zhuǎn)化為一顆 b叉樹, 葉子結(jié)點(diǎn)為數(shù)據(jù)格中的數(shù)據(jù)值, 每個(gè)葉子結(jié)點(diǎn)的父節(jié)點(diǎn)為其所有葉子結(jié)點(diǎn)的和。圖6顯示了分層方法的結(jié)構(gòu)。

圖6 分層方法結(jié)構(gòu)Figure 6 Hierarchical mechanism

分層方法的一個(gè)優(yōu)勢(shì)是, 對(duì)于任何范圍查詢,所使用的結(jié)點(diǎn)個(gè)數(shù)不會(huì)超過(guò)(b- 1 )h個(gè), Qardaji等人[24]還提出, 這種分層方法對(duì)于各種范圍的查詢的其中,h為整個(gè)樹不包含根節(jié)點(diǎn)的層數(shù), 從葉子層數(shù)開始計(jì)數(shù), 根節(jié)點(diǎn)為h+ 1層。b為樹的分支因數(shù)。與Dwork的方案相比, 精度有了明顯的提高。為了優(yōu)化分層方法的精度, Qardaji等人[24]把Hay等人[25]之前提出的一種Constrained Inference方法應(yīng)用于分層方法。這種方法對(duì)樹形結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)進(jìn)行了 2步細(xì)化的處理, 分別為Weighted Averaging和Mean Consistency。首先執(zhí)行Weighted Averaging步驟, 從葉子結(jié)點(diǎn)開始向上遍歷直到根節(jié)點(diǎn), 并用結(jié)點(diǎn)的原始噪聲值的加權(quán)平均值與其所有子節(jié)點(diǎn)的和來(lái)更新每個(gè)結(jié)點(diǎn)上的值。

用n[v]來(lái)表示加入噪聲的結(jié)點(diǎn)v。Weighted Averaging具體過(guò)程如下:

Weighted Averaging的意義在于, 從葉子結(jié)點(diǎn)向上更新每個(gè)結(jié)點(diǎn)上的計(jì)數(shù), 以降低每個(gè)結(jié)點(diǎn)上的方差。

而Mean Consistency與之相反, 從根節(jié)點(diǎn)開始向下遍歷, 更新每個(gè)結(jié)點(diǎn)的值, 目的是使得加入噪聲后, 父節(jié)點(diǎn)上的值和其所有子節(jié)點(diǎn)上的值的和能保證相等。具體的過(guò)程如下:

Qardaji等人[24]還分析了Constrained Inference方法對(duì)于分層方法的影響。得出結(jié)論, 在加入Constrained Inference方法后, 每個(gè)結(jié)點(diǎn)的方差最小

Xiao等人[26]在分層方法上提出了一種哈爾小波變換的機(jī)制, 該方案在哈爾系數(shù)上添加噪聲來(lái)實(shí)現(xiàn)隱私保護(hù), 而且只適用于二叉樹。該方案中, 根節(jié)點(diǎn)不再是所有子節(jié)點(diǎn)的和, 而是其所有子節(jié)點(diǎn)的平均值。對(duì)于所有的非葉子結(jié)點(diǎn)v, 哈爾系數(shù)其中l(wèi)a和ra分別為結(jié)點(diǎn)v的左子樹的所有葉子結(jié)點(diǎn)的平均值和右子樹的所有葉子結(jié)點(diǎn)的平均值。在進(jìn)行查詢時(shí), 對(duì)于任意一個(gè)結(jié)點(diǎn)v, 如果已知它的所有葉子結(jié)點(diǎn)的平均值a, 則al和ar可由如下方式計(jì)算al=a+hv,ar=a-hv?；诠盒〔ㄗ儞Q的分層方法結(jié)構(gòu)如圖4所示。

圖7 基于哈爾小波變換的分層方法結(jié)構(gòu)Figure 7 Hierarchical mechanism based Haar wavelet transform

另一種有效的降低噪聲的方法是, 將所有數(shù)據(jù)格合并為若干個(gè)分區(qū), 每個(gè)分區(qū)的頻數(shù)為其中全部頻數(shù)的平均值。然后在每個(gè)合并的分區(qū)中添加噪聲,這樣就可以減少添加的噪聲數(shù)。但是如何劃分使得分區(qū)最優(yōu), 是一個(gè)新的研究問題。Xu等人[27]采用平方誤差和來(lái)衡量一種分區(qū)方案的優(yōu)劣程度:

根據(jù)這一度量方法, Xu等人提出了NoiseFirst方案用于在直方圖上實(shí)現(xiàn)差分隱私保護(hù)。

NoiseFirst基于拉普拉斯機(jī)制, 首先加入噪聲,然后遍歷得到最優(yōu)的分割數(shù)據(jù)格方案, 再對(duì)直方圖進(jìn)行分割合并。

但是 NoiseFirst方案只適用于一維的 V-優(yōu)化直方圖發(fā)布。針對(duì)這一問題, Xiao等人[28]提出了DPCube方案, 結(jié)合單元?jiǎng)澐峙c kd-樹的思想, 用以獲得多維V-優(yōu)化直方圖, 來(lái)支持多維直方圖的數(shù)據(jù)發(fā)布。

綜上所述, 這 5種方法主要應(yīng)用于隱私信息全生命周期中的隱私保護(hù)和隱私發(fā)布/存儲(chǔ)/交換的部分。

另外, 還可以通過(guò)先對(duì)直方圖結(jié)構(gòu)進(jìn)行重新組織再加入噪聲來(lái)實(shí)現(xiàn)差分隱私。根據(jù)聚類方法重新劃分直方圖中的數(shù)據(jù)格, Xu等人[27]提出了StructureFirst方案, 采用平方誤差和來(lái)衡量一種直方圖分區(qū)方案的優(yōu)劣程度, 結(jié)合指數(shù)機(jī)制, 對(duì)原始直方圖進(jìn)行壓縮得到了滿足差分隱私的 V-優(yōu)化直方圖。該方案的缺點(diǎn)在于, 沒有顧及到重構(gòu)誤差和噪音誤差之間的平衡; 對(duì)于一些數(shù)據(jù)格個(gè)數(shù)比較多的直方圖, 該方法效率非常低。Acs等人[29]提出了P-HPartation方案來(lái)解決該問題, 該方案結(jié)合自適應(yīng)的層次聚類技術(shù)和貪婪二等分策略, 平衡了StructureFirst方案中的重構(gòu)誤差與噪音誤差并且提高了效率。根據(jù)傅里葉變換理論, Rastogi等人[30]結(jié)合離散傅里葉變換和逆離散傅里葉變換以及拉普拉斯機(jī)制, 發(fā)布滿足差分隱私的直方圖。

除了直方圖發(fā)布技術(shù), 還存在基于劃分的數(shù)據(jù)發(fā)布技術(shù)。Qardaji等人[31]提出了 UG方案, 對(duì)針對(duì)二維空間數(shù)據(jù), 結(jié)合劃分粒度與拉普拉斯機(jī)制對(duì)數(shù)據(jù)進(jìn)行劃分, 實(shí)現(xiàn)基于差分隱私的數(shù)據(jù)發(fā)布。但是該方案的缺點(diǎn)在于, 沒有考慮數(shù)據(jù)分布的密度和稀疏。針對(duì)這一問題, Qardaji等人[31]又提出了AG方案, 該方案是對(duì)UG方案的改進(jìn), 通過(guò)自適應(yīng)劃分策略來(lái)避免單元過(guò)于密集與過(guò)于稀疏的問題。

另外, 還可以通過(guò)非交互式算法發(fā)布合成數(shù)據(jù)集或加入噪聲的數(shù)據(jù)集來(lái)實(shí)現(xiàn)數(shù)據(jù)發(fā)布。針對(duì)高維數(shù)據(jù), Chen等人[32]提出一種基于取樣的框架,通過(guò)聯(lián)結(jié)樹對(duì)高維數(shù)據(jù)中每個(gè)數(shù)據(jù)屬性取樣分析,生成帶有噪聲的屬性依賴關(guān)系圖, 再根據(jù)關(guān)系圖合成數(shù)據(jù)集來(lái)進(jìn)行高維數(shù)據(jù)發(fā)布。對(duì)于用戶軌跡數(shù)據(jù)數(shù)據(jù)集, Chen等人[33]還結(jié)合前綴樹結(jié)構(gòu), 生成帶有噪聲的前綴樹, 再根據(jù)此前綴樹生成用于發(fā)布的凈化數(shù)據(jù)集。Li等人[34]提出壓縮機(jī)制, 通過(guò)使用壓縮技術(shù), 將噪聲加入稀疏數(shù)據(jù)集的取樣樣本中,將噪聲的大小降低到 (log)On。Machanavajjhala等人[35]通過(guò)設(shè)計(jì)帶有噪聲的統(tǒng)計(jì)模型從原始數(shù)據(jù)集中隨機(jī)取樣以生成凈化過(guò)的數(shù)據(jù)集用來(lái)發(fā)布。Zhou等人[36]通過(guò)隨機(jī)線性變換或仿射變換來(lái)壓縮數(shù)據(jù)集。如表2所示, 表2總結(jié)了本節(jié)中說(shuō)明的差分隱私算法的優(yōu)缺點(diǎn)。

綜上所述, 這15種方法主要應(yīng)用于隱私信息全生命周期中的隱私保護(hù)和隱私發(fā)布/存儲(chǔ)/交換的部分。

5 基于差分隱私保護(hù)的數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)

由于數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)往往要處理海量的用戶數(shù)據(jù), 這其中會(huì)蘊(yùn)含有大量的用戶隱私信息, 如何在保護(hù)用戶隱私信息的同時(shí), 還可以挖掘分析出可用的信息, 是隱私保護(hù)研究的一個(gè)重要課題。因此,數(shù)據(jù)挖掘是差分隱私應(yīng)用的一個(gè)重要領(lǐng)域。

表2 差分隱私在數(shù)據(jù)發(fā)布中方案總結(jié)Table 2 Summary of DP in data release

Mohammed等人[42]提出了一種基于泛化技術(shù)的非交互模式匿名化數(shù)據(jù)挖掘算法, 通過(guò)在泛化技術(shù)中加入指數(shù)噪聲來(lái)實(shí)現(xiàn)差分隱私保護(hù)。該方案設(shè)計(jì)了一種非交互式的差分隱私機(jī)制。它使用分類樹來(lái)對(duì)原始數(shù)據(jù)集進(jìn)行分類, 并對(duì)屬性信息進(jìn)行泛化。在該方案中, 采用了信息增益來(lái)選擇分割屬性, 在分類樹中, 以信息增益來(lái)作為可用性函數(shù), 對(duì)每個(gè)結(jié)點(diǎn)的分割值進(jìn)行可用性度量, 屬性 A對(duì)于數(shù)據(jù)集 D的信息增益可表示為:

其中H(D)表示數(shù)據(jù)集 D的經(jīng)驗(yàn)熵, 而H(D|A)表示用屬性A對(duì)數(shù)據(jù)集D劃分后D的經(jīng)驗(yàn)熵。以此作為可用性函數(shù), 通過(guò)指數(shù)機(jī)制來(lái)對(duì)屬性進(jìn)行分割,最后結(jié)合拉普拉斯機(jī)制實(shí)現(xiàn)差分隱私保護(hù)。圖 8說(shuō)明了這種數(shù)據(jù)挖掘算法的框架。

另一種差分隱私的數(shù)據(jù)挖掘方案基于樸素貝葉斯分類器。樸素貝葉斯分類器是數(shù)據(jù)挖掘中一種常用的分類器, 樸素貝葉斯模型發(fā)源于古典數(shù)學(xué)理論,有穩(wěn)定的分類效率, 并且對(duì)小規(guī)模的數(shù)據(jù)表現(xiàn)很好,能個(gè)處理多分類任務(wù), 適合增量式訓(xùn)練, 尤其是數(shù)據(jù)量超出內(nèi)存時(shí), 我們可以一批批的去增量訓(xùn)練,而且對(duì)缺失數(shù)據(jù)不太敏感, 算法也比較簡(jiǎn)單, 常用于文本分類。Vaidya等人[43]基于樸素貝葉斯的概念,提出了一種基于差分隱私的樸素貝葉斯模型。該方案分別對(duì)離散型分類屬性和連續(xù)型分類屬性的敏感度進(jìn)行的計(jì)算。

圖8 非交互式差分隱私數(shù)據(jù)挖掘框架Figure 8 Non-interactive DP framework for data mining

對(duì)于離散型分類屬性, 由于一個(gè)元素只能影響一條記錄, 所以敏感度為1, 而對(duì)于連續(xù)型分類屬性,需要通過(guò)正態(tài)分布來(lái)預(yù)測(cè)數(shù)據(jù), 因此需要對(duì)均值μ和方差δ分別計(jì)算敏感度。Vaidya等人[43]指出, 如果數(shù)據(jù)集中屬性Xj在值域[lj,uj]上時(shí), 均值μ的敏感而方差δ的敏感度為其中n為數(shù)據(jù)集的大小。在得到對(duì)應(yīng)的參數(shù)的敏感度之后, 該方案通過(guò)在原始的樸素貝葉斯分類器的參數(shù)上加上由對(duì)應(yīng)敏感度生成的噪聲來(lái)實(shí)現(xiàn)差分隱私保護(hù)。

在機(jī)器學(xué)習(xí)中, 主要分為有監(jiān)督學(xué)習(xí)和無(wú)監(jiān)督學(xué)習(xí)。其中有監(jiān)督學(xué)習(xí)中, 線性回歸是一種簡(jiǎn)單有效的模型, 對(duì)于線性回歸, Zhang等人[36]提出了一種函數(shù)機(jī)制, 通過(guò)在線性回歸模型中的代價(jià)函數(shù)的系數(shù)上加上噪聲, 再通過(guò)梯度下降法等方法求解最優(yōu)模型。該方案的優(yōu)勢(shì)在于提高了線性回歸模型的精度,但是一旦生成模型就是不可逆的。

對(duì)于分類算法, 支持向量機(jī)和 logisitc回歸是常用的方法。對(duì)于支持向量機(jī), Chaudhuri等人[37-38]提出了 2點(diǎn)假設(shè), 假設(shè)求解的參數(shù)是通過(guò)凸優(yōu)化得到的,并且一個(gè)樣本點(diǎn)的變化會(huì)導(dǎo)致代價(jià)函數(shù)邊界變化。在這2點(diǎn)假設(shè)下, Chaudhuri等人提出了輸出擾動(dòng)機(jī)制和目標(biāo)擾動(dòng)機(jī)制。輸出擾動(dòng)機(jī)制首先訓(xùn)練模型, 然后在模型中加入噪聲以實(shí)現(xiàn)差分隱私。目標(biāo)擾動(dòng)機(jī)制通過(guò)在代價(jià)函數(shù)中引入一個(gè)線性擾動(dòng)項(xiàng)對(duì)代價(jià)函數(shù)進(jìn)行擾動(dòng), 再?gòu)脑摯鷥r(jià)函數(shù)中學(xué)習(xí)出加入噪聲的支持向量機(jī)模型。對(duì)于logistic回歸, Zhang等人[36]還將函數(shù)機(jī)制應(yīng)用在了 logistic回歸上, 通過(guò)對(duì)logistic回歸的代價(jià)函數(shù)進(jìn)行泰勒展開, 將其轉(zhuǎn)化為多項(xiàng)式, 然后再對(duì)多項(xiàng)式的每一項(xiàng)系數(shù)加入噪聲,再通過(guò)梯度下降法等方法求解最優(yōu)模型。

對(duì)于核函數(shù)支持向量機(jī), 與線性支持向量機(jī)不同的是, 核函數(shù)支持向量機(jī)包含全部的訓(xùn)練數(shù)據(jù),為了避免公開數(shù)據(jù), Rubinstein等人[39]提出了一種隱私保護(hù)的核函數(shù)支持向量機(jī), 該方案首先構(gòu)造一個(gè)和隱私數(shù)據(jù)無(wú)關(guān)的空間, 然后將原始數(shù)據(jù)映射到構(gòu)造的空間, 通過(guò)使用核函數(shù)來(lái)估計(jì)樣本空間中的原始數(shù)據(jù)以避免公開發(fā)布原始數(shù)據(jù)。

在無(wú)監(jiān)督學(xué)習(xí)中, k-均值方法是一種常用的聚類方法。Blum 等人[40]給出了提供差分隱私保護(hù)的 k-均值算法．由于在計(jì)算每個(gè)記錄與質(zhì)心的距離時(shí)會(huì)泄露隱私, 因此在SuLQ框架下通過(guò)發(fā)布聚類質(zhì)心和記錄數(shù)量的估計(jì)值來(lái)滿足隱私保護(hù)的要求, 但查詢聚類質(zhì)心的函數(shù)敏感度為聚類的最大直徑, 而以此敏感度計(jì)算出的噪聲量較大, 降低了聚類結(jié)果的可用性。針對(duì)這一問題, Kobbi等人[18]提出了基于Sample-Aggregate框架的k-均值聚類方法。但是該方案的問題在于, 只有取樣的數(shù)據(jù)有一定的一致性時(shí)聚類結(jié)果才有較高可用性, 因此 Dan等人[41]提出了基于核心集的方法來(lái), 該方案通過(guò)從 d維空間G中的n個(gè)數(shù)據(jù)點(diǎn)中計(jì)算出核心點(diǎn)集GSG?, 通過(guò)對(duì)該核心點(diǎn)集進(jìn)行聚類能得到近似的結(jié)果。如表3所示,表3總結(jié)了本節(jié)中說(shuō)明的差分隱私算法的優(yōu)缺點(diǎn)

綜上所述, 這 9種方法主要被應(yīng)用于數(shù)據(jù)挖掘領(lǐng)域, 其中, Mohammed等人提出的基于泛化技術(shù)的非交互模式匿名化數(shù)據(jù)挖掘算法屬于隱私信息全生命周期中的隱私發(fā)布/存儲(chǔ)/交換部分和隱私分析部分, 而基于差分隱私的樸素貝葉斯分類方法屬于隱私分析部分。

表3 差分隱私在數(shù)據(jù)挖掘中方案總結(jié)Table 3 Summary of DP algorithm in data mining

其中, Δv表示max|f(Di′ )-f(Dk′)|, 指在所有的子數(shù)據(jù)集中進(jìn)行查詢所產(chǎn)生的最大差值。在給定隱私泄露程度后, 可以唯一的求解出參數(shù)∈。該方案的缺陷在于, 這種方法在一定程度上依賴于數(shù)據(jù)集中數(shù)據(jù)的分布。因?yàn)樵谕茖?dǎo)后驗(yàn)概率時(shí), 經(jīng)過(guò)了一步不等根據(jù)數(shù)據(jù)集中數(shù)據(jù)分布的不同, 這樣的縮放帶來(lái)的誤差也就不同。因此有時(shí)這一步會(huì)使得∈的理論上界遠(yuǎn)遠(yuǎn)大于實(shí)際上界。這時(shí)使用∈的理論上界會(huì)導(dǎo)致“過(guò)保護(hù)”的情況, 使得數(shù)據(jù)可用性降低。

Naldi等人[45]提出了一種基于區(qū)間估算理論的度量方法。該方案中, 度量了加入噪聲后的變量c?和真實(shí)值c之間的距離, 用它們之間的距離來(lái)度量提供的隱私程度, 以此來(lái)計(jì)算合適的參數(shù)∈。該方案中定義了一種對(duì)隱私保護(hù)級(jí)別的描述,

其中,w是一個(gè)控制?與c之間距離的參數(shù),w越大則說(shuō)明?與c之間距離越大, 則隱私保護(hù)級(jí)別越高, 反之則說(shuō)明隱私保護(hù)級(jí)別越低。而p則表示真實(shí)值落在[? -wc,+wc]之間的概率, 概率越大說(shuō)明隱私保護(hù)級(jí)別越低, 反之說(shuō)明隱私保護(hù)級(jí)別越高。Naldi等人[45]給出了最終的參數(shù)∈的表達(dá)式為

6 差分隱私參數(shù)度量方法

在差分隱私模型中, 隱私預(yù)算參數(shù)∈是一個(gè)關(guān)鍵的參數(shù), 對(duì)于這個(gè)參數(shù)的選取不能僅僅通過(guò)直覺。Lee等人[44]提出了一種根據(jù)后驗(yàn)概率來(lái)度量參數(shù)∈所提供的隱私保護(hù)程度的方案。該方案定義了一種攻擊模型, 攻擊者的目的是猜測(cè)數(shù)據(jù)集D的相鄰數(shù)據(jù)集D′, 在該攻擊模型中, 先驗(yàn)概率定義為攻擊者看到差分隱私機(jī)制發(fā)布的結(jié)果之前, 對(duì)于數(shù)據(jù)集D′的猜測(cè)正確的概率, 后驗(yàn)概率定義為攻擊者看到差分隱私機(jī)制發(fā)布的結(jié)果之后, 再對(duì)于數(shù)據(jù)集D′猜測(cè)正確的概率。Lee等人定義隱私泄露程度為后驗(yàn)概率與先驗(yàn)概率的差值, 差值越大, 說(shuō)明保護(hù)程度越低。Lee等人指出, 對(duì)于數(shù)據(jù)集相鄰Di′猜測(cè)正確的后驗(yàn)概率, 將其定義為 β (′), 那么后驗(yàn)概率有如下等式:

綜上所述, 這兩種方法都是對(duì)差分隱私預(yù)算參數(shù)∈進(jìn)行度量的, 主要應(yīng)用于隱私信息全生命周期中的隱私分析部分。

7 差分隱私的其他應(yīng)用

Mcsherry等人[46]首次將差分隱私應(yīng)用在推薦系統(tǒng)中, 在分析輸入系統(tǒng)中的各項(xiàng)目之間的關(guān)系時(shí),他們先建立項(xiàng)目相似度協(xié)方差矩陣, 然后向矩陣中加入Laplace噪聲, 最后將加入噪聲的協(xié)方差矩陣提交給推薦系統(tǒng)執(zhí)行常規(guī)推薦算法。Machanavajjhal等人[47]將差分隱私應(yīng)用于社交網(wǎng)絡(luò)中, 在社交網(wǎng)絡(luò)中往往用圖來(lái)表示用戶之間的關(guān)系, 用圖中的結(jié)點(diǎn)表示用戶, 結(jié)點(diǎn)之間的邊表示用戶之間的關(guān)系。用戶之間的關(guān)系往往是敏感信息, 所以Machanavajjhal等人以結(jié)點(diǎn)上的鄰居數(shù)為可用性函數(shù), 用指數(shù)機(jī)制隨機(jī)生成邊, 實(shí)現(xiàn)差分隱私保護(hù)。

Mcsherry等人[48]還開發(fā)的一套為隱私敏感數(shù)據(jù)提供差分隱私保護(hù)的框架。PINQ框架提供一系列的API, 便于可以自己根據(jù)需求編寫程序來(lái)使用 PINQ框架進(jìn)行相關(guān)的差分隱私保護(hù)系統(tǒng)開發(fā), 框架中還提供了豐富的差分隱私數(shù)據(jù)分析的應(yīng)用實(shí)例。但是PINQ框架的缺點(diǎn)在于, 無(wú)法防止隱蔽信道攻擊等多種攻擊。

針對(duì)PINQ框架的缺點(diǎn), Haeberlen等人[49]設(shè)計(jì)了一個(gè)新的差分隱私的工具集模型 Fuzz, 該模型也可以讓用戶自主編程實(shí)現(xiàn)所需功能。它主要由 3部分組成, 分別為程序語(yǔ)言編譯器, 類型檢查器以及查詢處理器。其中, 類型檢查器的作用是在執(zhí)行一個(gè)查詢前判斷現(xiàn)有的可用預(yù)算能否進(jìn)行查詢, 最后將查詢交由查詢處理器執(zhí)行, 返回差分隱私查詢結(jié)果。Fuzz的框架如圖9所示。

圖9 Fuzz框架Figure 9 Framework of Fuzz

綜上所述, Mcsherry等人[48]提出的基于差分隱私的推薦系統(tǒng)和 Machanavajjhal等人[49]提出的基于差分隱私的社交網(wǎng)絡(luò)方法, 屬于隱私信息的全生命周期的隱私保護(hù)和隱私發(fā)布/存儲(chǔ)/交換部分, 而Dwork等人[23]和 Haeberlen等人[49]設(shè)計(jì)的差分隱私框架屬于隱私保護(hù)部分。

8 結(jié)束語(yǔ)

差分隱私保護(hù)是一種通用、靈活、具有堅(jiān)實(shí)的數(shù)學(xué)理論支撐的隱私保護(hù)方法, 可以用來(lái)解決很多傳統(tǒng)密碼學(xué)不適合甚至不可行的問題, 實(shí)現(xiàn)了隱私的語(yǔ)義安全, 因此引起越來(lái)越多研究者的興趣。差分隱私保護(hù)在近兩年取得了飛速的發(fā)展, 隨著大數(shù)據(jù),人工智能領(lǐng)域的興起, 差分隱私的被越來(lái)越多的應(yīng)用在這些場(chǎng)景下。

1) 差分隱私分為交互式差分隱私和非交互式差分隱私, 交互式差分隱私主要通過(guò)設(shè)計(jì)接口的方式,在查詢結(jié)果上加入噪聲來(lái)實(shí)現(xiàn)隱私保護(hù)。而非交互式的差分隱私保護(hù)機(jī)制需要直接將數(shù)據(jù)集通過(guò)隱私保護(hù)算法處理后發(fā)布, 以滿足用戶的查詢需求。雖然已經(jīng)有一些非交互式的差分隱私算法, 但對(duì)于如何降低計(jì)算復(fù)雜度, 如何處理數(shù)值型數(shù)據(jù)以及如何提供更廣泛的查詢類型等問題上還有待進(jìn)一步研究。

2) 差分隱私雖然現(xiàn)在已經(jīng)被用于數(shù)據(jù)挖掘, 推薦系統(tǒng)等領(lǐng)域, 但是差分隱私對(duì)于挖掘數(shù)據(jù)保護(hù)后,還能對(duì)數(shù)據(jù)分析者提供多少可用信息, Fredrikson等人[50]通過(guò)實(shí)驗(yàn)分析了差分隱私數(shù)據(jù)挖掘算法和常規(guī)數(shù)據(jù)挖掘算法對(duì)于藥物劑量預(yù)測(cè)以及病人身體狀況的差距, 但是目前還沒有一個(gè)合理通用的度量方法。

另外, 機(jī)器學(xué)習(xí)中往往需要對(duì)大量的數(shù)據(jù)進(jìn)行分析, 這些數(shù)據(jù)中往往包含著大量的用戶隱私信息,而隨著機(jī)器學(xué)習(xí)的發(fā)展, 差分隱私與機(jī)器學(xué)習(xí)的結(jié)合將是未來(lái)的一個(gè)研究熱點(diǎn)。因此, 在差分隱私和機(jī)器學(xué)習(xí)中, 主要有以下問題需要解決。

3) 如何解決樣本數(shù)據(jù)集中缺失數(shù)據(jù)的問題, 傳統(tǒng)機(jī)器學(xué)習(xí)方法不能滿足差分隱私的需求。

4) 醫(yī)療數(shù)據(jù)集中, 很多體征數(shù)據(jù)只是暫時(shí)的,例如化驗(yàn)結(jié)果只能代表病人這一時(shí)期的體征, 多次的化驗(yàn)結(jié)果之間沒有相關(guān)性, 而且對(duì)于數(shù)據(jù)的擾動(dòng)很有可能使數(shù)據(jù)失去重要的信息, 因此需要有應(yīng)對(duì)這種類型數(shù)據(jù)的差分隱私模型。

5) 隱私是否能在不犧牲機(jī)器學(xué)習(xí)模型可用性的條件下實(shí)現(xiàn)。一種已有的思路是, 當(dāng)噪聲大小小于樣本抽樣的隨機(jī)性的時(shí)候, 噪聲對(duì)隱私的就不會(huì)產(chǎn)生影響。

6) 在正則化的機(jī)器學(xué)習(xí)模型中, 差分隱私是否可以與正則化的想法兼容。