基于差分隱私的隱私保護數據發布研究綜述

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

（1.四川大學計算機學院，成都610065；2.四川虹微技術有限公司，成都610000）

0 引言

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

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

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

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

1.1 差分隱私定義和相關概念

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

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

當δ=0 時，式（2）為ε-LDP。

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

1.2 組合原理

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

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

1.3 兩種實現機制

目前，差分隱私主要有兩種實現機制：Laplace 機制[3]與指數機制[4]。

（1）拉普拉斯（Laplace）機制

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

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

（2）指數（Exponential）機制

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

該函數評估輸出?的質量。定義得分函數取決于應用程序，并且不同的應用程序會產生不同的得分函數。

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

2 研究現狀

隱私保護數據發布是差分隱私的一個重要研究方向，差分隱私保護最早是應用在數據庫領域。大數據時代下，工業和互聯網數據呈現爆發式增長，如何對海量數據進行發布與分析，從海量數據中挖掘出最大價值的同時保護數據和個人隱私安全，已經成為數據庫應用、數據挖掘、機器學習、數據發布等領域的研究熱點。

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

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

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

Hay 等人[7]描述了一種有效的算法，用于發布網絡度分布的可證明的私有估計。這是第一次將差分隱私保護應用到圖結構中對結點的度進行約束。

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

2012 年，Acs 對Rastogi 的FPA 提出了一種改進地具有自適應的傅立葉變換算法EFPA，通過添加打分函數和差分隱私指數機制，保證了數據發布的準確性。

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

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

Fan 等人[11]提出了FAST，這是一種基于過濾和自適應采樣在差分隱私下發布實時聚合統計信息的新穎框架。為了最大程度地降低總體隱私成本，FAST 根據檢測到的數據動態自適應地對長時間序列進行采樣。為了提高每個時間戳的數據發布準確性，FAST 預測了非采樣點的數據值，并校正了采樣點的噪聲觀測值。

Su 等人[12]提出了PrivPfC，這是一種用于發布數據以進行分類的新的差分私有方法。

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

3 其他研究方向

目前差分隱私保護還應用在推薦系統、社交網絡等方面的數據發布。

（1）基于差分隱私保護的推薦系統。

推薦系統是使用數據挖掘、機器學習等技術，首先收集用戶的歷史行為數據，如購物記錄、商品評論、搜索記錄等個人信息，從這些數據中挖掘有價值的信息進行分析和建模，最后當用戶瀏覽信息時實現精準地向不同用戶推薦個性化的信息。個人歷史行為等數據的采集過程中，用戶隱私存在數據泄露的安全隱患。為了解決這一問題，差分隱私開始在推薦系統中廣泛應用，但是目前的研究都是基于降低推薦精度為代價來提高隱私保護強度。因此，如何在實現隱私保護和推薦質量之間的平衡是今后的一個研究重點。

（2）基于差分隱私保護的社交網絡。

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

4 結語

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

本文簡要介紹了差分隱私保護在數據發布領域的研究歷程和其他研究點，隨著機器學習等技術的發展，差分隱私保護將會在更多領域保護用戶個人隱私數據安全。