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

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

1 引言

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

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

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

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

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

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

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

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

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

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

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

2 差分隱私基礎(chǔ)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 差分隱私模型

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

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

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

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

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

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

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

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

定義 3. 局部敏感度. 對于一個查詢函數(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ù)集共同決定, 因為局部敏感度只是對于一個數(shù)據(jù)集做變化。

因為局部敏感度限制了一對相鄰數(shù)據(jù)集中的一個數(shù)據(jù)集, 所以如果在局部敏感度中, 給定的數(shù)據(jù)集和全局敏感度中使 ||f(D) -f(D′)||1達(dá)到最大的數(shù)據(jù)集相同時, 局部敏感度等于全局敏感度。所以, 局部敏感度和全局敏感度的關(guān)系可以表示為:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖5 矩陣機制模型Figure 5 Matrix mechanism

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Xiao等人[26]在分層方法上提出了一種哈爾小波變換的機制, 該方案在哈爾系數(shù)上添加噪聲來實現(xiàn)隱私保護(hù), 而且只適用于二叉樹。該方案中, 根節(jié)點不再是所有子節(jié)點的和, 而是其所有子節(jié)點的平均值。對于所有的非葉子結(jié)點v, 哈爾系數(shù)其中l(wèi)a和ra分別為結(jié)點v的左子樹的所有葉子結(jié)點的平均值和右子樹的所有葉子結(jié)點的平均值。在進(jìn)行查詢時, 對于任意一個結(jié)點v, 如果已知它的所有葉子結(jié)點的平均值a, 則al和ar可由如下方式計算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ù)格合并為若干個分區(qū), 每個分區(qū)的頻數(shù)為其中全部頻數(shù)的平均值。然后在每個合并的分區(qū)中添加噪聲,這樣就可以減少添加的噪聲數(shù)。但是如何劃分使得分區(qū)最優(yōu), 是一個新的研究問題。Xu等人[27]采用平方誤差和來衡量一種分區(qū)方案的優(yōu)劣程度:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表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ù)的分布。因為在推導(dǎo)后驗概率時, 經(jīng)過了一步不等根據(jù)數(shù)據(jù)集中數(shù)據(jù)分布的不同, 這樣的縮放帶來的誤差也就不同。因此有時這一步會使得∈的理論上界遠(yuǎn)遠(yuǎn)大于實際上界。這時使用∈的理論上界會導(dǎo)致“過保護(hù)”的情況, 使得數(shù)據(jù)可用性降低。

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

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

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

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

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

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

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

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

針對PINQ框架的缺點, Haeberlen等人[49]設(shè)計了一個新的差分隱私的工具集模型 Fuzz, 該模型也可以讓用戶自主編程實現(xiàn)所需功能。它主要由 3部分組成, 分別為程序語言編譯器, 類型檢查器以及查詢處理器。其中, 類型檢查器的作用是在執(zhí)行一個查詢前判斷現(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ā)布/存儲/交換部分, 而Dwork等人[23]和 Haeberlen等人[49]設(shè)計的差分隱私框架屬于隱私保護(hù)部分。

8 結(jié)束語

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

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

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

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

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

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

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

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