歐陽(yáng)恒，陳洪超

(貴州輕工職業(yè)技術(shù)學(xué)院 信息工程系，貴州 貴陽(yáng) 550025)

0 引言

在真實(shí)世界許多數(shù)據(jù)集中，數(shù)據(jù)集元組之間存在相互依賴關(guān)系，而非獨(dú)立。Kifer和Machanavajjhala[5]發(fā)現(xiàn)，當(dāng)數(shù)據(jù)元組有依賴關(guān)系時(shí)，DP存在一定的局限性。Zhu等人[6]提出關(guān)聯(lián)元組的非交互式直方圖發(fā)布方法，首次解決了元組間相關(guān)性帶來(lái)的隱私泄露風(fēng)險(xiǎn)。Liu等人[7]提出ε-依賴性差異隱私(ε-DDP)，并使用拉普拉斯機(jī)制實(shí)現(xiàn)噪聲擾動(dòng)。Zhao等人[8]優(yōu)化了Liu等人提出的拉普拉斯機(jī)制，添加更少的噪聲來(lái)解決元組間的相關(guān)性引起的隱私泄露。然而，基于依賴差分隱私的高斯機(jī)制的研究還存在一定的空白。

本文主要貢獻(xiàn)：一是提出了一種推理攻擊，對(duì)手利用元組之間的依賴性從差分隱私查詢結(jié)果中獲取敏感信息，二是本文提出(ε，δ)-依賴差分隱私((ε，δ)-DDP)的定義，量化了二范數(shù)敏感度，并設(shè)計(jì)了一種高斯機(jī)制實(shí)現(xiàn)(ε，δ)-DDP的噪聲擾動(dòng)。

1 相關(guān)概念

定義1(相鄰數(shù)據(jù)集[9])假設(shè)數(shù)據(jù)集D和D′具有完全相同的數(shù)據(jù)屬性結(jié)構(gòu)，如果數(shù)據(jù)集D和D′之間至多只相差一條記錄，即|D-D′|=1。數(shù)據(jù)集D和D′是相鄰數(shù)據(jù)集(Adjacent Datasets)。

定義2((ε，δ)-差分隱私，(ε，δ)-DP[10])設(shè)一個(gè)隨機(jī)機(jī)制M：R→Y，滿足(ε，δ)-差分隱私，則對(duì)于任意兩個(gè)鄰近的數(shù)據(jù)集D和D′，M(D)所有的輸出E?T，有下列不等式成立：

P(D)∈E]≤eεP(D′)∈E]+δ

(1)

其中隱私預(yù)算ε是隱私保護(hù)程度的一個(gè)參數(shù)，平衡數(shù)據(jù)的安全性和可用性。δ(通常很小)是能夠容忍不滿足ε-差分隱私的部分，如果δ=0，那么滿足ε-差分隱私。ε-差分隱私一般稱為純差分隱私，(ε，δ)-差分隱私一般稱為近似差分隱私

定義3(全局敏感度[11])數(shù)據(jù)集D和D′至多相差一條數(shù)據(jù)，對(duì)于任意一個(gè)查詢函數(shù)f：D→Rd，函數(shù)f的全局敏感度為：

(2)

定義4(隱私損失函數(shù)[12])設(shè)一個(gè)隨機(jī)機(jī)制M，隱私損失函數(shù)LM，D，D′(Y)可以表示為M作用到相鄰數(shù)據(jù)集D和D′，輸出隨機(jī)變量Y相同時(shí)兩個(gè)概率之間的距離。定義如下：

(3)

其中FM(D)(Y)是輸出隨機(jī)變量Y=(D)的概率密度函數(shù)，如果選擇高斯機(jī)制添加噪聲，那么隱私損失函數(shù)同樣服從高斯分布，即LM，D，D′(Y)=(Δ2f/2σ2，Δ2f/σ2)[13]。

2 差分隱私的隱私風(fēng)險(xiǎn)

由于在真實(shí)的應(yīng)用領(lǐng)域中，數(shù)據(jù)集中的元組其實(shí)有著相互依賴的關(guān)系[14]，而差分隱私在提出之初就隱含著構(gòu)成數(shù)據(jù)集的數(shù)據(jù)元組之間是相互獨(dú)立的假設(shè)。事實(shí)上，這是一個(gè)薄弱的假設(shè)，尤其是因?yàn)橛捎谟脩糁g的社會(huì)關(guān)系、行為習(xí)慣和基因相互作用[15-16]，導(dǎo)致元組依賴在數(shù)據(jù)集中必然存在。例如，在社交網(wǎng)絡(luò)圖中(節(jié)點(diǎn)代表用戶，邊代表“友誼”關(guān)系)，圖中未明確連接的兩個(gè)節(jié)點(diǎn)之間的“友誼”可以從其他節(jié)點(diǎn)之間存在的邊推斷出來(lái)[17]。對(duì)手可以訪問(wèn)擾動(dòng)后的查詢結(jié)果，并且知道用戶的直系親屬是被查詢數(shù)據(jù)庫(kù)的一部分，因此很容易推斷出用戶對(duì)傳染病的易感性。對(duì)手可以使用輔助信息通道訪問(wèn)這些依賴關(guān)系，并利用差分隱私中的缺陷，獲取隱私數(shù)據(jù)，如圖1所示。

圖1 元組依賴的圖例

一個(gè)數(shù)據(jù)集D=(Di，Dj)，其中Di和Dj具有概率依賴關(guān)系，設(shè)Dj=0.5Di+0.5X，考慮一個(gè)簡(jiǎn)單的推理攻擊，其中一個(gè)對(duì)手發(fā)出一個(gè)和查詢：f(D)=Di+Dj，此時(shí)對(duì)手可以推斷出Di的值。

P[M(Di=1，Dj)∈E]/P[M(Di=0，Dj)∈E]≤eε

(4)

其中c(δ)≥1，不等式(4)恒成立。

P[M(Di=1，Dj)∈E]/P[M(Di=0，Dj)∈E]≤eε

(5)

式(5)將在1≤c(δ)≤1.5范圍內(nèi)不成立，存在隱私泄露的風(fēng)險(xiǎn)。

3 (ε，δ)-依賴差分隱私

傳統(tǒng)的差分隱私，作用于元組相關(guān)的數(shù)據(jù)集時(shí)，并不能有效得防止上述攻擊，存在隱私泄露得風(fēng)險(xiǎn)。

定義5(依賴相鄰數(shù)據(jù)集[7])若數(shù)據(jù)集D(L，R)中一個(gè)元組值的變化，導(dǎo)致數(shù)據(jù)集D′(L，R)中最多有L-1其他元組的值產(chǎn)生變化，引起的變化大小關(guān)系為R，則數(shù)據(jù)集D(L，R)和D′(L，R)是依賴相鄰數(shù)據(jù)集。

定義6((ε，δ)-依賴差分隱私，(ε，δ)-DDP)設(shè)一個(gè)隨機(jī)機(jī)制M：→滿足(ε，δ)-DDP，則對(duì)于任意兩個(gè)依賴鄰近數(shù)據(jù)集D(L，R)和D′(L，R)，M(d)所有的輸出E?有下列不等式成立：

P[M(D(L，R))∈E]≤eεP[M(D′(L，R))∈E]+δ

(6)

其中L表示依賴大小，R表示數(shù)據(jù)元組之間依賴關(guān)系的大小。

3.1 DDP全局敏感度

(7)

其中，由于Di從di1到di2的變化，輸出結(jié)果是有界的。

使用高斯噪聲擾動(dòng)查詢結(jié)果。首先將式(7)進(jìn)一步變換為下列等式：

(8)

等式(8)的右邊第一項(xiàng)進(jìn)一步計(jì)算，可以得到：

(9)

其中ΔDi是由于Di的變化而產(chǎn)生的最大差異。從等式(9)可以看出，與傳統(tǒng)的差分隱私的噪聲方差完全相同，因此(ε，δ)-DP只是在Di和Dj不相關(guān)時(shí)的一個(gè)特例。而式(8)的右邊第二項(xiàng)包含Di和Dj的依賴關(guān)系，也就是相關(guān)性。

(10)

其中ρij表示Di的變化將引起Dj發(fā)生變化的依賴程度。最后，結(jié)合式(8)～(10)，可以得到：

(11)

(1)因?yàn)棣裪j是衡量?jī)蓚€(gè)元組的相關(guān)性的大小，因此ρij∈[0，1]。

(2)當(dāng)ρij=0時(shí)，此時(shí)元組間沒(méi)有相關(guān)關(guān)系，滿足(ε，δ)-DP。

(4)是不對(duì)稱的，即ρij≠ρji(例如：遺傳病父母可以影響子女，而子女卻不能影響父母)。

前面分析了兩個(gè)元組依賴關(guān)系下，敏感度的度量，類似的可以推廣到包含兩個(gè)以上元組的數(shù)據(jù)集上的任意查詢函數(shù)的場(chǎng)景。

定理1(依賴敏感度) 數(shù)據(jù)集D(L，R)和D′(L，R)是依賴相鄰數(shù)據(jù)集，對(duì)于任意一個(gè)查詢函數(shù)f：D→Rd，函數(shù)f的依賴敏感度為：

(12)

其中，j∈[1，2，…，L]表示有L個(gè)元組與第i個(gè)元組的相關(guān)程度，且ρij=1。

3.2 (ε，δ)-DDP高斯機(jī)制算法

根據(jù)依賴敏感度，本文設(shè)計(jì)了一個(gè)有效的高斯機(jī)制來(lái)實(shí)現(xiàn)(ε，δ)-DDP和支持依賴元組上的差分隱私擾動(dòng)，并描述了基于現(xiàn)有高斯機(jī)制的依賴差分隱私高斯機(jī)制算法，該算法滿足(ε，δ)-DDP。

定理2((ε，δ)-GMA-DDP)對(duì)于依賴數(shù)據(jù)集D(L，R)上的一個(gè)查詢函數(shù)f：D→Rd，其依賴敏感度為Δ2fDS，隨機(jī)機(jī)制M滿足(ε，δ)-DDP，則需要滿足下式：

M(D)=f(D)+(0，σ2)

(13)

根據(jù)以上的噪聲擾動(dòng)機(jī)制，可以順利對(duì)一個(gè)查詢返回含有噪聲的結(jié)果，并且滿足(ε，δ)-DDP的隱私保證，然而在交互式查詢中，通常需要回答多次查詢，這種情況下，是否依然滿足相應(yīng)的隱私保證。因此，對(duì)于(ε，δ)-DP的組合定理，在(ε，δ)-DDP中同樣適用。

3.3 (ε，δ)-DDP安全分析

本文采用Kifer等人[5]提出的兩個(gè)隱私公理：變換不變性和凸性性質(zhì)，分析(ε，δ)-DDP的安全性。任何完整的隱私定義都應(yīng)該滿足這兩個(gè)公理。

定理3(變換不變性)對(duì)于任意一個(gè)隨機(jī)算法M作用在依賴大小為L(zhǎng)和依賴關(guān)系為R的數(shù)據(jù)集D(L，R)上，且M滿足(ε，δ)-DDP，那么對(duì)于其他任何隨機(jī)化算法A，Am(·)=A(M(·))也滿足數(shù)據(jù)集D(L，R)上的(ε，δ)=DDP。

證明：P[A(M(D))=E|di1]

=∑DP[A(O)=E]P[M(D)=O|di1]

≤∑DP[A(O)=E]eεP[M(D)=O|di2]+δ

=eεP[A(M(D))=E|di2]+δ

定理4(凸性性質(zhì))對(duì)于任意兩個(gè)隨機(jī)化算法M1、M2作用在依賴大小為L(zhǎng)和依賴關(guān)系為R的數(shù)據(jù)集D(L，R)上，且都滿足(ε，δ)=DDP，設(shè)Mp表示一個(gè)算法，該算法以概率p運(yùn)行M1，以概率1-p運(yùn)行M2，那么Mp也滿足數(shù)據(jù)集D(L，R)上的(ε，δ)=DDP。

證明：

P[Mp(D)=E|di1]

=pP[M1(D)=E|di1]+(1-p)P[M2(D)=E|di1]

≤eεpP[M1(D)=E|di2]+eε(1-p)P[M2(D)=E|di2]+δ

=eεP[Mp(D)=E|di2]+δ

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

4.1 實(shí)驗(yàn)環(huán)境與數(shù)據(jù)集

該實(shí)驗(yàn)中所使用的軟硬件具體參數(shù)如下：

(1)操作系統(tǒng)：Windows10；

(2)硬件參數(shù)：Intel(R)Core(TM)i7-10700F CPU，2.9 GHz，RAM內(nèi)存16 GB；

(3)編譯環(huán)境及工具：Python3.6，PyCharm。

本文采用Adult真實(shí)數(shù)據(jù)集IPUMS。從2022年的1 700條數(shù)據(jù)，選取了其中10 000條數(shù)據(jù)，其中每條數(shù)據(jù)包括以下4個(gè)屬性：Total personal income，Total family income，Age，Sex。

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

實(shí)驗(yàn)前將采用的數(shù)據(jù)集元組間的依賴程度設(shè)置為固定值：0.5。與Liu等人[7]在2016年提出的線性算法(Baseline)和依賴差分隱私的拉普拉斯機(jī)制(DDP-Lap)對(duì)比，設(shè)置查詢?yōu)椤捌骄鶄€(gè)人總收入”，因?yàn)樵谏鲜鰯?shù)據(jù)集中，用戶的個(gè)人總收入在0到100 000之間，所以敏感度為(100 000-0)/10 000=10。0<εi<1中隨機(jī)采樣，δ=0.1。

如圖2所示，隨著查詢次數(shù)的增加，查詢結(jié)果中的噪聲之和逐漸累積，Baseline算法絕對(duì)誤差與查詢次數(shù)呈線性關(guān)系，這將使得添加的噪聲非常大，導(dǎo)致查詢結(jié)果不可用，正如預(yù)期的那樣，GMA-DDP的噪聲量明顯低于Baseline算法與DDP-Lap，這表明GMA-DDP向查詢結(jié)果中添加了更少的噪聲，使查詢結(jié)果更接近于真實(shí)結(jié)果，并達(dá)到了相同的隱私保護(hù)水平。

圖2 GMA-DDP誤差對(duì)比

如圖3所示，本文也從(α，β)=Accuracy的角度來(lái)對(duì)比三個(gè)算法的隱私性與可用性的平衡，這是衡量隱私性與可用性的常用指標(biāo)。實(shí)驗(yàn)表明，GMA-DDP在相同的隱私水平下具有更高的可用性，在相同的可用性下，降低隱私預(yù)算的開(kāi)銷，提供更強(qiáng)的隱私保護(hù)水平，尤其在隱私預(yù)算較小(高隱私水平)的情況下，GMA-DDP的可用性更高。

圖3 GMA-DDP效用對(duì)比

5 結(jié)論

本文針對(duì)差分隱私定義應(yīng)用到依賴數(shù)據(jù)集時(shí)，存在隱私泄露風(fēng)險(xiǎn)的問(wèn)題，根據(jù)(ε，δ)=DDP的定義，量化了在依賴數(shù)據(jù)集下敏感度的大小。根據(jù)依賴敏感度，設(shè)計(jì)了滿足(ε，δ)=DDP的噪聲擾動(dòng)機(jī)制—依賴高斯機(jī)制。最后在真實(shí)數(shù)據(jù)集上，將GMA-DDP的可用性與Baseline算法和DDP-Lap進(jìn)行對(duì)比，實(shí)驗(yàn)結(jié)果表明GMA-DDP有較好的可用性。