王廣藝，楊 庚

（1.南京郵電大學計算機學院、軟件學院、網(wǎng)絡空間安全學院；2.江蘇省大數(shù)據(jù)安全與智能處理重點實驗室，江蘇南京 210023）

0 引言

頻率估計是數(shù)據(jù)挖掘領域研究的一個基本問題，旨在計算特定數(shù)據(jù)項出現(xiàn)的頻率，有助于云服務運營商了解客戶端軟件最新統(tǒng)計數(shù)據(jù)，檢測惡意軟件行為，也可應用于頻繁出現(xiàn)的數(shù)據(jù)項（heavy hitter）查詢、用戶行為預測等。然而，如果直接采集用戶信息，可能存在嚴重的隱私泄露隱患，攻擊者可通過鏈接攻擊、前景知識攻擊等方式推測用戶持有的數(shù)據(jù)項，不可信的第三方數(shù)據(jù)收集者也可能意外泄露用戶敏感信息。如何高效地兼顧隱私保護與頻率估計準確性是數(shù)據(jù)挖掘領域亟需解決的問題。

差分隱私（Differential Privacy，DP）［1］是一種基于數(shù)據(jù)擾動的隱私保護方法，具有嚴格的數(shù)學定義，可對隱私保護程度進行量化分析；同時，差分隱私無需考慮特殊的攻擊假設，攻擊者無法根據(jù)不同的輸出判斷記錄是否在原數(shù)據(jù)集中。差分隱私分為中心差分隱私（Central Differential Privacy，CDP）和本地差分隱私（Local Differential Privacy，LDP）［2-4］，因而針對頻率估計問題的差分隱私算法包括CDP 頻率估計算法和LDP 頻率估計算法。

在傳統(tǒng)CDP 頻率估計中，數(shù)據(jù)管理員向數(shù)據(jù)庫添加隨機化噪聲，發(fā)布查詢結果。CDP 頻率估計可與機器學習算法深度融合，如頻繁項集挖掘、頻繁序列挖掘、頻繁子圖挖掘等［5］。但是，由于數(shù)據(jù)存儲系統(tǒng)安全性、用戶對數(shù)據(jù)管理員的信任度等因素限制，CDP 頻率估計在實際應用中存在較大局限。

為了應對CDP 頻率估計存在的問題，Kasiviswanathan等［3］于2011 年正式提出LDP。LDP 直接在用戶端擾動數(shù)據(jù)編碼結果，將其發(fā)送至服務器，之后服務器進行統(tǒng)計查詢。由于真實數(shù)據(jù)一直保留在用戶設備端，服務器不需要承擔隱私泄露的風險。LDP 具有輕量化的優(yōu)勢，在計算能力較弱的設備上也能輕松實現(xiàn)。目前LDP 頻率估計已被應用于微軟Windows10 操作系統(tǒng)［6］、小米MIUI 等以提升軟件質量、改進用戶體驗。

但是，LDP 頻率估計也存在通信成本較高、添加的噪聲較多、依賴的用戶規(guī)模較大和高維數(shù)據(jù)分析準確性較低等問題。針對這些問題，已有研究聚焦于如何進一步提高LDP 頻率估計的實用性?，F(xiàn)有方法主要分為三類，第一類是單值頻率估計方法，如Rappor 算法［7］、HCMS 算法［8］等；第二類是泛化頻率估計方法，如DE 算法、OUE 算法、OLH算法等［9］；第三類是集合數(shù)據(jù)頻率估計方法，如LDPMiner算法［10］、SVSM 算法［11］、PrivSet 算法［12］等。本文著重介紹LDP 在這3 種頻率估計中的應用，深入分析不同算法性能，對下一步研究工作進行展望。

1 LDP 頻率估計基礎知識

1.1 本地差分隱私

LDP 是一種強隱私保護方法，該技術可收集單個隨機答案，給予用戶一定的可否認性，也使數(shù)據(jù)收集者免于隱私泄露的風險。同時，通過分析大量該類隨機數(shù)據(jù)，數(shù)據(jù)收集者仍可建立準確的統(tǒng)計模型。

定義1 ε-本地差分隱私［4］。給定算法M，定義域為Domain（M），值域為Range（M）。M滿足本地差分隱私，當且僅當對任意一對輸入t和t’（t，t’∈Domain（M）），成立不等式為：

其中，t*?Range（M）。ε（ε＞0）稱為隱私預算。ε越小表示隱私性越好、可用性越差。

差分隱私有3 個重要特性：①序列組合性［13］。給定z個隱私算法｛f1，f2，…fz｝和數(shù)據(jù)集D，執(zhí)行在D上的fi滿足εi（1≤i≤z）-差分隱私，則z個算法組合算法滿足∑iεi-差分隱私；②并行組合性［13］。將數(shù)據(jù)集D分成z個不相交的子集，D=｛D1，D2，…Dz｝，執(zhí)行在每個子數(shù)據(jù)集上的算法滿足εi（1≤i≤z）-差分隱私，則整個算法滿足max｛εi｝-差分隱私；③后期處理的影響［14］。對差分隱私算法的結果作后期處理，則算法仍滿足差分隱私，且隱私保護水平與原先算法保持一致。

CDP 具備這3 條性質，LDP 兼具第1、3 條性質。LDP沒有直接的并行組合性，因為每個用戶只有1 條記錄，不能被切分。

定義2 敏感度［14］。敏感度是差分隱私中的1 個重要概念。對于任意1 個函數(shù)function：D→Rd，敏感度Δ（func?tion）定義為：

R表示映射的實數(shù)空間，d表示函數(shù)function的查詢維度，D和D’是任意兩個鄰近數(shù)據(jù)集（D和D’差別至多為1個記錄）。

1.2 LDP 頻率估計

LDP 頻率估計指為用戶提供LDP 保護的同時確定數(shù)據(jù)項頻率的過程。給定數(shù)據(jù)集D=｛v1，v2，…vn｝，對任意元素v∈D，算法f的目標是以滿足LDP 的方式計算v出現(xiàn)的頻率。算法f主要分為3 步：①將用戶值編碼成1 個向量或1 個數(shù)；②在用戶端擾動編碼結果；③服務器解碼聚合和校正。隨機響應［15］是算法f采取的主流擾動機制，確保數(shù)據(jù)集在輸出信息時受單條記錄的影響始終低于某個閾值。針對隨機響應舉例如下：當回答1 個二值問題時，回答者秘密地拋擲一枚不均勻的硬幣（正面朝上的概率為Pr，反面朝上的概率為1-Pr，Pr＞0.5）。若正面朝上，回答真實答案；若反面朝上，回答相反答案。根據(jù)LDP 定義，eε=Pr（/1-Pr）。

差分隱私還具有隱私增益性［16］。在設計自適應頻率估計算法時，隱私增益性是否成立是算法選擇的重要指標。隱私增益性表示通過使用更小的采樣率，使算法達到更高的隱私保護水平。具體而言，將差分隱私算法f應用到數(shù)據(jù)集D，利用采樣率β（β＜1）從原始數(shù)據(jù)集中獲得D。為滿足ε-LDP，算法f可使用更大的隱私預算ε’（ε’＞ε）。ε’與ε的關系如式（3）所示。

該性質成立與否取決于算法f的內(nèi)部結構。

1.3 頻繁項集挖掘

頻繁項集挖掘是數(shù)據(jù)挖掘領域的一項重要技術，旨在找出頻繁出現(xiàn)在事務數(shù)據(jù)集中的項集［17］。設D是事務數(shù)據(jù)集，D=｛D1，D2，…Dn｝，D中數(shù)據(jù)項的集合I=｛item1，item2，…itemsize｝，Di?I（1≤i≤n）。設非空集合set?I，則稱set為1個項集。set的支持度是D中包含set的事務計數(shù)。若set的支持度大于預定義閾值λ，則稱set為頻繁項集。頻繁項集具有極重要的單調性：頻繁項集子項集一定是頻繁的，非頻繁項集的超集一定是非頻繁的。

頻繁項集挖掘的經(jīng)典算法包括Apriori 算法［18］、FPGrowth 算法［19］和Eclat 算法［20］。Apriori 算法通過限制產(chǎn)生候選項集挖掘頻繁模式，F(xiàn)P-Growth 算法借助頻繁模式樹發(fā)現(xiàn)頻繁項集，而Eclat 算法采用倒排思想。

項集填充采樣是頻繁項集挖掘過程中常用方法［10］。首先指定長度參數(shù)len、項集itemset、額外項集合dummy=｛i1，i2，…ilen｝，對任意i∈dummy，i?I。額外項在計算頻率時忽略不計。若項集長度|itemset|＜len，則從dummy中隨機挑選len-|itemset|個不同的項添加到itemset中；若|itemset|＞len，則從itemset中均勻采樣len個項構成新項集，如果itemset無序，可直接截斷。將itemset長度統(tǒng)一轉化為len后，從itemset中均勻采樣單個數(shù)據(jù)項輸出，記輸出項為v。

2 LDP 頻率估計性能分析

盡管LDP 頻率估計為用戶和數(shù)據(jù)收集者提供了很強的隱私保證，但是LDP 是以最嚴格的假設為基礎，即假設攻擊者擁有最大背景知識，而這在實際情況中十分罕見。由于LDP 對隱私性的保護過于嚴格，這在很大程度上影響了結果可用性。在許多應用中，LDP 頻率估計也暴露出一些問題，如通信成本較高、隨機化噪聲較多、依賴數(shù)據(jù)量較大和高維數(shù)據(jù)分析準確性較低等，因此，LDP 算法應當再三權衡隱私性、可用性、數(shù)據(jù)量的關系。

受限于用戶設備的網(wǎng)絡和電量等因素，LDP 頻率估計應當維持合理的通信成本。然而，LDP 在用戶端對數(shù)據(jù)的編碼結果通常為1 個向量，為了提高頻率估計的準確性，用戶端應當發(fā)送盡可能多的坐標。此外，在LDP 頻率估計中，用戶可能需要參與多個查詢?nèi)蝿?，用戶和服務器之間會進行多次通信。上述方式將增加通信成本。當用戶記錄是高維數(shù)據(jù)時，通信代價也較高。

由于在CDP 中敏感度是常數(shù)，所以CDP 噪聲為Ω（1）。然而，在LDP 中，任意兩個用戶不知曉對方的記錄，因此，LDP 不存在全局敏感性的概念。LDP 對每個用戶數(shù)據(jù)都添加噪聲，擾動結果被發(fā)送至服務器。即使每個用戶的隨機化噪聲均為常數(shù)，服務器聚合結果的噪聲也會達到Ω（n0.5）（n為用戶個數(shù)）。因此，LDP 和CDP 相比，添加的隨機噪聲較多，這導致準確性較差。

在設計LDP 頻率估計算法時，為了抵消正負向噪聲，服務器需聚合大量的擾動結果，該方法需要較大的數(shù)據(jù)量。然而，在網(wǎng)絡空間安全等領域，用戶規(guī)模較小是常見現(xiàn)象。例如，當一位信息安全工程師正在分析針對特定漏洞的惡意軟件行為時，只有受到惡意軟件感染的用戶的觀察報告才有意義，但由于惡意軟件的針對性，受感染的用戶數(shù)量可能很少。由于用戶規(guī)模無法達到LDP 依賴的數(shù)據(jù)量大小，這會導致統(tǒng)計值與真實結果之間的偏離程度更為明顯。

當用戶記錄是高維數(shù)據(jù)時，即每條用戶記錄包含多個數(shù)據(jù)項，一個直觀的解決方案是分割隱私預算，多次調用LDP 算法分別采集每個位置數(shù)據(jù)項，利用差分隱私序列組合性使算法滿足LDP。然而，由于數(shù)據(jù)高維性，該方案致使每個數(shù)據(jù)項分配到的隱私預算很少，這降低了查詢準確性和查詢效率。

3 頻率估計中的本地差分隱私保護方法

LDP 頻率估計需要解決上述性能分析問題，但是目前LDP 頻率估計方法仍然不能達到這一目的，所以更多的科研人員重點研究怎樣為頻率估計提供更可靠的LDP 保證和更高的查詢準確性。這些研究主要包含3 類方法：單值頻率估計方法、泛化頻率估計方法和集合數(shù)據(jù)頻率估計方法。本文將分別討論這3 種類型的LDP 方法在頻率估計中的應用。

3.1 單值頻率估計

單值頻率估計指每個用戶只有一個數(shù)據(jù)項，用戶將自身數(shù)據(jù)編碼加噪后發(fā)送至服務器，服務器會根據(jù)候選項集合分析大量隨機數(shù)據(jù)，建立統(tǒng)計模型。單值頻率估計主要采用的技術包括哈希函數(shù)和矩陣變換，這兩種技術可以在降低通信成本的前提下獲得合理的統(tǒng)計準確性。谷歌Rappor 算法［7］、蘋果CMS 算法［8］和HCMS 算法［8］均應用了哈希函數(shù)技術，其中HCMS 算法還應用了矩陣變換技術。

3.1.1 Rappor 算法

Rappor 算法將隨機響應與布隆過濾串［21］結合。設布隆過濾串B（也稱比特串）的長度為k，哈希函數(shù)個數(shù)為h。用戶首先使用布隆過濾器將v映射到B，然后使用擾動機制對B添加噪聲。擾動過程分為永久隨機響應和瞬時隨機響應。記永久隨機響應的結果為B’，B’在用戶端被緩存，用戶每次使用真實數(shù)據(jù)時B’會代替B，這樣即使用戶值被報告多次，攻擊者也無法推斷出用戶真實答案。給定概率參數(shù)r，對于B中每個坐標i，有：

記瞬時隨機響應的結果S=（s1，s2，…sk），初始化S為0，指定概率參數(shù)p、q，則：

用戶發(fā)送S。

永久隨機響應滿足ε1-LDP，其中，

在式（6）中，若不考慮布隆過濾器，如果1 個比特串長度為1，Pr（0|0）=Pr（1|1）=1-0.5r，Pr（1|0）=Pr（0|1）=0.5r，則此時隱私保護程度為ln（（1-0.5r）/0.5r）。再經(jīng)過布隆過濾后，每一個原始值被映射到的比特串中最多有h個1，對于兩個原始輸入，它們的比特串最多只有2h位不一樣。因此，式（6）中隱私保護程度需乘以2h。

瞬時隨機響應的結果依賴p，q，r。

瞬時隨機響應滿足ε2-LDP，其中，

為了降低哈希函數(shù)沖突概率，每個用戶被隨機分配到1 個組中。假設有num個組，用戶在發(fā)送數(shù)據(jù)時需說明自己屬于哪個組。由于每個用戶組在布隆過濾器中使用不同的哈希函數(shù)，若num太小，則分組很可能造成哈希函數(shù)值碰撞；若num太大，每個組用戶數(shù)會很少，這導致頻率估計中誤差較大。

現(xiàn)以1 個具體應用案例說明服務器端解碼過程。假設詞庫中只有單詞1、單詞2 和單詞3，對應布隆過濾串分別為10 001 000、01 000 010 和00 010 010。服務器需要統(tǒng)計詞庫中每個單詞出現(xiàn)的次數(shù)。用戶將經(jīng)過永久隨機響應的比特串保存在本地。用戶每使用1 次單詞，就經(jīng)過1次瞬時隨機響應把比特串發(fā)送至服務器。假設單詞1 出現(xiàn)兩次，單詞2 和單詞3 出現(xiàn)1 次，對應比特相加得到比特串bitString=21 012 020。

服務器的目標是確定bitString，它采集每一個比特上1的總數(shù)（一共有k個比特）。由于每個比特相互獨立，服務器可先只分析1 列。設第i個比特有w個1，n-w個0（n為用戶個數(shù)），服務器平均收到的1 的個數(shù)為count。

服務器通過式（10）估計原始值中每個比特1 的個數(shù)，本例中，服務器計算得到bitString=21 012 020。由于每個用戶組哈希函數(shù)公開，服務器了解每個單詞對應的布隆過濾串，結合bitString計算出單詞1 出現(xiàn)兩次，單詞2 和單詞3 均出現(xiàn)1 次。此外，服務器還需借助假設檢驗、最小二乘法和LASSO 回歸進一步擬合詞頻。Rappor 算法中的哈希函數(shù)導致服務器端復雜的解碼過程，而且哈希函數(shù)值碰撞問題依然存在。

3.1.2 CMS 算法

用戶從哈希函數(shù)集合｛h1，h2，…h(huán)k｝中均勻采樣1 個哈希函數(shù)，將項v散列到輸出域中的1 個數(shù)，結果用長度為m的向量vector單熱編碼表示（散列結果對應坐標置為1，其余坐標為0）。用戶對向量中的每個坐標以概率Pr作真實回答，以概率1-Pr作相反回答。用戶將哈希函數(shù)索引與向量發(fā)送至服務器。此時vector 只有一個坐標為1，敏感度為2，所以為滿足差分隱私，Pr取值為：

服務器使用所有來自用戶的向量構建k×m的矩陣Matrix。每當1 個向量到達服務器，服務器將向量添加到Matrix的第j行（j為哈希函數(shù)索引）。服務器取出Matrix［j，hj（v）］（1≤j≤k）并計算均值。

3.1.3 HCMS 算法

HCMS 算法首先類似CMS 算法，用戶得到向量vector。設H為哈達瑪基變換矩陣，vector’=H·vector。vector’中的每個坐標取1 或-1。用戶從vector’中隨機采樣1 個坐標，對該坐標以概率eε/（1+eε）作真實回答。用戶將哈希函數(shù)索引、vector’采樣索引、坐標值發(fā)送至服務器。

服務器使用來自用戶的報告值構建矩陣Matrix。Ma?trix的第（j，index）個元素聚合了用戶使用哈希函數(shù)hj與采樣索引index的坐標值。服務器使用哈達瑪矩陣的逆矩陣對Matrix作矩陣變換，最后計算Matrix［j，hj（v）］（1≤j≤k）k個元素的均值。

HCMS 算法中的矩陣變換與Rappor 算法中的哈希函數(shù)功能類似，可降低通信成本，但是在編碼過程中也會造成額外的信息損失。

3.2 泛化頻率估計

為了比較同等隱私保護水平下不同單值頻率估計算法計算復雜度、查詢準確性和通信成本，需將單值頻率估計推廣到一般情形。泛化頻率估計的核心問題是設計合適的擾動機制。擾動的目的是保證得到頻率的無偏估計，同時盡可能減小統(tǒng)計值方差。該問題的主要挑戰(zhàn)是減小高維數(shù)據(jù)帶來的影響。

Wang 等［9］提出了一個泛化頻率估計機制：pure LDP。pure LDP 首先定義函數(shù)Support，Support（y）表示通過y可以確定出現(xiàn)的用戶值構成的集合。定義概率p*、q*為：

PE是編碼擾動函數(shù)，｛y|v1∈Support（y）｝是v1的支持集合。p*表示任意值v1被映射到v1的支持集合的概率，q*表示任意其他值被映射到v1的支持集合的概率。當且僅當存在概率p*和q*，p*＞q*時，機制pure LDP 成立。為了滿足ε-LDP，q*＞0，p*/q*≤eε。

在pure LDP 中，假設共有n個用戶，元素i出現(xiàn)的真實次數(shù)為c（i），可通過式（14）計算c（i）的無偏估計。

其中yj是用戶j發(fā)送的值。

文獻［9］得到了3 種效果較好的擾動方法：DE、OUE、OLH，具體描述如下：

DE 算法：設用戶值為v，項空間大小為|I|。擾動公式為：

此時Support（i）=｛i｝，p*=p，q*=q。

OUE 算法：用戶項被單熱編碼成向量B。擾動公式為：

因為eε=（p（1-q））/（（1-p）q），所以可作如下變換，ε=ε1+ε2，eε1=p/（1-p），eε2=（1-q）/q。ε1和ε2分別是傳送比特1與比特0 消耗的隱私預算。由于向量中只有1 個坐標為1，因此，用戶在發(fā)送比特0 時應該分配更多的隱私預算。在極端情況下，令ε1=0，ε2=ε，可得到p和q的最優(yōu)值。OUE 的支持函數(shù)Support（B）=｛i|B［i］=1｝，p*=p，q*=q。

OLH 算法：設H為哈希函數(shù)集合，用戶從H中均勻采樣得到函數(shù)function，function將用戶值v映射到［g］=｛0，1，…g-1｝中的一個元素b，其中g≥2。OLH 的信息損失包含兩個方面：編碼階段的信息損失與差分隱私擾動引起的信息損失。當g較大時，LDP 頻率估計算法在編碼階段可保留更多信息，在隨機響應時則損失更多信息。通過對估計值方差求偏微分，OLH 算法得到g的最優(yōu)值為。擾動公式為：

該方法的支持函數(shù)Support（＜function，b’＞）=｛i|function（i）=b’｝，p*=0.5，q*=1/g。

DE 在|I|較小時估計更準確。當|I|較大時，OUE 和OLH表現(xiàn)更好且準確性一致。OUE 計算成本低，通信成本高。OLH 通過應用哈希函數(shù)降低了通信成本，但同時增加了計算復雜度。

為了滿足LDP，添加的噪聲可能導致許多項的估計頻率小于0。此外，LDP 算法可能導致頻率總和不等于1。Wang 等［22］指出服務器可以利用非負性（所有項頻率均大于等于0）和規(guī)范性（頻率總和為1）這一事實提高頻率估計準確性。算法利用先驗分布時，估計會偏向先驗分布。還考慮了多種利用先驗分布的算法，這些算法中有的只要求頻率滿足非負性，有的只要求頻率滿足規(guī)范性，有的要求兩個性質均被滿足。但是引入概率先驗分布又會帶來其它問題。例如，將所有負估計值改為0 可提高個別頻率估計值準確性，然而引入的正偏差會累積到范圍查詢中。

Jiang 等［23］研究了本地信息隱私（Local Information Pri?vacy，LIP），LIP 對敵手的背景知識建模，利用概率先驗分布設計隱私保護機制。LIP 所需噪聲取決于隱私預算與數(shù)據(jù)先驗分布。LIP 根據(jù)先驗分布計算擾動參數(shù)。當數(shù)據(jù)值相當確定時，翻轉該值概率較小；當數(shù)據(jù)值發(fā)生概率較小時，LIP 通過較大的擾動概率保護其隱私。因此，LIP 得到了比LDP 更高的可用性。其構建了1 個通用機制估計收集到的數(shù)據(jù)項，該機制將估計值均方差最小化，可被視為隨機響應的一般形式。

現(xiàn)有LDP 機制往往以相同的方式擾動數(shù)據(jù)，或對輸入添加相同大小的噪聲。然而，在許多實際場景中，不同的輸入具有不同程度的敏感性，因此，用戶需要不同級別的隱私保護水平。Gu 等［24］設計了輸入判別隱私保護算法，以反映不同輸入的隱私要求，并首次提出輸入判別本地差分隱私（InputDiscriminative Local Differential Privacy，IDLDP）的概念，設計了基于一元編碼的IDUE 算法，通過求解最優(yōu)化問題計算擾動概率。由于輸入判別保護的存在，IDUE 算法實用性更高。

已有研究主要目標是提高輸出結果可用性，DP 算法安全性被忽略。Cao 等［25］研究了針對LDP 頻率估計的數(shù)據(jù)投毒攻擊。其研究表明為了根據(jù)攻擊者的需要操縱數(shù)據(jù)分析結果，攻擊者可注入虛假用戶，虛假用戶將偽造的數(shù)據(jù)發(fā)送至服務器。不同的LDP 頻率估計算法對投毒攻擊有不同的安全級別。例如，OUE 和OLH 對投毒攻擊具有相似的安全級別；當項數(shù)目大于閾值時，DE 的安全性低于OUE 和OLH。該研究還設計了兩種對策防御投毒攻擊。在第1 個對策中，服務器對項頻率的概率分布建模，要求項估計頻率滿足非負性和規(guī)范性。由于投毒攻擊是通過虛假用戶偽造數(shù)據(jù)，所以虛假用戶的數(shù)據(jù)可能遵循與真實用戶數(shù)據(jù)不同的模式，因此，在第2 個對策中，服務器通過分析用戶數(shù)據(jù)統(tǒng)計模式檢測虛假用戶。但該研究未涉及如何將投毒攻擊推廣到LDP 頻繁模式挖掘。

3.3 集合數(shù)據(jù)頻率估計

集合數(shù)據(jù)頻率估計研究的是當每條用戶記錄中包含多個數(shù)據(jù)項時如何進行數(shù)據(jù)發(fā)布。集合數(shù)據(jù)頻率估計包括heavy hitter 查詢、頻繁項集挖掘、數(shù)據(jù)項分布估計和高維數(shù)據(jù)分析等。不同于單值頻率估計，集合數(shù)據(jù)頻率估計通常需考慮隱私預算分配問題。

heavy hitter 查詢目的是發(fā)現(xiàn)頻率高于給定閾值的項。由于每個用戶數(shù)據(jù)項個數(shù)不同，因此，該問題具有挑戰(zhàn)性。針對該問題，Qin 等［10］設計了LDPMiner 算法。LDPMiner使用填充采樣技術，若用戶端不填充項集，則很難計算單個數(shù)據(jù)項被采樣的概率，服務器也很難對頻率進行準確估計。

設每個用戶ui的數(shù)據(jù)集合為vi，長度參數(shù)為len，用戶數(shù)為n，項空間大小為d，第j個項出現(xiàn)次數(shù)為cj，則

服務器需確定top-k頻繁項及其對應頻率。

LDPMiner 包含兩個階段：

階段一：用戶使用len對事務填充采樣得到v，使用一半的隱私預算對v進行擾動，將擾動結果發(fā)送至服務器。服務器確定估計頻率最高的2k個項，構建候選項集合IC，將IC廣播給用戶。

階段二：用戶計算IC與事務的交集，使用取值為2k的長度參數(shù)對交集填充采樣得到v，使用一半的隱私預算對v進行隨機響應，將擾動結果發(fā)送至服務器。服務器需將候選項統(tǒng)計計數(shù)乘以2k。

因為兩個階段均滿足差分隱私，根據(jù)差分隱私的序列組合性，LDPMiner 滿足ε-LDP。LDPMiner 的缺點是只能確定頻繁項，不能挖掘頻繁項集。

目前已有多篇文獻研究了CDP 頻繁項集挖掘［26-28］，但是針對LDP 頻繁模式挖掘問題的研究很少。Wang 等［11］設計了heavy hitter 查詢算法SVIM 與頻繁項集挖掘算法SVSM，發(fā)現(xiàn)GRR 算法（即前文所述的DE 算法）具備隱私增益性，而OUE 算法和OLH 算法不具備該性質。依據(jù)該性質，Wang 等設計了自適應頻率估計機制Adaptive。Adaptive 機制可根據(jù)隱私預算ε、項空間大小d、長度參數(shù)len選擇合適的頻率估計算法。

其中，GRR 和OUE 括號里的參數(shù)表示算法被調用時實際使用的隱私預算。

不同于LDPMiner 采取分割隱私預算的策略，SVIM 算法將用戶分成3 組，每組用戶參與1 項查詢?nèi)蝿铡VIM分成3 個階段：

階段1：第1 組用戶使用取值為1 的長度參數(shù)對事務填充采樣得到v，使用Adaptive 機制報告v。服務器統(tǒng)計頻率最高的2k個項，構建頻繁項候選集合IC，把IC廣播給下一組用戶。

階段2：第2 組用戶首先計算事務與IC的交集，之后使用Adaptive 機制報告交集大小。服務器計算len（保證90% 的交集長度不大于len），之后將IC和len發(fā)送至下一組用戶。

階段3：第3 組用戶求事務與IC的交集，使用len對交集填充采樣得到v，通過Adaptive 機制報告v。服務器計算IC中每個項的頻率，得到top-k頻繁項及對應頻率。

頻繁項集挖掘的挑戰(zhàn)是如何減小頻繁項集候選集合大小。SVSM 算法將用戶分成5 組，對應該算法5 個階段，前3 個階段的算法流程和SVIM 一致。

階段4：記top-k頻繁項構成的集合為topKS。服務器根據(jù)topKS構建頻繁項集候選集合：生成topKS所有子集，在生成過程中，一旦發(fā)現(xiàn)子集長度大于，則直接丟棄該子集。因為若子集長度大于，該項集非空子集個數(shù)會大于k，而子集支持度大于等于項集支持度，所以該項集不可能是頻繁項集。對topKS的一個子集X而言，服務器使用式（20）估計X頻率。

其中Φ（x）是項x的頻率。服務器選擇頻率最高的2k個子集構成頻繁項集的候選集合ISC，把ISC發(fā)送至下一組用戶。第4 組用戶尋找同時在事務和ISC中的項集，滿足條件的項集構成集合vs，使用Adaptive 機制報告vs大小。服務器計算len，之后將ISC和len發(fā)送至下一組用戶。

階段5：第5 組用戶尋找同時在事務和ISC中的項集，滿足條件的項集構成集合vs。vs是集合的集合，但同樣可采用類似填充采樣的方法獲取vs中的項集v。用戶使用Adaptive 機制報告v。服務器對ISC中的每個項集計算頻率，將頻率乘以校正因子以提高估計準確性。由此，服務器得到top-k頻繁項集。

由于猜測頻率，SVSM 算法統(tǒng)計誤差變大。填充長度的選擇是主觀的，目前沒有理論支持。如何自適應地選擇合理的填充長度依然是一個亟待解決的問題。

Wang 等［12］設計了一種集合數(shù)據(jù)聚合算法：PrivSet。PrivSet 可幫助服務器統(tǒng)計分析集合數(shù)據(jù)（如數(shù)據(jù)項的分布估計、集合大小的分布估計）。在PrivSet 算法中，每個用戶獨立使用差分隱私指數(shù)機制［29］輸出元素定義域的1 個子集，該過程不需要分割隱私預算。根據(jù)元素定義域大小、集合中的最大項目數(shù)和隱私預算等參數(shù)校準輸出子集的大小及其輸出概率。為了解決集合異構性問題，PrivSet 算法將填充項添加到集合數(shù)據(jù)中。有了這些填充項，服務器可估計用戶集合大小分布，該估計過程不會造成額外的隱私損失。

Wang 等［30］研究了LDP 高維數(shù)據(jù)分析問題，指出當用戶記錄同時包含數(shù)值屬性和分類屬性時，服務器可分別對集合中的數(shù)值屬性與分類屬性進行均值估計和頻率估計。值得注意的是，一旦用戶端使用單熱編碼將某個分類屬性編碼成長度為total的向量（total為該屬性所有取值情況的個數(shù)），求解頻率估計可以轉化為求解均值估計。提出了分段機制PM 和混合機制HM，并將PM 和HM 擴展到多維數(shù)據(jù)中。該方案可用于傳統(tǒng)機器學習（如線性回歸、邏輯回歸和SVM 分類），但目前尚不清楚如何將其應用于更深層次的數(shù)據(jù)分析任務（如深度神經(jīng)網(wǎng)絡）。

4 未來挑戰(zhàn)

當前已有一些綜述性文獻針對LDP 的發(fā)展方向問題進行了研究。如文獻［31-32］主要關注機器學習中的本地差分隱私保護；文獻［33］主要側重于LDP 在安全車聯(lián)網(wǎng)中可能的應用方向；文獻［34］介紹了LDP 空間數(shù)據(jù)采集問題；文獻［35］總結了LDP 頻率估計的主要問題，包括統(tǒng)計準確性問題、數(shù)據(jù)安全性問題、計算復雜度問題和通信成本問題。針對LDP 頻率估計的現(xiàn)有解決方案只能在一定范圍內(nèi)、一定條件下取得理想效果。與CDP 相比，LDP 是一個相對較新的研究領域，而且由于LDP 的性質獨特，科研人員仍面臨不少挑戰(zhàn)。

（1）融合CDP 和LDP 的優(yōu)勢難度很大?，F(xiàn)有差分隱私文獻通常將CDP 和LDP 分開考慮，但這兩種隱私保護模型并不是對立關系。融合CDP 和LDP 可以允許用戶在本地添加少量噪聲，同時實現(xiàn)較高級別的隱私保護程度。然而，該操作涉及安全混洗和復雜的數(shù)學推導證明。安全混洗通常是黑盒模型，缺乏具體的實現(xiàn)方法。文獻［36］設計了混合差分隱私方案以查詢heavy hitter，計算Web 搜索日志中最流行的記錄。該方案對內(nèi)測用戶和普通用戶分組分別應用不同的隱私保護模型，提高了輸出結果可用性，但需要付出額外的預處理成本以劃分信任關系。

后續(xù)研究需繼續(xù)關注如何更好地實現(xiàn)CDP 和LDP 的優(yōu)勢互補。例如借助密碼學原語和非串通的服務器，使隱私保護頻率估計能夠提供近似CDP 的準確性保證，同時類似LDP 不依賴可靠的第三方數(shù)據(jù)收集者。

（2）自適應分配隱私預算方法不足。當用戶記錄是高維數(shù)據(jù)或用戶參與多個查詢?nèi)蝿諘r，算法通常需分配隱私預算。隱私預算分配決定了差分隱私隨機化噪聲，影響隱私保護水平和結果可用性。若隱私預算分配次數(shù)較多，會迅速增加噪聲，導致數(shù)據(jù)可用性急劇下降。因此，LDP 頻率估計需優(yōu)化隱私預算分配。然而，由于許多LDP 算法創(chuàng)新點與隱私預算分配無關，它們通常將隱私預算均勻分配。

在CDP 中，王璇［37］利用泰勒級數(shù)、p級數(shù)、特殊級數(shù)分配隱私預算，減小了噪聲增量速度，分析比較了不同隱私預算分配方案的優(yōu)缺點。研究人員可以考慮在LDP 中運用級數(shù)知識自適應分配隱私預算，觀察頻率估計算法性能可否進一步提高。

（3）高維數(shù)據(jù)隱私效用權衡依然困難。LDP 高維數(shù)據(jù)分析取得隱私效用權衡是十分困難的。已有方法主要利用哈希函數(shù)［7，9］、矩陣投影［8，38］（如哈達瑪矩陣、正交矩陣）處理該問題，但是現(xiàn)有方法主要聚焦于單值頻率估計。當算法處理集合數(shù)據(jù)時，通常采樣1 個或幾個數(shù)據(jù)項并將數(shù)據(jù)項發(fā)送至服務器。采樣可減小通信代價，但勢必導致統(tǒng)計準確性降低。

未來可進一步關注LDP 高維數(shù)據(jù)統(tǒng)計方法，主要考慮兩個方面的問題：如何提高集合數(shù)據(jù)采樣效率和統(tǒng)計精度；如何借助數(shù)據(jù)項間的關聯(lián)進行降維，平衡查詢準確性與通信開銷。

（4）缺乏實時數(shù)據(jù)發(fā)布方法。用戶數(shù)據(jù)可能隨時間發(fā)生變化，需服務器每隔一段時間重新計算統(tǒng)計值?，F(xiàn)有LDP 頻率估計方法主要關注靜態(tài)數(shù)據(jù)，而許多現(xiàn)實場景要求數(shù)據(jù)發(fā)布方法具有連續(xù)數(shù)據(jù)發(fā)布能力。在發(fā)布每一次數(shù)據(jù)的過程中，服務器很難預知后續(xù)需發(fā)布的數(shù)據(jù)。每次發(fā)布數(shù)據(jù)均會累加噪聲方差，最終降低了數(shù)據(jù)可用性。因此，服務器需提高LDP 頻率估計連續(xù)數(shù)據(jù)發(fā)布的精確性和效率，滿足大規(guī)模連續(xù)數(shù)據(jù)發(fā)布的要求。在LDP 中，針對該問題的主要方法是緩存技術，然而當數(shù)據(jù)頻繁發(fā)生改變或數(shù)據(jù)變化劇烈時，緩存技術失效。

LDP 實時數(shù)據(jù)發(fā)布需考慮兩種變化情況：①用戶個數(shù)如何變化；②用戶數(shù)據(jù)如何變化。同時，科研人員可使用滑動窗口模型［39］、自適應隱私預算分配、用戶動態(tài)分組等方法改進擴展LDP 連續(xù)數(shù)據(jù)頻率估計算法。

5 結語

隨著移動智能設備計算能力和存儲能力的不斷增強，眾包數(shù)據(jù)采集和數(shù)據(jù)挖掘技術迅速發(fā)展。同時個人隱私問題成為用戶關注焦點，隱私問題極大限制了數(shù)據(jù)挖掘在工業(yè)中的應用。因此，設計保護個人隱私的數(shù)據(jù)發(fā)布框架具有重要意義。

LDP 作為一種新興的隱私保護模型，可同時保護用戶隱私和服務器隱私，成為信息安全領域研究熱點。由于當前LDP 頻率估計方法依然存在許多問題尚未解決，科研人員需繼續(xù)深入研究本地差分隱私保護，促進數(shù)據(jù)挖掘技術在實際應用中進一步發(fā)展。