局部差分隱私的新型實現方法

董濤 劉蕓菲

摘要：有效的隱私保護數據發布解決方案之一是局部差分隱私，隨機響應是實現這種隱私保護模型的有效方式。對基于二次擾動的局部差分隱私實現方法進行了研究。為衡量D和D'的離散程度，在計算原始數據集和擾動數據集的分布均值和方差的基礎上實驗驗證了D和D'間的KL-散度。實驗結果表明本文所采用的二次擾動方法可以帶來較小的效用損失。

關鍵詞：局部差分隱私；隨機響應；二次擾動

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2018）30-0234-02

Abstract： One of the effective privacy protection data publishing solutions is local differential privacy， which is an effective way to implement this privacy protection model. This paper proposes a local differential privacy implementation method based on secondary perturbation. In order to measure the degree of dispersion of D and D'， the KL-divergence between D and D' is experimentally verified on the basis of calculating the mean and variance of the distribution of the original dataset and the perturbed dataset. The experimental results show that the secondary perturbation method used in this paper can bring less utility loss.

Key words： local differential privacy； random response； secondary perturbation

1 引言

對于企業來說，在數據收集、使用以及公布的過程中，用戶隱私不可避免地暴露在外。2006年，Netflix舉辦了一個名為Netflix Prize的預測算法的比賽，結果導致了用戶身份的泄露[1-2]。

k-anonymity、l-diversity、t-closeness[3]方法常被用于隱私數據的保護，這些方法的提出在一定程度上抵御了隱私攻擊，但這種基于分組數據產生的隱私保護模型會隨著攻擊方法的不同而做出相應的改變。基于以上的原因，人們需要一種魯棒性比較好的隱私保護模型。2006年，微軟研究院的Dwork[4]提出了差分隱私的概念，從而使這種隱私保護模型成為可能。

2 局部差分隱私實現

局部差分隱私：給定n個用戶，每個用戶對應一條記錄。給定一個隱私算法M及其定義域 Dom（M）和值域Ran（M），若算法M在任意兩條記錄t和t'（t，[t'∈dom（M）]）上得到相同輸出結果t*（[t*∈Ran（M）]）滿足下列不等式，則M滿足ε-局部差分隱私。

局部差分隱私的定義從理論的角度保證了算法滿足ε-本地化差分隱私，而實現ε-本地化差分隱私保護需要數據擾動機制的介入。隨機響應技術[5]的基本思想是以一定的概率將另一個值cj替換原始數據集中的每個ci。我們使用θj，i來表示類別ci被隨機化為cj的概率，其中i， j=1， ， n。我們用P*（ci）， P（ci）分別表示擾動數據，原始數據中ci的概率。

在上面的等式中，原始數據集分布[P]是我們試圖找出的。而擾動數據集分布[P*]可用每個類別的頻率來估計。

實現局部差分隱私的關鍵在于隨機響應矩陣M的構造。二次擾動具體實現要在多值屬性的基礎上進行構造，設屬性Ak具有m個屬性值，分別用v1， v2， …， vm表示。若Ak=vi （i=1， 2， …， m）在原數據集中所占的比例為，則采用均勻擾動得擾動矩陣MB為：

3 實驗

為了實驗的準確性，采取的是美國1994年人口普查數據庫抽取而來的Adult數據集。本文進行四組隱私預算ε的實驗，分別為組1（ε1 =0.2，ε2 = 0.8）、組2（ε1 =0.3，ε2 = 0.7）、組3（ε1 =0.4，ε2 = 0.6）和組4（ε1 =0.5，ε2 = 0.5），為達到度量這方面的目的，利用平均KL-散度度量原始數據集D和擾動數據集D'之間的距離，數據集分別劃分為L=（1K、2K、4K、8K、16、30K），由此得到如圖1所示的對比圖。

圖1（a）是對數據集D分別進行四組隱私預算限制下的數據集擾動，在得到D'后，根據數據集L的分片數據進行一次平均KL–散度的計算結果。由圖可看出四組實驗均有一定的擾動誤差，為了減少隨機擾動的偏差，本文又做了十組實驗得到圖1（b），由圖1（a）和圖1（b）的對比得到兩個結論：（1）表明擾動誤差得到了較好的減少；（2）組3（ε1 =0.4，ε2 = 0.6）時D和D'間的平均KL–散度值最少，這表明本文的方法在保證了局部差分隱私的同時有著較好的數據效用。

4 結束語

實驗結果表明本文所采用的二次擾動方法能更好地保持原始數據集的分布特性，在數據效用和披露風險方面具有較好的效果。然而，文中還有不完美的地方，主要是關于數據集僅限在單表數據庫的處理，下一步我們將對多表數據庫時如何擾動進行研究，以更好的維持數據效用，保護用戶的隱私信息。

參考文獻：

[1] Zhang J， Cormode G， Procopiuc C M， et al. Privbayes： Private data release via bayesian networks[J]. ACM Transactions on Database Systems （TODS）， 2017， 42（4）： 25.

[2] Zhu， T.， et al.， Differentially Private Data Publishing and Analysis： A Survey. IEEE Transactions on Knowledge & Data Engineering， 2017. 29（8）： p. 1619-1638.

[3] Mancuhan， K. and C. Clifton， Statistical Learning Theory Approach for Data Classification with l-diversity[C]//. Proceedings of the 2017 SIAM International Conference on Data Ming. Society for industrial and Applied Mathematics， 2017： p. 651-659.

[4] Dwork C. Differential Privacy[C]// International Colloquium on Automata， Languages， and Programming. Springer， Berlin， Heidelberg， 2006：1-12.

[5] Huang Z， Du W. OptRR： Optimizing Randomized Response Schemes for Privacy-Preserving Data Mining[C]// IEEE， International Conference on Data Engineering. IEEE， 2008：705-714.

【通聯編輯：梁書】