局部差分隱私的不變后隨機(jī)

朱海明

摘要：傳統(tǒng)的差分隱私保護(hù)可能面臨由于第三方數(shù)據(jù)收集者而導(dǎo)致隱私泄漏的威脅。局部差分隱私作為新提出的隱私保護(hù)模型，考慮了來自不可信第三方的隱私攻擊。本文用局部差分隱私的思想，在不變后隨機(jī)響應(yīng)基礎(chǔ)上進(jìn)行改進(jìn)。首先，構(gòu)造隨機(jī)轉(zhuǎn)化矩陣P，使其滿足局部差分隱私與不變后隨機(jī)響應(yīng)的要求；其次，設(shè)計(jì)對(duì)敏感屬性的隱私保護(hù)方法，并給出數(shù)據(jù)擾動(dòng)的算法；最后，實(shí)驗(yàn)驗(yàn)證原始數(shù)與擾動(dòng)數(shù)據(jù)的統(tǒng)計(jì)頻率，kL-散度等。實(shí)驗(yàn)結(jié)果表明本文所用隨機(jī)化可以帶來較小的效用損失，簡化對(duì)擾動(dòng)數(shù)據(jù)的分析。

關(guān)鍵詞：局部差分隱私； 數(shù)據(jù)； 隱私保護(hù)； PRAM； 擾動(dòng)

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）20-0259-03

Local Differential Privacy and Invariant Post Randomization Method

ZHU Hai-ming

（School of Computer Science and Engineering， Anhui University of Science and Technology，Huainan 232001，China）

Abstract：Traditional differential privacy protection may face the threat of privacy leakage due to third-party data collectors. As a newly proposed privacy protection model， local differential privacy considers privacy attacks from untrusted third parties. This article uses the idea of local differential privacy to improve on the basis of invariant PRAM. First， the stochastic transformation matrix P is constructed to satisfy the requirements of local differential privacy and invariant PRAM. Secondly， the privacy protection method for sensitive attributes is designed and the data perturbation algorithm is given. Finally， the experiment verifies the statistics of the original number and disturbance data. Frequency， kL-divergence， etc. The experimental results show that the randomization used in this paper can bring less utility loss and simplify the analysis of disturbance data.

Key words：local differential privacy； data； privacy protection； PRAM； perturbation

1 引言

在大數(shù)據(jù)時(shí)期，數(shù)據(jù)成為科學(xué)研究的基石。隨著信息技術(shù)，特別是網(wǎng)絡(luò)、存儲(chǔ)、移動(dòng)終端的快速發(fā)展，使得信息數(shù)據(jù)的采集、管理和利用變得愈來愈簡單。而在采集、分析用戶數(shù)據(jù)時(shí)，可能會(huì)泄漏用戶的隱私 [1]。2017年11月，Ube爆出客戶數(shù)據(jù)遭到泄漏。2018年3月Facebook被爆5000萬用戶數(shù)據(jù)泄漏。因此，在數(shù)據(jù)采集的過程中，數(shù)據(jù)提供者對(duì)于涉及自己隱私的敏感問題，通常不愿提供真實(shí)的數(shù)據(jù)，甚至拒絕提供任何信息。在進(jìn)行數(shù)據(jù)分析時(shí)候使用這樣的數(shù)據(jù)就會(huì)得到準(zhǔn)確性很差，甚至是完全錯(cuò)誤的結(jié)果。因此，如何在進(jìn)行數(shù)據(jù)收集與挖掘的同時(shí)保護(hù)用戶的隱私的安全已經(jīng)成為近年來數(shù)據(jù)挖掘研究的熱點(diǎn)之一。

隨機(jī)響應(yīng)技術(shù)最早是由warner，在1965年提出，用于解決“如何獲取一個(gè)回答者可能不愿意如實(shí)作答的敏感問題的準(zhǔn)確答案”這樣一個(gè)問題[2]。在收集數(shù)據(jù)階段對(duì)被調(diào)查者的敏感信息進(jìn)行保護(hù)。Dwork等人在2006年提出了差分隱私的概念，其實(shí)現(xiàn)機(jī)制是添加拉普拉斯噪音或者指數(shù)噪音[3]。

本文提出了滿足差分隱私要求的不變后隨機(jī)響應(yīng)。有效地解決了隨機(jī)化方法中擾動(dòng)矩陣P的選擇問題，考慮了對(duì)于二值屬性的具體應(yīng)用。其應(yīng)用場景主要包括：終端媒體的用戶數(shù)據(jù)采集，網(wǎng)絡(luò)問卷隱私信息的保護(hù)，云數(shù)據(jù)隱私信息的采集等方面。

不變后隨機(jī)響應(yīng)在局部差分隱私的使用可以在數(shù)據(jù)集滿足隱私保護(hù)要求的同時(shí)，最大化數(shù)據(jù)效用。最后，使用UCI機(jī)器學(xué)習(xí)庫的Adult數(shù)據(jù)集進(jìn)行了廣泛的實(shí)驗(yàn)，并通過期望比率來判斷擾動(dòng)文件是否安全；探究了隱私預(yù)算與不同數(shù)據(jù)量對(duì)數(shù)據(jù)可用性的影響；通過對(duì)比原始文件與擾動(dòng)后文件的KL-散度，來分析算法對(duì)數(shù)據(jù)效用的影響。

2 基本概念

假設(shè)原始的數(shù)據(jù)具有數(shù)據(jù)表D（NA，SA）形式，NA非敏感屬性的域是[{A1，A2，…，Ad}]，敏感屬性SA的域是[{B1，B2，…，Bd}]。r[NA]和r[NB]指數(shù)據(jù)庫中第r條記錄NA，SA的值。[xi]的數(shù)量指具有[xi]值的記錄的數(shù)量，[xi]的頻率指具有[xi]值的記錄的數(shù)量在整個(gè)記錄中的百分比[4]。一般通過對(duì)敏感屬性的擾動(dòng)來實(shí)現(xiàn)隱私保護(hù)，而非敏感屬性在數(shù)據(jù)發(fā)布中通常不做改變，本文，主要以單敏感屬性來討論，對(duì)多敏感屬性也可看作是單屬性的擴(kuò)充。本文選取部分Adult數(shù)據(jù)作為實(shí)驗(yàn)數(shù)據(jù)，以其中workclass屬性作為敏感屬性，原始文件屬性統(tǒng)計(jì)見表1。

2.1 不變后隨機(jī)響應(yīng)

后隨機(jī)化方法（PRAM）是由Kooiman等人在1997作為數(shù)據(jù)文件統(tǒng)計(jì)公開控制的一種方法[5]。

后隨機(jī)響應(yīng)技術(shù)方式是把原始文件中某些分類變量的值，根據(jù)給定的概率機(jī)制轉(zhuǎn)變?yōu)槠渌闹?，并且產(chǎn)生一個(gè)新的數(shù)據(jù)文件。換句話說，新產(chǎn)生的擾動(dòng)后的文件中的記錄與原始記錄中的個(gè)體屬性的值有可能是不同的，通過這種方式，引入了數(shù)據(jù)的不確定性：用戶不能確定文件中的信息是原始信息還是由于PRAM造成的擾動(dòng)信息。從而保證了個(gè)體隱私安全。PRAM一個(gè)重要的方面是這個(gè)擾動(dòng)是按照一定概率機(jī)制的，這個(gè)概率機(jī)制可以用于數(shù)據(jù)的分析，可以降低擾動(dòng)對(duì)統(tǒng)計(jì)結(jié)果的影響。

令[ ξ] 表示在應(yīng)用PRAM的原始文件中的敏感屬性分類變量，并讓X表示擾動(dòng)文件中的相同的分類變量。此外，假定[ξ]有k個(gè)類別，因此對(duì)應(yīng)的X也有k個(gè)類別，編號(hào)為1，…， K。定義應(yīng)用PRAM所涉及的轉(zhuǎn)移概率[pkl= IP（X = l |ξ= k）]，即原始分?jǐn)?shù)[ξ]= k變?yōu)榉謹(jǐn)?shù)X =l的概率。對(duì)于所有k，l = 1，…， K。PRAM可用由K×K馬爾可夫矩陣P來描述，其條目是轉(zhuǎn)移概率[pkl]。最后，令[ξ（r）]和X（r）分別表示對(duì)應(yīng)的原始和擾動(dòng)后的數(shù)據(jù)文件中第r條記錄的變量的值。應(yīng)用PRAM意味著，對(duì)于給定[ξr=k]，以及概率分布[pk1，...pkk]，那么便可以求得[xr]上的值。對(duì)于原始文件中的每個(gè)記錄，認(rèn)為此過程是獨(dú)立其他記錄的[5]。

一般的PRAM對(duì)轉(zhuǎn)移概率的馬爾可夫矩陣P只是假設(shè)P本身是可逆的，并未施加更多的限制，該矩陣的逆可以結(jié)合擾動(dòng)后的文件來校正列聯(lián)表，以獲得對(duì)原始文件產(chǎn)生的相應(yīng)表的無偏估計(jì)。如Kooiman等人研究的在其他幾種統(tǒng)計(jì)分析的情況下，矩陣P的逆可以用來糾正PRAM對(duì)統(tǒng)計(jì)分析的影響。

例如：用 [Tξ ]表示原始文件中的（復(fù)合）變量[ ξ ]的列聯(lián)表，[TX ]表示對(duì)應(yīng)的擾動(dòng)文件的相應(yīng)表。

[ETX|ξ1，…，ξn=ptTξ]

其中t表示轉(zhuǎn)置，n是數(shù)據(jù)文件中的記錄數(shù)，因此可以通過定義獲得無偏估計(jì)：

[Tξ=（P-1）tTX]

這簡單例子可以看出，通過公布的擾動(dòng)后的數(shù)據(jù)和矩陣P，可以估計(jì)出原始數(shù)據(jù)的統(tǒng)計(jì)結(jié)果。但一般PRAM在進(jìn)行統(tǒng)計(jì)分析時(shí)要考慮對(duì)矩陣P的使用，進(jìn)行額外的步驟以獲得無偏估計(jì)。 于是，不變的PRAM被 Gouweleeuw等人提出討論（1997不變的PRAM）。不變的PRAM技術(shù)是對(duì)馬爾可夫矩陣P的選擇施加額外的條件，使得用戶使用擾動(dòng)文件進(jìn)行數(shù)據(jù)統(tǒng)計(jì)分析時(shí)，不需要再考慮錯(cuò)誤分類帶來的影響，就好像它是原始文件一樣。 簡單來說不變的PRAM技術(shù)，對(duì)矩陣P的選擇要滿足馬爾可夫矩陣以及方程：

[ptTξ=Tξ]

下面給出一個(gè)轉(zhuǎn)移矩陣P增加額外條件的構(gòu)造，假設(shè)對(duì)于k=1，..，K.[ Tξ（k）≥ Tξ（K）>0]，且0[<θ<1。 用 Tξ（k）]表示原始文件中變量值ξ= k的記錄數(shù)。[pkl]由下式得到

[pkl=1-（θTξ（K）/Tξ（K）） if l=kθTξ（K）/（（K-1）Tξ（K）） if l≠k]

可以驗(yàn)證P={[Pkl]}是滿足馬爾可夫矩陣的，此時(shí)

[ETX|ξ1，…，ξn=ptTξ=Tξ]

可以得到無偏估計(jì)：

[Tξ=TX]

這意味對(duì)于不變的PRAM，[Tξ] 的估計(jì)量可以直接由擾動(dòng)后的文件獲得，不再需要轉(zhuǎn)移概率矩陣P的參與，簡化了分析步驟。

2.2 局部差分隱私

局部差分隱私保護(hù)技術(shù)是在傳統(tǒng)差分隱私保護(hù)技術(shù)的基礎(chǔ)上的進(jìn)一步改進(jìn)，區(qū)別于傳統(tǒng)的差分隱私需要可信的數(shù)據(jù)收集者局部差分隱私不需要可信的數(shù)據(jù)收集者[6][7]。

其具有傳統(tǒng)差分隱私保護(hù)技術(shù)的組合特性，并采用隨機(jī)響應(yīng)擾動(dòng)機(jī)制進(jìn)行擴(kuò)展來抵御不可信第三方數(shù)據(jù)采集器帶來的隱私攻擊。局部差分隱私的形式化定義如下：

定義1.給定n個(gè)數(shù)據(jù)記錄，給定一個(gè)算法機(jī)制M，且其定義域?yàn)镈om（M）和值域?yàn)镽an（M），若任兩條在Dom（M）上的記錄t和t'作為算法M的輸入，而可以得到一致輸出結(jié)果t* （ t*[∈] Ran（M） ），則認(rèn)為機(jī)制M滿足[ε-]局部差分隱私：

[Pr [Mt=t*]≤eε×Pr [Mt'=t*]]

2.3 隱私保護(hù)與效用度量

隱私保護(hù)要在保護(hù)用戶隱私的前提下盡可能地滿足數(shù)據(jù)分析對(duì)于數(shù)據(jù)效用的需求。在PRAM方法中隱私披露的風(fēng)險(xiǎn)通過預(yù)期比率的概念來衡量，預(yù)期比率的定義是：擾動(dòng)文件中（觀察值等于原始文件中值的）預(yù)期記錄數(shù)，和擾動(dòng)文件中觀察值不等于原始文件中值的預(yù)期記錄數(shù)的比。定義如下：

[ERk=pkkTξ（k）l≠kplkTξ（l） for k=1，…，K]

ER（k）的值越小，x = k的記錄越不可能屬于該值，因此擾動(dòng)文件越安全。

由于目前許多數(shù)據(jù)分析應(yīng)用都與數(shù)據(jù)的概率分布有關(guān)，因此在評(píng)估數(shù)據(jù)庫的效用時(shí)，本文采用KL-散度度量數(shù)據(jù)的效用。

KL-散度（Kullback–Leibler Divergence）是用來比較兩個(gè)概率分布的接近程度，本文中用來分析原始數(shù)據(jù)與擾動(dòng)后數(shù)據(jù)在同一個(gè)屬性上分布的距離，代表原始數(shù)據(jù)被擾動(dòng)后其分布信息的減少程度，計(jì)算公式如下：

[DKL=ip（i）logP（i）Q（i）]

3 局部差分隱私的不變后隨機(jī)

首先考慮敏感屬性是二值屬性的情況，二值屬性是指僅有兩個(gè)值的屬性，如值是或否的屬性。分別用u和v表示屬性的兩個(gè)值，用pu ， pv 表示對(duì)應(yīng)值擾動(dòng)概率 ，其中pv=1--pu對(duì)二值屬性擾動(dòng)的轉(zhuǎn)移矩陣一般構(gòu)造為以下形式：

P是馬爾科夫矩陣，puv=P（u|v）， 表示原始值為v擾動(dòng)為u的概率。在進(jìn)行擾動(dòng)時(shí)為保證滿足[ε]-局部化差分隱私，需要對(duì)P進(jìn)行選擇，據(jù)定義，隱私預(yù)算[ε]為：

[ε=ln （pu/pv ）]

根據(jù)需要滿足的隱私預(yù)算保護(hù)，構(gòu)造出轉(zhuǎn)移概率矩陣P[8][9]。

下面使用二階段后隨機(jī)響應(yīng)方式實(shí)現(xiàn)不變后隨機(jī)響應(yīng)，二階段的PRAM主要思想是：假設(shè)原始數(shù)據(jù)中屬性[ ξ] 使用任意的馬爾可夫矩陣P進(jìn)行擾動(dòng)。然后由擾動(dòng)后文件中的值，可以計(jì)算原始文件中[ξ]的概率分布。再用這個(gè)概率分布將干擾文件轉(zhuǎn)換回來。通常經(jīng)過兩次擾動(dòng)后的文件可以看作是應(yīng)用不變PRAM的結(jié)果[10][11]。

用轉(zhuǎn)移矩陣P對(duì)原始數(shù)據(jù)ξ進(jìn)行擾動(dòng)，擾動(dòng)后的對(duì)應(yīng)的數(shù)據(jù)記為X。

[P? uv = pu?u+（1-pv）?v（1-pu）?u+pv?v ]

根據(jù)對(duì)擾動(dòng)后文件的統(tǒng)計(jì)分析，可以用數(shù)據(jù)集X與矩陣P，估計(jì)原始數(shù)據(jù)集的概率分布。用[Plk]表示ξ的原始值為k的概率：

[Plk=IPξ=k|X=l=pklTξ（k）jpljTξ（j）]

此時(shí)我們得到了一個(gè)新的轉(zhuǎn)移矩陣[Plk，]再將此轉(zhuǎn)移概率矩陣應(yīng)用于第一次擾動(dòng)后的數(shù)據(jù)上

用X*來表示這兩次擾動(dòng)后的文件中[ξ]的值，那么可以看出x*與原始數(shù)據(jù)中[ξ]的概率分布是相同的。這樣就相當(dāng)于使用了一個(gè)符合不變PRAM的轉(zhuǎn)移概率矩陣對(duì)原始文件進(jìn)行擾動(dòng)。

即是按照[eε]/k-1+[eε] 的概率響應(yīng)輸出真實(shí)值，以1/ k-1+[eε]的概率響應(yīng)輸出剩下的k-1個(gè)結(jié)果的任意一種，使其滿足[ε-局部差分隱私]。

4 實(shí)驗(yàn)評(píng)估

對(duì)隱私保護(hù)而言，隱私保護(hù)程度與數(shù)據(jù)可用性呈負(fù)相關(guān)，隱私保護(hù)程度高則數(shù)據(jù)可用性低，隱私保護(hù)程度低則數(shù)據(jù)可用性高.本文中不變后隨機(jī)的局部查分隱私通過控制隨機(jī)響應(yīng)技術(shù)輸出真實(shí)值的概率值來控制數(shù)據(jù)的偏離程度，進(jìn)而保護(hù)隱私。

本文使用UCI機(jī)器學(xué)習(xí)庫的Adult數(shù)據(jù)集，從中抽取5個(gè)屬性為原始數(shù)據(jù)集，其中以workclass 屬性為敏感屬性，具體統(tǒng)計(jì)值見表1。圖2對(duì)比了一般PRAM與不變PRAM的統(tǒng)計(jì)結(jié)果，可以看出后者結(jié)果更加接近原始數(shù)據(jù)，可以簡化數(shù)據(jù)分析步驟。

以下實(shí)驗(yàn)利用上述的度量方法，即通過期望比來度量隱私的披露風(fēng)險(xiǎn)，用KL-散度來度量數(shù)據(jù)的效用。同考慮的不同的[ε ]值對(duì)統(tǒng)計(jì)結(jié)果造成的影響.其中，[ε ]包含以下三種取值：0.1， 0.5以及0.9。表1 是在不變后隨機(jī)局部差分隱私的算法上取不同[ε ]的，與原始數(shù)據(jù)和擾動(dòng)數(shù)據(jù)之間的距離值越小，它們之間的差異越小，失真數(shù)據(jù)庫的效用越好。以KL-散度作為距離差異的效用損失。

5 結(jié)束語

本文提出了滿足局部差分隱私的不變后隨機(jī)算法。該算法首先選取數(shù)據(jù)屬性中的敏感屬性作為擾動(dòng)對(duì)象，對(duì)其進(jìn)行擾動(dòng)獲得初次擾動(dòng)的數(shù)據(jù)；然后通過對(duì)此數(shù)據(jù)進(jìn)行分析，得到二次擾動(dòng)的轉(zhuǎn)移概率；再由計(jì)算結(jié)果進(jìn)行二次擾動(dòng)，得到最終的發(fā)布數(shù)據(jù)。實(shí)驗(yàn)結(jié)果分析表明，該算法在滿足隱私保護(hù)的前提下還具有很好的效用性，且簡化了對(duì)擾動(dòng)數(shù)據(jù)的分析。

參考文獻(xiàn)：

[1] Y Sei， A Ohsuga.Differential Private data collection and analysis based on randomized multiple dummies for untrust-ed mobile crowdsensing[J]. IEEE Transactions on Infor-mation Forensics and Security， 2017， 12（4）： 926-939.

[2] Domingo-Ferrer J， Torra V. Disclosure control methods and information loss for microdata[C]// Confidentiality， Disclosure and Data Access： Theory and Practical Application for Statistical Agencies. 2001.

[3] Dwork C.Differential privacy： a survey of results[C]//International Conference on Theory and Applications of MODELS of Computation.Springer-Verlag，2008：1-19.

[4] Wang K，Han C，F(xiàn)u A W.Randomization Resilient To Sensitive Reconstruction[J].Annals of Internal Medicine，2012，158（2）：397-403.

[5] Gouweleeuw J. Post randomization for statistical disclosure control：Theory and implementation[J].Journal of Official Statistics， 1998， 14（4）：463.

[6] 張嘯劍，孟小峰.面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J].計(jì)算機(jī)學(xué)報(bào)，2014（4）：927-949.

[7] 李楊， 溫雯， 謝光強(qiáng). 差分隱私保護(hù)研究綜述[J].計(jì)算機(jī)應(yīng)用研究，2012，29（9）：3201-3205.

[8] 吳英杰，陳景林，蔡建平，等.基于矩陣機(jī)制的差分隱私數(shù)據(jù)發(fā)布方法的誤差分析[J].計(jì)算機(jī)科學(xué)與技術(shù)前沿，2018：1-15.

[9] Yingjie Wu，Jinglin Chen，Jianping Cai，et al.Error analysis of differential privacy data publishing method with matrix mechanism[J].Journal of Frontiers of Computer Science and Technology，2018：1-15.

[10] Nayak T K，Adeshiyan S A.On Invariant Post-randomization for Statistical Disclosure Control[J].International Statistical Review，2016，84（1）：26-42.

[11] H N.，J L D.，M O.Optimal differentially private mecha-nisms for randomised response[J].IEEE Transactions on Information Forensics and Security，2017，12（11）：2726-2735.