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

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

0 引言

我們在享受著推薦算法、圖像識別、語音識別等智能技術(shù)發(fā)展帶來的紅利的同時，數(shù)據(jù)在其背后承擔(dān)著推動技術(shù)不斷迭代的關(guān)鍵角色。

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

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

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

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

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

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

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

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

1.2 組合原理

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

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

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

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

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

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

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

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

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

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

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

2 研究現(xiàn)狀

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

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

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

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

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

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

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

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

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

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

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

Yan 等人[13]提出了一種用于大位置數(shù)據(jù)發(fā)布的自適應(yīng)采樣機(jī)制和隱私保護(hù)方法，并設(shè)計了一種基于比例積分微分（PID）控制器的自適應(yīng)采樣機(jī)制。為了確保已發(fā)布數(shù)據(jù)的隱私，他們又提出了一種啟發(fā)式四叉樹劃分方法以及相應(yīng)的隱私預(yù)算分配策略。在2020年，他們又提出了一種基于有前途的深度學(xué)習(xí)范式的集中發(fā)布大位置數(shù)據(jù)的發(fā)布間隔預(yù)測方法[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ù)，如購物記錄、商品評論、搜索記錄等個人信息，從這些數(shù)據(jù)中挖掘有價值的信息進(jìn)行分析和建模，最后當(dāng)用戶瀏覽信息時實現(xiàn)精準(zhǔn)地向不同用戶推薦個性化的信息。個人歷史行為等數(shù)據(jù)的采集過程中，用戶隱私存在數(shù)據(jù)泄露的安全隱患。為了解決這一問題，差分隱私開始在推薦系統(tǒng)中廣泛應(yīng)用，但是目前的研究都是基于降低推薦精度為代價來提高隱私保護(hù)強(qiáng)度。因此，如何在實現(xiàn)隱私保護(hù)和推薦質(zhì)量之間的平衡是今后的一個研究重點(diǎn)。

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

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

4 結(jié)語

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

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