局部差分隱私的新型實(shí)現(xiàn)方法

董濤 劉蕓菲

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

關(guān)鍵詞：局部差分隱私；隨機(jī)響應(yīng)；二次擾動(dòng)

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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 引言

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

k-anonymity、l-diversity、t-closeness[3]方法常被用于隱私數(shù)據(jù)的保護(hù)，這些方法的提出在一定程度上抵御了隱私攻擊，但這種基于分組數(shù)據(jù)產(chǎn)生的隱私保護(hù)模型會(huì)隨著攻擊方法的不同而做出相應(yīng)的改變?；谝陨系脑?，人們需要一種魯棒性比較好的隱私保護(hù)模型。2006年，微軟研究院的Dwork[4]提出了差分隱私的概念，從而使這種隱私保護(hù)模型成為可能。

2 局部差分隱私實(shí)現(xiàn)

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

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

在上面的等式中，原始數(shù)據(jù)集分布[P]是我們?cè)噲D找出的。而擾動(dòng)數(shù)據(jù)集分布[P*]可用每個(gè)類別的頻率來估計(jì)。

實(shí)現(xiàn)局部差分隱私的關(guān)鍵在于隨機(jī)響應(yīng)矩陣M的構(gòu)造。二次擾動(dòng)具體實(shí)現(xiàn)要在多值屬性的基礎(chǔ)上進(jìn)行構(gòu)造，設(shè)屬性Ak具有m個(gè)屬性值，分別用v1， v2， …， vm表示。若Ak=vi （i=1， 2， …， m）在原數(shù)據(jù)集中所占的比例為，則采用均勻擾動(dòng)得擾動(dòng)矩陣MB為：

3 實(shí)驗(yàn)

為了實(shí)驗(yàn)的準(zhǔn)確性，采取的是美國(guó)1994年人口普查數(shù)據(jù)庫(kù)抽取而來的Adult數(shù)據(jù)集。本文進(jìn)行四組隱私預(yù)算ε的實(shí)驗(yàn)，分別為組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），為達(dá)到度量這方面的目的，利用平均KL-散度度量原始數(shù)據(jù)集D和擾動(dòng)數(shù)據(jù)集D'之間的距離，數(shù)據(jù)集分別劃分為L(zhǎng)=（1K、2K、4K、8K、16、30K），由此得到如圖1所示的對(duì)比圖。

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

4 結(jié)束語(yǔ)

實(shí)驗(yàn)結(jié)果表明本文所采用的二次擾動(dòng)方法能更好地保持原始數(shù)據(jù)集的分布特性，在數(shù)據(jù)效用和披露風(fēng)險(xiǎn)方面具有較好的效果。然而，文中還有不完美的地方，主要是關(guān)于數(shù)據(jù)集僅限在單表數(shù)據(jù)庫(kù)的處理，下一步我們將對(duì)多表數(shù)據(jù)庫(kù)時(shí)如何擾動(dòng)進(jìn)行研究，以更好的維持?jǐn)?shù)據(jù)效用，保護(hù)用戶的隱私信息。

參考文獻(xiàn)：

[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.

【通聯(lián)編輯：梁書】