局部差分隐私的不变后随机

朱海明

摘要：传统的差分隐私保护可能面临由于第三方数据收集者而导致隐私泄漏的威胁。局部差分隐私作为新提出的隐私保护模型，考虑了来自不可信第三方的隐私攻击。本文用局部差分隐私的思想，在不变后随机响应基础上进行改进。首先，构造随机转化矩阵P，使其满足局部差分隐私与不变后随机响应的要求；其次，设计对敏感属性的隐私保护方法，并给出数据扰动的算法；最后，实验验证原始数与扰动数据的统计頻率，kL-散度等。实验结果表明本文所用随机化可以带来较小的效用损失，简化对扰动数据的分析。

关键词：局部差分隐私； 数据； 隐私保护； 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 引言

在大数据时期，数据成为科学研究的基石。随着信息技术，特别是网络、存储、移动终端的快速发展，使得信息数据的采集、管理和利用变得愈来愈简单。而在采集、分析用户数据时，可能会泄漏用户的隐私 [1]。2017年11月，Ube爆出客户数据遭到泄漏。2018年3月Facebook被爆5000万用户数据泄漏。因此，在数据采集的过程中，数据提供者对于涉及自己隐私的敏感问题，通常不愿提供真实的数据，甚至拒绝提供任何信息。在进行数据分析时候使用这样的数据就会得到准确性很差，甚至是完全错误的结果。因此，如何在进行数据收集与挖掘的同时保护用户的隐私的安全已经成为近年来数据挖掘研究的热点之一。

随机响应技术最早是由warner，在1965年提出，用于解决“如何获取一个回答者可能不愿意如实作答的敏感问题的准确答案”这样一个问题[2]。在收集数据阶段对被调查者的敏感信息进行保护。Dwork等人在2006年提出了差分隐私的概念，其实现机制是添加拉普拉斯噪音或者指数噪音[3]。

本文提出了满足差分隐私要求的不变后随机响应。有效地解决了随机化方法中扰动矩阵P的选择问题，考虑了对于二值属性的具体应用。其应用场景主要包括：终端媒体的用户数据采集，网络问卷隐私信息的保护，云数据隐私信息的采集等方面。

不变后随机响应在局部差分隐私的使用可以在数据集满足隐私保护要求的同时，最大化数据效用。最后，使用UCI机器学习库的Adult数据集进行了广泛的实验，并通过期望比率来判断扰动文件是否安全；探究了隐私预算与不同数据量对数据可用性的影响；通过对比原始文件与扰动后文件的KL-散度，来分析算法对数据效用的影响。

2 基本概念

假设原始的数据具有数据表D（NA，SA）形式，NA非敏感属性的域是[{A1，A2，…，Ad}]，敏感属性SA的域是[{B1，B2，…，Bd}]。r[NA]和r[NB]指数据库中第r条记录NA，SA的值。[xi]的数量指具有[xi]值的记录的数量，[xi]的频率指具有[xi]值的记录的数量在整个记录中的百分比[4]。一般通过对敏感属性的扰动来实现隐私保护，而非敏感属性在数据发布中通常不做改变，本文，主要以单敏感属性来讨论，对多敏感属性也可看作是单属性的扩充。本文选取部分Adult数据作为实验数据，以其中workclass属性作为敏感属性，原始文件属性统计见表1。

2.1 不变后随机响应

后随机化方法（PRAM）是由Kooiman等人在1997作为数据文件统计公开控制的一种方法[5]。

后随机响应技术方式是把原始文件中某些分类变量的值，根据给定的概率机制转变为其他的值，并且产生一个新的数据文件。换句话说，新产生的扰动后的文件中的记录与原始记录中的个体属性的值有可能是不同的，通过这种方式，引入了数据的不确定性：用户不能确定文件中的信息是原始信息还是由于PRAM造成的扰动信息。从而保证了个体隐私安全。PRAM一个重要的方面是这个扰动是按照一定概率机制的，这个概率机制可以用于数据的分析，可以降低扰动对统计结果的影响。

令[ ξ] 表示在应用PRAM的原始文件中的敏感属性分类变量，并让X表示扰动文件中的相同的分类变量。此外，假定[ξ]有k个类别，因此对应的X也有k个类别，编号为1，…， K。定义应用PRAM所涉及的转移概率[pkl= IP（X = l |ξ= k）]，即原始分数[ξ]= k变为分数X =l的概率。对于所有k，l = 1，…， K。PRAM可用由K×K马尔可夫矩阵P来描述，其条目是转移概率[pkl]。最后，令[ξ（r）]和X（r）分别表示对应的原始和扰动后的数据文件中第r条记录的变量的值。应用PRAM意味着，对于给定[ξr=k]，以及概率分布[pk1，...pkk]，那么便可以求得[xr]上的值。对于原始文件中的每个记录，认为此过程是独立其他记录的[5]。

一般的PRAM对转移概率的马尔可夫矩阵P只是假设P本身是可逆的，并未施加更多的限制，该矩阵的逆可以结合扰动后的文件来校正列联表，以获得对原始文件产生的相应表的无偏估计。如Kooiman等人研究的在其他几种统计分析的情况下，矩阵P的逆可以用来纠正PRAM对统计分析的影响。

例如：用 [Tξ ]表示原始文件中的（复合）变量[ ξ ]的列联表，[TX ]表示对应的扰动文件的相应表。

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

其中t表示转置，n是数据文件中的记录数，因此可以通过定义获得无偏估计：

[Tξ=（P-1）tTX]

这简单例子可以看出，通过公布的扰动后的数据和矩阵P，可以估计出原始数据的统计结果。但一般PRAM在进行统计分析时要考虑对矩阵P的使用，进行额外的步骤以获得无偏估计。 于是，不变的PRAM被 Gouweleeuw等人提出讨论（1997不变的PRAM）。不变的PRAM技术是對马尔可夫矩阵P的选择施加额外的条件，使得用户使用扰动文件进行数据统计分析时，不需要再考虑错误分类带来的影响，就好像它是原始文件一样。 简单来说不变的PRAM技术，对矩阵P的选择要满足马尔可夫矩阵以及方程：

[ptTξ=Tξ]

下面给出一个转移矩阵P增加额外条件的构造，假设对于k=1，..，K.[ Tξ（k）≥ Tξ（K）>0]，且0[<θ<1。 用 Tξ（k）]表示原始文件中变量值ξ= k的记录数。[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ξ] 的估计量可以直接由扰动后的文件获得，不再需要转移概率矩阵P的参与，简化了分析步骤。

2.2 局部差分隐私

局部差分隐私保护技术是在传统差分隐私保护技术的基础上的进一步改进，区别于传统的差分隐私需要可信的数据收集者局部差分隐私不需要可信的数据收集者[6][7]。

其具有传统差分隐私保护技术的组合特性，并采用随机响应扰动机制进行扩展来抵御不可信第三方数据采集器带来的隐私攻击。局部差分隐私的形式化定义如下：

定义1.给定n个数据记录，给定一个算法机制M，且其定义域为Dom（M）和值域为Ran（M），若任两条在Dom（M）上的记录t和t'作为算法M的输入，而可以得到一致输出结果t* （ t*[∈] Ran（M） ），则认为机制M满足[ε-]局部差分隐私：

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

2.3 隐私保护与效用度量

隐私保护要在保护用户隐私的前提下尽可能地满足数据分析对于数据效用的需求。在PRAM方法中隐私披露的风险通过预期比率的概念来衡量，预期比率的定义是：扰动文件中（观察值等于原始文件中值的）预期记录数，和扰动文件中观察值不等于原始文件中值的预期记录数的比。定义如下：

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

ER（k）的值越小，x = k的记录越不可能属于该值，因此扰动文件越安全。

由于目前许多数据分析应用都与数据的概率分布有关，因此在评估数据库的效用时，本文采用KL-散度度量数据的效用。

KL-散度（Kullback–Leibler Divergence）是用来比较两个概率分布的接近程度，本文中用来分析原始数据与扰动后数据在同一个属性上分布的距离，代表原始数据被扰动后其分布信息的减少程度，计算公式如下：

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

3 局部差分隐私的不变后随机

首先考虑敏感属性是二值属性的情况，二值属性是指仅有两个值的属性，如值是或否的属性。分别用u和v表示属性的两个值，用pu ， pv 表示对应值扰动概率 ，其中pv=1--pu对二值属性扰动的转移矩阵一般构造为以下形式：

P是马尔科夫矩阵，puv=P（u|v）， 表示原始值为v扰动为u的概率。在进行扰动时为保证满足[ε]-局部化差分隐私，需要对P进行选择，据定义，隐私预算[ε]为：

[ε=ln （pu/pv ）]

根据需要满足的隐私预算保护，构造出转移概率矩阵P[8][9]。

下面使用二阶段后随机响应方式实现不变后随机响应，二阶段的PRAM主要思想是：假设原始数据中属性[ ξ] 使用任意的马尔可夫矩阵P进行扰动。然后由扰动后文件中的值，可以计算原始文件中[ξ]的概率分布。再用这个概率分布将干扰文件转换回来。通常经过两次扰动后的文件可以看作是应用不变PRAM的结果[10][11]。

用转移矩阵P对原始数据ξ进行扰动，扰动后的对应的数据记为X。

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

根据对扰动后文件的统计分析，可以用数据集X与矩阵P，估计原始数据集的概率分布。用[Plk]表示ξ的原始值为k的概率：

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

此时我们得到了一个新的转移矩阵[Plk，]再将此转移概率矩阵应用于第一次扰动后的数据上

用X*来表示这两次扰动后的文件中[ξ]的值，那么可以看出x*与原始数据中[ξ]的概率分布是相同的。这样就相当于使用了一个符合不变PRAM的转移概率矩阵对原始文件进行扰动。

即是按照[eε]/k-1+[eε] 的概率响应输出真实值，以1/ k-1+[eε]的概率响应输出剩下的k-1个结果的任意一种，使其满足[ε-局部差分隐私]。

4 实验评估

对隐私保护而言，隐私保护程度与数据可用性呈负相关，隐私保护程度高则数据可用性低，隐私保护程度低则数据可用性高.本文中不变后随机的局部查分隐私通过控制随机响应技术输出真实值的概率值来控制数据的偏离程度，进而保护隐私。

本文使用UCI机器学习库的Adult数据集，从中抽取5个属性为原始数据集，其中以workclass 属性为敏感属性，具体统计值见表1。图2对比了一般PRAM与不变PRAM的统计结果，可以看出后者结果更加接近原始数据，可以简化数据分析步骤。

以下实验利用上述的度量方法，即通过期望比来度量隐私的披露风险，用KL-散度来度量数据的效用。同考虑的不同的[ε ]值对统计结果造成的影响.其中，[ε ]包含以下三种取值：0.1， 0.5以及0.9。表1 是在不变后随机局部差分隐私的算法上取不同[ε ]的，与原始数据和扰动数据之间的距离值越小，它们之间的差异越小，失真数据库的效用越好。以KL-散度作为距离差异的效用损失。

5 结束语

本文提出了满足局部差分隐私的不变后随机算法。该算法首先选取数据属性中的敏感属性作为扰动对象，对其进行扰动获得初次扰动的数据；然后通过对此数据进行分析，得到二次扰动的转移概率；再由计算结果进行二次扰动，得到最終的发布数据。实验结果分析表明，该算法在满足隐私保护的前提下还具有很好的效用性，且简化了对扰动数据的分析。

参考文献：

[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，Fu 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] 张啸剑，孟小峰.面向数据发布和分析的差分隐私保护[J].计算机学报，2014（4）：927-949.

[7] 李杨， 温雯， 谢光强. 差分隐私保护研究综述[J].计算机应用研究，2012，29（9）：3201-3205.

[8] 吴英杰，陈景林，蔡建平，等.基于矩阵机制的差分隐私数据发布方法的误差分析[J].计算机科学与技术前沿，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.