樹索引數據差分隱私預算分配方法

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

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

0 引言

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

1 相關工作

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

2 基本概念

2.1 差分隱私

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

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

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

為了在給定的隱私預算內，將全部預算合理地分配到樹結構各個節點中，使樹結構整體滿足隱私預算，可以利用差分隱私的一個基本性質。

2.2 Laplace機制

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

3 隱私預算分配策略

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

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

3.1 等差數列分配法

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

由性質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)

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

3.2 等比數列分配法

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

由性質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)

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

3.3 算法實現

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

算法1 等差數列分配法。

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

Output：每層的隱私預算。

Initialε、h和d；

Create Tree(h，root)；

//創建樹

Build Tree(h，root)；

//構建樹索引

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)；

//將噪聲遞歸加入到其他節點中

end for

end if

outputεi

算法2 等比數列分配法。

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

Output：每層的隱私預算。

Initialε、h和q；

Create Tree(h，root)；

//創建樹

Build Tree(h，root)；

//構建樹索引

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)；

//將噪聲遞歸加入到其他節點中

end for

end if

outputεi

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

3.4 查詢誤差

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

(11)

(12)

4 實驗結果與分析

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

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

4.1 等差數列分配法分析

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

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

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

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

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

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

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

圖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)]時，根節點的Err(leveli)達到最大，進而導致總的誤差Err(Q)最大。同時，不論h值如何變化，均會出現一個d值使Err(Q)達到最小值，不過這個值隨著h的變化而變化，例如，當h=7時，d=0.024；當h=9時，d=0.018，因此，用戶可以根據總的查詢誤差隨著d值的變化情況，以及對總的查詢精確度的不同需求，來靈活選擇合適的隱私預算分配方式。

4.2 等比數列分配法分析

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

從圖5可以看出，從根節點到葉子節點，每層分配的隱私預算逐級遞增。當q設置為1.0時，樹每層分配的隱私預算都相同；當q設置為1.05和1.1時，從根節點到葉子節點，每層分配的隱私預算幾乎是呈線性增長；當q設置為1.26和1.415時，從根節點到葉子節點，每層分配的隱私預算呈指數增長。由于隱私預算的大小決定了隱私保護的力度，所以，當q=1時，樹每層的隱私保護度相同；當q>1時，從根節點到葉子節點，隱私保護度越來越高，因此，用戶可以根據對每層隱私保護度的不同需求，來調整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時，從根節點到葉子節點，樹每層的Err(leveli)是逐級遞增；當q設置為1.415時，每層的Err(leveli)幾乎相同；當q設置為1.5時，每層的Err(leveli)是逐級遞減，因此，當q設置為1.415時，從根節點到葉子節點，樹每層的查詢精確度幾乎相同；當11.415時，從根節點到葉子節點，樹每層的查詢精確度越來越高，因此，用戶可以根據對樹結構每層查詢精確度的不同需求，通過設置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的等比數列分配法，來合理分配隱私預算。

3)總的查詢誤差分析。

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

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

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

4.3 數據可用性分析

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

4.4 與其他分配策略的比較

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

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

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

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

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

4.5 等差數列分配法與等比數列分配法的比較

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

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

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

5 結語

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

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