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

1(南京航空航天大學計算機科學與技術學院 南京 211106) 2(廣西可信軟件重點實驗室(桂林電子科技大學) 廣西桂林 541004)

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

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

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

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

概括地說，本文的主要貢獻包括3個方面:

1)定義了SULDP模型;

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

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

1 相關工作

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

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

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

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

2 背景知識

2.1 本地差分隱私

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

定義1.ε-LDP[11].給定隱私預算ε≥0，對輸入域為X、輸出域為Y的擾動機制M:X→Y，該擾動機制M滿足ε-LDP，當且僅當對于任意輸入x,x′∈X，得到任意輸出y∈Y的概率滿足

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

(1)

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

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

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

定義2.(Xsen,Ypro,ε)-ULDP[21].給定Xsen?X，Ypro?Y，ε≥0，對輸入域為X、輸出域為Y的擾動機制M:X→Y，當且僅當擾動機制M滿足以下性質時，M滿足(Xsen,Ypro,ε)-ULDP.

1)對于任意y∈Yinv，有且僅有一個x∈Xnon，

M(y|x)>0,

(2)

且對于任意x≠x′，有

M(y|x′)=0.

(3)

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

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

(4)

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

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

2.3.1 GRR機制

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

(5)

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

2.3.2 RAPPOR機制

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

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

(6)

相應地，為0的位反轉為1的概率為

(7)

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

2.3.3 Wheel機制

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

(8)

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

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

3.1 符號描述

本文中所用到的主要符號描述如表1所示：

Table 1 Notations Description

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

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

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

當x∈s時，

M(yi|s)>0,

(9)

當x?s時，

M(yi|s)=0.

(10)

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

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

(11)

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

3.3 問題定義

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

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

3.4 效用評價標準

本文采用MSE對機制的效用進行評估.MSE表達式為

(12)

4 機制設計及理論分析

4.1 基于GRR的機制設計

4.1.1 方案描述

我們首先基于GRR提出滿足SULDP模型的suGRR(set-valued utility-optimized GRR)機制.在suGRR中，保護數(shù)據(jù)域Ypro是敏感數(shù)據(jù)域Xsen子集構成的集合，可逆數(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以表達式(13)所示的概率對s中每一條數(shù)據(jù)x進行擾動，然后將屬于Xsen的輸出z看作一個集合，即為suGRR輸出部分的y0，余下屬于Xnon的輸出z則分別對應y1,y2,…,yt，

(13)

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

(14)

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

(15)

4.1.2 理論分析

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

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

對于任意s,s′?X，輸出同一結果y0的概率為

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

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

證畢.

定理2.suGRR和suGRR-Sample頻率估計結果均為無偏估計.

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

x∈Xnon時，由擾動過程可知

因此，suGRR的頻率估計結果為無偏估計，同理，suGRR-Sample的頻率估計結果也是無偏估計.

證畢.

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

(16)

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

(17)

證明.由定理2可得，式(14)為無偏估計，因此MSE就等于方差，當x∈Xsen時，

當x∈Xnon時，

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

證畢.

4.2 基于RAPPOR的機制設計

4.2.1 方案描述

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

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

不失一般性，我們假設{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以表達式(18)所示的概率對a中每一位ai進行擾動得到bi，

(18)

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

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

(19)

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

(20)

4.2.2 理論分析

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

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

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

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

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

證畢.

定理5.suRAP和suRAP-Sample頻率估計結果均為無偏估計.

證明.當x∈Xsen時，有

x∈Xnon時，由擾動過程可知：

綜上，suRAP的頻率估計結果為無偏估計，同理，suRAP-Sample的頻率估計結果也是無偏估計.

證畢.

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

(21)

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

(22)

證明.與定理3證明過程類似.

4.3 基于Wheel的機制設計

4.3.1 方案描述

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

算法1.suWheel用戶端擾動算法.

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

輸出：三元組z=〈z0,z1,h〉，其中z0=y0表示保護數(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)所示概率密度得到擾動結果y0，其中l(wèi)是Cv的長度，令z0=y0；

④z1=?；

⑤ fori=1 tom:

⑥ ifxi∈Xnon:

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

⑧ addxiintoz1；

⑨ end if

⑩ end if

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

算法2.suWheel服務器端聚合算法.

①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中，對任意y∈Yinv，有且僅有一個x∈Xnon可擾動至該可逆數(shù)據(jù)，即當且僅當x∈s時，以r=1-eεp/Ω的概率輸出該可逆數(shù)據(jù)，因此滿足SULDP定義中式(9)、式(10)所規(guī)定的第1條性質.

對于任意集合s,s′?X，輸出同一結果y0的概率為

令

(23)

(24)

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

綜上，suWheel符合SULDP模型.

證畢.

定理8.suWheel頻率估計結果為無偏估計.

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

綜上，suWheel的頻率估計結果為無偏估計.

證畢.

定理9.當ε=O(1)時，suWheel的MSE表達式如式(25)：

(25)

證畢.

4.4 理論結果對比

我們首先對suGRR，suGRR-Sample，suRAP，suRAP-Sample，suWheel等5種機制的效用進行評估.因為

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

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

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

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

Table 3 Comparison of Comunication Cost

5 實 驗

5.1 實驗設置

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

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

Table 4 Description of Dataset Parameters

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

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

實驗采用MSE作為評估標準，用以評價頻率估計準確性.同時，為避免隨機性影響實驗結果,本文中每一項實驗重復進行10次,并取平均值作為結果.

5.2 實驗結果

5.2.1ε對MSE的影響

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

同時，基于GRR的2個機制的效用要明顯低于另外3個，這是因為實驗中數(shù)據(jù)域都很大，suGRR和suGRR-Sample中數(shù)據(jù)被擾動的概率會很大，頻率估計效果就會很差，這也與GRR的特性一致.

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

5.2.2 |Xsen|對MSE的影響

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

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

5.2.3d對MSE的影響

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

根據(jù)實驗結果來看，隨著d的增大，suGRR和suGRR-Sample的MSE呈現(xiàn)不變的趨勢，這是因為基于GRR的2種方法的敏感數(shù)據(jù)部分的MSE與|Xsen|2正相關，這使得2方面的影響相互抵消了.而其余3種則是與|Xsen|成正相關，因此前者的影響占了主導地位，MSE呈下降趨勢.

5.2.4m對MSE的影響

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

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

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

6 結 論

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

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

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