基于直方圖的隱私鍵-值數(shù)據(jù)收集算法

張嘯劍 徐雅鑫 付 楠 孟小峰

1(河南財(cái)經(jīng)政法大學(xué)計(jì)算機(jī)與信息工程學(xué)院 鄭州 450002) 2(中國(guó)人民大學(xué)信息學(xué)院 北京 100872)

(xjzhang82@ruc.edu.cn)

移動(dòng)互聯(lián)網(wǎng)環(huán)境下的新興技術(shù)快速發(fā)展與應(yīng)用，使得鍵-值(key-value)數(shù)據(jù)的獲取與收集變得尤為容易，例如網(wǎng)購(gòu)、健康醫(yī)療、金融等數(shù)據(jù)的收集與分析.鍵-值數(shù)據(jù)收集與分析能夠提升產(chǎn)品服務(wù)與設(shè)備服務(wù)的質(zhì)量，以及向用戶提供個(gè)性化的體驗(yàn).然而，鍵-值數(shù)據(jù)通常蘊(yùn)含著豐富的個(gè)人敏感信息，在提供給收集者或者第三方應(yīng)用的同時(shí)，個(gè)人的敏感信息有可能被泄露.表1為某不可信購(gòu)物網(wǎng)站收集用戶購(gòu)買與評(píng)分的記錄.通過(guò)表1中鍵的頻率以及鍵所對(duì)應(yīng)值的均值分析，可以學(xué)習(xí)出用戶的購(gòu)物行為模式與偏好.例如，商品k2的頻率為2，k2所對(duì)應(yīng)值的均值為0.61.不可信收集者分析出k2的頻率之后，即可對(duì)表1中的用戶進(jìn)行統(tǒng)計(jì)攻擊.因此，在此情景下，用戶無(wú)法控制自己的隱私數(shù)據(jù).本地差分隱私保護(hù)技術(shù)的出現(xiàn)有效地解決了此類矛盾.該技術(shù)允許每個(gè)用戶擾動(dòng)自身數(shù)據(jù)之后再響應(yīng)收集者的需求.

目前基于本地差分隱私的鍵-值收集算法包括PrivKV[1],KVUE[2],KVOH[2],PCKV-GRR[3],LDPKV[4].PrivKV,KVUE,KVOH,LDPKV算法基于鍵的整個(gè)值域進(jìn)行編碼，利用簡(jiǎn)單隨機(jī)抽樣技術(shù)減少收集者與用戶之間的通信代價(jià).然而，這4種算法均沒(méi)有考慮到鍵的值域稀疏性與偏斜性問(wèn)題.例如，假設(shè)表1中商品的值域?yàn)?.以u(píng)3為例，對(duì)其鍵編碼之后可以獲得長(zhǎng)度為7的向量(〈1,0.6〉,〈0,0〉,〈0,0〉,〈0,0〉,〈0,0〉,〈0,0〉,〈0,0〉).基于該向量進(jìn)行隨機(jī)抽樣時(shí)，〈0,0〉以67的概率被抽取到，而〈0,0〉對(duì)最終統(tǒng)計(jì)結(jié)果無(wú)效.當(dāng)鍵的值域非常大且稀疏時(shí)，PrivKV,KVUE,KVOH,LDPKV算法估計(jì)誤差比較高.

為了解決PrivKV,KVUE,KVOH,LDPKV算法無(wú)法應(yīng)對(duì)鍵的值域稀疏性問(wèn)題，PCKV-GRR利用填充-抽樣[5]技術(shù)減少稀疏性帶來(lái)的影響.其主要思想是利用給定長(zhǎng)度截?cái)嗝總€(gè)用戶所擁有的鍵-值對(duì)集合，然后利用啞元填充那些小于的鍵-值對(duì)集合.例如，表1中用戶u2利用=3截?cái)嗨鶕碛械逆I-值對(duì)集合后，該集合變成{〈k2,0.42〉,〈k4,0.6〉,}，其中為啞元.然而，該算法存在3點(diǎn)不足：

1) 與PrivKV類似，把隱私預(yù)算ε分割成ε1與ε2，其中ε1用來(lái)本地?cái)_動(dòng)鍵，而ε2用來(lái)擾動(dòng)每個(gè)鍵所對(duì)應(yīng)的值；

2) 在設(shè)定本地?cái)_動(dòng)概率時(shí)，沒(méi)有考慮真實(shí)鍵對(duì)最終估計(jì)的影響，無(wú)論鍵擾動(dòng)自身還是其他值均設(shè)定相同的擾動(dòng)概率；

若用戶直接發(fā)送所擁有的鍵-值對(duì)長(zhǎng)度,則會(huì)導(dǎo)致隱私泄露.此外，如何選擇合理的至關(guān)重要，直接影響最終鍵頻率與均值的估計(jì)精度.例如，以真實(shí)稀疏數(shù)據(jù)TalkingData為例，該數(shù)據(jù)集中非零鍵-值對(duì)所占的比例僅為6.9%.根據(jù)該數(shù)據(jù)中60 032個(gè)用戶的鍵-值對(duì)長(zhǎng)度分布(如圖1所示)可知，98%的用戶的鍵-值對(duì)長(zhǎng)度小于50.因此，的理想選擇區(qū)間為[0,50].

Fig. 1 Length distribution of TalkingData key-value pair圖1 TalkingData鍵-值對(duì)長(zhǎng)度分布

結(jié)合文獻(xiàn)[1-4]可知，收集與分析鍵-值數(shù)據(jù)過(guò)程中存在的挑戰(zhàn)包括：1)用戶在設(shè)計(jì)本地?cái)_動(dòng)算法時(shí)，如何設(shè)置真實(shí)鍵的擾動(dòng)概率以及維持鍵與值之間的關(guān)聯(lián)性；2)由于鍵-值數(shù)據(jù)的值域通常很大且稀疏，如何設(shè)計(jì)有效的最優(yōu)截?cái)嚅L(zhǎng)度；3)收集者如何以較小的通信代價(jià)收集所有用戶的鍵-值數(shù)據(jù).總而言之，目前還沒(méi)有一個(gè)行之有效且滿足本地差分隱私的鍵-值收集與分析算法能夠克服上述算法存在的問(wèn)題.為此，本文基于本地差分隱私技術(shù)提出了一種鍵-值數(shù)據(jù)收集算法能夠兼顧3方面挑戰(zhàn)需求.

本文主要貢獻(xiàn)有3個(gè)方面：

1) 為了解決挑戰(zhàn)1，提出一種基于直方圖技術(shù)的鍵-值頻率與均值估計(jì)算法HISKV.不同于PrivKV,KVOH,LDPKV,PCKV-GRR算法，HISKV算法在不分割隱私預(yù)算的情況下，利用直方圖技術(shù)對(duì)鍵-值對(duì)進(jìn)行整體擾動(dòng)，進(jìn)而維持了鍵-值之間的關(guān)聯(lián)性.同時(shí)，對(duì)于真實(shí)的鍵分配較大的本地?cái)_動(dòng)概率.

2) 為了有效解決挑戰(zhàn)2與挑戰(zhàn)3，提出了一種最優(yōu)截?cái)嗨惴▉?lái)尋找截?cái)嚅L(zhǎng)度.不同于PCKV-GRR算法中的經(jīng)驗(yàn)設(shè)置，HISKV利用用戶分組策略與部分隱私預(yù)算估計(jì).結(jié)合利用填充-抽樣技術(shù)處理鍵值域的稀疏性問(wèn)題.

3) 理論分析了HISKV算法滿足ε-本地差分隱私，以及頻率與均值估計(jì)的無(wú)偏性、誤差邊界以及最大偏差.通過(guò)合成數(shù)據(jù)與真實(shí)數(shù)據(jù)實(shí)驗(yàn)分析，HISKV算法具有較高的可用性.

1 相關(guān)工作

本地化差分隱私技術(shù)在假設(shè)收集者完全不可信的情況下，允許每個(gè)用戶利用隨機(jī)響應(yīng)機(jī)制[6]本地?cái)_動(dòng)自己的數(shù)據(jù)，并把噪音結(jié)果發(fā)送給收集者.目前本地化差分隱私研究主要集中于頻率估計(jì)[7-11]與均值估計(jì)[12-15].GRR[7]算法通過(guò)直接編碼將整個(gè)類別屬性的值域進(jìn)行轉(zhuǎn)換，然后對(duì)原始值進(jìn)行本地?cái)_動(dòng)，而該算法的通信代價(jià)與誤差均較高.類似于GRR算法，RAPPOR[8]算法結(jié)合一元編碼與布隆過(guò)濾技術(shù)把類別屬性的整個(gè)值域散列到較小的值域中，結(jié)合散列值域統(tǒng)計(jì)每個(gè)類別屬性的頻率.該算法能夠永久性或者及時(shí)性地保護(hù)每個(gè)用戶的數(shù)據(jù)，相應(yīng)的通信代價(jià)較低.基于RAPPOR算法，O-RR[9]算法借助散列編碼與分組操作估計(jì)整個(gè)類別屬性的概率分布情況.無(wú)論是GRR，RAPPOR及其變種算法，它們的誤差均隨著值域的增加而增加.OLH[7]算法克服了對(duì)值域大小的依賴，該算法利用優(yōu)化本地散列技術(shù)將整個(gè)值域Hash到較小地址空間.為了進(jìn)一步減少通信代價(jià)，在較高計(jì)算代價(jià)的基礎(chǔ)上，SHist[10]算法采用隨機(jī)矩陣投影技術(shù)對(duì)類別屬性值域進(jìn)行編碼，隨機(jī)擾動(dòng)1個(gè)比特位發(fā)送給收集者.此外，LDPMiner[11]算法基于SHist算法研究了集-值數(shù)據(jù)下的Heavy Hitter問(wèn)題.不同于上述基于類別屬性的頻率估計(jì)算法，文獻(xiàn)[12-15]集中研究[-1,1]中數(shù)值均值的估計(jì).Duchi[12-13]算法基于離散化操作，對(duì)數(shù)值型屬性的均值進(jìn)行估計(jì)，并取得較小的通信代價(jià)與較低的估計(jì)誤差.基于Duchi算法，Harmony[14]算法在多維數(shù)值元組中隨機(jī)抽取單個(gè)數(shù)值并擾動(dòng)成離散值，然而該算法的估計(jì)結(jié)果遠(yuǎn)離了區(qū)間[-1,1]中的真實(shí)值.PM[15]算法能夠?qū)-1,1]中的真實(shí)值擾動(dòng)到一個(gè)連續(xù)的區(qū)間，并在該連續(xù)區(qū)間中計(jì)算出該擾動(dòng)值的左右邊界.在隱私預(yù)算較大時(shí)，PM算法的估計(jì)精度明顯高于Duchi與Harmony算法.

盡管文獻(xiàn)[7-15]對(duì)類別屬性與數(shù)值屬性上的頻率與均值進(jìn)行了較為系統(tǒng)的研究，然而這些算法很難直接應(yīng)用于鍵-值數(shù)據(jù)，其主要原因在于這些算法沒(méi)有考慮鍵-值對(duì)之間的關(guān)聯(lián)性.文獻(xiàn)[1-4]對(duì)鍵-值數(shù)據(jù)上的頻率與均值估計(jì)進(jìn)行了研究.基于RAPPOR與Harmony算法，PrivKV[1]算法對(duì)鍵-值數(shù)據(jù)的頻率與均值進(jìn)行了估計(jì)，PrivKV與Harmony的主要區(qū)別在于PrivKV把擾動(dòng)后的數(shù)值修正操作放到了收集者端.然而，PrivKV算法由于分割隱私預(yù)算導(dǎo)致估計(jì)精度較低.KVOH[2]與LDPKV[4]算法結(jié)合鍵-值數(shù)據(jù)值域與擾動(dòng)輸出值域之間的整體映射關(guān)系，利用GRR算法對(duì)離散化后的鍵-值對(duì)進(jìn)行擾動(dòng).然而，這2種算法的誤差易受到值域大小的影響.不同于PrivKV,KVOH,LDPKV 3種算法，PCKV-GRR[3]算法利用填充-抽樣操作對(duì)原始鍵-值序列進(jìn)行截?cái)嗯c抽樣，然后再利用GRR算法進(jìn)行本地?cái)_動(dòng).盡管PCKV-GRR在值域較大且稀疏的情況下優(yōu)于KVOH與PrivKV，但是該算法的誤差同樣受到值域大小的影響，并且沒(méi)有顧及到如何設(shè)置有效鍵的擾動(dòng)概率以及截?cái)嚅L(zhǎng)度的計(jì)算方法.基于上述分析，本文提出一種基于本地差分隱私的鍵-值收集與分析算法HISKV，該算法利用直方圖技術(shù)統(tǒng)一估計(jì)鍵的頻率及其均值，利用最優(yōu)截?cái)嚅L(zhǎng)度與填充-抽樣技術(shù)處理值域稀疏問(wèn)題.

2 定義與問(wèn)題

2.1 本地差分隱私

不同于中心化差分隱私保護(hù)技術(shù)，本地差分隱私技術(shù)通常要求用戶在本地保護(hù)自己的數(shù)據(jù)，把擾動(dòng)之后的數(shù)據(jù)報(bào)告給不可信的收集者，從而實(shí)現(xiàn)隱私不被泄露.本地差分隱私的形式化定義為：

定義1.ε-本地差分隱私.給定一個(gè)隨機(jī)算法A及其定義域Dom(A)和值域Range(A)，若算法A在任意2條不同元組t與t′(t,t′∈Dom(A))上得到相同輸出結(jié)果o(o∈Range(A))滿足不等式：

Pr[A(t)=o]≤eε×Pr[A(t′)=o]，

(1)

則A滿足ε-本地差分隱私.其中ε為隱私預(yù)算，其值越小則算法A的隱私保護(hù)程度越高.

2.2 隨機(jī)應(yīng)答機(jī)制

隨機(jī)應(yīng)答機(jī)制[6]是實(shí)現(xiàn)本地差分隱私的常用技術(shù).在用戶發(fā)送數(shù)據(jù)ti之前，對(duì)其進(jìn)行隨機(jī)擾動(dòng).該機(jī)制的原始思想是用戶在響應(yīng)敏感的布爾問(wèn)題時(shí)，以概率p真實(shí)應(yīng)答，以q的概率給出相反的應(yīng)答.為了使隨機(jī)應(yīng)答機(jī)制滿足ε-本地差分隱私，通常設(shè)置p=eε(1+eε),q=1(1+eε).目前，基于隨機(jī)應(yīng)答機(jī)制出現(xiàn)了以GRR為代表的本地?cái)_動(dòng)算法.給定ki,kj∈{1,2,…,d}，GRR算法：

(2)

2.3 問(wèn)題描述

類似文獻(xiàn)[4]，給定n個(gè)用戶U={u1,u2,…,un}和一個(gè)收集者，每個(gè)用戶擁有鍵-值對(duì)集合.K={k1,k2,…,kd}為鍵的值域，d為該值域大小，V=[-1,1]為鍵所對(duì)應(yīng)值的值域.Si={〈kj,vj〉|1≤j≤li,kj∈K,vj∈V}為用戶ui所擁有的鍵-值對(duì)集合，其中l(wèi)i表示Si的長(zhǎng)度.收集者收集所有用戶的鍵-值數(shù)據(jù)后，通常估計(jì)鍵所對(duì)應(yīng)的頻率以及值所對(duì)應(yīng)的均值，具體計(jì)算為

(3)

(4)

采用均方誤差與相對(duì)誤差度量fk與μk的估計(jì)精度.本文要解決的問(wèn)題是在設(shè)計(jì)滿足本地差分隱私的頻率與均值估計(jì)算法的同時(shí)，要盡可能獲得誤差較小的估計(jì)結(jié)果.

3 基于直方圖技術(shù)的鍵-值數(shù)據(jù)收集算法

3.1 HISKV算法

不同于文獻(xiàn)[1-4]中的收集算法，HISKV算法不需要對(duì)每個(gè)用戶的鍵按照值域進(jìn)行編碼，而是僅對(duì)鍵所對(duì)應(yīng)值進(jìn)行離散化處理.給定某個(gè)鍵-值對(duì)〈k,v〉，只對(duì)值v進(jìn)行離散化操作，結(jié)果為

(5)

例如，設(shè)〈漢堡,0.4〉為某一個(gè)鍵-值對(duì)，則0.4以0.7的概率離散化+1；以0.3的概率離散化為-1.

根據(jù)式(5)可知，每個(gè)用戶所擁有鍵的對(duì)應(yīng)值均被離散化成2個(gè)類別，分別為+1或者-1，而所有的鍵還保持原來(lái)的值.因此，可以在{d,+1}與{d,-1}這2個(gè)二維值域內(nèi)構(gòu)建相應(yīng)的直方圖來(lái)估計(jì)鍵的頻率以及所對(duì)應(yīng)值的均值，其中每個(gè)鍵即是直方圖的桶.結(jié)合桶的頻率可以估計(jì)每個(gè)鍵的頻率及所對(duì)應(yīng)值的均值.如表1所示，用戶u1，u2，u3的鍵-值對(duì)經(jīng)過(guò)離散化之后的值為{〈k1,+1〉,〈k2,+1〉,〈k3,-1〉,〈k4,-1〉,〈k5,+1〉},{〈k2,-1〉,〈k4,+1〉},{〈k5,+1〉}.根據(jù)d={k1,k2,k3,k4,k5,k6,k7}以及d所對(duì)應(yīng)的值{+1,-1}可獲得相應(yīng)直方圖(如圖2所示).根據(jù)圖2可以估計(jì)出d中每個(gè)鍵的頻率及均值.例如，鍵k2的頻率為23，k2所對(duì)應(yīng)值的均值為1.

Fig. 2 Two-dimensional range histogram圖2 二維值域直方圖

結(jié)合直方圖技術(shù)的HISKV算法如算法1所示：

算法1.HISKV算法.

輸入：n個(gè)用戶、每個(gè)用戶所擁有的鍵-值對(duì)集合S={S1,S2,…,Sn}、隱私預(yù)算ε、鍵的值域d；

輸出：頻率向量f*、均值向量μ*.

①f*←?,μ*←?；

② 收集者將n個(gè)用戶分成2組βn,(1-β)n；

④ for 在[(1-β)n]內(nèi)的每個(gè)用戶ui執(zhí)行步驟⑤～⑥;*每個(gè)用戶擾動(dòng)*

LRR_KV(Si,ε,)；

⑦ end for

⑨ ifkj∈[1,2(d+)] then

HISKV算法是基于本地差分隱私解決鍵的頻率以及所對(duì)應(yīng)值的估計(jì)問(wèn)題.首先收集者從n個(gè)用戶中抽取βn個(gè)用戶(β為抽取概率)(步驟②).基于βn個(gè)用戶利用OETL算法估計(jì)最優(yōu)截?cái)嚅L(zhǎng)度(步驟③).每個(gè)用戶結(jié)合截?cái)嚅L(zhǎng)度對(duì)自身所擁有的鍵值對(duì)集合進(jìn)行截?cái)嗷蛘咛畛?然后再均勻隨機(jī)抽樣一個(gè)鍵-值對(duì)本地?cái)_動(dòng)，并把擾動(dòng)結(jié)果報(bào)告給收集者(步驟④～⑦).收集者聚集所有用戶的報(bào)告值后，估計(jì)每個(gè)鍵的頻率以及值所對(duì)應(yīng)的均值(步驟⑧～).由LRR_KV算法中的抽樣可知，每個(gè)用戶僅擾動(dòng)一組鍵-值對(duì)報(bào)告給收集者，進(jìn)而使得收集者與用戶之間的通信代價(jià)為O(1).接下來(lái)闡述LRR_KV與OETL算法，其中LRR_KV算法具體細(xì)節(jié)如算法2所示：

算法2.LRR_KV算法.

輸入：(1-β)n用戶中任意ui的鍵-值集合Si、隱私預(yù)算ε、截?cái)嚅L(zhǎng)度；

① 〈kj,vj〉←Padding-Sampling(Si,)；

②〈kj,±1〉←Discretizing(〈kj,vj〉)；

③ if thej-th pair 〈kj,vj〉 is 〈kj,1〉 then

⑤ else if thej-th pair 〈kj,vj〉 is 〈kj,-1〉 then

⑦ end if

結(jié)合LRR_KV算法，用戶ui首先利用算法3步驟①對(duì)集合Si進(jìn)行填充-抽樣操作，進(jìn)而獲得〈kj,vj〉.結(jié)合〈kj,vj〉，用戶ui利用式(5)對(duì)值vj進(jìn)行離散化操作(步驟②).然后結(jié)合離散化結(jié)果〈kj,±1〉進(jìn)行本地?cái)_動(dòng)(步驟②～⑦).結(jié)合用戶ui的鍵-值對(duì)集合Si，LRR_KV算法的具體實(shí)現(xiàn)思路如圖3所示：

Fig. 3 LRR KV local disturbance圖3 LRR_KV本地?cái)_動(dòng)示意圖

根據(jù)圖3可知，用戶ui所抽取的鍵-值對(duì)〈kj,vj〉經(jīng)過(guò)離散化后變成〈kj,1〉或者〈kj,-1〉.以概率p1,q1,q2分別將〈kj,1〉與〈kj,-1〉擾動(dòng)成4種不同的情況.其中一種情況是〈kj,1〉與〈kj,-1〉以概率p1擾動(dòng)成自身.由式(2)可知，p1=eε(eε+d′-1)，其中，d′=2(d+).如何設(shè)置剩余3種的擾動(dòng)概率是一個(gè)大的挑戰(zhàn).文獻(xiàn)[3]中PCKV-GRR算法在相應(yīng)參數(shù)取得最優(yōu)時(shí)，剩余3種概率均取值為1(eε+d′-1).然而，該算法卻忽略一種事實(shí)，即不論〈kj,1〉以概率q1擾動(dòng)成〈kj,-1〉或者〈kj,-1〉以概率q1擾動(dòng)成〈kj,1〉，鍵kj并沒(méi)有被擾動(dòng)成值域d′中的其他值.此種情況對(duì)鍵kj的頻率及其所對(duì)應(yīng)值的均值估計(jì)均有效.因此，概率q1的值不應(yīng)該取平均值，應(yīng)該傾向性地取較大的值.由定義1可知下式成立：

影響LRR_KV算法本地?cái)_動(dòng)效果包括2個(gè)因素：Padding-Sampling算法的設(shè)計(jì)以及如何獲得最優(yōu)截?cái)嚅L(zhǎng)度.接下來(lái)結(jié)合文獻(xiàn)[5]設(shè)計(jì)填充-抽樣算法.

算法3.Padding-Sampling算法.

輸入：Si、截?cái)嚅L(zhǎng)度；

輸出：所抽取的鍵-值對(duì)(kj,vj).

① ifli>then*li表示Si的長(zhǎng)度*

②ui不放回地從Si,隨機(jī)采樣個(gè)鍵值對(duì)，得到抽取個(gè)鍵-值對(duì)*

③ else ifli

④ui用-li個(gè)從{〈1,0〉,〈2,0〉,…,〈l,0〉}集合采樣的啞元填充Si,得到

⑥ end if

⑦ return 〈kj,vj〉.

用戶ui利用Si的長(zhǎng)度li與截?cái)嚅L(zhǎng)度比較.如果li>，則從Si中無(wú)放回地抽取個(gè)鍵-值對(duì)形成(步驟①②);否則，從啞元鍵-值對(duì)集合{〈1,0〉,〈2,0〉,…,〈l,0〉}中隨機(jī)抽取-li個(gè)鍵-值對(duì)填充Si，并獲得(步驟③④).結(jié)合用戶以概率1抽取一個(gè)鍵-值對(duì)〈kj,vj〉.

算法4.OETL算法.

輸入：n、β、ε、鍵的值域d；

① for 在[βn]的每個(gè)用戶ui執(zhí)行步驟②～③;*每個(gè)用戶擾動(dòng)*

④ end for

⑧ end for

βn中的每個(gè)用戶利用GRR算法本地?cái)_動(dòng)自己鍵-值對(duì)長(zhǎng)度li，步驟①～④發(fā)送給收集者；步驟⑤～⑧收集者計(jì)算并修正每個(gè)長(zhǎng)度的計(jì)數(shù);步驟⑨利用第90個(gè)百分位數(shù)求解后;步驟⑩收集者將發(fā)送給(1-β)n中的每個(gè)用戶.

3.2 HISKV隱私性與可用性分析

本節(jié)主要從本地差分隱私闡述HISKV算法的隱私性以及無(wú)偏性估計(jì)、方差及其最大偏差來(lái)闡述其可用性.從算法1可知，HISKV算法采用用戶分組的形式分別估計(jì)頻率與均值(LRR_KV算法)以及最優(yōu)截?cái)嚅L(zhǎng)度(OETL算法).

定理1.OETL算法滿足ε-本地差分隱私.

證明. 結(jié)合[βn]集合中用戶所給定任意的li與lj，算法OETL的輸出為l′，則不等式成立：

則OETL算法滿足ε-本地差分隱私.

證畢.

定理2.LRR_KV算法滿足ε-本地差分隱私.

1) 當(dāng)〈k*,v*〉=〈kj,1〉時(shí)，根據(jù)定義1可知：

2) 當(dāng)〈k*,v*〉=〈kj,-1〉時(shí)，類似于第1種情況：

通過(guò)4種情況可知LRR_KV算法滿足ε-本地差分隱私.

證畢.

由定理1與定理2以及差分隱私的序列組合性質(zhì)可知，HISKV收集鍵-值數(shù)據(jù)的過(guò)程滿足本地差分隱私.HISKV的可用性主要從LRR_KV算法與OETL算法的誤差來(lái)度量.OETL算法的誤差主要來(lái)自于GRR算法的本地?cái)_動(dòng)操作，根據(jù)文獻(xiàn)[7]可知，OETL算法產(chǎn)生的方差為βn(eε+d-2)(eε-1)2.LRR_KV算法的可用性主要從無(wú)偏性、方差、最大偏差來(lái)度量.盡管收集者可以估計(jì)出鍵k的頻率以及所對(duì)應(yīng)值的均值但由于LRR_KV算法的本地?cái)_動(dòng)使得與會(huì)偏離真實(shí)值.而我們期望與均要滿足無(wú)偏性，即與成立.

根據(jù)二項(xiàng)分布構(gòu)造極大似然函數(shù)：

(6)

(7)

將式(7)帶入式(6)可推理出：

(8)

證畢.

(9)

(10)

證畢.

其中n′=(1-β)n.

(11)

(12)

證畢.

證畢.

至少以概率1-η成立，其中n為用戶個(gè)數(shù)，為最優(yōu)截?cái)嚅L(zhǎng)度，β為用戶分組抽樣率.

則可知：

(13)

證畢.

證畢.

4 實(shí)驗(yàn)結(jié)果與分析

文獻(xiàn)[4]結(jié)論部分所給出的未來(lái)研究點(diǎn)正是本文的研究工作。因此，從實(shí)驗(yàn)平臺(tái)、實(shí)驗(yàn)數(shù)據(jù)集以及隱私參數(shù)ε的設(shè)置均與文獻(xiàn)[4]保持一致。實(shí)驗(yàn)平臺(tái)是4核Intel i7-4790 CPU(4 GHz)，8 GB內(nèi)存，Win7系統(tǒng)，Python實(shí)現(xiàn)所有算法.采用TalkingData，JData，GAUSS，LNR四個(gè)數(shù)據(jù)集驗(yàn)證文中相關(guān)算法.4個(gè)數(shù)據(jù)集具體細(xì)節(jié)如表2所示：

Table 2 Characteristics of Datasets

其中GAUSS和LNR這2個(gè)數(shù)據(jù)集為合成數(shù)據(jù)集，鍵和值分別遵循高斯和線性分布.TalkingData是從與移動(dòng)應(yīng)用的SDK中收集而得，包含60 822個(gè)設(shè)備和306類應(yīng)用程序.JData來(lái)自于JD.com，包含2016年的5 060萬(wàn)條銷售記錄，該數(shù)據(jù)集記錄了2016年間105 180個(gè)用戶對(duì)442個(gè)品牌的5 060萬(wàn)條購(gòu)買記錄.

隱私參數(shù)ε分別取值為0.1，0.2，0.4，0.8，1.6，3.2.此外，實(shí)驗(yàn)分別對(duì)4個(gè)數(shù)據(jù)集中頻率最高的top10， top20，top30，top40，top50的鍵值進(jìn)行統(tǒng)計(jì)，在每種情況下進(jìn)行500次實(shí)驗(yàn)并求取平均值作為最終的計(jì)算結(jié)果.

在文獻(xiàn)[4]中，我們分別實(shí)現(xiàn)了LDPKV,PrivKV,KVOH,RAPPOR以及Harmony算法，并結(jié)合MSE與RE進(jìn)行了綜合對(duì)比分析.因此，本文主要對(duì)比HISKV算法與上述6種算法的性能.

1) 基于TalkingData數(shù)據(jù)集的多種算法的MSE和RE值比較.

圖4(a)～(f)描述了HISKV，PCKV-GRR，PrivKV，KVOH，LDPKV，RAPPOR，Harmony算法的MSE值和RE值的比較結(jié)果.由圖4(a)的實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，當(dāng)ε從0.1變化到3.2時(shí)，6種算法的MSE值均減少，而HISKV算法的精度優(yōu)于其他5種算法.當(dāng)ε=1.6時(shí)，HISKV算法的精度是PCKV-GRR算法的近4倍，是PrivKV和KVOH算法的將近3倍，是LDPKV算法的將近1倍.盡管文獻(xiàn)[4]中提到LDPKV算法優(yōu)于PrivKV和KVOH算法，然而由于該算法沒(méi)有考慮到鍵-值的稀疏性(如圖1所示)，過(guò)多的〈0, 0〉對(duì)使得該算法的MSE大于HISKV算法.

Fig. 4 The key-value frequency and mean estimation of TalkingData圖4 基于TalkingData的鍵-值頻率與均值估計(jì)結(jié)果

由圖4(c)～(f)可知，當(dāng)ε固定，鍵的數(shù)目從top10增加到top50時(shí)，相應(yīng)算法的RE值均增大，但HISKV算法的精度卻優(yōu)于其他4種算法，其原因在于HISKV算法利用最優(yōu)截?cái)嚅L(zhǎng)度削弱了鍵-值值域稀疏帶來(lái)的影響.由圖4(b)中6種算法的均值MSE比較結(jié)果可知，當(dāng)ε從0.1變化到3.2時(shí)，6種算法的均值MSE均呈現(xiàn)下降趨勢(shì)，而HISKV算法估計(jì)出的均值精度明顯優(yōu)于其他5種算法.當(dāng)ε=1.6時(shí)，HISKV算法的均值精度是LDPKV算法的將近1倍.其主要原因在于HISKV算法利用直方圖將鍵-值對(duì)進(jìn)行統(tǒng)一編碼擾動(dòng)，避免了隱私預(yù)算的分割，合理增大了擾動(dòng)成真實(shí)鍵的本地?cái)_動(dòng)概率.此外，HISKV算法利用截?cái)?抽樣技術(shù)避免了鍵-值稀疏性帶來(lái)的影響，實(shí)現(xiàn)了隱私增強(qiáng).

2) 基于JData數(shù)據(jù)集的多種算法的MSE和RE值比較.

圖5(a)～(f)描述了JData數(shù)據(jù)集上7種算法的MSE值和RE值的比較結(jié)果.根據(jù)圖5(a)的實(shí)驗(yàn)結(jié)果可知，當(dāng)ε從0.1變化到3.2時(shí)，6種算法的MSE值均減少.當(dāng)ε=1.6時(shí)，HISKV算法的精度是PCKV-GRR算法的近6倍，是PrivKV和KVOH算法的將近3倍，是LDPKV的將近2倍.其主要原因是PCKV-GRR算法沒(méi)有顧及真實(shí)鍵本地?cái)_動(dòng)概率的傾向性設(shè)置問(wèn)題，PrivKV和KVOH算法隱私預(yù)算進(jìn)行分割，LDPKV算法沒(méi)有考慮值域稀疏性帶來(lái)的影響.圖5(b)描述了HISKV算法與其他5種算法有關(guān)均值MSE值的比較.當(dāng)ε從0.1變化到3.2時(shí)，HISKV算法的均值精度優(yōu)于其他5種算法.當(dāng)ε=0.8時(shí)，HISKV算法的均值精度是PrivKV算法的近4倍，是PCKV-GRR算法的近3倍，是Harmony與KVOH的近2倍，是LDPKV算法的近1倍.在固定ε且變換top10到top50的情況下，HISKV算法同樣優(yōu)于其他4種算法.其主要原因是HISKV算法利用抽樣-截?cái)嗉夹g(shù)、本地?cái)_動(dòng)概率的傾向性設(shè)置以及隱私預(yù)算不分割策略提升了鍵-值的頻率與均值估計(jì)精度.

Fig. 5 The key-value frequency and mean estimation of JData圖5 基于JData的鍵-值頻率與均值估計(jì)結(jié)果

Fig. 6 The key-value frequency and mean estimation of LNR圖6 基于LNR的鍵-值頻率與均值估計(jì)結(jié)果

Fig. 7 The key-value frequency and mean estimation of GAUSS圖7 基于GAUSS的鍵-值頻率與均值估計(jì)結(jié)果

3) 基于LNR，GAUSS數(shù)據(jù)集的多種算法的MSE和RE值比較.

圖6和圖7描述了7種算法基于LNR與GAUSS合成數(shù)據(jù)集上的MSE與RE的對(duì)比結(jié)果.在百萬(wàn)級(jí)別的數(shù)據(jù)上，當(dāng)ε從0.1變化到3.2時(shí)，HISKV算法的精度優(yōu)于其他6種算法，如圖6(a)、圖6(b)、圖7(a)、圖7(b)所示.文獻(xiàn)[4]給出了LDPKV算法在LNR與GAUSS數(shù)據(jù)集上優(yōu)于PrivKV,KVOH,RAPPOR以及Harmony算法.而本文的HISKV算法卻明顯有LDPKV算法，其主要原因在于LNR與GAUSS數(shù)據(jù)集中同樣存在鍵-值的稀疏性問(wèn)題，而HISKV算法的最優(yōu)截?cái)嚅L(zhǎng)度技術(shù)卻可以有效減弱鍵-值稀疏性帶來(lái)的影響.此外，當(dāng)固定鍵值的個(gè)數(shù)且ε從0.1變化到0.8時(shí)，所有算法在LNR與GAUSS數(shù)據(jù)集上的RE值均下降，如圖6(c)～(f)、圖7(c)～(f)所示.當(dāng)ε=0.2時(shí)，鍵值為top40時(shí)，HISKV算法的精度相對(duì)于PCKV-GRR算法，在LNR數(shù)據(jù)集上達(dá)到了近5倍，在GAUSS數(shù)據(jù)集上達(dá)到了近6倍，其主要原因是HISKV算法利用直方圖將鍵-值對(duì)看成一個(gè)整體進(jìn)行擾動(dòng)，不但減少了隱私預(yù)算分割和擾動(dòng)次數(shù)，同時(shí)其增大了擾動(dòng)成真實(shí)數(shù)據(jù)的概率.

5 結(jié)束語(yǔ)

針對(duì)本地差分隱私保護(hù)下收集鍵-值數(shù)據(jù)存在的問(wèn)題，本文結(jié)合現(xiàn)有的該類數(shù)據(jù)收集算法存在的不足，提出了基于直方圖技術(shù)的收集算法HISKV，引入基于用戶分組策略的最優(yōu)截?cái)嚅L(zhǎng)度估計(jì)算法，結(jié)合真實(shí)鍵的實(shí)際擾動(dòng)情況設(shè)置合理的擾動(dòng)概率，并利用填充-抽樣技術(shù)減少用戶與收集者之間的通信代價(jià).從本地差分隱私定義角度分析了HISKV滿足ε-本地差分隱私.理論分析了HISKV的無(wú)偏性、所產(chǎn)生的方差以及最大偏差，最后通過(guò)4種數(shù)據(jù)集驗(yàn)證了HISKV算法的可用性.實(shí)驗(yàn)結(jié)果表明，HISKV明顯優(yōu)于現(xiàn)有的同類算法.未來(lái)工作考慮動(dòng)態(tài)環(huán)境下的隱私鍵-值數(shù)據(jù)的收集與分析問(wèn)題.