本地差分隱私頻率估計(jì)研究綜述

王廣藝，楊 庚

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

0 引言

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

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

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

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

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

1 LDP 頻率估計(jì)基礎(chǔ)知識(shí)

1.1 本地差分隱私

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

定義1 ε-本地差分隱私［4］。給定算法M，定義域?yàn)镈omain（M），值域?yàn)镽ange（M）。M滿足本地差分隱私，當(dāng)且僅當(dāng)對(duì)任意一對(duì)輸入t和t’（t，t’∈Domain（M）），成立不等式為：

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

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

CDP 具備這3 條性質(zhì)，LDP 兼具第1、3 條性質(zhì)。LDP沒有直接的并行組合性，因?yàn)槊總€(gè)用戶只有1 條記錄，不能被切分。

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

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

1.2 LDP 頻率估計(jì)

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

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

該性質(zhì)成立與否取決于算法f的內(nèi)部結(jié)構(gòu)。

1.3 頻繁項(xiàng)集挖掘

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

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

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

2 LDP 頻率估計(jì)性能分析

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

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

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

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

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

3 頻率估計(jì)中的本地差分隱私保護(hù)方法

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

3.1 單值頻率估計(jì)

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

3.1.1 Rappor 算法

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

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

用戶發(fā)送S。

永久隨機(jī)響應(yīng)滿足ε1-LDP，其中，

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

瞬時(shí)隨機(jī)響應(yīng)的結(jié)果依賴p，q，r。

瞬時(shí)隨機(jī)響應(yīng)滿足ε2-LDP，其中，

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

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

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

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

3.1.2 CMS 算法

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

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

3.1.3 HCMS 算法

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

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

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

3.2 泛化頻率估計(jì)

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

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

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

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

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

文獻(xiàn)［9］得到了3 種效果較好的擾動(dòng)方法：DE、OUE、OLH，具體描述如下：

DE 算法：設(shè)用戶值為v，項(xiàng)空間大小為|I|。擾動(dòng)公式為：

此時(shí)Support（i）=｛i｝，p*=p，q*=q。

OUE 算法：用戶項(xiàng)被單熱編碼成向量B。擾動(dòng)公式為：

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

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

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

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

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

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

現(xiàn)有LDP 機(jī)制往往以相同的方式擾動(dòng)數(shù)據(jù)，或?qū)斎胩砑酉嗤笮〉脑肼?。然而，在許多實(shí)際場景中，不同的輸入具有不同程度的敏感性，因此，用戶需要不同級(jí)別的隱私保護(hù)水平。Gu 等［24］設(shè)計(jì)了輸入判別隱私保護(hù)算法，以反映不同輸入的隱私要求，并首次提出輸入判別本地差分隱私（InputDiscriminative Local Differential Privacy，IDLDP）的概念，設(shè)計(jì)了基于一元編碼的IDUE 算法，通過求解最優(yōu)化問題計(jì)算擾動(dòng)概率。由于輸入判別保護(hù)的存在，IDUE 算法實(shí)用性更高。

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

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

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

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

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

服務(wù)器需確定top-k頻繁項(xiàng)及其對(duì)應(yīng)頻率。

LDPMiner 包含兩個(gè)階段：

階段一：用戶使用len對(duì)事務(wù)填充采樣得到v，使用一半的隱私預(yù)算對(duì)v進(jìn)行擾動(dòng)，將擾動(dòng)結(jié)果發(fā)送至服務(wù)器。服務(wù)器確定估計(jì)頻率最高的2k個(gè)項(xiàng)，構(gòu)建候選項(xiàng)集合IC，將IC廣播給用戶。

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

因?yàn)閮蓚€(gè)階段均滿足差分隱私，根據(jù)差分隱私的序列組合性，LDPMiner 滿足ε-LDP。LDPMiner 的缺點(diǎn)是只能確定頻繁項(xiàng)，不能挖掘頻繁項(xiàng)集。

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

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

不同于LDPMiner 采取分割隱私預(yù)算的策略，SVIM 算法將用戶分成3 組，每組用戶參與1 項(xiàng)查詢?nèi)蝿?wù)。SVIM分成3 個(gè)階段：

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

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

階段3：第3 組用戶求事務(wù)與IC的交集，使用len對(duì)交集填充采樣得到v，通過Adaptive 機(jī)制報(bào)告v。服務(wù)器計(jì)算IC中每個(gè)項(xiàng)的頻率，得到top-k頻繁項(xiàng)及對(duì)應(yīng)頻率。

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

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

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

階段5：第5 組用戶尋找同時(shí)在事務(wù)和ISC中的項(xiàng)集，滿足條件的項(xiàng)集構(gòu)成集合vs。vs是集合的集合，但同樣可采用類似填充采樣的方法獲取vs中的項(xiàng)集v。用戶使用Adaptive 機(jī)制報(bào)告v。服務(wù)器對(duì)ISC中的每個(gè)項(xiàng)集計(jì)算頻率，將頻率乘以校正因子以提高估計(jì)準(zhǔn)確性。由此，服務(wù)器得到top-k頻繁項(xiàng)集。

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

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

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

4 未來挑戰(zhàn)

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

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

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

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

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

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

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

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

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

5 結(jié)語

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

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