朱海明

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

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

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

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

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

不變后隨機響應(yīng)在局部差分隱私的使用可以在數(shù)據(jù)集滿足隱私保護要求的同時，最大化數(shù)據(jù)效用。最后，使用UCI機器學習庫的Adult數(shù)據(jù)集進行了廣泛的實驗，并通過期望比率來判斷擾動文件是否安全；探究了隱私預(yù)算與不同數(shù)據(jù)量對數(shù)據(jù)可用性的影響；通過對比原始文件與擾動后文件的KL-散度，來分析算法對數(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ù)量在整個記錄中的百分比[4]。一般通過對敏感屬性的擾動來實現(xiàn)隱私保護，而非敏感屬性在數(shù)據(jù)發(fā)布中通常不做改變，本文，主要以單敏感屬性來討論，對多敏感屬性也可看作是單屬性的擴充。本文選取部分Adult數(shù)據(jù)作為實驗數(shù)據(jù)，以其中workclass屬性作為敏感屬性，原始文件屬性統(tǒng)計見表1。

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

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

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

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

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

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

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

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

[Tξ=（P-1）tTX]

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

[ptTξ=Tξ]

下面給出一個轉(zhuǎn)移矩陣P增加額外條件的構(gòu)造，假設(shè)對于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]

可以驗證P={[Pkl]}是滿足馬爾可夫矩陣的，此時

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

可以得到無偏估計：

[Tξ=TX]

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

2.2 局部差分隱私

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

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

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

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

2.3 隱私保護與效用度量

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

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

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

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

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

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

3 局部差分隱私的不變后隨機

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

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

[ε=ln （pu/pv ）]

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

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

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

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

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

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

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

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

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

4 實驗評估

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

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

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

5 結(jié)束語

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

參考文獻：

[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ā)布和分析的差分隱私保護[J].計算機學報，2014（4）：927-949.

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

[8] 吳英杰，陳景林，蔡建平，等.基于矩陣機制的差分隱私數(shù)據(jù)發(fā)布方法的誤差分析[J].計算機科學與技術(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.