效用優(yōu)化的本地差分隱私集合數(shù)據(jù)頻率估計(jì)機(jī)制

曹依然 朱友文,2 賀星宇 張 躍

1(南京航空航天大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 南京 211106) 2(廣西可信軟件重點(diǎn)實(shí)驗(yàn)室(桂林電子科技大學(xué)) 廣西桂林 541004)

隨著經(jīng)濟(jì)科技的飛速發(fā)展和信息技術(shù)的普及應(yīng)用，人們時(shí)時(shí)刻刻都在不斷地產(chǎn)生大量的數(shù)據(jù)信息.作為一種重要的數(shù)據(jù)形式，集合數(shù)據(jù)在日常生活中有著廣泛的應(yīng)用場(chǎng)景，如購(gòu)買過(guò)的物品、近期到過(guò)的地點(diǎn)等，都可以表示為集合數(shù)據(jù).通過(guò)對(duì)這些數(shù)據(jù)進(jìn)行收集、記錄和分析，可以挖掘出它們中的隱藏信息，對(duì)學(xué)術(shù)、工業(yè)、社會(huì)服務(wù)等多個(gè)領(lǐng)域都有重要意義.例如通過(guò)分析用戶的購(gòu)買記錄，可以得出用戶購(gòu)買需求，從而提高交易成功率；通過(guò)分析車聯(lián)網(wǎng)系統(tǒng)中的GPS數(shù)據(jù)，可以得出實(shí)時(shí)路況和擁堵情況，從而提供交通流量控制服務(wù).但這些數(shù)據(jù)中往往包含著大量隱私信息，如購(gòu)物數(shù)據(jù)會(huì)反映個(gè)人生活習(xí)慣和財(cái)務(wù)狀況、軌跡數(shù)據(jù)會(huì)包含家庭和工作地址，如果直接將這些數(shù)據(jù)提供給其他人使用，不僅會(huì)對(duì)個(gè)人的人身安全、財(cái)產(chǎn)安全造成極大的威脅，也會(huì)使得用戶不再愿意共享數(shù)據(jù).目前，區(qū)塊鏈[1]、邊緣計(jì)算[2]、機(jī)器學(xué)習(xí)[3-4]等領(lǐng)域已經(jīng)關(guān)注到了隱私保護(hù)問(wèn)題的重要性，并針對(duì)特定問(wèn)題提出了隱私保護(hù)的解決方案.然而，如何在保護(hù)用戶隱私的前提下對(duì)數(shù)據(jù)進(jìn)行收集，仍是學(xué)術(shù)界亟待解決的問(wèn)題.

當(dāng)今，針對(duì)隱私保護(hù)，主要的解決方案可以分為3類：匿名化技術(shù)[5-6]、密碼學(xué)技術(shù)[7-8]，以及差分隱私[9-10].差分隱私擁有嚴(yán)格的形式化安全模型，并具有高效低開銷的特點(diǎn)，是當(dāng)今研究的熱點(diǎn)方向.作為差分隱私的一大變種，本地差分隱私(local differential privacy, LDP)[11]在繼承了差分隱私優(yōu)點(diǎn)的基礎(chǔ)上，摒棄了對(duì)可信第三方的需求，大大提高了模型的實(shí)用性.自從2013年被正式提出至今，本地差分隱私技術(shù)已經(jīng)有了長(zhǎng)足的發(fā)展與改進(jìn)，其應(yīng)用場(chǎng)景也十分寬泛，如機(jī)器學(xué)習(xí)[12-13]、網(wǎng)絡(luò)服務(wù)[14]、數(shù)據(jù)的統(tǒng)計(jì)與優(yōu)化[15-17]，等等.同時(shí)，本地差分隱私也已經(jīng)廣泛部署到工業(yè)界實(shí)際應(yīng)用中，蘋果公司將其應(yīng)用到手機(jī)上來(lái)保護(hù)用戶的使用數(shù)據(jù)[18-19]，谷歌公司也設(shè)計(jì)了基于本地差分隱私的組件RAPPOR[20]來(lái)采集用戶行為數(shù)據(jù).

但是，現(xiàn)有的本地差分隱私機(jī)制大多并未考慮到，針對(duì)實(shí)際應(yīng)用中不同數(shù)據(jù)的隱私保護(hù)需求差異，可以通過(guò)降低對(duì)非敏感數(shù)據(jù)的保護(hù)程度來(lái)減小估計(jì)誤差.為此，Murakami等人提出了效用優(yōu)化本地差分隱私(utility-optimized local differential privacy, ULDP)模型[21]，通過(guò)對(duì)不同的數(shù)據(jù)處以不同的擾動(dòng)方法，從而在保障敏感數(shù)據(jù)隱私安全的前提下提高數(shù)據(jù)效用.然而，ULDP模型僅僅可以處理用戶數(shù)據(jù)均為敏感值或均為非敏感值的情況，當(dāng)用戶數(shù)據(jù)為集合數(shù)據(jù)，并且既包含敏感值又包含非敏感值時(shí)，ULDP模型難以直接適用.在很多現(xiàn)實(shí)應(yīng)用中，用戶的集合數(shù)據(jù)會(huì)同時(shí)包含敏感值和非敏感值，比如，一位用戶的購(gòu)物訂單記錄為{梳子，洗發(fā)水，衛(wèi)生紙，胃藥}，此時(shí)梳子、衛(wèi)生紙和洗發(fā)水是非敏感值，而胃藥則是敏感值，ULDP模型無(wú)法直接處理該類數(shù)據(jù).因此，需要提出一種新的模型，來(lái)處理用戶數(shù)據(jù)且既包含敏感值又包含非敏感值的情況，保證在不降低對(duì)敏感數(shù)據(jù)保護(hù)效果的前提下，提高頻率估計(jì)結(jié)果準(zhǔn)確度.

本文首先定義了針對(duì)集合數(shù)據(jù)的效用優(yōu)化本地差分隱私模型，該模型是ULDP模型在集合數(shù)據(jù)上的理論拓展，可以處理用戶數(shù)據(jù)且既包含敏感值又包含非敏感值的情況，具有更廣泛的適用性.隨后，本文基于集合數(shù)據(jù)效用優(yōu)化本地差分隱私(set-valued data utility-optimized local differential privacy, SULDP)模型提出了5種頻率估計(jì)機(jī)制，并通過(guò)理論分析證明了所提出的5種機(jī)制能夠?qū)γ舾袛?shù)據(jù)實(shí)現(xiàn)與現(xiàn)有的本地差分隱私機(jī)制完全相同的保護(hù)效果，同時(shí)通過(guò)降低對(duì)非敏感數(shù)據(jù)的保護(hù)效果，提高頻率估計(jì)結(jié)果的準(zhǔn)確度.最后，本文在多個(gè)真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集上展開了實(shí)驗(yàn)，結(jié)果表明本文所提機(jī)制可以有效降低估計(jì)誤差，提升整體數(shù)據(jù)效用.

概括地說(shuō)，本文的主要貢獻(xiàn)包括3個(gè)方面:

1)定義了SULDP模型;

2)基于傳統(tǒng)頻率估計(jì)機(jī)制，本文提出了符合SULDP模型的5種頻率估計(jì)機(jī)制suGRR,suGRR-Sample,suRAP,suRAP-Sample和suWheel;

3)通過(guò)理論分析和實(shí)驗(yàn)對(duì)比了提出的5種機(jī)制，證明了這5種機(jī)制相較于原始機(jī)制均在效用方面有所提升，其中suWheel機(jī)制表現(xiàn)最優(yōu).

1 相關(guān)工作

針對(duì)用戶集合數(shù)據(jù)進(jìn)行的統(tǒng)計(jì)分析在推薦系統(tǒng)等領(lǐng)域都有著重要的研究意義，直觀地，我們可以將針對(duì)類別數(shù)據(jù)的方法應(yīng)用到集合數(shù)據(jù)的每一個(gè)條目上，但同時(shí)為了滿足差分隱私的定義，還需要根據(jù)條目數(shù)量對(duì)隱私預(yù)算進(jìn)行劃分，當(dāng)數(shù)量較大時(shí)，會(huì)導(dǎo)致數(shù)據(jù)效用急劇降低.

文獻(xiàn)[22]基于RAPPOR實(shí)現(xiàn)了集合數(shù)據(jù)頻率估計(jì)，雖然比直接劃分隱私預(yù)算的效果要好，但是在進(jìn)行擾動(dòng)時(shí)仍然需要將隱私預(yù)算除以集合數(shù)據(jù)條數(shù)，集合變大時(shí)數(shù)據(jù)效用仍然很低，并且通信代價(jià)也很高.文獻(xiàn)[23]提出了PrivSet機(jī)制，它是基于指數(shù)機(jī)制實(shí)現(xiàn)的，輸出域?yàn)閿?shù)據(jù)域的大小固定為k的所有子集，根據(jù)與輸入集合是否相交來(lái)確定各個(gè)子集的輸出概率，數(shù)據(jù)效用相較于文獻(xiàn)[22]有所提升，但是k的最優(yōu)取值是需要根據(jù)理論分析的均方誤差(MSE)來(lái)確定的，由于分析結(jié)果非常復(fù)雜，無(wú)法直接計(jì)算出最優(yōu)的k，只能通過(guò)順序查找來(lái)找到，當(dāng)數(shù)據(jù)域較大時(shí)就會(huì)造成很高的計(jì)算代價(jià).文獻(xiàn)[24]提出了Wheel機(jī)制，這也是目前效果最好的集合數(shù)據(jù)頻率估計(jì)機(jī)制.Wheel機(jī)制通過(guò)哈希將原始集合數(shù)據(jù)映射到[0,1)上，然后以一定的概率密度從[0,1)上取值作為輸出，Wheel機(jī)制的通信代價(jià)比RAPPOR和PrivSet都要低，并且文獻(xiàn)[24]還證明了Wheel機(jī)制的MSE達(dá)到了集合數(shù)據(jù)頻率估計(jì)MSE的理論最優(yōu)下界.但是Wheel等機(jī)制都是在LDP的定義下實(shí)現(xiàn)的，LDP模型為所有用戶和所有輸入提供同等的隱私保護(hù).

文獻(xiàn)[21]將輸入域分為敏感數(shù)據(jù)和非敏感數(shù)據(jù)，在保證敏感數(shù)據(jù)的不可區(qū)分性的前提下，以一定的概率降低對(duì)非敏感數(shù)據(jù)的保護(hù)效果，提高了整體的數(shù)據(jù)效用.類似的機(jī)制還有文獻(xiàn)[25-26]提出的個(gè)性化本地差分隱私，為用戶提供了個(gè)性化的隱私需求，但并未考慮到數(shù)據(jù)層面.而文獻(xiàn)[27]提出的地理位置不可區(qū)分性則主要根據(jù)不同數(shù)據(jù)之間的距離來(lái)確定它們輸出同一結(jié)果的概率，距離越近則概率越大，這也可以在一定程度上提高數(shù)據(jù)效用，但是由于距離度量需要滿足三角不等式，因此針對(duì)某些數(shù)據(jù)類型是不適用的.

但是ULDP是基于類別數(shù)據(jù)提出的，如果想直接應(yīng)用到集合數(shù)據(jù)就需要?jiǎng)澐蛛[私預(yù)算，這會(huì)對(duì)數(shù)據(jù)效用產(chǎn)生極大的影響.綜上，現(xiàn)有方法均存在不足之處，本文針對(duì)集合數(shù)據(jù)的效用優(yōu)化頻率估計(jì)機(jī)制進(jìn)行了研究.

2 背景知識(shí)

2.1 本地差分隱私

在本地差分隱私中，由用戶自己在本地對(duì)數(shù)據(jù)進(jìn)行擾動(dòng)，然后將擾動(dòng)后的數(shù)據(jù)發(fā)送給服務(wù)器，服務(wù)器再利用這些數(shù)據(jù)計(jì)算得到所需的統(tǒng)計(jì)信息.由于服務(wù)器無(wú)法接觸到用戶的原始數(shù)據(jù)，因而無(wú)法獲得用戶的隱私信息.本地差分隱私的形式化定義如下.

定義1.ε-LDP[11].給定隱私預(yù)算ε≥0，對(duì)輸入域?yàn)閄、輸出域?yàn)閅的擾動(dòng)機(jī)制M:X→Y，該擾動(dòng)機(jī)制M滿足ε-LDP，當(dāng)且僅當(dāng)對(duì)于任意輸入x,x′∈X，得到任意輸出y∈Y的概率滿足

M(y|x)≤eεM(y|x′).

(1)

不難看出，ε-LDP保證了任意攻擊者無(wú)法從輸出結(jié)果推斷出確切的原始輸入，并且當(dāng)隱私預(yù)算ε趨近于0時(shí)，X中所有數(shù)據(jù)都以幾乎相同的概率輸出同一結(jié)果，即隱私預(yù)算ε越小，對(duì)用戶隱私保護(hù)程度越強(qiáng).

2.2 效用優(yōu)化本地差分隱私

LDP并未考慮用戶不同數(shù)據(jù)的敏感度差異，如統(tǒng)計(jì)用戶身體狀況時(shí)，對(duì)于“癌癥”和“感冒”都使用了同樣的擾動(dòng)方法，這會(huì)使得對(duì)一些非敏感數(shù)據(jù)“感冒”保護(hù)效果過(guò)強(qiáng)，使得數(shù)據(jù)效用減弱.效用優(yōu)化本地差分隱私就是針對(duì)這一問(wèn)題進(jìn)行了改進(jìn).ULDP將原始數(shù)據(jù)集X劃分成敏感數(shù)據(jù)集Xsen和非敏感數(shù)據(jù)集Xnon,將輸出集劃分為保護(hù)數(shù)據(jù)集Ypro和可逆數(shù)據(jù)集Yinv，它的形式化定義如下.

定義2.(Xsen,Ypro,ε)-ULDP[21].給定Xsen?X，Ypro?Y，ε≥0，對(duì)輸入域?yàn)閄、輸出域?yàn)閅的擾動(dòng)機(jī)制M:X→Y，當(dāng)且僅當(dāng)擾動(dòng)機(jī)制M滿足以下性質(zhì)時(shí)，M滿足(Xsen,Ypro,ε)-ULDP.

1)對(duì)于任意y∈Yinv，有且僅有一個(gè)x∈Xnon，

M(y|x)>0,

(2)

且對(duì)于任意x≠x′，有

M(y|x′)=0.

(3)

2)對(duì)于任意輸入x,x′∈X，得到任意給定輸出y∈Ypro的概率滿足

M(y|x)≤eεM(y|x′).

(4)

2.3 現(xiàn)有的頻率估計(jì)機(jī)制

我們介紹了3種常見(jiàn)的本地差分隱私頻率估計(jì)機(jī)制GRR(generalized randomized response)機(jī)制、RAPPOR機(jī)制和Wheel機(jī)制的擾動(dòng)過(guò)程.這3種機(jī)制均可應(yīng)用于保護(hù)隱私的集合數(shù)據(jù)頻率估計(jì)，然而都難以應(yīng)對(duì)集合數(shù)據(jù)中同時(shí)包含敏感值和非敏感值的情況.

2.3.1 GRR機(jī)制

在GRR機(jī)制[28]中，輸出域與輸入域相同，即X=Y，給定ε≥0，則GRR以表達(dá)式(5)所示的概率將x擾動(dòng)成y，

(5)

式(5)表示了GRR處理類別數(shù)據(jù)的方式，若要處理集合數(shù)據(jù)，則需要先對(duì)數(shù)據(jù)進(jìn)行抽樣，將其轉(zhuǎn)化為類別數(shù)據(jù)，或者根據(jù)集合數(shù)據(jù)條數(shù)劃分隱私預(yù)算，再對(duì)集合中每條數(shù)據(jù)分別處理.

2.3.2 RAPPOR機(jī)制

RAPPOR機(jī)制[20]需要先對(duì)原始數(shù)據(jù)進(jìn)行編碼，通過(guò)獨(dú)熱編碼將x映射為向量c，然后再對(duì)c進(jìn)行擾動(dòng)，當(dāng)用戶數(shù)據(jù)為類別數(shù)據(jù)時(shí)，c中只有1位為1，這一位以p=eε/2/(eε/2+1)的概率保持不變，其余為0的位則以q=1/(eε/2+1)的概率反轉(zhuǎn)為1.

隨后工作[22]又對(duì)RAPPOR進(jìn)行了改進(jìn)，使之可以處理集合數(shù)據(jù).設(shè)每個(gè)用戶有m條數(shù)據(jù)，則編碼后的向量c中有m個(gè)1，為了滿足ε-LDP，這些位保持不變的概率為

(6)

相應(yīng)地，為0的位反轉(zhuǎn)為1的概率為

(7)

此外，與GRR類似，RAPPOR也可以直接從集合中抽樣出一條數(shù)據(jù)，然后直接使用原始的RAPPOR進(jìn)行處理.

2.3.3 Wheel機(jī)制

Wheel機(jī)制[24]是由Wang等人在2020年提出的用于集合數(shù)據(jù)頻率估計(jì)的機(jī)制，具有通信代價(jià)低、估計(jì)誤差小的優(yōu)點(diǎn).Wheel機(jī)制用戶端的擾動(dòng)過(guò)程主要分為2步：第1步是將x通過(guò)哈希函數(shù)映射到v∈[0,1)，第2步則是根據(jù)式(8)所示的概率密度得到擾動(dòng)結(jié)果y

(8)

其中v={v1,v2,…,vm}是用戶數(shù)據(jù)哈希后的結(jié)果；Cv={t|t∈[vi,vi+p)或[0,vi+p-1),i∈{1,2,…,m}}表示總體覆蓋區(qū)域；參數(shù)p=1/(2m-1+meε)表示覆蓋長(zhǎng)度；l是Cv的長(zhǎng)度，即總覆蓋長(zhǎng)度；參數(shù)Ω=mpeε+1-mp則是正則化因子.注意擾動(dòng)結(jié)果y∈[0,1)，也就是輸出域是[0,1).

3 針對(duì)集合數(shù)據(jù)的效用優(yōu)化本地差分隱私模型

3.1 符號(hào)描述

本文中所用到的主要符號(hào)描述如表1所示：

Table 1 Notations Description

3.2 效用優(yōu)化本地差分隱私模型的建立

ULDP模型雖然就數(shù)據(jù)敏感性問(wèn)題進(jìn)行了研究，但是僅能處理用戶輸入均為敏感值或均為非敏感值的情況.當(dāng)用戶集合數(shù)據(jù)中既包含敏感值，又包含非敏感值時(shí)，ULDP模型就無(wú)法直接處理了.例如統(tǒng)計(jì)用戶購(gòu)物數(shù)據(jù)時(shí)，假設(shè)某一位用戶的購(gòu)物記錄為{香蕉，牛奶，洗衣液，心臟病藥物}，此時(shí)心臟病藥物為敏感值而其他數(shù)據(jù)則為非敏感值，ULDP模型就難以直接適用了.因此我們提出了SULDP模型，通過(guò)降低對(duì)集合中非敏感數(shù)據(jù)的保護(hù)效果，來(lái)提高統(tǒng)計(jì)結(jié)果的準(zhǔn)確性.這里我們首先給出SULDP的形式化定義.

1)對(duì)于任意yi∈Yinv，其中1≤i≤t，有且僅有一個(gè)x∈Xnon可以映射到y(tǒng)i，即

當(dāng)x∈s時(shí)，

M(yi|s)>0,

(9)

當(dāng)x?s時(shí)，

M(yi|s)=0.

(10)

2)對(duì)于任意輸入集合s,s′?X，得到任意輸出y0∈Ypro的概率滿足

M(y0|s)≤eεM(y0|s′).

(11)

在定義3中，式(11)保證了對(duì)敏感值的保護(hù)程度不會(huì)降低；式(9)和式(10)則對(duì)應(yīng)非敏感值，允許通過(guò)降低對(duì)其保護(hù)效果來(lái)提高統(tǒng)計(jì)結(jié)果的準(zhǔn)確性.同時(shí)，如果限定每個(gè)輸入集合大小為1時(shí)，即|s|=1，那么SULDP將退化到ULDP模型.因此，ULDP模型是我們SULDP模型的一種特殊情況.SULDP模型是ULDP模型在集合數(shù)據(jù)上的理論拓展，具有更廣泛的適用性.

3.3 問(wèn)題定義

本文專注于在保證用戶敏感數(shù)據(jù)保護(hù)效果的前提下，提升頻率估計(jì)結(jié)果準(zhǔn)確性.我們考慮的系統(tǒng)模型中包含n個(gè)用戶和1個(gè)服務(wù)器.其中，每個(gè)用戶i持有一個(gè)私有的集合si={x1,x2,…,xm}，s?X，即X為原始數(shù)據(jù)的全集，令|X|=d.我們假設(shè)X中既包含敏感值，又包含非敏感值，所有敏感值構(gòu)成的集合記為Xsen，所有非敏感值構(gòu)成的集合記為Xnon，Xsen∪Xnon=X.

定義3中我們假設(shè)用戶手中數(shù)據(jù)條數(shù)是一定的，但通過(guò)簡(jiǎn)單擴(kuò)展可以處理用戶手中數(shù)據(jù)條數(shù)不同的情況.即通過(guò)填充采樣[29]的方式，將用戶數(shù)據(jù)條數(shù)統(tǒng)一為m.具體擴(kuò)展方式為：首先由服務(wù)器根據(jù)前期調(diào)研或?qū)嶋H情況指定m.然后由用戶在本地對(duì)自己數(shù)據(jù)進(jìn)行預(yù)處理.若數(shù)據(jù)條數(shù)小于m，則使用虛假數(shù)據(jù)補(bǔ)齊到m條；若數(shù)據(jù)條數(shù)大于m，則從中隨機(jī)抽取m條，然后再對(duì)數(shù)據(jù)進(jìn)行后續(xù)處理.

3.4 效用評(píng)價(jià)標(biāo)準(zhǔn)

本文采用MSE對(duì)機(jī)制的效用進(jìn)行評(píng)估.MSE表達(dá)式為

(12)

4 機(jī)制設(shè)計(jì)及理論分析

4.1 基于GRR的機(jī)制設(shè)計(jì)

4.1.1 方案描述

我們首先基于GRR提出滿足SULDP模型的suGRR(set-valued utility-optimized GRR)機(jī)制.在suGRR中，保護(hù)數(shù)據(jù)域Ypro是敏感數(shù)據(jù)域Xsen子集構(gòu)成的集合，可逆數(shù)據(jù)域Yinv與非敏感數(shù)據(jù)域Xnon相等，令p=eε/m/(eε/m+|Xsen|-1),q=1/(eε/m+|Xsen|-1)，r=(eε/m-1)/(eε/m+|Xsen|-1)，給定集合數(shù)據(jù)s，則suGRR以表達(dá)式(13)所示的概率對(duì)s中每一條數(shù)據(jù)x進(jìn)行擾動(dòng)，然后將屬于Xsen的輸出z看作一個(gè)集合，即為suGRR輸出部分的y0，余下屬于Xnon的輸出z則分別對(duì)應(yīng)y1,y2,…,yt，

(13)

相應(yīng)地，當(dāng)服務(wù)器收到用戶發(fā)來(lái)的數(shù)據(jù)后，首先需要對(duì)X中所有數(shù)據(jù)出現(xiàn)的次數(shù)進(jìn)行統(tǒng)計(jì)，設(shè)x出現(xiàn)次數(shù)為Fx，然后再以表達(dá)式(14)所示的方法計(jì)算出其頻率估計(jì)值，

(14)

不難發(fā)現(xiàn)，suGRR本質(zhì)上是對(duì)隱私預(yù)算ε進(jìn)行了劃分，當(dāng)m增大時(shí)，分配給每項(xiàng)數(shù)據(jù)的隱私預(yù)算會(huì)很小，使得誤差變大.因此我們基于抽樣的思想又提出了suGRR-Sample，它的擾動(dòng)和估計(jì)過(guò)程與suGRR類似，只不過(guò)每個(gè)用戶只抽出一條數(shù)據(jù)進(jìn)行擾動(dòng)并提交，所以p=eε/(eε+|Xsen|-1),q=1/(eε+|Xsen|-1)，r=(eε-1)/(eε+|Xsen|-1)，相應(yīng)地，服務(wù)器估計(jì)頻率的公式也需要改變成式(15)：

(15)

4.1.2 理論分析

定理1.suGRR和suGRR-Sample均符合SULDP模型.

證明.suGRR中，對(duì)任意y∈Yinv，有且僅有一個(gè)x∈Xnon可擾動(dòng)至該可逆數(shù)據(jù)，即當(dāng)且僅當(dāng)x∈s時(shí)，以r的概率輸出該可逆數(shù)據(jù)，因此滿足SULDP定義中式(9)、式(10)所規(guī)定的第1條性質(zhì).

對(duì)于任意s,s′?X，輸出同一結(jié)果y0的概率為

因此滿足式(11)所規(guī)定的第2條性質(zhì).

綜上，suGRR符合SULDP模型，同理，我們也可以證明suGRR-Sample符合SULDP模型.

證畢.

定理2.suGRR和suGRR-Sample頻率估計(jì)結(jié)果均為無(wú)偏估計(jì).

證明.在suGRR中，x∈Xsen時(shí)，F(xiàn)x可以看作是nf(x)個(gè)成功概率為p和n(m-f(x))個(gè)成功概率為q的伯努利變量之和，因此，

x∈Xnon時(shí)，由擾動(dòng)過(guò)程可知

因此，suGRR的頻率估計(jì)結(jié)果為無(wú)偏估計(jì)，同理，suGRR-Sample的頻率估計(jì)結(jié)果也是無(wú)偏估計(jì).

證畢.

定理3.suGRR的MSE表達(dá)式如式(16)：

(16)

suGRR-Sample的MSE表達(dá)式如式(17)：

(17)

證明.由定理2可得，式(14)為無(wú)偏估計(jì)，因此MSE就等于方差，當(dāng)x∈Xsen時(shí)，

當(dāng)x∈Xnon時(shí)，

將p,q,r帶入，即可得到式(16).同理，也可以證明suGRR-Sample的MSE表達(dá)式為式(17).

證畢.

4.2 基于RAPPOR的機(jī)制設(shè)計(jì)

4.2.1 方案描述

基于GRR的擾動(dòng)過(guò)程雖然簡(jiǎn)單、易于實(shí)現(xiàn)，但是當(dāng)數(shù)據(jù)域很大時(shí)，p,q,r會(huì)趨向于0，會(huì)使得數(shù)據(jù)擾動(dòng)概率過(guò)大，數(shù)據(jù)效用降低，而RAPPOR則不會(huì)受此影響.因此，基于RAPPOR，我們提出滿足SULDP模型的suRAP(set-valued utility-optimized RAPPOR)機(jī)制.

在suRAP中，首先會(huì)對(duì)數(shù)據(jù)進(jìn)行獨(dú)熱編碼，即將用戶手中的集合數(shù)據(jù)s編碼為一個(gè)d比特的向量a，每一位都與原始數(shù)據(jù)域中的一條數(shù)據(jù)相對(duì)應(yīng)，若s中包含有xi，則令a的第i位為1，即a中有m個(gè)1，其余位為0.

不失一般性，我們假設(shè){x1,x2,…,x|Xsen|}為敏感數(shù)據(jù)Xsen，{x|Xsen|+1,x|Xsen|+2,…,x|X|}為非敏感數(shù)據(jù)Xnon，則Ypro={(y1,y2,…,y|X|)|y1,y2,…,y|X|∈{0,1}}，Yinv=Xnon.令p=eε/2m/(eε/2m+1),q=1/(eε/2m+1)，r=(eε/2m-1)/eε/2m，則suRAP以表達(dá)式(18)所示的概率對(duì)a中每一位ai進(jìn)行擾動(dòng)得到bi，

(18)

則y0就等于向量b，同時(shí)，若xi∈Xnon且bi=1，則表示輸出了可逆數(shù)據(jù)xi，即我們可以直接使用b來(lái)表示(y0,y1,…,yt),t≤|snon|.

服務(wù)器端收到用戶發(fā)來(lái)的數(shù)據(jù)后，首先需要對(duì)b中所有位出現(xiàn)1的次數(shù)進(jìn)行統(tǒng)計(jì)，設(shè)x對(duì)應(yīng)位出現(xiàn)1的次數(shù)為Fx，則其估計(jì)頻率為

(19)

類似地，為了避免劃分隱私預(yù)算ε，我們也基于采樣提出了suRAP-Sample，此時(shí)p=eε/2/(eε/2+1)，q=1/(eε/2+1)，r=(eε/2-1)/eε/2，用戶從s中隨機(jī)抽取一條數(shù)據(jù)并編碼為a，注意這時(shí)a中只有一位為1，然后同樣使用式(18)進(jìn)行擾動(dòng)并提交結(jié)果給服務(wù)器，服務(wù)器統(tǒng)計(jì)出x對(duì)應(yīng)位出現(xiàn)1的次數(shù)Fx后，即可根據(jù)式(20)計(jì)算出x的估計(jì)頻率，

(20)

4.2.2 理論分析

定理4.suRAP和suRAP-Sample均符合SULDP模型.

證明.suRAP中，對(duì)于任意s,s′?X，輸出同一結(jié)果y0的概率為

因此滿足式(11)所規(guī)定的第2條性質(zhì).

對(duì)任意y∈Yinv，有且僅有一個(gè)x∈Xnon可擾動(dòng)至該可逆數(shù)據(jù)，即當(dāng)且僅當(dāng)x∈s時(shí)，以r的概率輸出該可逆數(shù)據(jù)，因此滿足SULDP定義中式(9)、式(10)所規(guī)定的第1條性質(zhì).

綜上，suRAP符合SULDP模型，同理，我們也可以證明suRAP-Sample符合SULDP模型.

證畢.

定理5.suRAP和suRAP-Sample頻率估計(jì)結(jié)果均為無(wú)偏估計(jì).

證明.當(dāng)x∈Xsen時(shí)，有

x∈Xnon時(shí)，由擾動(dòng)過(guò)程可知：

綜上，suRAP的頻率估計(jì)結(jié)果為無(wú)偏估計(jì)，同理，suRAP-Sample的頻率估計(jì)結(jié)果也是無(wú)偏估計(jì).

證畢.

定理6.suRAP的MSE表達(dá)式如式(21)：

(21)

suRAP-Sample的MSE表達(dá)式如式(22)：

(22)

證明.與定理3證明過(guò)程類似.

4.3 基于Wheel的機(jī)制設(shè)計(jì)

4.3.1 方案描述

雖然基于RAPPOR處理集合數(shù)據(jù)相較于基于GRR的效果有所提升，但是其通信代價(jià)很高，并且效果也并非目前最優(yōu)的，因此我們?cè)诒竟?jié)提出滿足SULDP模型的suWheel(set-valued utility-optimized wheel)，具體的擾動(dòng)算法如算法1所示.

算法1.suWheel用戶端擾動(dòng)算法.

輸入：集合數(shù)據(jù)s={x1,x2,…,xm}、敏感數(shù)據(jù)域Xsen、非敏感數(shù)據(jù)域Xnon、隱私預(yù)算ε、用戶數(shù)據(jù)條數(shù)m、覆蓋長(zhǎng)度p=1/(2m-1+meε)、正則化因子Ω=mpeε+1-mp、哈希函數(shù)h:X→[0.0,1.0)；

輸出：三元組z=〈z0,z1,h〉，其中z0=y0表示保護(hù)數(shù)據(jù)，z1={y1,y2,…,yt}(t≤|snon|)表示可逆數(shù)據(jù)，h為該用戶使用的哈希函數(shù).

①v={h(x1),h(x2),…,h(xm)}={v1,v2,…,vm}；/*將原始數(shù)據(jù)映射到[0.0,1.0)上*/

②Cv={t|t∈[vi,vi+p)或[0,vi+p-1),i∈{1,2,…,m}}；

以Q(y0|v)所示概率密度得到擾動(dòng)結(jié)果y0，其中l(wèi)是Cv的長(zhǎng)度，令z0=y0；

④z1=?；

⑤ fori=1 tom:

⑥ ifxi∈Xnon:

⑦ ify0?[vi,vi+p)且[0,vi+p-1)

⑧ addxiintoz1；

⑨ end if

⑩ end if

其中z0對(duì)應(yīng)的是y0，z1則對(duì)應(yīng)yi(1≤i≤t).令Cvx為元素x對(duì)應(yīng)的覆蓋區(qū)域，當(dāng)x∈s時(shí)，輸出的z0屬于該區(qū)域的概率為Ptrue=peε/(mpeε+1-mp)，當(dāng)x?s時(shí)，概率則為Pfalse=p.

算法2.suWheel服務(wù)器端聚合算法.

①Fx=0；

② ifx∈Xsen

③ fori=1 ton

④v=hi(x)；

⑥Fx=Fx+1；

⑦ end if

⑧ end for

⑩ end if

4.3.2 理論分析

定理7.suWheel符合SULDP模型.

證明.suWheel中，對(duì)任意y∈Yinv，有且僅有一個(gè)x∈Xnon可擾動(dòng)至該可逆數(shù)據(jù)，即當(dāng)且僅當(dāng)x∈s時(shí)，以r=1-eεp/Ω的概率輸出該可逆數(shù)據(jù)，因此滿足SULDP定義中式(9)、式(10)所規(guī)定的第1條性質(zhì).

對(duì)于任意集合s,s′?X，輸出同一結(jié)果y0的概率為

令

(23)

(24)

化簡(jiǎn)得l(eε-1)≤mp(eε-1)，因?yàn)閘為覆蓋區(qū)域的總長(zhǎng)度，并且各個(gè)元素覆蓋區(qū)域之間可能會(huì)存在相交的情況，因此l≤mp，又有ε≥0，所以式(24)恒成立.即滿足SULDP定義中式(11)所規(guī)定的第2條性質(zhì).

綜上，suWheel符合SULDP模型.

證畢.

定理8.suWheel頻率估計(jì)結(jié)果為無(wú)偏估計(jì).

證明.當(dāng)x∈Xsen時(shí)，F(xiàn)x可以看作是nf(x)個(gè)成功概率為Ptrue和n(1-f(x))個(gè)成功概率為Pfalse的伯努利變量之和，因此

綜上，suWheel的頻率估計(jì)結(jié)果為無(wú)偏估計(jì).

證畢.

定理9.當(dāng)ε=O(1)時(shí)，suWheel的MSE表達(dá)式如式(25)：

(25)

證畢.

4.4 理論結(jié)果對(duì)比

我們首先對(duì)suGRR，suGRR-Sample，suRAP，suRAP-Sample，suWheel等5種機(jī)制的效用進(jìn)行評(píng)估.因?yàn)?/p>

根據(jù)定理3、定理6和定理9，我們可以計(jì)算得到ε=O(1)時(shí)本文機(jī)制與現(xiàn)有本地差分隱私機(jī)制分別所對(duì)應(yīng)的MSE，結(jié)果如表2所示.

f(Xnon)表示非敏感數(shù)據(jù)的真實(shí)頻率總和，因此MSE的前半部分，即敏感數(shù)據(jù)造成的誤差在實(shí)際應(yīng)用中占主導(dǎo)地位.而在實(shí)際應(yīng)用中，敏感數(shù)據(jù)在總體數(shù)據(jù)中的占比往往很小，即|Xsen|

Table 2 Comparison of MSE when ε=O(1)

除了數(shù)據(jù)效用，通信代價(jià)也是評(píng)價(jià)一個(gè)機(jī)制好壞與否的重要標(biāo)準(zhǔn)，假設(shè)suWheel中使用的哈希函數(shù)是從集合H中選取的，表3給出了相應(yīng)的結(jié)果.可以看出suWheel雖然比suGRR-Sample略高，但是仍然是可以接受的.

Table 3 Comparison of Comunication Cost

5 實(shí) 驗(yàn)

5.1 實(shí)驗(yàn)設(shè)置

我們的實(shí)驗(yàn)環(huán)境設(shè)置如下：操作系統(tǒng)為Windows 10，處理器為Inter i7-6700 CPU，內(nèi)存為32 GB，實(shí)驗(yàn)所用的語(yǔ)言為Python 3.6.

我們?cè)?個(gè)數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn)，表4展示了它們的參數(shù)信息.銷售數(shù)據(jù)集[30]包含了英國(guó)一家商店一年的在線交易信息，該商店主要銷售成人、兒童和家居用品，我們將敏感數(shù)據(jù)設(shè)置為兒童用品；動(dòng)漫數(shù)據(jù)集[31]則描述了用戶對(duì)一些動(dòng)漫的評(píng)分，我們將每位用戶評(píng)分的動(dòng)漫作為一條集合數(shù)據(jù)，并將類別為成人、驚悚、恐怖的動(dòng)漫作為敏感數(shù)據(jù)；對(duì)電影數(shù)據(jù)集[32]也是類似的處理.

Table 4 Description of Dataset Parameters

我們是將常規(guī)意義上可能會(huì)泄露用戶隱私的數(shù)據(jù)設(shè)置為敏感值.比如銷售數(shù)據(jù)集中兒童用品會(huì)泄露用戶孩子的性別和年齡；動(dòng)漫數(shù)據(jù)集和電影數(shù)據(jù)集中給成人、驚悚等類別的動(dòng)漫、電影評(píng)價(jià)的信息則會(huì)泄露用戶的觀影偏好，而針對(duì)此類特殊類別的影視的喜好信息對(duì)于用戶而言往往也是較為敏感的.在實(shí)際應(yīng)用中，針對(duì)敏感值和非敏感值的劃分，可以由服務(wù)器根據(jù)常識(shí)和專業(yè)知識(shí)決定，同時(shí)根據(jù)用戶的使用反饋來(lái)進(jìn)行補(bǔ)充，也可以通過(guò)問(wèn)卷調(diào)查等調(diào)研方式收集各個(gè)用戶認(rèn)為的敏感數(shù)據(jù)，然后由服務(wù)器取并集作為敏感值劃分結(jié)果.

此外，我們所使用的3個(gè)真實(shí)數(shù)據(jù)集都是不定長(zhǎng)的，因此需要對(duì)它們進(jìn)行預(yù)處理，通過(guò)填充采樣的方法將之轉(zhuǎn)換為定長(zhǎng)數(shù)據(jù).同時(shí)，我們還使用蓄水池抽樣的方法生成了模擬數(shù)據(jù)集.

實(shí)驗(yàn)采用MSE作為評(píng)估標(biāo)準(zhǔn)，用以評(píng)價(jià)頻率估計(jì)準(zhǔn)確性.同時(shí)，為避免隨機(jī)性影響實(shí)驗(yàn)結(jié)果,本文中每一項(xiàng)實(shí)驗(yàn)重復(fù)進(jìn)行10次,并取平均值作為結(jié)果.

5.2 實(shí)驗(yàn)結(jié)果

5.2.1ε對(duì)MSE的影響

本節(jié)對(duì)比了5種機(jī)制在不同隱私預(yù)算ε下的性能差異，實(shí)驗(yàn)結(jié)果如圖1所示.可以看出，隨著隱私預(yù)算ε的增大，5種機(jī)制的MSE都在減小，相應(yīng)地，頻率估計(jì)結(jié)果會(huì)更加準(zhǔn)確，數(shù)據(jù)效用也就越高.即ε越大，隱私保護(hù)程度越低，MSE越小，數(shù)據(jù)效用越高.

同時(shí)，基于GRR的2個(gè)機(jī)制的效用要明顯低于另外3個(gè)，這是因?yàn)閷?shí)驗(yàn)中數(shù)據(jù)域都很大，suGRR和suGRR-Sample中數(shù)據(jù)被擾動(dòng)的概率會(huì)很大，頻率估計(jì)效果就會(huì)很差，這也與GRR的特性一致.

除此之外，文獻(xiàn)[21]提出了基于ULDP的uRR和uRAP機(jī)制，并建議通過(guò)劃分隱私預(yù)算來(lái)實(shí)現(xiàn)對(duì)集合元素的頻率估計(jì)需求，劃分隱私預(yù)算的uRR實(shí)際上就等同于本文所提出的suRR，而suRAP則是基于改進(jìn)的RAPPOR[22]實(shí)現(xiàn)的，效果比劃分隱私預(yù)算的uRAP要更好.因此，無(wú)論是與本文所提出的4種機(jī)制比較，還是與文獻(xiàn)[21]比較，suWheel都是表現(xiàn)最優(yōu)的機(jī)制.

5.2.2 |Xsen|對(duì)MSE的影響

本節(jié)通過(guò)隨機(jī)抽樣的方法選取敏感數(shù)據(jù)，來(lái)調(diào)整敏感數(shù)據(jù)域在全體數(shù)據(jù)域中的占比，進(jìn)而評(píng)估|Xsen|對(duì)MSE的影響.我們將隱私預(yù)算ε固定為1，結(jié)果如圖2所示.可以看出，隨著|Xsen|的增大，5種機(jī)制的MSE都會(huì)增大，即敏感數(shù)據(jù)越多，需要的擾動(dòng)就越多，估計(jì)結(jié)果的準(zhǔn)確度就越低，數(shù)據(jù)的整體效用就會(huì)越差.

此外，當(dāng)|Xsen|/|X|=1，即用戶數(shù)據(jù)均為敏感值時(shí)，等同于直接使用原始的GRR，RAPPOR等機(jī)制進(jìn)行處理，此時(shí)效果是最差的.這也證明了通過(guò)對(duì)數(shù)據(jù)進(jìn)行劃分，然后根據(jù)敏感與否加以不同的處理方式，確實(shí)可以在一定程度提高整體數(shù)據(jù)效用.

5.2.3d對(duì)MSE的影響

數(shù)據(jù)域大小d也對(duì)數(shù)據(jù)效用有一定的影響.由于真實(shí)數(shù)據(jù)集的數(shù)據(jù)域是固定的，因此本節(jié)通過(guò)不同大小的模擬數(shù)據(jù)集來(lái)進(jìn)行評(píng)估.實(shí)驗(yàn)設(shè)置的d的取值范圍為{16,32,64,…,1 024}，并且敏感數(shù)據(jù)占比為0.25，隱私預(yù)算ε=1，m=8，結(jié)果如圖3所示:

根據(jù)實(shí)驗(yàn)結(jié)果來(lái)看，隨著d的增大，suGRR和suGRR-Sample的MSE呈現(xiàn)不變的趨勢(shì)，這是因?yàn)榛贕RR的2種方法的敏感數(shù)據(jù)部分的MSE與|Xsen|2正相關(guān)，這使得2方面的影響相互抵消了.而其余3種則是與|Xsen|成正相關(guān)，因此前者的影響占了主導(dǎo)地位，MSE呈下降趨勢(shì).

5.2.4m對(duì)MSE的影響

本節(jié)則主要評(píng)估了m對(duì)MSE的影響，同樣是通過(guò)構(gòu)造不同模擬數(shù)據(jù)集來(lái)進(jìn)行實(shí)驗(yàn).令敏感數(shù)據(jù)占比為0.25，隱私預(yù)算ε=1，數(shù)據(jù)域大小d=256，設(shè)置m的取值范圍為{1,2,4,8,…,64}.

與5.2.3節(jié)的分析類似，m對(duì)MSE的影響也包括2方面：1)其余參數(shù)一定，m越大，每條數(shù)據(jù)對(duì)應(yīng)的真實(shí)頻率就越低，相應(yīng)的MSE也就越大；2)如4.4節(jié)所示，suWheel的敏感部分的MSE與m呈正相關(guān)，其余4種機(jī)制更是與m2呈正相關(guān)，因此m越大，MSE也越大.

實(shí)驗(yàn)結(jié)果如圖4所示，隨著m的增大，5種機(jī)制的數(shù)據(jù)效用都會(huì)變低，并且suWheel的MSE增大的幅度要明顯小于另外4個(gè)機(jī)制.

6 結(jié) 論

現(xiàn)有本地差分隱私集合數(shù)據(jù)頻率估計(jì)機(jī)制在設(shè)計(jì)時(shí)并未考慮數(shù)據(jù)的敏感性差異，本文針對(duì)這一問(wèn)題，首先定義了針對(duì)集合數(shù)據(jù)的效用優(yōu)化本地差分隱私模型，并提出了符合SULDP模型的suGRR，suGRR-Sample，suRAP，suRAP-Sample和suWheel機(jī)制，在保證敏感數(shù)據(jù)隱私保護(hù)效果不降低的前提下，提高了整體的數(shù)據(jù)效用.從理論和實(shí)驗(yàn)的結(jié)果來(lái)看，suWheel具有低通信代價(jià)和高數(shù)據(jù)效用的特點(diǎn)，是整體表現(xiàn)最優(yōu)的機(jī)制.

未來(lái)的工作包括2個(gè)方面：1)研究使用本文所提的思想，對(duì)本地差分隱私下的其他機(jī)制，如均值估計(jì)機(jī)制等進(jìn)行改進(jìn)；2)當(dāng)前工作只是將數(shù)據(jù)分為了敏感和非敏感2種類型，那么可以通過(guò)對(duì)敏感程度進(jìn)一步細(xì)分來(lái)達(dá)到更高的數(shù)據(jù)效用.

作者貢獻(xiàn)聲明：曹依然負(fù)責(zé)完成實(shí)驗(yàn)并撰寫論文；朱友文提出了算法思路和實(shí)驗(yàn)方案；賀星宇和張躍協(xié)助設(shè)計(jì)了實(shí)驗(yàn)方案和對(duì)比分析.