依賴差分隱私：關聯數據集下的高斯機制*

歐陽恒，陳洪超

(貴州輕工職業技術學院 信息工程系，貴州 貴陽 550025)

0 引言

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

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

1 相關概念

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

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

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

(1)

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

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

(2)

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

(3)

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

2 差分隱私的隱私風險

由于在真實的應用領域中，數據集中的元組其實有著相互依賴的關系[14]，而差分隱私在提出之初就隱含著構成數據集的數據元組之間是相互獨立的假設。事實上，這是一個薄弱的假設，尤其是因為由于用戶之間的社會關系、行為習慣和基因相互作用[15-16]，導致元組依賴在數據集中必然存在。例如，在社交網絡圖中(節點代表用戶，邊代表“友誼”關系)，圖中未明確連接的兩個節點之間的“友誼”可以從其他節點之間存在的邊推斷出來[17]。對手可以訪問擾動后的查詢結果，并且知道用戶的直系親屬是被查詢數據庫的一部分，因此很容易推斷出用戶對傳染病的易感性。對手可以使用輔助信息通道訪問這些依賴關系，并利用差分隱私中的缺陷，獲取隱私數據，如圖1所示。

圖1 元組依賴的圖例

一個數據集D=(Di，Dj)，其中Di和Dj具有概率依賴關系，設Dj=0.5Di+0.5X，考慮一個簡單的推理攻擊，其中一個對手發出一個和查詢：f(D)=Di+Dj，此時對手可以推斷出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范圍內不成立，存在隱私泄露的風險。

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

傳統的差分隱私，作用于元組相關的數據集時，并不能有效得防止上述攻擊，存在隱私泄露得風險。

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

定義6((ε，δ)-依賴差分隱私，(ε，δ)-DDP)設一個隨機機制M：→滿足(ε，δ)-DDP，則對于任意兩個依賴鄰近數據集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表示數據元組之間依賴關系的大小。

3.1 DDP全局敏感度

(7)

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

使用高斯噪聲擾動查詢結果。首先將式(7)進一步變換為下列等式：

(8)

等式(8)的右邊第一項進一步計算，可以得到：

(9)

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

(10)

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

(11)

(1)因為ρij是衡量兩個元組的相關性的大小，因此ρij∈[0，1]。

(2)當ρij=0時，此時元組間沒有相關關系，滿足(ε，δ)-DP。

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

前面分析了兩個元組依賴關系下，敏感度的度量，類似的可以推廣到包含兩個以上元組的數據集上的任意查詢函數的場景。

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

(12)

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

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

根據依賴敏感度，本文設計了一個有效的高斯機制來實現(ε，δ)-DDP和支持依賴元組上的差分隱私擾動，并描述了基于現有高斯機制的依賴差分隱私高斯機制算法，該算法滿足(ε，δ)-DDP。

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

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

(13)

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

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

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

定理3(變換不變性)對于任意一個隨機算法M作用在依賴大小為L和依賴關系為R的數據集D(L，R)上，且M滿足(ε，δ)-DDP，那么對于其他任何隨機化算法A，Am(·)=A(M(·))也滿足數據集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(凸性性質)對于任意兩個隨機化算法M1、M2作用在依賴大小為L和依賴關系為R的數據集D(L，R)上，且都滿足(ε，δ)=DDP，設Mp表示一個算法，該算法以概率p運行M1，以概率1-p運行M2，那么Mp也滿足數據集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 實驗結果

4.1 實驗環境與數據集

該實驗中所使用的軟硬件具體參數如下：

(1)操作系統：Windows10；

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

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

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

4.2 實驗結果分析

實驗前將采用的數據集元組間的依賴程度設置為固定值：0.5。與Liu等人[7]在2016年提出的線性算法(Baseline)和依賴差分隱私的拉普拉斯機制(DDP-Lap)對比，設置查詢為“平均個人總收入”，因為在上述數據集中，用戶的個人總收入在0到100 000之間，所以敏感度為(100 000-0)/10 000=10。0<εi<1中隨機采樣，δ=0.1。

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

圖2 GMA-DDP誤差對比

如圖3所示，本文也從(α，β)=Accuracy的角度來對比三個算法的隱私性與可用性的平衡，這是衡量隱私性與可用性的常用指標。實驗表明，GMA-DDP在相同的隱私水平下具有更高的可用性，在相同的可用性下，降低隱私預算的開銷，提供更強的隱私保護水平，尤其在隱私預算較小(高隱私水平)的情況下，GMA-DDP的可用性更高。

圖3 GMA-DDP效用對比

5 結論

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