[[375638]]

物聯(lián)網(wǎng)會感知大量數(shù)據(jù)，感知數(shù)據(jù)通常需要發(fā)布和共享。但數(shù)據(jù)在發(fā)布和共享時面臨巨大的隱私泄露風險。隨著數(shù)據(jù)挖掘技術的不斷提高，經(jīng)過隱私保護的物聯(lián)網(wǎng)數(shù)據(jù)中的敏感信息也越來越容易被數(shù)據(jù)挖掘者獲取，因此，如何保護發(fā)布數(shù)據(jù)中的隱私問題，成為了一個新的研究熱點。

從根本上來講，數(shù)據(jù)發(fā)布隱私保護就是在數(shù)據(jù)發(fā)布的同時，盡可能地保護發(fā)布數(shù)據(jù)中的隱私信息。差分隱私作為目前數(shù)據(jù)發(fā)布隱私保護的一個標準，它能夠在數(shù)據(jù)發(fā)布的過程中，對原始數(shù)據(jù)進行一定的處理，從而達到保護原始數(shù)據(jù)中敏感信息的目的。簡單來說，差分隱私數(shù)據(jù)發(fā)布就是數(shù)據(jù)擁有者將數(shù)據(jù)通過某種形式向外界展示，并利用差分隱私技術對數(shù)據(jù)中的隱私信息進行保護的過程。

01 差分隱私的概念

差分隱私是目前數(shù)據(jù)發(fā)布隱私保護技術中具有強大理論保證和嚴格數(shù)學證明的隱私保護模型。差分隱私保護是對數(shù)據(jù)添加擾動保護的一種保護技術，它可以不考慮攻擊者的背景知識，通過添加一定規(guī)律的噪聲來保證數(shù)據(jù)集的統(tǒng)計特征不變，同時也對數(shù)據(jù)集進行了保護，方便研究者在數(shù)據(jù)進行保護以后對數(shù)據(jù)進行一些挖掘、統(tǒng)計工作，不泄露用戶的隱私。

差分隱私具有嚴格的數(shù)學證明，該機制可以確保在對數(shù)據(jù)進行保護以后不會影響輸出結果的統(tǒng)計特性，攻擊者無法判斷該用戶是不是在該數(shù)據(jù)集中，因為使用差分隱私保護以后對于數(shù)據(jù)的查詢結果在形式上不可區(qū)分，所以保證了用戶的個人隱私信息不被泄露。

差分隱私可以增加或刪除數(shù)據(jù)庫中的一條記錄，使得攻擊者在具有任何知識背景的情況下都無法判斷某條記錄是否存在于正在被分析的數(shù)據(jù)庫中。假設存在一個數(shù)據(jù)表，如圖1所示，該數(shù)據(jù)是某醫(yī)院的門診病歷記錄，其中包括病人的姓名、年齡、性別、臨床診斷等信息，圖1（a）是原始數(shù)據(jù)記錄的直方圖發(fā)布形式。如果攻擊者想要知道Cole的診斷情況，并且具有強大的背景知識，如攻擊者已經(jīng)知道Cole的性別為男、年齡在60~80歲之間，以及其他人的臨床診斷信息，那么攻擊者將能夠推斷出Cole的臨床診斷信息，從而導致Cole的隱私信息被泄露。差分隱私想要解決的也正是這類問題，即在攻擊者具有任何背景知識的情況下，都不會泄露數(shù)據(jù)集中的隱私信息。

圖1（b）給出了經(jīng)過差分隱私技術處理過的直方圖發(fā)布的結果，從圖中可以看出，即使攻擊者知道年齡在60~80歲之間除了Cole以外所有人的信息，他也沒辦法獲取Cole的診斷信息。

圖1  醫(yī)院門診病歷記錄（統(tǒng)計數(shù)據(jù)直方圖發(fā)布）

差分隱私：經(jīng)典的差分隱私（DP）最初是基于數(shù)據(jù)集提出的隱私保護概念，它可為數(shù)據(jù)隱私的保護效果提供嚴格的信息論層次的保證。DP以概率的形式描述原始數(shù)據(jù)集的微小變化對最終統(tǒng)計輸出的影響，并通過隱私參數(shù)￡來約束這一概率變化，達到隱私保護的目的。

假設D是具有n個記錄、d個屬性的數(shù)據(jù)集，并且假設變量r表示數(shù)據(jù)集中的一條記錄。兩個數(shù)據(jù)集D和D′是兄弟數(shù)據(jù)集，即如果它們有相同的屬性，并且只有一個記錄不同，令ri表示這個記錄，Di表示帶有ri記錄的數(shù)據(jù)集，D-i表示刪除ri記錄的數(shù)據(jù)集，則差分隱私定義如下。

ε-差分隱私：對于差別至多為一個記錄的兩個數(shù)據(jù)集D和D′，Range(A)表示一個隨機函數(shù)A的取值范圍，Pr[Es]表示事件Es的披露風險，若隨機函數(shù)A提供ε-差分隱私保護，則對于所有的S⊆Range(A)，都滿足如下所示：

如圖2所示，算法通過添加一些規(guī)律的噪聲來實現(xiàn)差分隱私，同時保證在刪除或者添加某一條記錄的時候，查詢的一些統(tǒng)計概率不發(fā)生變化，從而保護了用戶之間的隱私信息。

圖2  隨機算法在鄰近數(shù)據(jù)集上的輸出概率

（ε,δ）-差分隱私：對于差別至多為一個記錄的兩個數(shù)據(jù)集D和D′，Range(A)表示一個隨機函數(shù)K的取值范圍，Pr[Es]表示事件Es的披露風險，若隨機函數(shù)A提供（ε,δ）差分隱私保護，則對于所有的S⊆Range(A)，都滿足如下所示：

其中，D和D′表示相鄰數(shù)據(jù)集，根據(jù)相鄰數(shù)據(jù)集的差異，可將差分隱私分為有界差分隱私（Bounded Differential Privacy，BDP）和無界差分隱私（Unbounded Differential Privacy，UDP）。在BDP中，D和D′是相鄰數(shù)據(jù)集，可以通過替代D′中的一個實體而得到D。在UDP中，D和D′是相鄰數(shù)據(jù)集，可以通過添加或刪除D′中的一個實體而得到D。BDP中的相鄰數(shù)據(jù)集具有相同的大小，而UDP中卻沒有這個約束。

（ε,δ）-差分隱私是ε-差分隱私的松弛版本，其允許違反隱私的概率被參數(shù)δ控制在一個很小的范圍內(nèi)。這個定義的隱私保護在ε-差分隱私帶來過量噪聲而導致較低的效用性的場景中，可以展現(xiàn)出明顯的優(yōu)勢。

差分隱私能通過添加隨機噪聲來實現(xiàn)查詢操作，這個被添加的噪聲是隱私參數(shù)ε的一個函數(shù)，這個查詢的性質(zhì)被稱為敏感度。敏感度的類型會隨著兩個相鄰的數(shù)據(jù)庫的查詢結果而改變，在大多數(shù)情況下，我們會將全局敏感度作為決定查詢結果安全性的一個重要的參數(shù)。

ε表示隱私預算，是衡量隱私保護強度的參數(shù)。由上圖可知，ε值越小，算法的隱私保護程度就越強。反之，隱私保護程度就越弱。差分隱私保證了無論數(shù)據(jù)庫中任意一條記錄存在與否，對算法的輸出分布幾乎沒有影響。

相鄰數(shù)據(jù)集：若D與D′為相鄰數(shù)據(jù)集，則D可通過D′添加、刪除或修改一個數(shù)據(jù)元組得到。

從上述定義可以看出，對于任意兩個相鄰的數(shù)據(jù)集，它們輸出同一結果的概率比率差距介于e-ε和eε之間；由此可知，參數(shù)ε對控制隱私泄露量起著至關重要的作用。

基于DP的定義，學者們設計出一些滿足要求的隨機化機制；在相同的ε水平下，機制的設計和適用性會極大地影響隱私化數(shù)據(jù)的可用性。

全局敏感度：對于給定的查詢函數(shù)f:Dn→Rd，f的Lp全局敏感度定義為：

GSf=maxD,D′||f(D)-f(D′)||p

數(shù)據(jù)集D和D′之間最多相差一條數(shù)據(jù)記錄。

局部敏感度：對于給定的查詢函數(shù)f:Dn→Rd，其中D∈Dn，D的Lp局部敏感度定義為：

LSf(D)=maxD′|| f(D)-f(D′)||p

對于一些查詢操作函數(shù)f，得到的∆f都是比較小的，對于計數(shù)查詢函數(shù)來說∆f=1，并且這個屬性和查詢函數(shù)有關，和數(shù)據(jù)集的屬性無關，可以通過這個屬性來對數(shù)據(jù)集進行發(fā)布操作，即進行多種函數(shù)操作以使數(shù)據(jù)集滿足數(shù)據(jù)保護要求，一般使用拉普拉斯機制和指數(shù)機制進行差分隱私保護。

差分隱私算法具有組合特性，即幾個滿足差分隱私的獨立算法通過組合得到的算法仍滿足差分隱私。差分隱私的組合特性保證了一系列差分隱私算法計算的隱私，根據(jù)這個特性可得出以下性質(zhì)。

順序組合（Sequential Composition）：如果一個機制M由多個子機制構成，如M=（M1,M2,…,Mn），其中Mi滿足εi-差分隱私，那么機制M滿足εi-差分隱私，其中

并行組合（Parallel Composition）。如果數(shù)據(jù)庫中的每個不相交的子集Di在機制Mi下都滿足εi-差分隱私，那么

在機制Mi下也滿足εi-差分隱私。

02 差分隱私保護模型

差分隱私數(shù)據(jù)發(fā)布主要有兩種保護模型：交互式保護模型和非交互式保護模型。如圖3所示，在交互式保護模型下，數(shù)據(jù)擁有者根據(jù)實際需要設計滿足差分隱私的數(shù)據(jù)發(fā)布算法A，當用戶向服務器發(fā)出查詢請求Q時，在隱私預算沒有消耗完的情況下，返回給用戶的查詢結果將經(jīng)過差分隱私算法A添加一定量的噪聲，即用戶獲得的查詢結果是添加噪聲后的答案，而不是真實答案。這種交互式保護模型具有時效性較好的特點，能夠及時更新數(shù)據(jù)庫并實時返回查詢結果。但該模型存在的問題就是隱私預算消耗過快，需要利用有限的隱私預算盡可能多地對查詢請求進行回答，這其中也涉及如何為每次查詢分配隱私預算的問題。

圖3  交互式保護模型

圖4所示為差分隱私數(shù)據(jù)發(fā)布的非交互式保護模型。數(shù)據(jù)擁有者首先利用差分隱私算法A對要發(fā)布的數(shù)據(jù)進行隱私保護，然后形成一個新的合成數(shù)據(jù)庫，合成數(shù)據(jù)庫與原始數(shù)據(jù)庫具有相似的統(tǒng)計特征。此時，用戶所有的查詢以及數(shù)據(jù)挖掘等操作都是在合成數(shù)據(jù)庫上進行的，以保證原始數(shù)據(jù)中的隱私信息不被泄露。這種模型的特點就是不限制用戶的查詢次數(shù)，但會導致數(shù)據(jù)發(fā)布的可用性較低、數(shù)據(jù)查詢的時效性較差。

圖4  非交互式保護模型

03 差分隱私數(shù)據(jù)發(fā)布機制

任何滿足差分隱私定義的機制都可以被看作差分隱私數(shù)據(jù)發(fā)布機制，目前很多差分隱私數(shù)據(jù)發(fā)布機制被提出，如拉普拉斯機制、指數(shù)機制、中位數(shù)機制、矩陣機制等，但拉普拉斯機制和指數(shù)機制是在差分隱私數(shù)據(jù)發(fā)布中應用最廣泛的兩種機制。這兩種機制都可以在滿足差分隱私的情況下，對發(fā)布的數(shù)據(jù)進行隱私保護。此外還有敏感數(shù)據(jù)集發(fā)布機制和非敏感數(shù)據(jù)集發(fā)布機制。

（1）拉普拉斯機制

拉普拉斯機制（Laplace Mechanism）適用于輸出結果是數(shù)值型的查詢函數(shù)。該機制通過在真實的輸出結果中添加合適的拉普拉斯噪聲以獲得差分隱私，噪聲是根據(jù)滿足概率分布

的拉普拉斯分布LAP(λ)而產(chǎn)生的，其中λ是分布的規(guī)模因子，其值取決于全局敏感度∆f和預期的差分隱私變量ε，該分布的方差為σ2=2λ2。下面的定理與定義具體給出了這些變量之間的關系。

對于任意的f:Dn→Rd，當

時，添加滿足拉普拉斯分布LAP(λ)的機制的輸出結果滿足ε-差分隱私。

拉普拉斯機制：若一個機制M滿足ε-差分隱私，并且在數(shù)據(jù)集D上存在一個函數(shù)f:D→R，則拉普拉斯機制可表示為：

M（D）=f（D）+LAP（∆/ε）

拉普拉斯機制的原理就是向真實的數(shù)據(jù)中加入獨立的拉普拉斯噪聲，該噪聲由尺度參數(shù)為λ的拉普拉斯概率密度函數(shù)產(chǎn)生。如果用LAP（λ）表示拉普拉斯噪聲，則拉普拉斯機制有如下定義：

（2）指數(shù)機制

對于非數(shù)值型數(shù)據(jù)，差分隱私利用指數(shù)機制對結果進行隨機化的處理，并用一個打分函數(shù)q（D,Φ）來評估輸出Φ的質(zhì)量。另外，由于打分函數(shù)依賴于實際的應用，因此不同的應用會有不同的打分函數(shù)，這導致沒有一個通用的打分函數(shù)可以利用。

指數(shù)機制（Exponential Mechanism）：令q（D,Φ）表示數(shù)據(jù)集D的一個打分函數(shù)，該函數(shù)可以度量輸出Φ的質(zhì)量。∆q表示輸出Φ的敏感度，當指數(shù)機制M滿足下式時，其滿足差分隱私。

在實際應用中，有許多查詢函數(shù)的輸出結果是非數(shù)值型的，這導致添加拉普拉斯噪聲沒有任何意義。為此，部分學者提出了指數(shù)機制以實現(xiàn)非數(shù)值型數(shù)據(jù)的差分隱私保護，并設計了可以獲得更好查詢響應的應用場景。首先定義一個效用函數(shù)u:(D×τ)→R，向輸出域R中的輸出r中添加實數(shù)值噪聲。這里，數(shù)值越大表示效用性越好。然后以滿足

的概率選擇一個輸出r∈R，其中，∆u=maxD,D′,∀r|u(D,r)−u(D′,r)|是效用函數(shù)的敏感度。由于u值越大越容易被選擇，因此該機制可以看作對u的最優(yōu)化。此外，效用函數(shù)對數(shù)據(jù)庫中單條記錄的改變是不敏感的。

下面給出一個具體的實例來說明指數(shù)機制。假如班級舉辦運動會，需要挑選一個項目來進行比賽，為了保護投票的信息不被泄露，因為最后得到的結果不是數(shù)值型的，所以使用指數(shù)機制進行保護；對票數(shù)進行計數(shù)統(tǒng)計時，很顯然函數(shù)的∆q=1，因此，按照指數(shù)機制的要求對表1中的投票結果進行保護，即可算出各個項目的概率值。

表1  指數(shù)機制應用實例

從上表的計算結果可以看出，當隱私保護參數(shù)比較大的時候，輸出結果的概率值也比較大，同時，如果隱私保護參數(shù)變小的話，則最后的結果會趨于相等。

對于任意的查詢函數(shù)u:(D×τ)→R，指數(shù)機制以

的概率選擇一個輸出r時可以保證ε-差分隱私。

（3）敏感候選集發(fā)布機制

針對敏感候選集，因為里面包含的不僅是群體用戶的行為特征區(qū)域，還有用戶之間的關聯(lián)位置信息，所以為了重點保護用戶的位置信息不被攻擊者推斷攻擊而泄露用戶的位置關聯(lián)信息，針對敏感候選集提出了關聯(lián)敏感度差分隱私保護方法，即對差分隱私中的全局敏感度進行改進，進而減少噪聲的引入。然后對敏感候選集中的所有聚類簇進行隱私保護，以保護用戶的關聯(lián)位置隱私。上文得到了用戶個體的關聯(lián)敏感度，并且根據(jù)得到的敏感候選集的關聯(lián)屬性的強弱可以合理地分配ε的大小，保證數(shù)據(jù)保護的隱私預算滿足差分隱私的要求。針對每個敏感候選集中的用戶個體進行個性化重點保護，對于那些關聯(lián)信息比較強的用戶，使用比較強的機制進行數(shù)據(jù)保護；對于那些關聯(lián)性比較弱的用戶，使用相對弱的機制進行數(shù)據(jù)保護，進而把用戶的關聯(lián)信息降到一個可接受的范圍之內(nèi)，這樣攻擊者進行關聯(lián)攻擊的時候，可以得到用戶的關聯(lián)屬性的個數(shù)就會大大減少。

在處理完用戶的敏感候選集以后，得到的數(shù)據(jù)既保護了用戶的位置信息，又保護了用戶的關聯(lián)信息，并且把數(shù)據(jù)操作轉(zhuǎn)化到了矩陣上進行，這使得算法的復雜度進一步降低。

（4）非敏感候選集發(fā)布機制

針對非敏感候選集的用戶位置數(shù)據(jù)，主要是對其中的非停留點位置數(shù)據(jù)進行隱私保護。用戶的非停留點包含了大量的路徑問題，如果不加以保護，則會使用戶的隱私信息泄露。針對用戶軌跡點，雖然其也有一部分的關聯(lián)信息，但是并沒有停留區(qū)域表現(xiàn)得那么嚴重。如果對用戶的軌跡點單純地使用差分隱私的拉普拉斯噪聲進行處理，則會在現(xiàn)有的軌跡位置上形成毛刺點，這樣很難抵抗攻擊者的濾波攻擊。因此，這里針對這個問題使用了指數(shù)機制，并且在極坐標系下結合用戶位置的速度和方向因素來添加相鄰位置點的噪聲，使得噪聲的添加更能保護用戶的隱私，對抗濾波攻擊。算法主要是針對相鄰位置點，計算出下一個點的速度、方向和距離，然后把笛卡爾坐標系轉(zhuǎn)換成極坐標系進行不同維度的噪聲添加，這樣添加的噪聲更加符合現(xiàn)實生活的要求，并且對于攻擊者有更好的抵抗能力。這樣得到的數(shù)據(jù)就可以防止攻擊者的濾波攻擊，使得在添加了保護的基礎上還維護了數(shù)據(jù)集的可用性，還能使得隱私保護和數(shù)據(jù)集的可用性都有一個很好的平衡。

04 數(shù)據(jù)發(fā)布面臨的挑戰(zhàn)

目前，雖然許多研究人員致力于數(shù)據(jù)發(fā)布隱私保護技術的研究，但隨著信息技術的發(fā)展，數(shù)據(jù)的規(guī)模不斷增大，數(shù)據(jù)種類也變得更加復雜多樣，尤其是隨著數(shù)據(jù)挖掘技術水平的提高，隱私保護技術在數(shù)據(jù)發(fā)布中的研究意義更加凸顯。差分隱私作為數(shù)據(jù)發(fā)布隱私保護技術的標準，對于解決當前數(shù)據(jù)發(fā)布與隱私保護之間的矛盾至關重要。因此，研究更好的差分隱私數(shù)據(jù)發(fā)布方法有著重要的現(xiàn)實意義。綜上可知，現(xiàn)有差分隱私數(shù)據(jù)發(fā)布主要面臨的挑戰(zhàn)如下。

（1）數(shù)據(jù)類型的變化

目前由于現(xiàn)實生活中的許多應用都傾向于動態(tài)的產(chǎn)生并發(fā)布數(shù)據(jù)，與之前相比，數(shù)據(jù)類型由靜態(tài)轉(zhuǎn)為了動態(tài)，這導致之前提出的許多差分隱私數(shù)據(jù)發(fā)布方法并不適用于當前的動態(tài)數(shù)據(jù)發(fā)布。如果用靜態(tài)數(shù)據(jù)的發(fā)布方法來發(fā)布動態(tài)數(shù)據(jù)，就可能會由隱私預算有限而導致發(fā)布數(shù)據(jù)的可用性極差。即使目前已提出一些適用于動態(tài)數(shù)據(jù)發(fā)布的差分隱私方法，但動態(tài)數(shù)據(jù)發(fā)布的可用性仍有待提高。

（2）隱私預算的分配

在差分隱私數(shù)據(jù)發(fā)布中，隱私預算的分配和數(shù)據(jù)的發(fā)布效用息息相關，尤其在動態(tài)數(shù)據(jù)的發(fā)布過程中，如果不能合理分配有限的隱私預算，就可能會導致動態(tài)數(shù)據(jù)發(fā)布的效用變差。現(xiàn)有差分隱私動態(tài)數(shù)據(jù)發(fā)布方法大部分采用了比較樸素的方法來分配隱私預算，如將隱私預算以均勻、遞增或遞減的方式分配到需要發(fā)布的采樣點上，而并沒有根據(jù)動態(tài)數(shù)據(jù)的特點將有限的隱私預算進行合理的分配，從而導致隱私預算過早耗盡或浪費。因此，如何在動態(tài)數(shù)據(jù)發(fā)布中合理分配有限的隱私預算成為了差分隱私動態(tài)數(shù)據(jù)發(fā)布面臨的一個挑戰(zhàn)。