汪小寒，韓慧慧，張澤培，俞慶英，鄭孝遙

(1.安徽師范大學(xué) 計(jì)算機(jī)與信息學(xué)院，安徽 蕪湖 241003； 2.安徽師范大學(xué) 網(wǎng)絡(luò)與信息安全安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 蕪湖 241003)(*通信作者電子郵箱hanxiaoahnu@sina.com)

0 引言

在移動(dòng)通信時(shí)代，人們的醫(yī)療、支付、購(gòu)物、導(dǎo)航等數(shù)字化服務(wù)使數(shù)據(jù)收集變得容易，收集的數(shù)據(jù)發(fā)布與共享具有重要價(jià)值，例如，利用城市社交網(wǎng)絡(luò)數(shù)據(jù)不僅可以優(yōu)化道路設(shè)計(jì)，避免交通堵塞，還可以分析個(gè)人感興趣的區(qū)域、用戶的日常軌跡數(shù)據(jù)和居住地址，及具體分布，為決策提供支持。然而，數(shù)據(jù)發(fā)布與共享時(shí)，攻擊者利用各種數(shù)據(jù)挖掘算法，使用戶的隱私信息嚴(yán)重泄露[1]，因此，需要保護(hù)其中的敏感信息不被泄露。經(jīng)典的基于k-anonymity模型[2]隱私保護(hù)方法，易受最小性攻擊、推理攻擊和組合攻擊等，難以提供足夠的隱私安全。差分隱私保護(hù)[3-6]作為新興的隱私保護(hù)方法，具有堅(jiān)實(shí)的數(shù)學(xué)基礎(chǔ)，即使攻擊者掌握了最大的背景知識(shí)，也無(wú)法推理出用戶的隱私信息，可以提供足夠的隱私安全，在學(xué)術(shù)界和工業(yè)界都取得了很好的應(yīng)用效果。其基本思想是向原始數(shù)據(jù)集或查詢函數(shù)返回結(jié)果中添加滿足Laplace分布的噪聲，以達(dá)到隱私保護(hù)的目的。

1 相關(guān)工作

現(xiàn)有的這些隱私預(yù)算分配策略只適應(yīng)特定的空間數(shù)據(jù)應(yīng)用，用戶不能根據(jù)數(shù)據(jù)的隱私保護(hù)需求，個(gè)性化選擇合適的分配方式，來(lái)合理分配隱私預(yù)算，因此，本文提出等差數(shù)列分配法和等比數(shù)列分配法兩種隱私預(yù)算ε分配策略，利用等差和等比數(shù)列的特征，用戶通過調(diào)整差值或比值來(lái)靈活分配隱私預(yù)算，將給定的總的隱私預(yù)算分配給樹結(jié)構(gòu)的每一層；同時(shí)，本文通過數(shù)學(xué)證明和實(shí)驗(yàn)分析，驗(yàn)證了這兩種方法能滿足用戶個(gè)性化設(shè)置差分隱私預(yù)算的需求。

2 基本概念

2.1 差分隱私

差分隱私一般要求任何兩個(gè)數(shù)據(jù)集僅相差一個(gè)元組，隨機(jī)算法的輸出大約是相同的，即在輸入數(shù)據(jù)集中添加或刪除單個(gè)元組，對(duì)輸出不會(huì)產(chǎn)生太大影響，即使攻擊者具有任意背景知識(shí)，也無(wú)法從發(fā)布的查詢輸出中推斷出任何個(gè)體信息的記錄是否在數(shù)據(jù)集中，從而保護(hù)了敏感信息[14]。

定義1 相鄰數(shù)據(jù)集[11]。如果D1和D2是相鄰數(shù)據(jù)集，則D1和D2有著相同的屬性結(jié)構(gòu)，且僅相差一個(gè)元組，記為‖D1-D2‖=1。

定義2 差分隱私[11]。設(shè)D和D′為相鄰的兩個(gè)數(shù)據(jù)集，A為數(shù)據(jù)集上的隨機(jī)算法，S是A任意一組可能的輸出，如果Pr[A(D)∈S]≤eεPr[A(D′)∈S]，則稱算法A滿足ε-差分隱私。其中，參數(shù)ε被稱為隱私預(yù)算，ε越小隱私保護(hù)度越高，但是數(shù)據(jù)的利用率越低。

為了在給定的隱私預(yù)算內(nèi)，將全部預(yù)算合理地分配到樹結(jié)構(gòu)各個(gè)節(jié)點(diǎn)中，使樹結(jié)構(gòu)整體滿足隱私預(yù)算，可以利用差分隱私的一個(gè)基本性質(zhì)。

2.2 Laplace機(jī)制

自從Dwork等[3]引入差分隱私以來(lái)，Laplace機(jī)制成為差分隱私的標(biāo)準(zhǔn)工具。通過它向隱私數(shù)據(jù)統(tǒng)計(jì)信息中加入服從Laplace分布的噪聲，以實(shí)現(xiàn)ε-差分隱私保護(hù)。

3 隱私預(yù)算分配策略

給定二維空間數(shù)據(jù)集D，向它加入服從Laplace分布的噪聲后形成數(shù)據(jù)集D′，最終發(fā)布擾動(dòng)后的數(shù)據(jù)集D′。本文的目標(biāo)是根據(jù)用戶對(duì)數(shù)據(jù)的隱私保護(hù)需求選擇合適的分配方式，來(lái)合理分配隱私預(yù)算，因此，本文提出等差數(shù)列分配法和等比數(shù)列分配法兩種隱私預(yù)算分配策略。

圖1 四叉樹索引隱私預(yù)算ε分配

3.1 等差數(shù)列分配法

從葉子節(jié)點(diǎn)所在的層次起，每一層次分配的隱私預(yù)算與它的上一層次的差等于同一常數(shù)d(d≥0)，即將隱私預(yù)算ε0，ε1，ε2，…，εh分別分配給從0層到h層次的樹結(jié)構(gòu)，其中，εi=εh+(h-i)d。

由性質(zhì)1可得：

(1)

由式(1)可得：

εh=ε/(h+1)-hd/2

(2)

把εh=ε/(h+1)-hd/2代入εi=εh+(h-i)d得：

εi=ε/(h+1)+(h/2-i)d

(3)

因?yàn)棣舏>0，同時(shí)d≥0，所以0≤d<2/[h(h+1)]。

綜合以上可得：

εi=ε/(h+1)+(h/2-i)d; 0≤d<2/[h(h+1)]

(4)

由以上分析可知，當(dāng)給定總的隱私預(yù)算和樹結(jié)構(gòu)的高度，用戶只需調(diào)整d值，就可以改變隱私預(yù)算的分配方式。當(dāng)d值設(shè)置為0時(shí)，樹結(jié)構(gòu)每層分配的隱私預(yù)算相同，等同于均勻分配隱私預(yù)算。當(dāng)0

3.2 等比數(shù)列分配法

從葉子節(jié)點(diǎn)所在的層次起，每一層次分配的隱私預(yù)算與它的上一層次的比等于同一常數(shù)q(q≥1)，即將隱私預(yù)算ε0，ε1，ε2，…，εh分別分配給從0層到h層次的樹結(jié)構(gòu)的每一層，其中εi=εhqh-i(0≤i≤h)。

由性質(zhì)1可得：

(5)

(6)

由式(5)～(6)可得：

εh=ε(1-q)/(1-qh+1)

(7)

將εh=ε(1-q)/(1-qh+1)代入εi=εhqh-i可得：

εi=εqh-i(1-q)/(1-qh+1)；q>1

(8)

εi=ε/(h+1)；q=1

(9)

綜合以上可得：

(10)

由以上分析可知，當(dāng)給定總的隱私預(yù)算和樹結(jié)構(gòu)的高度，用戶只需調(diào)整q值，就可以改變隱私預(yù)算的分配方式。當(dāng)q值設(shè)置為1時(shí)，樹結(jié)構(gòu)每層分配的隱私預(yù)算相同，等同于均勻分配隱私預(yù)算。當(dāng)q>1時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)每層分配的隱私預(yù)算以q倍增加，不難理解，只要稍微改動(dòng)公式就可以變成從葉子點(diǎn)到根節(jié)點(diǎn)每層分配的隱私預(yù)算以q倍增加。

3.3 算法實(shí)現(xiàn)

本文提出的等差數(shù)列分配法和等比數(shù)列分配法算法詳細(xì)描述，分別如算法1和算法2所示。

算法1 等差數(shù)列分配法。

Input：給定的總的隱私預(yù)算ε，樹的高度h，參數(shù)d。

Output：每層的隱私預(yù)算。

Initialε、h和d；

Create Tree(h，root)；

//創(chuàng)建樹

Build Tree(h，root)；

//構(gòu)建樹索引

fori

εi=ε/(h+1)+(h/2-i)d；

GetNoise(εi)；

//獲取Laplace噪聲

end for

if (root!=NULL)

Count′=Count+Noise；

for eachroot->child

AddLaplace(root->child，hcount，Noise)；

//將噪聲遞歸加入到其他節(jié)點(diǎn)中

end for

end if

outputεi

算法2 等比數(shù)列分配法。

Input：給定的總的隱私預(yù)算ε，樹的高度h，參數(shù)q。

Output：每層的隱私預(yù)算。

Initialε、h和q；

Create Tree(h，root)；

//創(chuàng)建樹

Build Tree(h，root)；

//構(gòu)建樹索引

fori

if (q=1)

εi=ε/(h+1)；

else

εi=εqh-i(1-q)/(1-qh+1)；

end if

GetNoise(εi)；

//獲取Laplace噪聲

end for

if (root!=NULL)

Count′=Count+Noise；

for eachroot->child

AddLaplace(root->child，hcount，Noise)；

//將噪聲遞歸加入到其他節(jié)點(diǎn)中

end for

end if

outputεi

以上兩種算法中，用戶只需調(diào)整相鄰兩層分配隱私預(yù)算的差值d或比值q，則可以動(dòng)態(tài)改變隱私預(yù)算的分配方式，以滿足用戶的多樣化需求。這兩種算法將總的隱私預(yù)算分配給樹的每一層的時(shí)間復(fù)雜度為O(n),以及將噪聲添加到每個(gè)節(jié)點(diǎn)中的時(shí)間復(fù)雜度為均為O(nlbn)，因此，這兩種算法總的時(shí)間復(fù)雜度均為O(nlbn)，且該算法簡(jiǎn)單易于理解。

3.4 查詢誤差

對(duì)于任何查詢函數(shù)Q(如圖1中虛線矩形框)，讓Q′表示Q對(duì)樹結(jié)構(gòu)計(jì)算后的回答，那么Q′是對(duì)查詢函數(shù)Q無(wú)偏估計(jì)的真實(shí)回答(此時(shí)加入的噪聲為0)，則方差D(Q′)是查詢精確性的一個(gè)有力指標(biāo)。同文獻(xiàn)[8,11]，本文也定義誤差測(cè)量為Err(Q)=D(Q′)。

(11)

(12)

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

為了檢驗(yàn)本文所提等差和等比隱私預(yù)算分配方法的效果，本文從樹結(jié)構(gòu)每層分配的隱私預(yù)算、每層的查詢誤差和總的查詢誤差三個(gè)方面進(jìn)行分析，并且與常用的均勻分配法和幾何分配法進(jìn)行分析和比較。

本文實(shí)驗(yàn)環(huán)境為：Intel Core i5- 6300HQ CPU @ 2.30 GHz，4 GB內(nèi)存，Windows 10操作系統(tǒng)，Visual Studio 2015，C++語(yǔ)言實(shí)現(xiàn)，實(shí)驗(yàn)是基于四叉樹索引結(jié)構(gòu)。根據(jù)文獻(xiàn)[15]，當(dāng)隱私預(yù)算0<ε≤1時(shí)，數(shù)據(jù)的可用性較好，可以更好地實(shí)現(xiàn)隱私保護(hù)的目的，因此，實(shí)驗(yàn)中總的隱私預(yù)算ε設(shè)置為0.1、0.5和1。假設(shè)查詢函數(shù)為全局敏感度Δf是1的計(jì)數(shù)查詢函數(shù)。

4.1 等差數(shù)列分配法分析

1)每層分配的隱私預(yù)算分析。

給定總的隱私預(yù)算ε為0.5，樹結(jié)構(gòu)的深度h為7，d值分別設(shè)置為0，0.01，0.02和0.03，樹每層隱私預(yù)算分配如圖2所示。

圖2 不同d值下每層隱私預(yù)算分配對(duì)比

從圖2可以看出，當(dāng)d設(shè)置為0時(shí)，樹結(jié)構(gòu)每層分配的隱私預(yù)算相同；當(dāng)d設(shè)置為0.01，0.02和0.03時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，每層分配的隱私預(yù)算呈線性增長(zhǎng)。由于隱私預(yù)算的大小決定了隱私保護(hù)的力度，所以，當(dāng)d=0時(shí)，樹每層的隱私保護(hù)度相同；當(dāng)0

2)每層的查詢誤差分析。

給定總的隱私預(yù)算ε為1，樹深度h為7，d值分別設(shè)置為0，0.01，0.02，0.025和0.03，樹每層查詢誤差Err(leveli)的變化如圖3所示。

從圖3可以看出，隨著d值增加，根節(jié)點(diǎn)的Err(leveli)逐漸增加，葉子節(jié)點(diǎn)的Err(leveli)逐漸減小。當(dāng)樹高度一定時(shí)，每層的Err(leveli)由d值和所在層次的大小所決定，因此，當(dāng)d分別設(shè)置為0，0.01和0.02時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，樹每層的Err(leveli)均以指數(shù)級(jí)增長(zhǎng)；當(dāng)d設(shè)置為0.025和0.03時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，樹結(jié)構(gòu)每層的Err(leveli)是先減小后增加。以上說明，隨著d值增加，Err(leveli)走勢(shì)會(huì)改變，根節(jié)點(diǎn)的查詢精確度越來(lái)越小，葉子節(jié)點(diǎn)的查詢精確度越來(lái)越高，因此，用戶可以根據(jù)對(duì)樹結(jié)構(gòu)每層查詢精確度的不同需求，來(lái)靈活選擇合適的隱私預(yù)算分配方式。

圖3 不同d值下每層查詢誤差變化

3)總的查詢誤差分析。

給定總的隱私預(yù)算ε分別為0.5和1，樹深度h為7時(shí)，則隨著設(shè)置不同的d值，總誤差Err(Q)變化情況如圖4所示。

圖4 d值對(duì)總查詢誤差影響

從圖4可以看出，當(dāng)d值一定時(shí)，隨著ε值的增加，Err(Q)值逐漸減小，因此，給定總的隱私預(yù)算ε越高，整體查詢精確度就越高。當(dāng)ε值一定時(shí)，隨著d值的增加，Err(Q)先減少后增加，且當(dāng)d值無(wú)限接近于2/[h(h+1)]時(shí)，Err(Q)會(huì)急速增加到最大，這是因?yàn)閐值接近2/[h(h+1)]時(shí)，根節(jié)點(diǎn)的Err(leveli)達(dá)到最大，進(jìn)而導(dǎo)致總的誤差Err(Q)最大。同時(shí)，不論h值如何變化，均會(huì)出現(xiàn)一個(gè)d值使Err(Q)達(dá)到最小值，不過這個(gè)值隨著h的變化而變化，例如，當(dāng)h=7時(shí)，d=0.024；當(dāng)h=9時(shí)，d=0.018，因此，用戶可以根據(jù)總的查詢誤差隨著d值的變化情況，以及對(duì)總的查詢精確度的不同需求，來(lái)靈活選擇合適的隱私預(yù)算分配方式。

4.2 等比數(shù)列分配法分析

1)每層分配的隱私預(yù)算分析。

從圖5可以看出，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，每層分配的隱私預(yù)算逐級(jí)遞增。當(dāng)q設(shè)置為1.0時(shí)，樹每層分配的隱私預(yù)算都相同；當(dāng)q設(shè)置為1.05和1.1時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，每層分配的隱私預(yù)算幾乎是呈線性增長(zhǎng)；當(dāng)q設(shè)置為1.26和1.415時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，每層分配的隱私預(yù)算呈指數(shù)增長(zhǎng)。由于隱私預(yù)算的大小決定了隱私保護(hù)的力度，所以，當(dāng)q=1時(shí)，樹每層的隱私保護(hù)度相同；當(dāng)q>1時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，隱私保護(hù)度越來(lái)越高，因此，用戶可以根據(jù)對(duì)每層隱私保護(hù)度的不同需求，來(lái)調(diào)整q值，以選擇合適的隱私預(yù)算分配方式。

圖5 不同q值下每層隱私預(yù)算分配對(duì)比

2)每層的查詢誤差分析。

給定總的隱私預(yù)算ε為1，樹深度h為7，q值分別設(shè)置為1.0，1.1，1.26，1.415和1.5時(shí)，樹每層查詢誤差Err(leveli)的變化情況如圖6所示。

圖6 不同q值下每層的查詢誤差變化

從圖6可以看出，當(dāng)q分別設(shè)置為1.0，1.1和1.26時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，樹每層的Err(leveli)是逐級(jí)遞增；當(dāng)q設(shè)置為1.415時(shí)，每層的Err(leveli)幾乎相同；當(dāng)q設(shè)置為1.5時(shí)，每層的Err(leveli)是逐級(jí)遞減，因此，當(dāng)q設(shè)置為1.415時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，樹每層的查詢精確度幾乎相同；當(dāng)11.415時(shí)，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，樹每層的查詢精確度越來(lái)越高，因此，用戶可以根據(jù)對(duì)樹結(jié)構(gòu)每層查詢精確度的不同需求，通過設(shè)置q值的大小來(lái)滿足需求，以靈活選擇自己需要的隱私預(yù)算分配方式。

當(dāng)q值設(shè)置為1.415，樹深度h為7時(shí)，分別給定總的隱私預(yù)算ε為0.1、0.5和1時(shí)，樹每層查詢誤差Err(leveli)的變化情況如圖7所示。

從圖7可以看出，當(dāng)q設(shè)置為1.415時(shí)，不管給定的總的隱私預(yù)算ε為何值，每層的查詢誤差Err(leveli)幾乎相同，且給定的總的隱私預(yù)算越大，每層查詢誤差Err(leveli)越小。由此說明，當(dāng)給定的總的隱私預(yù)算越大，樹每層的查詢精確度越高，且當(dāng)q設(shè)置為1.415時(shí)，樹每層的查詢精確度幾乎一致，因此當(dāng)用戶需要每層的查詢精確度相同時(shí)，可以選擇把q值設(shè)置為1.415的等比數(shù)列分配法，來(lái)合理分配隱私預(yù)算。

3)總的查詢誤差分析。

給定總的隱私預(yù)算ε分別為0.5和1，樹深度h為7時(shí)，隨著q值變化，總誤差Err(Q)變化情況如圖8所示。

圖7 q是1.415時(shí)每層的查詢誤差變化

圖8 q值對(duì)總查詢誤差影響

4.3 數(shù)據(jù)可用性分析

Dwork[15]指出隱私預(yù)算越小，則添加的噪聲越大，提供的隱私保護(hù)度越大，但是數(shù)據(jù)的可用性越小，因此，數(shù)據(jù)的可用性受到隱私預(yù)算影響。從圖2可知，在等差數(shù)列分配法下，當(dāng)d=0時(shí)，每層分配的隱私預(yù)算相同；當(dāng)01，從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)，每層分配的隱私預(yù)算呈指數(shù)增長(zhǎng)，因此，每層分配的隱私預(yù)算大小受到q值影響，即在等比數(shù)列分配法下，數(shù)據(jù)的可用性受到相鄰兩層分配的隱私預(yù)算比值影響，因此，用戶可以根據(jù)對(duì)數(shù)據(jù)可用性的不同需求，來(lái)靈活選擇合適的隱私預(yù)算分配方式。

4.4 與其他分配策略的比較

本文將提出的等差數(shù)列分配法和等比數(shù)列分配法與隱私預(yù)算分配常用的均勻分配[3]和幾何分配[11]兩種方法作分析比較。分別從樹結(jié)構(gòu)每層查詢誤差和總的查詢誤差兩個(gè)方面分析，實(shí)驗(yàn)結(jié)果如圖9～10所示。

給定總的隱私預(yù)算ε為1，樹深度h為7，其中等差數(shù)列分配法中設(shè)置d值為0.024，等比數(shù)列分配法中設(shè)置q為1.415，不同的隱私預(yù)算分配策略使樹結(jié)構(gòu)每層產(chǎn)生的查詢誤差的結(jié)果如圖9所示。

圖9 不同分配策略下每層查詢誤差對(duì)比

給定總的隱私預(yù)算ε為1，樹深度h從5到9變化，其中等差數(shù)列分配法中針對(duì)不同的h值選擇使總的查詢誤差達(dá)到最小的d值。為了與上面每層查詢誤差分析比較相一致，等比數(shù)列分配法中選擇q值為1.415，不同的隱私預(yù)算分配策略產(chǎn)生總的查詢誤差結(jié)果如圖10所示。

圖10 不同分配策略下總的查詢誤差對(duì)比

4.5 等差數(shù)列分配法與等比數(shù)列分配法的比較

雖然等差數(shù)列分配法和等比數(shù)列分配法均可以根據(jù)用戶對(duì)數(shù)據(jù)隱私保護(hù)的不同需求來(lái)靈活分配隱私預(yù)算ε，但是等比數(shù)列分配法比等差數(shù)列分配法更加靈活，它具有以下優(yōu)點(diǎn)。

1)樹結(jié)構(gòu)每層的查詢精確度呈現(xiàn)規(guī)律性變化。圖6表明等比數(shù)列分配法中隨著q值的不同設(shè)置，樹結(jié)構(gòu)每層的查詢精確度會(huì)呈現(xiàn)規(guī)律性的變化趨勢(shì)。而等差數(shù)列分配法中隨著d值的不同設(shè)置，樹結(jié)構(gòu)每層的查詢精確度呈現(xiàn)無(wú)規(guī)律的變化趨勢(shì)，且當(dāng)d越接近2/[h(h+1)]時(shí)，樹結(jié)構(gòu)根節(jié)點(diǎn)的查詢精確度會(huì)變得很低，從而導(dǎo)致總的查詢精確度很低。

2)不受樹深度h的限制。等差數(shù)列分配法中0≤d<2/[h(h+1)]，d值的設(shè)置受到h的限制，當(dāng)h值越大，d值的取值范圍越小，當(dāng)h值越小，d值的取值范圍越大。而等比數(shù)列分配法中q≥1，不受樹結(jié)構(gòu)深度h的限制。

5 結(jié)語(yǔ)

本文提出等差數(shù)列分配法和等比數(shù)列分配法兩種隱私預(yù)算分配策略，能夠滿足用戶自行選擇的需求，可以根據(jù)隱私保護(hù)度和查詢精確度分配隱私預(yù)算。只要將給定的總的隱私預(yù)算以等差數(shù)列和等比數(shù)列的特征分配給樹的每一層，用戶就可以根據(jù)對(duì)數(shù)據(jù)隱私保護(hù)程度的不同需求，通過調(diào)整相鄰兩層分配隱私預(yù)算的差值或比值，來(lái)改變隱私預(yù)算的分配方式，可以個(gè)性化設(shè)置隱私預(yù)算，改變了傳統(tǒng)隱私預(yù)算均勻分配方法的不足。進(jìn)一步對(duì)這兩種方法作了分析比較，可知等比數(shù)列分配法比等差數(shù)列分配法更加靈活。

本文提出的兩種分配策略，考慮的只是數(shù)值型數(shù)據(jù)，并沒有對(duì)非數(shù)值數(shù)據(jù)或混合型數(shù)據(jù)進(jìn)行研究，下一步將對(duì)此作更加深入的研究。