樹索引數(shù)據(jù)差分隱私預算分配方法

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

(1.安徽師范大學 計算機與信息學院，安徽 蕪湖 241003； 2.安徽師范大學 網(wǎng)絡與信息安全安徽省重點實驗室，安徽 蕪湖 241003)(*通信作者電子郵箱hanxiaoahnu@sina.com)

0 引言

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

1 相關(guān)工作

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

2 基本概念

2.1 差分隱私

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

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

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

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

2.2 Laplace機制

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

3 隱私預算分配策略

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

圖1 四叉樹索引隱私預算ε分配

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

從葉子節(jié)點所在的層次起，每一層次分配的隱私預算與它的上一層次的差等于同一常數(shù)d(d≥0)，即將隱私預算ε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)

因為εi>0，同時d≥0，所以0≤d<2/[h(h+1)]。

綜合以上可得：

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

(4)

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

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

從葉子節(jié)點所在的層次起，每一層次分配的隱私預算與它的上一層次的比等于同一常數(shù)q(q≥1)，即將隱私預算ε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)

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

3.3 算法實現(xiàn)

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

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

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

Output：每層的隱私預算。

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é)點中

end for

end if

outputεi

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

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

Output：每層的隱私預算。

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é)點中

end for

end if

outputεi

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

3.4 查詢誤差

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

(11)

(12)

4 實驗結(jié)果與分析

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

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

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

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

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

圖2 不同d值下每層隱私預算分配對比

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

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

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

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

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

3)總的查詢誤差分析。

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

圖4 d值對總查詢誤差影響

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

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

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

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

圖5 不同q值下每層隱私預算分配對比

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

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

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

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

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

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

3)總的查詢誤差分析。

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

圖7 q是1.415時每層的查詢誤差變化

圖8 q值對總查詢誤差影響

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

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

4.4 與其他分配策略的比較

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

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

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

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

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

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

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

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

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

5 結(jié)語

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

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