差分隱私合成數(shù)據(jù)集發(fā)布研究

安徽理工大學(xué)計(jì)算機(jī)學(xué)院 劉文龍 方賢進(jìn)

?

差分隱私合成數(shù)據(jù)集發(fā)布研究

安徽理工大學(xué)計(jì)算機(jī)學(xué)院 劉文龍 方賢進(jìn)

【摘要】差分隱私保護(hù)模型框架中，合成數(shù)據(jù)集發(fā)布是差分隱私保護(hù)的一個(gè)重要應(yīng)用，也是一個(gè)重要研究熱點(diǎn)。本文主要研究和分析了差分隱私保護(hù)在合成數(shù)據(jù)集發(fā)布中的應(yīng)用，重點(diǎn)介紹該領(lǐng)域的研究進(jìn)展，并展望未來的研究方向。

【關(guān)鍵詞】差分隱私；數(shù)據(jù)合成；數(shù)據(jù)發(fā)布

差分隱私保護(hù)技術(shù)是2006年由來自微軟研究院的德沃柯(Dwork)等人提出的針對(duì)統(tǒng)計(jì)數(shù)據(jù)庫(kù)的保護(hù)模型。差分隱私保護(hù)模型作為一個(gè)嚴(yán)格定義的、可證明的隱私保護(hù)模型，近年來受到各學(xué)術(shù)界越來越多的重視和研究。

合成數(shù)據(jù)集的發(fā)布是差分隱私保護(hù)研究中的難點(diǎn)。研究主要集中于對(duì)數(shù)據(jù)集統(tǒng)計(jì)特征的發(fā)布機(jī)制，如直方圖發(fā)布。由于這些發(fā)布機(jī)制僅能描述數(shù)據(jù)集的一部分特征，因此在應(yīng)用場(chǎng)景上存在很大的局限性。現(xiàn)實(shí)的需求促進(jìn)了研究者對(duì)凈化數(shù)據(jù)集發(fā)布的研究。

1　隱私保護(hù)概述

最早出現(xiàn)的k-匿名隱私保護(hù)技術(shù)要求對(duì)數(shù)據(jù)表中的每一條記錄不能區(qū)分于其它k-1條記錄，即對(duì)數(shù)據(jù)中的所有元組進(jìn)行泛化處理，使得其不能再與其他任何人相對(duì)應(yīng)，如表1數(shù)據(jù)匿名化前后對(duì)比可以看出泛化后的數(shù)據(jù)不再像原數(shù)據(jù)一樣準(zhǔn)確，泛化對(duì)數(shù)據(jù)進(jìn)行了更為概括的描述，并保留了有用信息，從而使得數(shù)據(jù)依然具有可用性。

k-匿名和l-多樣技術(shù)不足之處都在于沒有嚴(yán)格定義攻擊模型，沒有對(duì)攻擊者的背景知識(shí)作出定量化定義。這樣使得從k-匿名剛開始的工作就陷入一個(gè)“新隱私保護(hù)模型不斷被提出但又不斷被攻破”的循環(huán)之中。直到Dwork等人提出差分隱私保護(hù)模型，類似問題才得到有效解決。

表1　數(shù)據(jù)匿名化前后對(duì)比

2　差分隱私

2.1差分隱私定義

差分隱私嚴(yán)格定義了攻擊者的背景知識(shí)：除了某一條記錄，假定攻擊者知曉原數(shù)據(jù)集中的所有信息，這樣的攻擊者幾乎是最強(qiáng)大的，而差分隱私依然能夠在這種情況下有效保護(hù)個(gè)人隱私信息。差分隱私保護(hù)模型擁有嚴(yán)謹(jǐn)?shù)慕y(tǒng)計(jì)學(xué)模型，方便了數(shù)學(xué)工具的使用以及定量分析和證明。正是由于差分隱私的諸多優(yōu)勢(shì)，使其一出現(xiàn)便迅速取代了之前的隱私模型，成為隱私研究的核心。

2.2差分隱私統(tǒng)計(jì)學(xué)模型

差分隱私保護(hù)的數(shù)學(xué)表達(dá)為：對(duì)于任意一對(duì)相鄰數(shù)據(jù)庫(kù)D1和D1，任意一個(gè)可能的帶噪中間件S，一個(gè)提供ε-差分隱私保護(hù)的算法A 必須滿足：

也就是說，由于對(duì)于輸入D1和D2，算法A 輸出S 的概率是相近的，所有即使攻擊者已經(jīng)知道了原數(shù)據(jù)中的絕大部分元組，他依然無法對(duì)剩余的元組做出準(zhǔn)確的推斷。對(duì)于任意一個(gè)可能的帶噪中間件S，Pr[A(D1)=S] 和Pr[A(D2)=S] 的比率總是被約束在[exp(-ε)，exp(ε)] 之間，即：

差分隱私保護(hù)模型的參數(shù)描述了上述兩個(gè)概率分布的相似性ε越小，概率的相似性越高，也就越難區(qū)分D1和D2，從而達(dá)到更高程度的隱私保護(hù)。

2.3差分隱私核心算法

德沃柯等人最先提出了差分隱私的通用隨機(jī)算法：拉普拉斯機(jī)制，其核心思想是通過向中間件加入拉普拉斯噪音來滿足定義一中的約束條件。對(duì)于一個(gè)數(shù)據(jù)查詢F，拉普拉斯機(jī)制首先生成真實(shí)結(jié)果F (D) 作為中間件，然后通過發(fā)布帶噪結(jié)果F(D)+η 來回答查詢，其中噪音η服從拉普拉斯分布。

德沃柯等人證明了當(dāng)λ≥ ΔF/ε時(shí)，拉普拉斯機(jī)制就能滿足ε- 差分隱私。

McSherry 和Tulwar所提出的指數(shù)機(jī)制也是差分隱私的經(jīng)典通用算法。該機(jī)制與拉普拉斯機(jī)制最大的不同在于，后者適用于當(dāng)數(shù)據(jù)查詢的返回值為實(shí)數(shù)值的場(chǎng)合，而前者則適用于數(shù)據(jù)查詢的范圍值域?yàn)殡x散值域的場(chǎng)合。現(xiàn)有的許多差分隱私算法在很大程度上都可以認(rèn)為是拉普拉斯機(jī)制與指數(shù)機(jī)制的組合與應(yīng)用。

3　差分隱私數(shù)據(jù)合成應(yīng)用

最早的數(shù)據(jù)合成算法的思路是首先從數(shù)據(jù)庫(kù)生成列聯(lián)表，然后通過拉普拉斯機(jī)制隨機(jī)加噪生成帶噪列聯(lián)表，最后還原出一個(gè)帶噪的合成數(shù)據(jù)庫(kù)。但是，這一思路在面向高維數(shù)據(jù)時(shí)會(huì)產(chǎn)生嚴(yán)重的問題：(1)列聯(lián)表的大小是數(shù)據(jù)維度的指數(shù)倍，這導(dǎo)致高維帶噪列聯(lián)表很難被計(jì)算出來；(2)由于列聯(lián)表的大小遠(yuǎn)大于數(shù)據(jù)庫(kù)，因此信息在列聯(lián)表中的分布極其稀疏，在加入噪音后，列聯(lián)表的信噪比將變得非常低，使得其無法反映原數(shù)據(jù)庫(kù)的有用信息。PrivBayes算法通過建立一個(gè)貝葉斯網(wǎng)絡(luò)找到一系列低維邊界圖來較好地逼近高維列聯(lián)表，然后將所有計(jì)算和加噪都在低維空間中進(jìn)行，從而有效解決高維列聯(lián)表帶來的計(jì)算復(fù)雜度高和信噪比低的問題。

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

正是由于差分隱私的諸多優(yōu)勢(shì)，使得其一出現(xiàn)便很快取代了之前的隱私保護(hù)模型，成為隱私研究的核心，并在計(jì)數(shù)查詢、數(shù)據(jù)挖掘和機(jī)器學(xué)習(xí)等多個(gè)領(lǐng)域得到了廣泛應(yīng)用。然而，當(dāng)前仍有很多需要深入開展研究工作，如攻擊模型的進(jìn)一步優(yōu)化、隱私保護(hù)與數(shù)據(jù)可用性的權(quán)衡等。

參考文獻(xiàn)

[1]陳德誠(chéng),丘平珠,唐炳莉.廣西氣象數(shù)據(jù)集設(shè)計(jì)與制作[J].氣象研究與應(yīng)用,2007(04).

[2]趙鳳英,王崇駿,陳世福.用于不均衡數(shù)據(jù)集的挖掘方法[J].計(jì)算機(jī)科學(xué),2007(09).

[3]孟小峰,張嘯劍.大數(shù)據(jù)隱私管理[J].計(jì)算機(jī)研究與發(fā)展,2015(02).