本地差分隱私保護(hù)及其應(yīng)用*

高志強(qiáng)，崔翛龍，周 沙，袁 琛

(武警工程大學(xué)烏魯木齊校區(qū),新疆 烏魯木齊 830049)

1 引言

隨著互聯(lián)網(wǎng)、云計(jì)算技術(shù)應(yīng)用領(lǐng)域的不斷擴(kuò)張和大數(shù)據(jù)分析技術(shù)的飛速發(fā)展，海量數(shù)據(jù)在個(gè)人、企業(yè)、研究機(jī)構(gòu)等源源不斷地產(chǎn)生。無論是互聯(lián)網(wǎng)巨頭還是各種社會(huì)組織越來越鐘情于收集和分析用戶數(shù)據(jù)[1]。例如，瀏覽器(Browser)和移動(dòng)應(yīng)用軟件(Mobile APP)無時(shí)無刻地通過收集用戶終端數(shù)據(jù)來訓(xùn)練機(jī)器學(xué)習(xí)模型，分析用戶行為模式；社會(huì)服務(wù)類企業(yè)會(huì)收集用戶的生活統(tǒng)計(jì)數(shù)據(jù)來制定相應(yīng)個(gè)性化服務(wù)方案[2 - 4]。收集用戶數(shù)據(jù)是把雙刃劍，第三方直接收集用戶信息不利于保護(hù)用戶隱私，然而不準(zhǔn)確地收集用戶信息，相應(yīng)的服務(wù)質(zhì)量就很難得到反饋提升，這樣也不利于公共利益。因此，在數(shù)據(jù)收集階段引入隱私保護(hù)機(jī)制來降低并控制隱私泄露的風(fēng)險(xiǎn)，平衡隱私保護(hù)與數(shù)據(jù)可用性之間的關(guān)系，解決和完善針對(duì)不犧牲用戶個(gè)人隱私的大數(shù)據(jù)分析問題和機(jī)制是極具理論和實(shí)際意義的。

從1977年Dalenius[5]提出的隱私控制的定義，到經(jīng)典數(shù)據(jù)脫敏方法k-anonymity[6]及其改進(jìn)模型[7 - 11]都存在著以下缺陷：(1)集中存儲(chǔ)模型下，非可信數(shù)據(jù)管理者使用戶無法直接控制個(gè)人隱私數(shù)據(jù)。(2)由于背景知識(shí)無法明確界定，基于等價(jià)類的隱私保護(hù)模型被迫隨著新攻擊技術(shù)的出現(xiàn)而不斷被動(dòng)調(diào)整。(3)無法提供嚴(yán)格且有效的數(shù)學(xué)理論來證明其隱私保護(hù)水平，無法定量分析隱私泄露風(fēng)險(xiǎn)。值得重視的是，即使被嚴(yán)格處理的數(shù)據(jù)也可能泄露用戶隱私，被去匿名化后的Netflix Prize競(jìng)賽歷史數(shù)據(jù)信息[2,12]，便可以通過數(shù)據(jù)關(guān)聯(lián)(Linkage)推斷出用戶具體隱私信息。

盡管早在2006年微軟研究院的科學(xué)家Dwork[13 - 17]提出了嚴(yán)格可證明的差分隱私保護(hù)技術(shù)DP(Differential Privacy)，但由于仍然需要第三方來管理用戶隱私數(shù)據(jù)，差分隱私一直是停留在理論研究層面的隱私定義，未被大規(guī)模地應(yīng)用于實(shí)際產(chǎn)品中。因此，為平衡“個(gè)人隱私”和“大數(shù)據(jù)分析”關(guān)系，滿足差分隱私保護(hù)特性，提高保護(hù)機(jī)制的隱私性和可用性，眾包模式下的本地差分隱私保護(hù)LDP(Local Differential Privacy)[2,12,18]的概念應(yīng)運(yùn)而生。LDP可以在不需要信任第三方數(shù)據(jù)管理者的情況下，直接在本地將隱私數(shù)據(jù)加噪來保護(hù)個(gè)人信息不被泄露，同時(shí)從宏觀角度保證數(shù)據(jù)收集者可正確地推斷出群體統(tǒng)計(jì)信息。

目前，LDP技術(shù)已被廣泛應(yīng)用于集值型流式頻繁項(xiàng)集挖掘的Heavy Hitters估計(jì)、眾包模式下字符串邊緣頻率估計(jì)和聯(lián)合概率估計(jì)、針對(duì)智能設(shè)備的機(jī)器學(xué)習(xí)等領(lǐng)域。值得關(guān)注的是，2014年，谷歌工程師Erlingsson等人[12]將基于隨機(jī)應(yīng)答和BloomFilter的RAPPOR(Randomized Aggregatable Privacy-Preserving Ordinal Response)技術(shù)成功應(yīng)用于Google Chrome中，在本地通過差分隱私機(jī)制收集用戶數(shù)據(jù)，首次揭開了LDP技術(shù)大規(guī)模應(yīng)用的面紗。隨后，F(xiàn)anti等人[2]提出加強(qiáng)版的RAPPOR，實(shí)現(xiàn)了數(shù)據(jù)字典未知情況下的本地學(xué)習(xí)多變量聯(lián)合概率分布估計(jì)。另外，2016年蘋果全球開發(fā)者大會(huì)WWDC2016(WorldWide Developers Conference)[19]上，蘋果軟件工程高級(jí)副總裁Federighi在Keynote中宣布IOS10的QuickType輸入法、emoji建議、spotlight全局搜索和備忘錄關(guān)鍵詞標(biāo)記，將采用“差分隱私保護(hù)技術(shù)”在設(shè)備終端本地收集用戶數(shù)據(jù)，并將隱私數(shù)據(jù)分析限制在用戶設(shè)備上，并不會(huì)將數(shù)據(jù)上傳到蘋果服務(wù)器。隨后，2017年6月，圣何塞McEnery會(huì)議中心的蘋果開發(fā)者大會(huì)(WWDC2017)[20]發(fā)布了面向開發(fā)者的機(jī)器學(xué)習(xí)API——CoreML，繼續(xù)強(qiáng)調(diào)用戶數(shù)據(jù)隱私的重要性，保證機(jī)器學(xué)習(xí)的數(shù)據(jù)處理在個(gè)人設(shè)備上完成，也就是說，個(gè)人數(shù)據(jù)不必離開用戶設(shè)備，用戶信息將不被發(fā)送到云端，因而用戶也能更好地獲得隱私保護(hù)權(quán)益。

因此，作為差分隱私研究的重要分支，LDP技術(shù)正在從理論研究走向大規(guī)模實(shí)際業(yè)界產(chǎn)品應(yīng)用，并逐漸成為差分隱私保護(hù)領(lǐng)域的一個(gè)研究熱點(diǎn)。近幾年來，LDP技術(shù)及其在各領(lǐng)域研究的結(jié)合使得大量新的成果不斷涌現(xiàn)。本文在總結(jié)已有研究成果的基礎(chǔ)上，對(duì)LDP理論發(fā)展及其在數(shù)據(jù)收集與數(shù)據(jù)分析領(lǐng)域的應(yīng)用進(jìn)行綜述，希望能夠?yàn)樵擃I(lǐng)域的研究者提供有價(jià)值的參考信息。

2 預(yù)備知識(shí)

2.1 差分隱私定義下的數(shù)據(jù)模型

差分隱私是不依賴于攻擊者背景知識(shí)的具有嚴(yán)格數(shù)學(xué)理論支撐的隱私定義，結(jié)合其應(yīng)用場(chǎng)景及針對(duì)數(shù)據(jù)處理和收集方式的不同，主要存在兩種數(shù)據(jù)分布模型：集中式模型，又稱為可信管理者模型(Trusted Curator)[3]和本地模型(Local Model)[1]，如圖1所示。

Figure 1 Data model in differential privacy圖1 差分隱私定義下的數(shù)據(jù)模型

傳統(tǒng)的集中式模型基于可信第三方，用戶終端與數(shù)據(jù)收集者被視為一個(gè)數(shù)據(jù)收集與分析的整體，而數(shù)據(jù)服務(wù)器(云端)直接存儲(chǔ)未處理的原始用戶隱私數(shù)據(jù)，經(jīng)過隱私處理(如加噪)等方式后統(tǒng)一對(duì)外發(fā)布。同時(shí)，集中式模型下又可以分為交互式和非交互式框架，目前，針對(duì)集中式差分隱私保護(hù)模型已有大量的研究成果[13,17,21 - 24]。Roth等人[21]提出了交互式數(shù)據(jù)發(fā)布的中位數(shù)機(jī)制(Median),能夠在相同預(yù)算下提供更多數(shù)量的查詢。Xu等人[22]提出了一種基于k-d樹的直方圖發(fā)布算法DPCube，當(dāng)參數(shù)(頻數(shù)分布緊密度閾值、空間分割次數(shù))的取值適當(dāng)時(shí)，DPCube算法在查詢數(shù)量和查詢誤差等方面具有很好的性能。此外，Engel等人[23]提出了小波變換方法(Privelet),Hay等人[24]提出了層次查詢方法，然而，這些針對(duì)差分隱私的數(shù)據(jù)發(fā)布和分析技術(shù)都基于可信管理者模型數(shù)據(jù)分布模型，集中式數(shù)據(jù)管理不可避免地面臨著巨大的隱私安全泄露風(fēng)險(xiǎn)，嚴(yán)重制約著隱私保護(hù)技術(shù)的發(fā)展。

在眾包模式下的分布式本地模型中，數(shù)據(jù)收集者(Data Collector)不可信任，數(shù)據(jù)服務(wù)器(云端)只能收到用戶加噪的數(shù)據(jù)，也就是說，數(shù)據(jù)收集者根本不可能收集到原始數(shù)據(jù)。其中，用戶在向數(shù)據(jù)收集者發(fā)送個(gè)人數(shù)據(jù)前，先在本地加入滿足差分隱私的噪聲擾動(dòng)，最后數(shù)據(jù)收集者根據(jù)收集到的噪聲數(shù)據(jù)，從統(tǒng)計(jì)學(xué)的角度近似估計(jì)出用戶群體的統(tǒng)計(jì)特性，而不是針對(duì)具體用戶個(gè)體進(jìn)行統(tǒng)計(jì)特性推斷。其中，每個(gè)用戶只與數(shù)據(jù)收集者分享原始數(shù)據(jù)的加噪版本，由差分隱私保護(hù)的原理容易證明，無論本地隱私保護(hù)機(jī)制的加噪輸出如何，都不能確定性地分析出具體的某一條記錄來自于哪個(gè)用戶個(gè)體，這既保證了群體統(tǒng)計(jì)信息的相對(duì)準(zhǔn)確性，又保護(hù)了個(gè)人精確的原始數(shù)據(jù)，從而解決了用戶隱私數(shù)據(jù)被不可信第三方外包管理的癥結(jié)。

目前，針對(duì)本地模型的隱私保護(hù)算法研究不斷涌現(xiàn)，文獻(xiàn)[2]和文獻(xiàn)[12]基于隨機(jī)響應(yīng)和BloomFilter，實(shí)現(xiàn)了用戶字符串的統(tǒng)計(jì)信息的收集和多次數(shù)據(jù)收集的長(zhǎng)效隱私保護(hù)。文獻(xiàn)[3]結(jié)合本地隱私保護(hù)和集中式數(shù)據(jù)模式，提出具有高可用性和隱私保護(hù)性的混合模型BLENDER。文獻(xiàn)[1]從生成式對(duì)抗神經(jīng)網(wǎng)絡(luò)的角度，結(jié)合差分隱私保護(hù)機(jī)制產(chǎn)生內(nèi)部攻擊數(shù)據(jù)，對(duì)協(xié)同式深度學(xué)習(xí)的安全性提出了挑戰(zhàn)。文獻(xiàn)[25]針對(duì)三星的智能移動(dòng)終端的隱私數(shù)據(jù)收集問題，利用本地差分隱私保護(hù)機(jī)制構(gòu)建了準(zhǔn)確高效的Harmony系統(tǒng)，實(shí)現(xiàn)了支持LDP的統(tǒng)計(jì)分析與機(jī)器學(xué)習(xí)功能。綜上所述，基于本地模型的最新研究成果涉及多個(gè)新興領(lǐng)域，無論是基于統(tǒng)計(jì)分析的理論研究[18,26,27]還是產(chǎn)品實(shí)現(xiàn)，都將LDP的研究推向一個(gè)前所未有的高度。

2.2 本地差分隱私保護(hù)

LDP技術(shù)是解決基于非可信第三方隱私數(shù)據(jù)收集的方法，其主要思想是保證收集者：(1)不能收集或擁有任何個(gè)人的精確信息；(2)可以推斷出用戶群體的泛化統(tǒng)計(jì)信息。具體來說，用戶在本地通過差分隱私技術(shù)來置亂原始數(shù)據(jù)，然后再把加噪數(shù)據(jù)發(fā)送給收集者。這樣，LDP既保護(hù)了用戶隱私，也避免了收集者面臨的隱私數(shù)據(jù)治理的問題。本節(jié)將介紹差分隱私保護(hù)模型的兩種形式化定義及定理。

定義1((ε,δ)-DP)[13]隨機(jī)算法A滿足(ε,δ)-DP，當(dāng)且僅當(dāng)所有鄰接數(shù)據(jù)庫(kù)D和D′只相差一條用戶記錄，對(duì)于算法A所有可能的輸出R?Range(A)滿足如下不等式：

Pr(A(D)∈R)≤eεPr(A(D′)∈R)+δ

(1)

其中，ε為隱私預(yù)算，用來調(diào)節(jié)算法A輸出結(jié)果的隱私保護(hù)程度，適用于集中式差分隱私模型和本地差分隱私模型。

定義2((ε,δ)-LDP)[18]隨機(jī)算法A滿足(ε,δ)-LDP，當(dāng)且僅當(dāng)所有用戶端數(shù)據(jù)對(duì)x1和x2，對(duì)于算法A所有可能的輸出R?Range(A)滿足不等式:

Pr(A(x1)∈R)≤eεPr(A(x2)∈R)+δ

(2)

當(dāng)δ=0時(shí)，式(2)成為ε-LDP。直觀地說，不管用戶端數(shù)據(jù)的改變量，數(shù)據(jù)收集者關(guān)于接收到用戶發(fā)送數(shù)據(jù)的背景知識(shí)改變不大。

兩種差分隱私保護(hù)模型的主要區(qū)別如表1所示，二者最重要的差別在于加入噪聲擾動(dòng)的時(shí)機(jī)不同。在本地模型中，數(shù)據(jù)在發(fā)送給收集者之前進(jìn)行隱私擾動(dòng)，而集中式模型先進(jìn)行原始數(shù)據(jù)收集，后進(jìn)行隱私處理。另外，在本地模型中，D代表一個(gè)用戶的數(shù)據(jù)，D′代表同一用戶依概率改變后的數(shù)據(jù)。

Table 1 Difference of the two differential privacy models表1 兩種差分隱私模型的差異

而集中式模型的D代表所有用戶的數(shù)據(jù)，D′代表除去有數(shù)據(jù)變化用戶的所有用戶數(shù)據(jù)。

在針對(duì)隱私數(shù)據(jù)分析的本地模型中，每個(gè)本地用戶用隨機(jī)器Qi擾亂個(gè)人數(shù)據(jù)vi得到zi，數(shù)據(jù)收集者將其匯總得到s，最后進(jìn)行數(shù)據(jù)分析。本地模型下的數(shù)據(jù)分析流程如圖2所示。

Figure 2 Analysis process under local model圖2 本地模型下的數(shù)據(jù)分析流程

差分隱私的序列組合特性是最常用的隱私預(yù)算ε分配策略(并行策略參見文獻(xiàn)[15])。

定理1(Laplace機(jī)制)[17]函數(shù)f：D→Rd，敏感度為Δf，隨機(jī)算法A(D)=f(D)+Y滿足ε-DP，其中Y～Lap(Δf/ε)為隨機(jī)噪聲。

Laplace機(jī)制經(jīng)常被用于本地模型中，常用于對(duì)數(shù)值型結(jié)果的隱私保護(hù)(指數(shù)機(jī)制、幾何機(jī)制參見文獻(xiàn)[15,16])。

2.3 隨機(jī)應(yīng)答

隨機(jī)應(yīng)答RR(Randomized Response)[28,29]是一種被用來保護(hù)敏感話題調(diào)查參與者隱私的技術(shù)，同時(shí)目前主流的本地差分隱私保護(hù)機(jī)制都是基于隨機(jī)應(yīng)答策略的。具體應(yīng)用場(chǎng)景為：每個(gè)人不是屬于組A就是組B，問題是在不能確定具體個(gè)人屬于哪組的前提下，估計(jì)組A中人數(shù)的比例。隨機(jī)應(yīng)答給出的解決方案：隨機(jī)選取n個(gè)人，隨機(jī)設(shè)備(可以是拋硬幣、摸球模型)以概率p指向A，以(1-p)指向B。在每輪調(diào)查中，受訪者只需回答設(shè)備指向(調(diào)查者未知)的組別是否與其真正的組別一致(Yes或No)，這樣便可以得到組A人數(shù)π的最大似然估計(jì)。其中，P(Xi=1)=πp+(1-π)(1-p)，P(Xi=0)=(1-π)p+π(1-p)，令n1、n-n1分別記為回答Yes和No的人數(shù)，則似然估計(jì)為L(zhǎng)=[πp+(1-π)(1-p)]n1[(1-π)p+π(1-p)]n-n1。易得，當(dāng)p≠1/2時(shí)，π的最大似然估計(jì)為:

通過RR技術(shù)，每個(gè)參與者都可以否認(rèn)“Yes”，因?yàn)檫@個(gè)結(jié)果基于設(shè)備的概率性，這樣實(shí)現(xiàn)了針對(duì)個(gè)體的隱私保護(hù)。作為一種加強(qiáng)版本，參與者可以進(jìn)行二次隨機(jī)應(yīng)答。若隨機(jī)設(shè)備采用拋硬幣方式實(shí)現(xiàn)，“Yes”的估計(jì)為2(Y-0.25)，其中Y為“Yes”應(yīng)答比例。重要的是，RR機(jī)制滿足差分隱私機(jī)制，不依賴于攻擊者的先驗(yàn)知識(shí)，可以在數(shù)據(jù)收集中保護(hù)任一參與者的隱私，參與者可以擁有ε=ln(0.75/(1-0.75))=ln (3) 的隱私保護(hù)水平[2,12]。

LDP模型最早由RR技術(shù)實(shí)現(xiàn)，并應(yīng)用于Google和Apple公司各自的產(chǎn)品中[2]?，F(xiàn)有基于RR技術(shù)的LDP機(jī)制在數(shù)據(jù)挖掘中具有一定的局限性，只適用于用戶數(shù)據(jù)類型為數(shù)值型或范圍型，而數(shù)據(jù)收集者的數(shù)據(jù)挖掘任務(wù)局限于基本統(tǒng)計(jì)，如計(jì)數(shù)或求中位值等。但是，RR技術(shù)及其改進(jìn)模型在收集群體層面的統(tǒng)計(jì)數(shù)據(jù)而不泄露個(gè)體數(shù)據(jù)方面具有優(yōu)越性能，目前已成為新的研究熱點(diǎn)。

3 主要研究方向

目前針對(duì)LDP的研究方向主要涉及基于隨機(jī)應(yīng)答與BloomFilter的編解碼方式研究、針對(duì)流式頻繁項(xiàng)集挖掘Heavy Hitters挖掘和針對(duì)智能終端的收集與機(jī)器學(xué)習(xí)等。

3.1 針對(duì)LDP的隨機(jī)應(yīng)答

已經(jīng)應(yīng)用于Google的Chrome瀏覽器的RAPPOR[12]是最早支持本地差分隱私的數(shù)據(jù)收集和眾包數(shù)據(jù)統(tǒng)計(jì)的通用技術(shù)，采用隨機(jī)應(yīng)答策略和BloomFilter保證在研究用戶群體數(shù)據(jù)時(shí)不能窺探到個(gè)體的信息，實(shí)現(xiàn)了針對(duì)客戶端群體的類別、頻率、直方圖和字符串類型統(tǒng)計(jì)數(shù)據(jù)的隱私保護(hù)分析。RAPPOR應(yīng)答被定義為比特位字符串，每一位都是對(duì)應(yīng)用戶端特性報(bào)告的邏輯謂詞隨機(jī)應(yīng)答，用來收集用戶群體的數(shù)值和序數(shù)值的統(tǒng)計(jì)，可以提供ln (3) 的差分隱私保護(hù)。

算法1用戶端的RAPPOR算法

輸入：用戶數(shù)據(jù)X，參數(shù)k(串長(zhǎng)度)，h(Hash個(gè)數(shù))，概率參數(shù)f、p、q。

輸出：數(shù)據(jù)報(bào)告s。

(1)信號(hào)處理。用h個(gè)哈希函數(shù)將X映射到大小為k的BloomFilterB上。

(2)永久隨機(jī)響應(yīng)(PRR)。每個(gè)X與BloomFilterB中的i生成二進(jìn)制報(bào)告B′。

(3)即時(shí)隨機(jī)響應(yīng)(IRR)。分配一個(gè)大小為k的比特串s，初始化為0，依照概率參數(shù)設(shè)置s中的比特i。

(4)報(bào)文。把收集的報(bào)告s發(fā)送到服務(wù)器。

在算法1中，RAPPOR采用兩個(gè)滿足差分隱私的機(jī)制：永久和即時(shí)的隨機(jī)應(yīng)答，不僅可以單獨(dú)調(diào)節(jié)隱私保護(hù)水平，而且BloomFilter可以增加額外的不確定性，不僅壓縮了報(bào)文大小，更增加了攻擊者的攻擊難度。如圖3所示，用戶數(shù)據(jù)為X=“Male”，BloomFilterB大小為k=8，哈希函數(shù)個(gè)數(shù)h=3，BloomFilterB產(chǎn)生永久隨機(jī)響應(yīng)B′，每次數(shù)據(jù)收集(如每天)，數(shù)據(jù)收集者得到即時(shí)隨機(jī)響應(yīng)X′。由差分隱私保證，最厲害的攻擊者最終只能收集到X′，不能推理到X。因?yàn)锽loomFilter中多個(gè)值映射為一個(gè)比特位，使針對(duì)用戶個(gè)人的攻擊更難實(shí)現(xiàn)。

Figure 3 Life-cycle of the RAPPOR圖3 RAPPOR報(bào)文的生命周期

RAPPOR在解碼過程中結(jié)合成熟的假設(shè)檢驗(yàn)、最小二乘求解和LASSO(Least Absolute Shrinkage and Selection Operator)回歸[30]實(shí)現(xiàn)了針對(duì)字符串抽樣群體頻率的高可用解碼框架。然而，RAPPOR的兩個(gè)假設(shè)經(jīng)常限制其實(shí)際應(yīng)用：(1)使用RAPPOR的數(shù)據(jù)收集者只能孤立地了解單一變量的分布。實(shí)際上，研究多個(gè)變量之間的關(guān)聯(lián)是更有意義的，比如，使用瀏覽器分析多個(gè)不相干的主頁瀏覽記錄或搜索URL與惡意軟件的安裝相關(guān)性關(guān)系。(2)數(shù)據(jù)收集者必須事先知道潛在字符串字典、安裝軟件的報(bào)告、名稱、hash值，然而這些是不可能作為先驗(yàn)知識(shí)的。針對(duì)以上問題，對(duì)未知分布多變量關(guān)聯(lián)分析和學(xué)習(xí)未知頻率分布的用戶端字符串可以作為解決方案，同時(shí)，構(gòu)建候選字符串字典并應(yīng)對(duì)大規(guī)模數(shù)據(jù)集的增加依然是制約算法效能的瓶頸，算法的并行化優(yōu)化和分布式集群擴(kuò)展可以作為一個(gè)有意義的研究方向。

3.2 基于LDP的流式頻繁項(xiàng)集挖掘

頻繁項(xiàng)集挖掘是數(shù)據(jù)挖掘領(lǐng)域的一項(xiàng)重要技術(shù)，可用于關(guān)聯(lián)規(guī)則挖掘、用戶行為預(yù)測(cè)以及相關(guān)性分析。而流式頻繁項(xiàng)集挖掘主要解決top-k頻繁項(xiàng)集任務(wù)，現(xiàn)有支持隱私保護(hù)的方案中，大量的通信消耗、隱私預(yù)算的損耗與可用性的平衡一直是基于LDP的流式頻繁項(xiàng)集挖掘難點(diǎn)。針對(duì)集值數(shù)據(jù)(Set-Valued Data)上的流式頻繁項(xiàng)集挖掘(Heavy Hitter Mining)任務(wù)，卡塔爾大學(xué)的于挺教授團(tuán)隊(duì)[31]在RAPPOR機(jī)制和Succinct Histgram的基礎(chǔ)上，提出的LDPMiner方法[4]將挖掘任務(wù)分成兩個(gè)子處理過程，如圖4所示。首先，Sampling SH算法完成對(duì)流式頻繁項(xiàng)的主成分識(shí)別工作，從噪聲數(shù)據(jù)中初步確定流式頻繁項(xiàng)的選值范圍，然后Sampling RAPPOR算法對(duì)前一過程的結(jié)果進(jìn)行頻數(shù)估計(jì)上的調(diào)優(yōu)處理，得到相比單一處理過程更為精確的流式頻繁項(xiàng)結(jié)果。

Figure 4 Framework of the LDPMiner圖4 LDPMiner的兩階段框架

3.3 其他成果

John等人[18]在2013年首先提出了Local Differential Privacy(1965年Warner提出的Random Response更早[28])。而蘋果的差分隱私技術(shù)著眼于整體又保護(hù)個(gè)體，是唯一一家將Differential Privacy作為標(biāo)準(zhǔn)大規(guī)模部署的公司，但不像Google的RAPPOR，其技術(shù)一直未開源。蘋果在WWDC2016、WWDC2017上倡導(dǎo)的Differetial Privacy和No User Profiling主要涉及三方面[19,20]：

(1)局部抽樣：以某一頻率局部采集一部分用戶的數(shù)據(jù)，而不是收集用戶的整體數(shù)據(jù)；

(2)Hash加密：用BloomFilter將用戶數(shù)據(jù)做Hash運(yùn)算，實(shí)現(xiàn)在保護(hù)用戶隱私的前提下，得到用戶是否使用某些固定表達(dá)的特征；

(3)噪聲擾動(dòng)：在收集用戶數(shù)據(jù)前，先加入隨機(jī)噪聲，只要被注入的噪音抽樣是正態(tài)分布的，那么整體來看，這些噪音最終將相互抵消。

這也給研究人員提供了避免在全局中暴露采樣信息的思路：無需建立User Profile，Group Profile的精度就足夠，只要數(shù)據(jù)量充足，即使只有加噪數(shù)據(jù)，依然可以獲得群體趨勢(shì)的統(tǒng)計(jì)量?？傊?，相比于效率低的傳統(tǒng)密碼學(xué)技術(shù)，蘋果、谷歌等公司不斷對(duì)本地差分隱私技術(shù)的商用，給我們對(duì)LDP技術(shù)的研究帶來很大的動(dòng)力，也希望蘋果公司采用的相關(guān)技術(shù)細(xì)節(jié)可以早日開源，進(jìn)一步推動(dòng)LDP理論研究和實(shí)際應(yīng)用。

本地差分隱私在數(shù)據(jù)挖掘中的應(yīng)用研究與差分隱私的理論發(fā)展密切相關(guān)。對(duì)基于LDP的主流算法的總結(jié)如表2所示。

Table 2 Comparison among different LDP models表2 主流LDP算法的比較

4 LDP的理論分析

縱觀現(xiàn)有文獻(xiàn)的研究，LDP技術(shù)差分隱私理論分析主要涉及統(tǒng)計(jì)分析理論、差分隱私證明等。LDP的差分隱私證明是嚴(yán)格的，尤其基于隨機(jī)響應(yīng)的本地隱私差分保護(hù)研究很廣泛。例如，可證明RAPPOR滿足差分隱私的定義。其中，永久隨機(jī)響應(yīng)(PRR)保證了來自真值的加噪值保護(hù)隱私。

證明S=s1,…，sk是RAPPOR產(chǎn)生的隨機(jī)報(bào)告，在已知用戶數(shù)據(jù)V的條件下，觀測(cè)任意S的概率，假設(shè)永久隨機(jī)響應(yīng)B′是已知的。

P(S=s|V=v)=

P(S=s|B,B′,v)·P(B′|B,v)·P(B|v)=

P(S=s|B′)·P(B′|B)·P(B|v)=

P(S=s|B′)·P(B′|B)

對(duì)于P(B′|B)相關(guān)概率如下：

不失一般性，BloomFilter的比特位1，…，h，設(shè)置為，b*={b1=1，…，bh=1，bh+1=0，…，bk=0}，

(1)

□

□

對(duì)于N個(gè)用戶報(bào)文，差分隱私考慮輸入只差一個(gè)記錄j(報(bào)告集D1和D2只差一個(gè)報(bào)告Sj)，其他的在比值中約掉。

為第n次數(shù)據(jù)收集，計(jì)算εn需要額外假設(shè)攻擊在從B′獲得信息的效能。N越大，ε∞越小。然而，基于隨機(jī)響應(yīng)的差分隱私理論分析依然處于起步階段，更高級(jí)的數(shù)理統(tǒng)計(jì)分析技術(shù)(如多隨機(jī)變量相關(guān)性分析等)的應(yīng)用將豐富本地差分隱私的理論研究。

5 結(jié)束語

隨著眾包模式的興起與大數(shù)據(jù)分析產(chǎn)業(yè)的推動(dòng)，本地差分隱私近年來的研究在理論上不斷發(fā)展和完善，并在統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、社交網(wǎng)絡(luò)等領(lǐng)域得到了初步應(yīng)用。本文介紹了本地差分隱私保護(hù)的基礎(chǔ)理論，并著重介紹了主流LDP技術(shù)的數(shù)據(jù)收集與數(shù)據(jù)分析方法，最后從理論推導(dǎo)的角度對(duì)LDP技術(shù)進(jìn)行分析。雖然LDP技術(shù)的研究和發(fā)展都較傳統(tǒng)差分隱私起步晚，仍是一個(gè)相對(duì)年輕的研究領(lǐng)域，但近年來其在互聯(lián)網(wǎng)領(lǐng)域的大規(guī)模應(yīng)用給學(xué)界和產(chǎn)業(yè)界都帶來強(qiáng)大動(dòng)力。對(duì)于本地差分隱私保護(hù)，在理論和應(yīng)用上都還存在一些難點(diǎn)以及新的方向需要進(jìn)一步深入研究，包括：

(1)基于LDP的眾包機(jī)器學(xué)習(xí)。

LDP技術(shù)源自于眾包模式，在支持用戶隱私保護(hù)的數(shù)據(jù)收集、支持隱私保護(hù)的機(jī)器學(xué)習(xí)、統(tǒng)計(jì)分析等領(lǐng)域具有很大的研究前景。國(guó)內(nèi)南京大學(xué)網(wǎng)絡(luò)合作與安全研究中心COSEC(Network Cooperation and Security Research Center)團(tuán)隊(duì)在抗大數(shù)據(jù)分析的隱私保護(hù)方法的研究中，提出的一種適用于各種移動(dòng)感知眾包任務(wù)的交易平臺(tái)便是一個(gè)很好的探索。然而，分布式條件下的數(shù)據(jù)同步與集中統(tǒng)計(jì)分析是一個(gè)不容忽視的技術(shù)難點(diǎn)。

(2)抵抗新型攻擊的能力方面。

文獻(xiàn)[1]中提出的具有隱私保護(hù)數(shù)據(jù)生成能力的生成式對(duì)抗網(wǎng)絡(luò)GAN(Generative Adversarial Networks)，可以針對(duì)該網(wǎng)絡(luò)模型欺騙眾包模式下的其他同等用戶，這種新型攻擊方式需要研究者引起重視。因此，完善本地隱私保護(hù)的理論根基，理清隱私保護(hù)與攻擊就是矛和盾的關(guān)系，才能不斷完善和提高，使LDP技術(shù)提供最可靠的用戶隱私保護(hù)支持。

(3)差分隱私下的大數(shù)據(jù)分析。

隨著大數(shù)據(jù)技術(shù)的發(fā)展，越來越多的應(yīng)用涉及到大數(shù)據(jù)，社交網(wǎng)絡(luò)、微博、醫(yī)療信息、生命科學(xué)以及定位系統(tǒng)服務(wù)等。利用Hadoop、Spark、Storm等大數(shù)據(jù)分析平臺(tái)，實(shí)現(xiàn)支持差分隱私的數(shù)據(jù)挖掘和分析，尤其是基于RAPPOR技術(shù)的本地隱私保護(hù)算法在大規(guī)模數(shù)據(jù)字典的構(gòu)建與計(jì)算效能間的優(yōu)化亟待解決。

總之，本地差分隱私保護(hù)是目前信息安全領(lǐng)域的研究熱點(diǎn)之一，也取得了豐富的研究成果。本文從理論和應(yīng)用的角度對(duì)本地差分隱私保護(hù)目前的研究狀況進(jìn)行綜述，希望能夠?yàn)樵擃I(lǐng)域的研究者提供有價(jià)值的參考信息。

[1] Hitaj B, Ateniese G, Pérez-Cruz F. Deep models under the GAN:Information leakage from collaborative deep learning[C]∥Proc of the 2017 ACM SIGSAC Conference on Computer and Communications Security, 2017:603-618.

[3] Avent B, Korolova A, Zeber D, et al. Blender: Enabling local search with a hybrid differential privacy model[C]∥Proc of the 26th USENIX Security Symposium, 2017: 747-764.

[4] Qin Z, Yang Y, Yu T, et al. Heavy hitter estimation over set-valued data with local differential privacy[C]∥Proc of the 2016 ACM SIGSAC Conference on Computer and Communications Security, 2016:192-203.

[5] Dalenius T.Towards a methodology for statistical disclosure control[J].Statistic Tidskrift,1977,15(2):429-444.

[6] Sweeney L.k-anonymity:A model for protecting privacy[J].International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems,2002,10(5):557-570.

[7] Machanavajjhala A, Gehrke J, Kifer D, et al.l-diversity: Privacy beyondk-anonymity[C]∥ Proc of the 22nd International Conference onData Engineering, 2006: 24.

[8] Li N, Li T, Venkatasubramanian S.t-closeness: Privacy beyondk-anonymity andl-diversity[C]∥Proc of IEEE 23rd International Conference on Data Engineering, 2007:106-115.

[9] Wong R C W, Li J, Fu A W C, et al. (α,k)-anonymity: An enhancedk-anonymity model for privacy preserving data publishing[C]∥Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006:754-759.

[10] Xiao X, Tao Y. M-invariance:Towards privacy preserving re-publication of dynamic datasets[C]∥Proc of the 2007 ACM SIGMOD International Conference on Management of Data,2007:689-700.

[11] Zhao Y, Du M, Le J, et al.A survey on privacy preserving approaches in data publishing[C]∥Proc of the 1st International Workshop on Database Technology and Applications,2009:128-131.

[12] Erlingsson U, Pihur V, Korolova A. RAPPOR:Randomized aggregatable privacy-preserving ordinal response[C]∥Proc of CCS’14,2014:1054-1067.

[13] Dwork C. A firm foundation for private dataanalysis[J].Communications of the ACM,2011,54(1):86-95.

[14] Dwork C,Krishnaram K,Frank M,et.al.Our data,ourselves:Privacy via distributed noise generation[C]∥Proc of the 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques (EUROCRYPT), 2006:486-503.

[15] Dwork C,Frank M,Kobbi N.Calibrating noise to sensitivity in private data analysis[C]∥Proc of the 3rd Theory of Cryptography Conference (TCC),2006:265-284.

[16] Dwork C, Moni N,Toniann P.Differential privacy under continual observation[C]∥Proc of the 42nd ACM Symposium on Theory of Computing (STOC),2010:715-724.

[17] Dwork C,Moni N,Toniann P.Pan-private streaming algorithms[C]∥Proc of the 1st Symposium on Innovations in Computer Science (ICS),2010:66-80.

[18] John C,Michael I,Martin J.Local privacy and statistical minimax rates[C]∥Proc of the IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS),2013:429-438.

[19] Novac O,Novac M,Gordan C,et al.Comparative study of Google Android,Apple iOS and Microsoft Windows Phone mobile operating systems[C]∥Proc of International Conference on Engineering of Modern Electric Systems, 2017:154-159.

[20] Slva M,Ramos T,Holanda M.Geographic information system with public participat on IoS system[C]∥Proc of the 12th Iberian Conference Information Systems and Technologies,2017:1-5.

[21] Dwork C,Aaron R.The algorithmic foundations of differential privacy[J].Foundations and Trends in Theoretical Computer Science,2014,9(3-4):211-407.

[22] Xu J. Differentially private histogram publication[J].The VLDB Journal,2013,22(6):797-822.

[23] Engel D, Eibl G. Wavelet-based multiresolution smart meter privacy[J].IEEE Transactions on Smart Grid,2017,8(4):1710-1721.

[24] Hay M, Machanavajjhala A, Miklau G, et al. Principled evaluation of differentially private algorithms using dpbench[C]∥Proc of the 2016 International Conference on Management of Data, 2016:139-154.

[25] Nguyên T T, Xiao X, Yang Y, et al.Collecting and analyzing data from smart device users with local differential privacy[J].arXiv preprint arXiv:1606.05053,2016.

[26] KairouzP,Bonawitz K,Ramage D.Discrete distribution estimation under local privacy[C]∥Proc of International Conference on Machine Learning (ICML),2016:2436-2444.

[27] Peter K,Sewoong O,Pramod V.Extremal mechanisms for local differential privacy[J].ar Xivpreprint ar Xiv:1407.1338,2014.

[28] Warner S L. Randomized response:A survey technique for eliminating evasive answer bias[J].Journal of the American Statistical Association,1965,60(309):63-69.

[29] Wikipedia.Randomized response[EB/OL].[2017-06-13].http://en.wikipedia.org/wiki/Randomized_response.

[30] Robert T.Regression shrinkage and selectionvia the Lasso[J].Journal of the Royal Statistical Society,1994,Series B,58:267-288.

[31] Bassily R,Smith A.Local,private,efficient protocols for succinct histograms[C]∥Proc of the 47th ACM Symposium on Theory of Computing (STOC),2015:127-135.