賀星宇, 朱友文,2,3, 張 躍

1. 南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 南京 211106

2. 桂林電子科技大學(xué) 廣西密碼學(xué)與信息安全重點(diǎn)實(shí)驗(yàn)室, 桂林 541004

3. 廣西師范大學(xué) 廣西多源信息挖掘與安全重點(diǎn)實(shí)驗(yàn)室, 桂林 541004

1 引言

近年來, 隨著信息技術(shù)和機(jī)器學(xué)習(xí)的普及應(yīng)用, 人們的各種信息(如行為、喜好等) 被各個公司、組織或團(tuán)體收集, 相關(guān)研究人員不斷探尋數(shù)據(jù)的深層規(guī)律和內(nèi)在價值. 數(shù)據(jù)可以幫助我們對當(dāng)前世界產(chǎn)生更加清晰的認(rèn)識, 做出更加合理的決策, 對商業(yè)公司、研究機(jī)構(gòu)和政府部門是極為重要的資源. 然而, 這些信息中包含大量用戶有意或無意泄漏的個人隱私, 這些隱私很容易隨著數(shù)據(jù)的收集、發(fā)布、使用而泄漏. 這些隱私泄漏風(fēng)險(xiǎn)不僅損害用戶的利益, 也會降低用戶共享數(shù)據(jù)的意圖, 因此應(yīng)用于數(shù)據(jù)收集過程中的隱私保護(hù)技術(shù)已成為學(xué)術(shù)界亟待解決的問題.

當(dāng)前, 隱私保護(hù)技術(shù)包括安全多方計(jì)算[1]、同態(tài)加密[2]、數(shù)據(jù)匿名[3]和差分隱私機(jī)制[4,5]等. 差分隱私(differential privacy, DP) 能夠?qū)﹄[私保護(hù)效果和執(zhí)行效率取得較好的平衡, 已逐漸成為學(xué)術(shù)界研究的熱點(diǎn)方向. 本地差分隱私(local differential privacy, LDP)[6]是差分隱私的重要分支, 它去除了傳統(tǒng)差分隱私中對可信第三方的需求, 增強(qiáng)了模型的實(shí)用性. 目前, LDP 模型在工業(yè)界得到了廣泛應(yīng)用[7,8], 比如谷歌、蘋果、華為、阿里等公司已將本地差分隱私技術(shù)應(yīng)用于Chrome、iOS、華為終端云和DataTrust等產(chǎn)品. GRR (generalized randomized response)[9]和SUE (symmetric unary encoding)[10]是目前常用的兩種本地差分隱私協(xié)議, 但當(dāng)原始數(shù)據(jù)定義域很大時它們都有一些不足: GRR 協(xié)議的數(shù)據(jù)效用將急劇下降而SUE 協(xié)議的通信代價將急劇上升. 在這種情況下, OLH (optimized local hashing)[10]協(xié)議在擁有較高估計(jì)結(jié)果數(shù)據(jù)效用時擁有很低的通信代價, 是原始數(shù)據(jù)取值范圍很大時的最優(yōu)協(xié)議之一.

本地差分隱私模型中, 所有數(shù)據(jù)都以相同方式進(jìn)行擾動, 很容易造成一部分?jǐn)?shù)據(jù)保護(hù)力度不足, 或是另一部分?jǐn)?shù)據(jù)受到過度保護(hù), 從而降低數(shù)據(jù)效用. 因此Murakami 等人提出了效用優(yōu)化本地差分隱私(utility-optimized local differential privacy, ULDP) 模型[11], 這是本地差分隱私模型的一個變型, 根據(jù)原始數(shù)據(jù)的敏感程度采用不同的擾動策略, 可以在保證敏感數(shù)據(jù)隱私安全的情況下提升數(shù)據(jù)效用. 但現(xiàn)有的ULDP 協(xié)議僅僅基于GRR 和SUE 這兩個協(xié)議提出了uRR (utility-optimized randomized response)協(xié)議和uRAP (utility-optimized randomized aggregatable privacy-preserving ordinal response) 協(xié)議.與GRR 和SUE 相似, 當(dāng)原始數(shù)據(jù)定義域很大時uRR 的數(shù)據(jù)效用很低; uRAP 的效用較高, 但通信代價很大.

針對原始數(shù)據(jù)定義域很大時現(xiàn)有的ULDP 協(xié)議無法兼顧通信代價和數(shù)據(jù)效用這一不足, 本文基于OLH 協(xié)議提出了符合ULDP 模型的uOLH (utility-optimized OLH) 協(xié)議, 該協(xié)議在原始數(shù)據(jù)定義域很大時可以同時具有低通信代價以及高數(shù)據(jù)效用. 這是本文的第一項(xiàng)工作.

之后, 對用戶的個性化隱私保護(hù)需求進(jìn)行考慮. 對于不同的用戶, 即使他們擁有相同的原始數(shù)據(jù), 他們對隱私保護(hù)力度也會具有不同的需求. 例如在統(tǒng)計(jì)疾病情況時, 一名即將比賽的運(yùn)動員顯然更不想讓別人得知自己得過骨折.

但目前關(guān)于個性化差分隱私的工作都有著各自的使用限制. 現(xiàn)有的部分個性化差分隱私協(xié)議應(yīng)用在位置隱私保護(hù)模型中[12,13],難以遷移至頻率估計(jì)協(xié)議. Gedik 等人設(shè)計(jì)的具有k-匿名性的個性化協(xié)議[14]和馬蘇杭等人設(shè)計(jì)的應(yīng)用于高維數(shù)據(jù)發(fā)布的個性化協(xié)議[15]均依賴于中心服務(wù)器實(shí)現(xiàn)個性化隱私, 因此用戶無法自由選擇隱私級別. Wang 等人提出的基于布隆過濾器的協(xié)議[16]和Chen 提出的私有空間數(shù)據(jù)聚合協(xié)議[17]只能輸出單一結(jié)果, 難以服務(wù)于不同可信度的數(shù)據(jù)使用者. Nie 等人提出一種用戶可自由選擇隱私預(yù)算的模型[18], 但該模型只包含一元編碼協(xié)議, 面對原始數(shù)據(jù)定義域很大的數(shù)據(jù)時通信開銷難以承受.

針對用戶的個性化隱私保護(hù)需求, 本文基于uOLH 協(xié)議提出了一種用戶可以自由選擇隱私級別, 控制自己的隱私保護(hù)力度, 并可為多種可信度的數(shù)據(jù)使用者服務(wù)的協(xié)議uOLH-DWC (utility-optimized OLH with data weighted combination). 該協(xié)議中的DWC 機(jī)制可對不同隱私級別估計(jì)值進(jìn)行優(yōu)化組合, 最小化估計(jì)頻率誤差. 這是本文的第二項(xiàng)工作.

本文的主要貢獻(xiàn)如下:

(1) 本文基于OLH 協(xié)議提出了符合ULDP 模型的uOLH 協(xié)議, 證明了uOLH 協(xié)議滿足ULDP 模型, 并計(jì)算了頻率估計(jì)結(jié)果的理論方差. 該協(xié)議在原始數(shù)據(jù)定義域很大時可同時具有低通信代價和高數(shù)據(jù)效用.

(2) 本文考慮了用戶的個性化隱私保護(hù)需求, 設(shè)計(jì)了不同隱私級別估計(jì)值的優(yōu)化組合機(jī)制DWC. 將其與uOLH 協(xié)議相結(jié)合, 提出了uOLH-DWC 協(xié)議. 該協(xié)議在保證用戶可以自由選擇隱私預(yù)算的前提下可將多個隱私級別的估計(jì)結(jié)果加權(quán)組合, 最小化估計(jì)結(jié)果誤差, 可輸出多個隱私級別的頻率估計(jì)結(jié)果.

(3) 本文在真實(shí)數(shù)據(jù)集與合成數(shù)據(jù)集上分別進(jìn)行了實(shí)驗(yàn), 從實(shí)驗(yàn)角度驗(yàn)證了當(dāng)原始數(shù)據(jù)定義域很大時, uOLH 協(xié)議擁有與uRR 協(xié)議相似的低通信代價和與uRAP 協(xié)議相似的高數(shù)據(jù)效用; uOLHDWC 協(xié)議在不同隱私級別下均可以提高頻率估計(jì)的數(shù)據(jù)效用.

本文結(jié)構(gòu)如下: 第2 節(jié)介紹一些基礎(chǔ)概念并給出uOLH 協(xié)議的模型定義; 第3 節(jié)給出uOLH 協(xié)議的具體內(nèi)容, 對該協(xié)議的性質(zhì)進(jìn)行了理論證明; 第4 節(jié)中考慮了用戶不同的個性化隱私需求, 基于uOLH 協(xié)議提出了uOLH-DWS 協(xié)議; 第5 節(jié)中在真實(shí)數(shù)據(jù)集和模擬數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn), 驗(yàn)證了上述方案的有效性; 第6 節(jié)為總結(jié)和展望.

2 基礎(chǔ)概念與模型定義

2.1 符號描述

本文中的符號描述可見表1.

表1 符號描述Table 1 Notations

2.2 預(yù)備知識

2.2.1 本地差分隱私

在本地差分隱私模型中, 用戶在本地對自己的原始數(shù)據(jù)進(jìn)行擾動, 并將擾動數(shù)據(jù)上傳至服務(wù)器. 服務(wù)器對擾動數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析, 估計(jì)出所有原始數(shù)據(jù)的頻率分布結(jié)果. 在上述過程中原始數(shù)據(jù)不會脫離用戶的控制范圍, 僅存在于用戶本地, 因此避免了原始數(shù)據(jù)流經(jīng)信道和服務(wù)器時所產(chǎn)生的隱私風(fēng)險(xiǎn). 本地差分隱私的形式化定義如下:

定義1 (?-LDP[6]) 給定? ＞0. 對于輸入域?yàn)閄、輸出域?yàn)閅的數(shù)據(jù)擾動算法f:X →Y, 該數(shù)據(jù)擾動算法f滿足?-LDP 定義當(dāng)且僅當(dāng)對于任意輸入x1,x2∈X得到任意輸出y ∈Y的概率滿足式(1):

可以看出, 本地差分隱私對任意兩個不同輸入值的輸出結(jié)果相似性進(jìn)行了約束, 這一限制使得具有任意背景知識的攻擊者都很難從輸出結(jié)果推斷出原始數(shù)據(jù), 極大地保護(hù)了用戶的隱私安全. 定義中的?被稱作隱私預(yù)算, 這個值具體地表明了隱私保護(hù)力度大小. 隨著隱私預(yù)算的增長, 隱私保護(hù)力度增強(qiáng), 但從擾動數(shù)據(jù)估計(jì)出的頻率分布效用會降低. 在實(shí)際使用中要兼顧隱私保護(hù)力度和數(shù)據(jù)效用, 選擇適當(dāng)?shù)碾[私預(yù)算.

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

在本地差分隱私模型中, 所有的數(shù)據(jù)都是以相同的方式進(jìn)行擾動的, 這忽視了數(shù)據(jù)之間的敏感性差異.例如在調(diào)查學(xué)生考試作弊情況時, “曾作弊” 這一回答比“未曾作弊” 更為敏感; 在調(diào)查用戶所患疾病時,“艾滋”、“癌癥” 這些回答比“感冒” 更為敏感. 如果對這些數(shù)據(jù)都以相同的方式進(jìn)行保護(hù), 很容易使得對敏感數(shù)據(jù)的保護(hù)力度過低, 產(chǎn)生額外隱私風(fēng)險(xiǎn); 或?qū)Ψ敲舾袛?shù)據(jù)過度保護(hù), 降低最終估計(jì)結(jié)果數(shù)據(jù)效用.

為解決上述問題, ULDP 這一模型被提出. 在ULDP 模型中, 數(shù)據(jù)的處理流程與LDP 一致, 但在數(shù)據(jù)擾動過程中有差異. 原始數(shù)據(jù)集合被劃分為敏感數(shù)據(jù)XS和非敏感數(shù)據(jù)XN兩部分, 擾動結(jié)果集合被劃分為保護(hù)數(shù)據(jù)YP和可逆數(shù)據(jù)YI兩部分. ULDP 的形式化定義如下:

定義2 ((XS,YP,?)-ULDP[11]) 給定XS ∈X,YP ∈Y,? ＞0. 對于輸入域?yàn)閄, 輸出域?yàn)閅的數(shù)據(jù)擾動算法f:X →Y, 該數(shù)據(jù)擾動算法f滿足(XS,YP,?)-ULDP 定義當(dāng)且僅當(dāng)滿足以下兩條性質(zhì):

(1) 對于任意y ∈YI, 有且僅有一個x ∈XN滿足式(2):

且對于任意x′/=x, 均滿足式(3):

(2) 對于任意x1,x2∈X, 任意y ∈YP, 均滿足式(4):

2.3 模型定義

該協(xié)議系統(tǒng)模型可見圖1, 協(xié)議中參與方有三方: 用戶、服務(wù)器和數(shù)據(jù)使用者. 有n個用戶, 每人持有一個原始數(shù)據(jù). 原始數(shù)據(jù)集合記為X, 該集合維度大小為d, 原始數(shù)據(jù)集合被劃分為敏感數(shù)據(jù)集合XS和非敏感數(shù)據(jù)集合XN兩部分, 二者不相交, 即d=|XS|+|XN|. 每個用戶根據(jù)自身情況和行為特征, 選擇一個隱私級別, 根據(jù)對應(yīng)的隱私預(yù)算在本地將自己的原始數(shù)據(jù)編碼并擾動, 將擾動結(jié)果發(fā)送至服務(wù)器. 服務(wù)器對所有用戶的擾動數(shù)據(jù)聚合并進(jìn)行統(tǒng)計(jì)分析, 估計(jì)出所有原始數(shù)據(jù)的頻率分布結(jié)果. 之后, 服務(wù)器將這些頻率估計(jì)結(jié)果發(fā)送至對應(yīng)的數(shù)據(jù)使用者.

圖1 系統(tǒng)模型Figure 1 System model

在第4 節(jié)中, 本文對此模型進(jìn)行擴(kuò)展, 使其可滿足用戶的個性化隱私保護(hù)需求, 允許用戶在發(fā)布的隱私級別中任意挑選, 自行決定隱私保護(hù)力度.

2.4 敵手模型

本文在“半誠實(shí)模型” (又稱誠實(shí)且好奇模型、被動攻擊者模型) 下進(jìn)行協(xié)議的構(gòu)造. 該模型假定所有參與者都會遵守協(xié)議約束, 按照協(xié)議步驟執(zhí)行, 但參與者會根據(jù)自身獲取的信息盡可能地推斷隱私數(shù)據(jù).用戶會將自己的真實(shí)數(shù)據(jù)編碼擾動并提交, 不會上傳偽造的數(shù)據(jù); 收集者(服務(wù)器) 會嚴(yán)格遵循協(xié)議步驟對數(shù)據(jù)進(jìn)行處理, 但會嘗試從獲取的擾動數(shù)據(jù)中推斷用戶的隱私信息; 數(shù)據(jù)使用者不會將獲得的估計(jì)結(jié)果分發(fā)給其他角色, 不會與服務(wù)器共謀. 我們對攻擊者的背景知識不做限制, 可以認(rèn)為攻擊者掌握了關(guān)于數(shù)據(jù)的任意范圍背景知識.

2.5 效用評估

本文將采用均方誤差(mean square error, MSE) 對協(xié)議和實(shí)驗(yàn)的效用進(jìn)行評估. 均方誤差的形式化定義如式(5):

其中c(i) 代表真實(shí)頻率, ?c(i) 代表估計(jì)頻率.

在進(jìn)行理論分析時, 上文中的MSE(?c) 很難得到一個確切值, 因此通常如式(6) 所示使用Var(?c(i)) 計(jì)算均方誤差.

3 基于OLH 的效用優(yōu)化本地差分隱私機(jī)制

3.1 方案內(nèi)容

使用本地哈希機(jī)制的LDP 協(xié)議目前主要有兩種: BLH (binary local hashing) 和OLH (optimized local hashing), 它們之間的區(qū)別在于哈希函數(shù)的值域大小. BLH 中哈希結(jié)果只會為0 或1, 這雖然極大降低了通信代價, 但將原始數(shù)據(jù)哈希至1 個比特這一步驟一方面產(chǎn)生了大量哈希碰撞, 另一方面造成了很多信息損失, 使得最終統(tǒng)計(jì)結(jié)果的數(shù)據(jù)效用嚴(yán)重降低. 針對這一點(diǎn), 有研究者提出了OLH 協(xié)議, 在該協(xié)議中擴(kuò)大了哈希函數(shù)的輸出范圍, 使其可輸出g個值, 并證明了當(dāng)g=e?+1 時, 該協(xié)議可以取得數(shù)據(jù)效用最優(yōu)的估計(jì)結(jié)果. 在本小節(jié)中我們基于OLH 協(xié)議, 提出一種符合ULDP 模型的uOLH 協(xié)議.

設(shè)置一個哈希函數(shù)集合H, 該集合里的所有哈希函數(shù)定義域均為d. 當(dāng)輸入值為敏感數(shù)據(jù)時被散列至g個值; 當(dāng)輸入值為非敏感數(shù)據(jù)時, 哈希函數(shù)直接輸出原始值, 即不對輸入值做任何操作, 直接保留非敏感數(shù)據(jù). 函數(shù)集合H 中的函數(shù)數(shù)量以|H| 表示.

不失一般性, 假定非敏感數(shù)據(jù)不會為{1,2,··· ,g}中的任意一個數(shù), 即XN ∩{1,2,··· ,g}=?. 敏感數(shù)據(jù)的哈希結(jié)果記為yp={1,2,··· ,g}, 非敏感數(shù)據(jù)的哈希結(jié)果記為yi=XN. 此協(xié)議中保護(hù)數(shù)據(jù)集合YP為{＜H,y ＞|H ∈H,y ∈yp}, 可逆數(shù)據(jù)集合YI為{＜H,y ＞|H ∈H,y ∈yi}. 若用戶在擾動步驟生成的結(jié)果b′分別屬于yp或yi, 則代表他們向服務(wù)器發(fā)送的擾動數(shù)據(jù)＜H,b′＞分別屬于保護(hù)數(shù)據(jù)集合YP或可逆數(shù)據(jù)集合YI.

uOLH 方案共分為3 個步驟: 編碼、擾動、聚合. 各步驟的詳細(xì)內(nèi)容如下:

步驟一 編碼

假定有n個用戶, 用戶手中的原始數(shù)據(jù)記為x, 為了減少后續(xù)的通信代價, 采用哈希函數(shù)對其進(jìn)行編碼. 用戶從H 中隨機(jī)選擇一個函數(shù)H對x進(jìn)行哈希操作, 得到編碼結(jié)果b, 即b=H(x). 根據(jù)上述對哈希函數(shù)的設(shè)置, 可以看出當(dāng)x為敏感數(shù)據(jù)時, 它將被編碼為{1,2,··· ,g}中的一個數(shù)據(jù); 當(dāng)x為非敏感數(shù)據(jù)時, 它的編碼結(jié)果為它本身.

步驟二 擾動

用戶將自己的原始數(shù)據(jù)編碼后, 在本地利用隨機(jī)擾動機(jī)制對其進(jìn)行擾動, 擾動結(jié)果記為b′. 根據(jù)用戶原始數(shù)據(jù)的敏感度差異, 需要選用不同的擾動方式對其進(jìn)行處理.

如果用戶的原始數(shù)據(jù)x為敏感數(shù)據(jù), 擾動方式如式(7):

如果用戶的原始數(shù)據(jù)x為非敏感數(shù)據(jù), 擾動方式如式(8):

步驟三 聚合

在這一階段服務(wù)器收集并聚合用戶發(fā)送的擾動數(shù)據(jù), 聚合后的集合記為G, 根據(jù)用戶數(shù)量可知G中共有n條數(shù)據(jù). 之后對擾動數(shù)據(jù)進(jìn)行統(tǒng)計(jì)分析, 估計(jì)出每個原始數(shù)據(jù)的頻率. 首先要介紹兩個在頻率估計(jì)時的輔助函數(shù). 第一個輔助函數(shù)是B(x,y) 函數(shù), 它的第一個參數(shù)是原始數(shù)據(jù)x, 第二個參數(shù)是擾動數(shù)據(jù)y(該擾動數(shù)據(jù)的格式是＜H,b′＞). 它的作用是判斷某個擾動數(shù)據(jù)是否和某個原始數(shù)據(jù)之間存在關(guān)聯(lián). 函數(shù)具體內(nèi)容可見式(9):

第二個輔助函數(shù)是BYI(y) 函數(shù), 它的參數(shù)是擾動數(shù)據(jù)y. 它的作用是判斷某個擾動數(shù)據(jù)是否是可逆數(shù)據(jù). 函數(shù)具體內(nèi)容可見式(10):

如果原始數(shù)據(jù)x是敏感數(shù)據(jù), 根據(jù)式(11) 對其進(jìn)行頻率估計(jì):

如果原始數(shù)據(jù)x是非敏感數(shù)據(jù), 根據(jù)式(12) 對其進(jìn)行頻率估計(jì):

3.2 理論分析

本小節(jié)將給出uOLH 的一些相關(guān)性質(zhì), 并進(jìn)行理論證明. 本文在定理和證明過程中將保留g, 使得這些性質(zhì)便于推廣.

定理1uOLH 的擾動過程符合ULDP 模型.

對于任意x1∈XS,x2∈XN, 若要輸出相同結(jié)果e?, 該結(jié)果只能屬于保護(hù)數(shù)據(jù)YP, 最終輸出相同結(jié)果的概率滿足式(14):

對于任意x1,x2∈XN, 若要輸出相同結(jié)果, 該結(jié)果只能屬于保護(hù)數(shù)據(jù)YP, 最終輸出相同結(jié)果的概率滿足式(15):

因此滿足ULDP 定義中式(4) 所規(guī)定的第二條性質(zhì).

綜上所述, uOLH 的擾動過程符合ULDP 模型, uOLH 為ULDP 協(xié)議.

定理2uOLH 協(xié)議的通信代價為O(log|H|+log(g+|XN|)).

證明:在uOLH 協(xié)議中用戶向服務(wù)器發(fā)送的擾動數(shù)據(jù)為＜H,b′＞, 該數(shù)據(jù)分為兩部分. 第一部分H是用戶選用的哈希函數(shù), 可以通過事先約定的方法將每一個哈希函數(shù)映射至1 到|H| 中的一個數(shù), 這一部分的通信代價為O(log|H|). 第二部分b′是用戶經(jīng)過編碼擾動后得到的擾動數(shù)據(jù), 這部分的通信代價為O(log(g+|XN|)). 綜上, 整體的通信代價為(log|H|+log(g+|XN|)).

由uRR 協(xié)議和uRAP 協(xié)議的定義可知, 它們的通信代價分別是O(log(|XS|+|XN|)) 和O(|XS|+|XN|). 可以看出當(dāng)原始數(shù)據(jù)定義域很大時, uOLH 和uRR 的通信代價接近, 而uRAP 的通信代價顯著大于其余兩個協(xié)議. 在5.2.1 節(jié)中會對各協(xié)議的通信代價進(jìn)行實(shí)驗(yàn)對比.

定理3uOLH 頻率估計(jì)得到的結(jié)果為無偏估計(jì).

證明:對于原始數(shù)據(jù)x, 它的真實(shí)頻率記為c(x). 非敏感數(shù)據(jù)的真實(shí)頻率總和記為c(XN).

若x為敏感數(shù)據(jù), 由擾動過程可知:

結(jié)合式(16)、式(17), 可知它的頻率估計(jì)步驟滿足式(18):

若x為非敏感數(shù)據(jù), 由擾動過程可知:

結(jié)合式(19), 可知它的頻率估計(jì)步驟滿足式(20):

綜上所述, 對于任意原始數(shù)據(jù)x, E[?c(x)]=c(x).

定理4 在uOLH 協(xié)議中, 估計(jì)頻率?c(x) 的方差如式(21) 所示:

證明: 若原始數(shù)據(jù)x為敏感數(shù)據(jù), 則?c(x) 的方差計(jì)算過程如式(22) 所示.

若原始數(shù)據(jù)x為非敏感數(shù)據(jù), 則?c(x) 的方差計(jì)算過程如式(23) 所示:

4 個性化的uOLH 協(xié)議

本節(jié)將考慮協(xié)議的個性化問題. 基于uOLH, 我們提出了允許用戶自由選擇隱私預(yù)算的uOLH-DWC協(xié)議, 并對估計(jì)結(jié)果進(jìn)行優(yōu)化. 下面是進(jìn)行了個性化擴(kuò)展的模型定義.

4.1 模型定義

服務(wù)器在事前將原始數(shù)據(jù)集合X劃分為敏感數(shù)據(jù)集合XS和非敏感數(shù)據(jù)集合XN兩部分; 設(shè)置h個隱私級別, 每個隱私級別對應(yīng)一個隱私預(yù)算.

有h個隱私級別, 每個隱私級別對應(yīng)著一個隱私預(yù)算, 例如隱私級別t對應(yīng)著隱私預(yù)算?t. 隨著隱私級別增加, 隱私預(yù)算也會變大. 對于任意兩個隱私級別i,j(i ＜j),?i必定小于?j. 原始數(shù)據(jù)的劃分和隱私級別的設(shè)置對所有用戶公開. 隱私級別示意圖可見圖2.

圖2 隱私級別Figure 2 Privacy level

有n個用戶, 每人持有一個原始數(shù)據(jù). 用戶自由選擇一個隱私級別, 根據(jù)對應(yīng)的隱私預(yù)算將自己的原始數(shù)據(jù)編碼并擾動, 之后將擾動數(shù)據(jù)＜H,b′＞和自己選擇的隱私級別一起發(fā)送給服務(wù)器.

數(shù)據(jù)使用者根據(jù)自身可信程度, 也被分配一個隱私級別. 這是為了對數(shù)據(jù)使用者的訪問范圍作出限制,若其隱私級別為t, 則只能獲取到隱私級別1 到t的擾動數(shù)據(jù)生成的頻率估計(jì)結(jié)果.

服務(wù)器按照隱私級別將所有的用戶擾動數(shù)據(jù)聚合, 同一隱私級別下的數(shù)據(jù)聚合至一個集合中. 之后在每個集合下獨(dú)立地進(jìn)行頻率估計(jì), 得到h個頻率估計(jì)結(jié)果. 服務(wù)器通過數(shù)據(jù)加權(quán)組合機(jī)制(DWC) 將這些頻率結(jié)果加權(quán)組合, 為每個隱私級別生成一個頻率估計(jì)結(jié)果, 并將這些頻率估計(jì)結(jié)果發(fā)送至對應(yīng)的數(shù)據(jù)使用者.

4.2 DWC 機(jī)制

不同隱私級別下的數(shù)據(jù)隱私預(yù)算不同, 因此很難一起進(jìn)行頻率估計(jì), 只能在每個隱私級別下單獨(dú)進(jìn)行頻率估計(jì). 從隱私預(yù)算的設(shè)置可以看出, 隨著隱私級別的擴(kuò)大, 該級別對應(yīng)的頻率估計(jì)結(jié)果會更加精確, 這也與數(shù)據(jù)使用者隱私級別的設(shè)計(jì)思路相吻合, 隱私級別越高的數(shù)據(jù)使用者可以獲取更精確的估計(jì)結(jié)果. 對于一個隱私級別為t的數(shù)據(jù)使用者, 他可以獲得t個頻率估計(jì)結(jié)果, 為了取得更高的數(shù)據(jù)效用他必然會選擇隱私級別t對應(yīng)的頻率估計(jì)結(jié)果.

但在這種情況一個隱私級別t的數(shù)據(jù)使用者只使用了隱私級別t下的擾動數(shù)據(jù), 前t-1 個隱私級別中的數(shù)據(jù)沒有被利用, 這浪費(fèi)了很大一部分?jǐn)?shù)據(jù), 也會降低數(shù)據(jù)使用者得到的數(shù)據(jù)效用.

因此本文提出數(shù)據(jù)加權(quán)組合(data weighted combination, DWC) 機(jī)制, 利用隱私級別為1 至t-1的擾動數(shù)據(jù)提高最終的數(shù)據(jù)效用.

為了盡可能多地利用這些數(shù)據(jù), 我們將這t個頻率分布結(jié)果進(jìn)行加權(quán)組合, 得到最終的頻率分布結(jié)果.

式(24) 中ωi為權(quán)重, DWC 的目標(biāo)是找到合適的權(quán)重, 使得～ct(x) 的MSE 最小.

引理1 加權(quán)組合得到的最終頻率分布結(jié)果～ct(x) 是真實(shí)頻率c(x) 的無偏估計(jì).

證明: 已知每個隱私級別下得到的頻率估計(jì)結(jié)果 ?ci(x) 都是真實(shí)頻率c(x) 的無偏估計(jì), 即E[?ci(x)]=c(x). 因此～ct(x) 滿足式(25):

現(xiàn)在所要解決的問題, 就是如何選擇權(quán)重, 使得最終的MSE 最小, 這是一個在約束條件下求最值的問題, 問題形式化定義如式(27) 所示:

證明: 本文采用拉格朗日乘數(shù)法來解決這一問題, 首先構(gòu)造拉格朗日函數(shù)L.

之后對函數(shù)的每個變量求偏導(dǎo), 使其等于0, 可以得到式(29):

由此得到了使MSE(～ct) 最小的權(quán)重. 易證Vi為一正數(shù), 因此對于任意i(i= 1,2,···,t) 均滿足0＜ωi ＜1, 滿足權(quán)重要求. 通過權(quán)重的構(gòu)造過程可以得知, 若將前t個頻率估計(jì)結(jié)果加權(quán)組合, 所得頻率估計(jì)結(jié)果的數(shù)據(jù)效用必定不小于前t個頻率估計(jì)結(jié)果中的任何一個. 在DWC 機(jī)制中計(jì)算Vi時需要使用c(XS) 與c(XN), 這兩個參數(shù)分別是全體敏感數(shù)據(jù)的頻率總和與全體非敏感數(shù)據(jù)的頻率總和, 我們可使用估計(jì)值對其進(jìn)行近似替代.

4.3 uOLH-DWC 協(xié)議

在找到了最佳權(quán)重后, DWC 機(jī)制就構(gòu)建完成. 將其與uOLH 協(xié)議結(jié)合, 即為符合個性化拓展模型的的uOLH-DWC 協(xié)議.

uOLH-DWC 協(xié)議也分為三個步驟: 編碼、擾動和聚合. 步驟一編碼和步驟二聚合的內(nèi)容與3.1 節(jié)中uOLH 協(xié)議的步驟一致, 只是用戶需要在步驟一前先選擇一個隱私級別, 拿到對應(yīng)的隱私預(yù)算. 用戶在執(zhí)行步驟二后, 除了所選的哈希函數(shù)和擾動數(shù)據(jù)＜H,b′＞外, 還需要把選擇的隱私級別發(fā)送給服務(wù)器.

可以注意到, 與uOLH 協(xié)議相比, uOLH-DWC 協(xié)議中會向服務(wù)器發(fā)送隱私級別這一信息, 即uOLHDWC 協(xié)議的通信代價為O(logh+log|H|+log(g+|XN|)). 隱私級別的數(shù)量通常不會太大, 因此對通信代價不會造成太大影響. 本文對現(xiàn)有ULDP 協(xié)議的通信代價進(jìn)行了總結(jié), 具體內(nèi)容可見表2.

表2 現(xiàn)有ULDP 協(xié)議通信代價Table 2 Communication cost of existing ULDP protocol

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

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

本文在兩個數(shù)據(jù)集上進(jìn)行了實(shí)驗(yàn). 第一個數(shù)據(jù)集為“藥物數(shù)據(jù)集”[19], 這是一個真實(shí)數(shù)據(jù)集, 包含了用戶的藥物購買情況, 共有215 063 條數(shù)據(jù), 原始數(shù)據(jù)集合大小為3672. 第二個數(shù)據(jù)集為“模擬數(shù)據(jù)集”,這是按照正態(tài)分布生成的人工數(shù)據(jù)集, 共有95 482 條數(shù)據(jù), 原始數(shù)據(jù)集合大小為1000. 在實(shí)驗(yàn)中本文令原始數(shù)據(jù)中50% 的數(shù)據(jù)為敏感數(shù)據(jù), uOLH 中哈希函數(shù)數(shù)量為512 個.

在實(shí)驗(yàn)環(huán)節(jié), 為避免隨機(jī)性影響實(shí)驗(yàn)結(jié)果, 本文中每一項(xiàng)實(shí)驗(yàn)重復(fù)進(jìn)行20 次, 并取平均值作為結(jié)果.

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

5.2.1 通信代價實(shí)驗(yàn)評估

該節(jié)實(shí)驗(yàn)總結(jié)了uRR、uRAP、uOLH 和uOLH-DWC 在實(shí)驗(yàn)中的通信代價(計(jì)算uOLH 通信代價時隱私預(yù)算視為2), 具體數(shù)值見表3.

表3 不同協(xié)議的通信代價對比Table 3 Communication cost comparison of different protocols

可以看出, uRAP 的通信代價顯著大于其他協(xié)議, 在藥物數(shù)據(jù)集中是其他協(xié)議的153 到306 倍, 在模擬數(shù)據(jù)集中是其他協(xié)議的45 到100 倍. 而uRR 與uOLH 的通信代價接近, 遠(yuǎn)遠(yuǎn)小于uRAP. uOLHDWC 因?yàn)橐~外傳輸用戶的隱私級別, 因此通信代價比uOLH 稍高, 但仍然遠(yuǎn)小于uRAP, 與uRR 通信代價相差不大. 這從實(shí)驗(yàn)角度證明了uOLH 和uOLH-DWC 具有低通信量的優(yōu)勢.

5.2.2 uOLH 數(shù)據(jù)效用實(shí)驗(yàn)評估

該節(jié)實(shí)驗(yàn)對比了uRR、uRAP、uOLH 在不同隱私預(yù)算下的性能表現(xiàn), 結(jié)果見圖3. 其中圖3(a) 為藥物數(shù)據(jù)集的結(jié)果, 圖3(b) 為模擬數(shù)據(jù)集的結(jié)果.

圖3 不同ULDP 協(xié)議的MSE 對比Figure 3 MSE comparison of different ULDP protocols

首先可以看出, 隨著隱私預(yù)算的擴(kuò)大, 三個協(xié)議的誤差都在縮小, 這與預(yù)期相符. uRR 的數(shù)據(jù)效用很差, 要明顯低于另外兩個協(xié)議, 這是因?yàn)閷?shí)驗(yàn)使用的兩個數(shù)據(jù)集原始數(shù)據(jù)定義域都很大, uRR 已不能適應(yīng)這種情況. 而uOLH 協(xié)議有著和uRAP 協(xié)議接近的性能, 在隱私預(yù)算較高時甚至優(yōu)于uRAP 協(xié)議. 結(jié)合上一節(jié)實(shí)驗(yàn)可知, 原始數(shù)據(jù)定義域很大時uRAP 的通信代價是uOLH 的45 到183 倍, 因此uOLH 協(xié)議在通信代價方面和數(shù)據(jù)效用方面都要優(yōu)于現(xiàn)有的ULDP 協(xié)議.

5.2.3 uOLH-DWC 數(shù)據(jù)效用實(shí)驗(yàn)評估

該節(jié)實(shí)驗(yàn)測試了uOLH-DWC 協(xié)議對于估計(jì)結(jié)果的優(yōu)化效果, 結(jié)果見圖4. 其中圖4(a) 為藥物數(shù)據(jù)集的結(jié)果, 圖4(b) 為模擬數(shù)據(jù)集的結(jié)果. 本文共設(shè)置了10 個隱私級別, 隱私級別1 的隱私預(yù)算為0.2, 隱私級別10 的隱私預(yù)算為2, 相鄰隱私級別隱私預(yù)算間隔0.2. 圖4 中“uOLH” 標(biāo)簽表示只進(jìn)行隱私級別的劃分, 不采用數(shù)據(jù)加權(quán)組合對估計(jì)值進(jìn)行優(yōu)化的結(jié)果, “uOLH-DWC” 標(biāo)簽表示uOLH-DWC 協(xié)議的結(jié)果.

圖4 是否使用DWS 機(jī)制的MSE 對比Figure 4 MSE comparison of whether to use the DWS mechanism

可以看出, 對于隱私級別1 的數(shù)據(jù)使用者, 是否使用uOLH-DWC 協(xié)議對結(jié)果沒有任何影響, 這是因?yàn)殡[私級別1 的數(shù)據(jù)使用者無法獲取其他級別的估計(jì)結(jié)果, 因此無法進(jìn)行加權(quán)組合. 從實(shí)驗(yàn)結(jié)果可以看出, 其他的隱私級別在使用uOLH-DWC 協(xié)議后都縮減了估計(jì)結(jié)果的誤差, 提高了數(shù)據(jù)效用. 這是因?yàn)榻?jīng)過加權(quán)組合后, 數(shù)據(jù)使用者相當(dāng)于從其他的隱私級別獲取到了更多的信息, 因此減少了估計(jì)誤差.

6 總結(jié)與展望

本文針對現(xiàn)有ULDP 協(xié)議在原始數(shù)據(jù)定義域很大時, 無法兼顧通信代價和數(shù)據(jù)效用的不足, 提出了一種符合ULDP 模型的uOLH 協(xié)議, 從理論和實(shí)驗(yàn)的結(jié)果表明, 與現(xiàn)有協(xié)議相比該協(xié)議可在原始數(shù)據(jù)定義域很大時同時取得低通信代價與高數(shù)據(jù)效用.

進(jìn)一步, 本文考慮了用戶的個性化隱私需求, 提出了uOLH-DWC 協(xié)議, 該協(xié)議允許用戶自由選擇隱私預(yù)算, 并產(chǎn)生多個隱私級別的頻率估計(jì)結(jié)果以服務(wù)于不同可信度的數(shù)據(jù)使用者. 從理論和實(shí)驗(yàn)的結(jié)果表明, 我們所提出的uOLH-DWC 協(xié)議可最小化輸出結(jié)果誤差, 提高數(shù)據(jù)效用.

我們未來的研究目標(biāo)是如何在個性化模型下進(jìn)一步提高數(shù)據(jù)效用.