基于差分隱私的隱私保護(hù)數(shù)據(jù)發(fā)布研究綜述

高明珠，徐庭銳，劉洋廷，陳彥如

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都610065；2.四川虹微技術(shù)有限公司，成都610000）

0 引言

我們?cè)谙硎苤扑]算法、圖像識(shí)別、語(yǔ)音識(shí)別等智能技術(shù)發(fā)展帶來(lái)的紅利的同時(shí)，數(shù)據(jù)在其背后承擔(dān)著推動(dòng)技術(shù)不斷迭代的關(guān)鍵角色。

互聯(lián)網(wǎng)快速發(fā)展時(shí)期，各種信息數(shù)據(jù)正呈現(xiàn)爆發(fā)式增長(zhǎng)，海量數(shù)據(jù)包含了企業(yè)的關(guān)鍵數(shù)據(jù)和個(gè)人的各類隱私數(shù)據(jù)，數(shù)據(jù)共享、數(shù)據(jù)發(fā)布、數(shù)據(jù)挖掘等變得越來(lái)越容易，這引起了企業(yè)和個(gè)人對(duì)隱私安全的擔(dān)憂。目前，社交網(wǎng)絡(luò)、互聯(lián)網(wǎng)巨頭、各類App 等熱衷于收集海量用戶數(shù)據(jù)，這些數(shù)據(jù)包含著大量的用戶隱私，如醫(yī)療記錄、用戶喜好、位置信息、教育程度等。數(shù)據(jù)爆發(fā)式增長(zhǎng)的同時(shí)也促進(jìn)了數(shù)據(jù)分析技術(shù)的快速發(fā)展，企業(yè)通過(guò)使用這些數(shù)據(jù)分析技術(shù)進(jìn)一步挖掘出高價(jià)值的用戶信息。與此同時(shí)，用戶的隱私面臨著更加巨大的威脅。由此可見(jiàn)，收集并分析用戶數(shù)據(jù)是一把雙刃劍。由第三方來(lái)收集用戶數(shù)據(jù)可能使用戶的隱私數(shù)據(jù)安全得不到保障，如果收集的數(shù)據(jù)不夠精準(zhǔn)又不利于企業(yè)對(duì)用戶數(shù)據(jù)進(jìn)行分析，這無(wú)法幫助企業(yè)提高企業(yè)服務(wù)質(zhì)量或支持企業(yè)事件決策。雖然這可以給用戶提供個(gè)性化的服務(wù)，提高服務(wù)質(zhì)量和精度，但是在數(shù)據(jù)收集、使用以及發(fā)布的過(guò)程中，用戶隱私不可避免地暴露在外。盡管有些數(shù)據(jù)集被分享或被發(fā)布出來(lái)之前，數(shù)據(jù)集中的較敏感的標(biāo)識(shí)符屬性已經(jīng)被刪除了，具有一定背景知識(shí)的攻擊者還是可以通過(guò)找到數(shù)據(jù)集之間的聯(lián)系來(lái)獲取用戶的個(gè)人信息，用戶的隱私安全也就得不到充分的保障。歷史上就有很多公開(kāi)數(shù)據(jù)暴露用戶隱私的案例，例如AOL 和Netflix 隱私泄露事件。

現(xiàn)有隱私保護(hù)技術(shù)主要包括：基于k-anonymity 的隱私保護(hù)、基于l-diversity 的隱私保護(hù)、基于t-close?ness 的隱私保護(hù)、ε-differential privacy（差分隱私）等保護(hù)技術(shù)。其中，雖然最早提出來(lái)的k-匿名、l-多樣化、t-closeness 等隱私保護(hù)方法能夠在一定程度上較好地保護(hù)敏感數(shù)據(jù)，但它們均難以抵抗新出現(xiàn)的組合攻擊、前景知識(shí)攻擊等手段。而差分隱私是具有嚴(yán)格的數(shù)學(xué)基礎(chǔ)和對(duì)背景知識(shí)弱依賴。

差分隱私的概念最初是由Dwork C 等人[1]在2006年提出。該方法與其他隱私保護(hù)方法不同，差分隱私最主要的貢獻(xiàn)在于提供了個(gè)人隱私泄露的數(shù)學(xué)定義，其最主要的目的就是在大大降低隱私泄露的同時(shí)提供最大數(shù)據(jù)可用性，并且保證個(gè)人隱私泄露不超過(guò)預(yù)先設(shè)定的隱私預(yù)算ε。

1.1 差分隱私定義和相關(guān)概念

其中，ε為隱私預(yù)算，用于量化算法A輸出結(jié)果或一個(gè)用戶的隱私保護(hù)程度。ε的值越大，隱私泄露的風(fēng)險(xiǎn)就越大。反之，ε越小，隱私泄露的風(fēng)險(xiǎn)就越小。它適用于中心化差分隱私模型和本地化差分隱私模型。在現(xiàn)實(shí)中，個(gè)人用戶的隱私還會(huì)有隨著查詢的次數(shù)增加的風(fēng)險(xiǎn)。

定義3（（ε，δ）-LDP）隨機(jī)算法A 滿足（（ε，δ）-LDP），當(dāng)且僅當(dāng)所有用戶端數(shù)據(jù)對(duì)x1和x2，對(duì)于算法A所有可能的輸出結(jié)果S?Range（A）滿足不等式：

當(dāng)δ=0 時(shí)，式（2）為ε-LDP。

定義4 對(duì)于任意一個(gè)函數(shù)?:D→Rd，則函數(shù)的全局敏感度為：

1.2 組合原理

差分隱私機(jī)制的組合有兩種類型，一種是串行組合，另一種是并行組合。

定理2 并行組合原理：M1（D1），M2（D2），M3（D3），…，Mn（Dn）分別表示輸入數(shù)據(jù)集為D1，D2，D3，…，Dn的一系列滿足ε-差分隱私。

1.3 兩種實(shí)現(xiàn)機(jī)制

目前，差分隱私主要有兩種實(shí)現(xiàn)機(jī)制：Laplace 機(jī)制[3]與指數(shù)機(jī)制[4]。

（1）拉普拉斯（Laplace）機(jī)制

Laplace 機(jī)制是向真實(shí)的查詢結(jié)果中添加服從La?place 分布的噪聲以實(shí)現(xiàn)滿足ε的差分隱私保護(hù)，適用于數(shù)值型輸出。對(duì)于非連續(xù)型數(shù)據(jù)，例如性別、種族等，拉普拉斯會(huì)輸出無(wú)效的數(shù)據(jù)。對(duì)于這樣的非連續(xù)型數(shù)據(jù)，我們需要借助于指數(shù)算法（Exponential algo?rithm）。

定義5 Laplace 機(jī)制：給定一個(gè)數(shù)據(jù)集D，設(shè)有函數(shù)?:D→R，設(shè)函數(shù)的全局敏感度為Δf，等式（4）隨機(jī)算法M提供ε-差分隱私。

（2）指數(shù)（Exponential）機(jī)制

對(duì)于非數(shù)字查詢，差分隱私使用指數(shù)（Exponential）機(jī)制對(duì)差分結(jié)果進(jìn)行隨機(jī)化，并與得分函數(shù)q(D,φ)，

該函數(shù)評(píng)估輸出?的質(zhì)量。定義得分函數(shù)取決于應(yīng)用程序，并且不同的應(yīng)用程序會(huì)產(chǎn)生不同的得分函數(shù)。

定義6 指數(shù)機(jī)制令q(D,φ)作為數(shù)據(jù)集D的得分函數(shù)，并且得分函數(shù)測(cè)量輸出φ∈φ的質(zhì)量，Δq表示φ的靈敏度，指數(shù)機(jī)制M滿足ε-差分隱私。

2 研究現(xiàn)狀

隱私保護(hù)數(shù)據(jù)發(fā)布是差分隱私的一個(gè)重要研究方向，差分隱私保護(hù)最早是應(yīng)用在數(shù)據(jù)庫(kù)領(lǐng)域。大數(shù)據(jù)時(shí)代下，工業(yè)和互聯(lián)網(wǎng)數(shù)據(jù)呈現(xiàn)爆發(fā)式增長(zhǎng)，如何對(duì)海量數(shù)據(jù)進(jìn)行發(fā)布與分析，從海量數(shù)據(jù)中挖掘出最大價(jià)值的同時(shí)保護(hù)數(shù)據(jù)和個(gè)人隱私安全，已經(jīng)成為數(shù)據(jù)庫(kù)應(yīng)用、數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)、數(shù)據(jù)發(fā)布等領(lǐng)域的研究熱點(diǎn)。

2006 年，Dwork C[1]首次提出了差分隱私的概念和拉普拉斯機(jī)制，并在后來(lái)的文獻(xiàn)中，進(jìn)一步研究和完善差分隱私保護(hù)理論。

Xiao 等人[5]提出了Privelet 小波樹(shù)算法，采用哈爾小波（Haar Wavelet）變換對(duì)原始等寬直方圖進(jìn)行轉(zhuǎn)換，即使用Haar 變換對(duì)屬性取值進(jìn)行變換，然后添加一定規(guī)模的噪聲到變換獲得的哈爾小波系數(shù)，并滿足ε差分隱私。最后使用帶噪的哈爾小波系數(shù)和逆變換得到屬性值對(duì)應(yīng)的帶噪計(jì)數(shù)值。

Xiao 等人[6]提出了一種多維差分隱私直方圖發(fā)布算法DPCube，可支持多維的單位長(zhǎng)度與較長(zhǎng)范圍計(jì)數(shù)查詢。該算法首先是使用單元?jiǎng)澐旨夹g(shù)，對(duì)原始數(shù)據(jù)集進(jìn)行分割，并給每個(gè)單元的統(tǒng)計(jì)信息添加適量的拉普拉斯噪聲，然后使用kd-樹(shù)結(jié)構(gòu)對(duì)所有添加噪聲后的單元進(jìn)行后置處理，即重新劃分，最后獲得多維V-優(yōu)化直方圖。

Hay 等人[7]描述了一種有效的算法，用于發(fā)布網(wǎng)絡(luò)度分布的可證明的私有估計(jì)。這是第一次將差分隱私保護(hù)應(yīng)用到圖結(jié)構(gòu)中對(duì)結(jié)點(diǎn)的度進(jìn)行約束。

Rastogi 等人[8]提出的FPA 是一種基于有損壓縮的離散傅立葉變換方法，該方法可以較好地支持單位長(zhǎng)度的范圍計(jì)數(shù)查詢，只用于一維直方圖轉(zhuǎn)換且查詢精度低。

2012 年，Acs 對(duì)Rastogi 的FPA 提出了一種改進(jìn)地具有自適應(yīng)的傅立葉變換算法EFPA，通過(guò)添加打分函數(shù)和差分隱私指數(shù)機(jī)制，保證了數(shù)據(jù)發(fā)布的準(zhǔn)確性。

Acs 等人[9]對(duì)FPA 進(jìn)行改進(jìn)和優(yōu)化，提出了具有自適應(yīng)性的傅立葉變換算法EFPA。該方法將傅立葉變換應(yīng)用于直方圖，并通過(guò)使用指數(shù)機(jī)制去除高頻分量來(lái)對(duì)其進(jìn)行壓縮，通過(guò)為指數(shù)機(jī)制設(shè)計(jì)更精確地得分函數(shù)并利用實(shí)值直方圖的傅立葉系數(shù)之間的內(nèi)在相關(guān)性來(lái)提高FPA 的性能。該文獻(xiàn)還提出了P-HPartition，它使用可分割的分層聚類（分區(qū)）方案來(lái)壓縮直方圖。

Xu 等人[10]提出兩個(gè)方法，即NoiseFirst 和Struc?tureFirst，用于計(jì)算符合DP 的直方圖，并且均支持較長(zhǎng)范圍計(jì)數(shù)查詢，并且查詢精度較高。它們主要的區(qū)別是噪聲注入的順序和直方圖結(jié)構(gòu)的計(jì)算步驟。Noise?First 首先向原始數(shù)據(jù)或其統(tǒng)計(jì)信息中添加適量的噪聲，然后對(duì)含噪數(shù)據(jù)集運(yùn)用規(guī)劃策略。StructureFirst 則是先對(duì)原始直方圖進(jìn)行轉(zhuǎn)換或有損壓縮，并得到V-優(yōu)化直方圖，再向轉(zhuǎn)換后的數(shù)據(jù)集添加噪聲。

Fan 等人[11]提出了FAST，這是一種基于過(guò)濾和自適應(yīng)采樣在差分隱私下發(fā)布實(shí)時(shí)聚合統(tǒng)計(jì)信息的新穎框架。為了最大程度地降低總體隱私成本，F(xiàn)AST 根據(jù)檢測(cè)到的數(shù)據(jù)動(dòng)態(tài)自適應(yīng)地對(duì)長(zhǎng)時(shí)間序列進(jìn)行采樣。為了提高每個(gè)時(shí)間戳的數(shù)據(jù)發(fā)布準(zhǔn)確性，F(xiàn)AST 預(yù)測(cè)了非采樣點(diǎn)的數(shù)據(jù)值，并校正了采樣點(diǎn)的噪聲觀測(cè)值。

Su 等人[12]提出了PrivPfC，這是一種用于發(fā)布數(shù)據(jù)以進(jìn)行分類的新的差分私有方法。

Yan 等人[13]提出了一種用于大位置數(shù)據(jù)發(fā)布的自適應(yīng)采樣機(jī)制和隱私保護(hù)方法，并設(shè)計(jì)了一種基于比例積分微分（PID）控制器的自適應(yīng)采樣機(jī)制。為了確保已發(fā)布數(shù)據(jù)的隱私，他們又提出了一種啟發(fā)式四叉樹(shù)劃分方法以及相應(yīng)的隱私預(yù)算分配策略。在2020年，他們又提出了一種基于有前途的深度學(xué)習(xí)范式的集中發(fā)布大位置數(shù)據(jù)的發(fā)布間隔預(yù)測(cè)方法[14]。

3 其他研究方向

目前差分隱私保護(hù)還應(yīng)用在推薦系統(tǒng)、社交網(wǎng)絡(luò)等方面的數(shù)據(jù)發(fā)布。

（1）基于差分隱私保護(hù)的推薦系統(tǒng)。

推薦系統(tǒng)是使用數(shù)據(jù)挖掘、機(jī)器學(xué)習(xí)等技術(shù)，首先收集用戶的歷史行為數(shù)據(jù)，如購(gòu)物記錄、商品評(píng)論、搜索記錄等個(gè)人信息，從這些數(shù)據(jù)中挖掘有價(jià)值的信息進(jìn)行分析和建模，最后當(dāng)用戶瀏覽信息時(shí)實(shí)現(xiàn)精準(zhǔn)地向不同用戶推薦個(gè)性化的信息。個(gè)人歷史行為等數(shù)據(jù)的采集過(guò)程中，用戶隱私存在數(shù)據(jù)泄露的安全隱患。為了解決這一問(wèn)題，差分隱私開(kāi)始在推薦系統(tǒng)中廣泛應(yīng)用，但是目前的研究都是基于降低推薦精度為代價(jià)來(lái)提高隱私保護(hù)強(qiáng)度。因此，如何在實(shí)現(xiàn)隱私保護(hù)和推薦質(zhì)量之間的平衡是今后的一個(gè)研究重點(diǎn)。

（2）基于差分隱私保護(hù)的社交網(wǎng)絡(luò)。

互聯(lián)網(wǎng)的飛速發(fā)展使得現(xiàn)實(shí)個(gè)體之間的聯(lián)系加強(qiáng)，個(gè)人在網(wǎng)絡(luò)中形成了不同的社交網(wǎng)絡(luò)，而這些社交網(wǎng)絡(luò)中包含了很多敏感信息，例如個(gè)人信息和朋友關(guān)系等，現(xiàn)有攻擊者可以通過(guò)個(gè)體之間的聯(lián)系來(lái)推測(cè)朋友關(guān)系和其他敏感信息。目前，差分隱私開(kāi)始成為解決社交網(wǎng)絡(luò)隱私保護(hù)方法之一，但是它對(duì)于數(shù)據(jù)集中記錄之間的關(guān)聯(lián)關(guān)系保護(hù)程度較低。因此，基于差分隱私設(shè)計(jì)更好地保護(hù)關(guān)聯(lián)數(shù)據(jù)間的敏感信息成為今后研究的一個(gè)重要方向。

4 結(jié)語(yǔ)

差分隱私保護(hù)是一種通用且具有堅(jiān)實(shí)理論基礎(chǔ)的隱私保護(hù)方法，它解決了很多傳統(tǒng)加密等方法無(wú)法解決的問(wèn)題，可以防止基于背景知識(shí)的攻擊，目前其引起了眾多學(xué)者的研究興趣，應(yīng)用領(lǐng)域也越來(lái)越廣泛。

本文簡(jiǎn)要介紹了差分隱私保護(hù)在數(shù)據(jù)發(fā)布領(lǐng)域的研究歷程和其他研究點(diǎn)，隨著機(jī)器學(xué)習(xí)等技術(shù)的發(fā)展，差分隱私保護(hù)將會(huì)在更多領(lǐng)域保護(hù)用戶個(gè)人隱私數(shù)據(jù)安全。