基于混合机制下的差分隐私直方图发布

摘 要：差分隐私在隐私保护中越来越受欢迎，它对具有任意背景知识的敌手可以提供严格的隐私保障。通过添加噪声使数据失真的技术，来起到保护隐私的目的。本文主要研究基于拉普拉斯机制和指数机制下的差分隐私直方图发布问题。机制的选择对隐私数据的发布是至关重要的。其中，Laplace机制适合数值型结果的隐私保护，指数机制运用于对非数值型结果的保护。本文在结构优先算法下，选择以上两种不同机制来实现满足差分隐私的直方图发布。

关键词：差分隐私;混合机制;隐私保护;直方图发布

中图分类号：TP309

文献标识码：A

文章编号 1000-5269（2018）04-0032-05

当今，随着经济的快速发展，互联网技术也得到了迅速的崛起，这一崛起给人们带来了极大的方便，可以说现在人们的生活样样都离不开网络，在支付、交通、导航、购物和健康方面，人们现在比以往更多地依靠数字服务。而这一技术的发展使各种组织能够轻松收集大量的个人信息，再比如某医院病人的医疗记录、网络搜索历史、出行记录等等。对这些数据进行分析也变得越来越重要。特别是对于政府部门、信息咨询组织以及研究机构来说，信息成为了很重要的研究及发展资源。数据的发布、共享与分析

方面的需求正在日益增长。然而，随着数据集的发布和共享，数据集里包含的个人隐私也很可能发生泄漏。虽然通过改动数据集的标识符属性，能够起到一定的隐私保护，但是在发生的隐私泄露案例说明，仅此操作是不能足以保障隐私安全的。因此，在1977年，统计学家Tore Dalenius提出了一个严格的数据隐私概念：攻击者在使用敏感数据集之前，对他们不认识的人应该一无所知.虽然这一定义具有理论上的指导意义，但显然它是主观的和模糊的。从已有的研究来看，k-匿名[1]和l-diversity是基于限制发布的泛化技术，k-匿名由Samarati和Sweeney提出可以保证任意一条记录与另外的k-1条记录不可区分。但k-匿名易受到一致性攻击和背景知识攻击。因此，Machanavajjhala等人提出l-diversity原则[2]，但由于其容易受到相似性攻击。鉴于此，直到2006年Cynthia Dwork提出差分隐私[3]这一新的定义从而解决了以上存在的根本性问题。在Dwork的定义之下，其要求是要做到具体某个记录的变化对数据集计算处理结果的影响微乎其微。

与传统的隐私保护相比，差分隐私的优点是：首先，差分隐私无需考虑攻击者所拥有的任何背景知识。其次，它有很强的数学理论作支撑，可对隐私保护模型作出证明和表示。正因为差分隐私这一优点，从而业界对差分隐私的研究引起了一番热潮，随后便拉开了它的帷幕。

本文主要研究基于两种机制下的直方图发布技术。Laplace机制[4]最早是由Dwork等人提出的，其大小主要由查询敏感度和隐私预算ε[5]决定。由于在一些实际运用中，查询不一定是针对数值型。于是，McSherry等人提出的指数机制[6]，其专针对查询结果为实体对象。而用直方图直接发布未经处理的数据会造成很大的隐私后患，因此，必须对数据进行加噪和箱分组处理，才能保证隐私安全，这两种处理技术离不开机制的选择。如图1为患有癌症病人的年龄分布，图2是其对应患者的年龄分布的原始直方图。这种类似的数据集在网上也是普遍存在。从直方图中可以直观地看到每个年龄段患者记录情况，其中40-45年龄段的患者就有5人。如果攻击者想要知道John是否患有此病，而已知数据库中剩余19人的患病情况。那么，攻击者从图2可以推断出John患了Cancer疾病，从而造成John的个人隐私泄漏。

因此，以上例子充分说明，若不对数据进行处理而直接发布，会造成很大的隐私后患。利用差分隐私保护方法，在直方图发布之前，对数据进行处理，就能达到隐私保护的效果。鉴于此，本文同时也提出了一种以服从差分隐私直方图发布[7]的算法，即Structure-First。它的原理是先对原始直方图进行分组，再对分组后的直方图加噪音，这种算法都需借助混合机制。

1 相关研究

对差分隐私数据的发布，研究者们提出了不同机制下的数据发布问题。Dwork等人提出了Laplace机制以及McSherry等人提出了指数机制，为后面研究差分隐私作了铺垫。李杨等人针对K-means中添加噪声后的数据偏离中心点的问题进行改进，提出了IDP-means[8]聚类方法，该方法提高了数据可用性。

Xiao等人[9]将Haar小波变换应用于差分隐私保护中，在添加噪音前先对数据实施小波变换，其提高了查询的准确度。

Li等人[10]提出的矩阵机制。在给定一组查询下，该机制请求与其具有相联关系的查询作出响应，与原有的作对比，其噪音量明显减少了。Roth和Roughgarden等人[11]提出了中位数机制，在该机制下，查询被分为“难查询”和“易查询”，他们的研究表明，给定域Z和k个查询，“难查询”的数量级为O（（log2k）（log2Z）），其它均为“易查询”。Hardt等人[12]提出了另一种有效机制，即PMN，该机制的理论来源于机器学习。该算法用于通过投票机制来构建一个复合算法。以上的研究大多是基于减小绝对误差的思想对查询精度进行优化，从而达到隐私保护的效果。

本文拟在差分隐私条件下，通过结构优先算法，使用拉普拉斯机制和指数机制来实现直方图数据发布。

3 混合机制下的差分隐私直方图发布-StructureFirst算法

差分隐私直方图发布很大程度上是依赖于直方图的结构。结构优先顾名思义就是先对原始统计好的直方图进行分组，再对分完组的直方图进行加噪;在对直方图进行分组时采用的是动态分组方法，对所有可能的分组中选择分组误差小的，再借助指数机制来确定新的直方图的边界点，最终得出误差小的分组直方图。最后借助拉普拉斯机制来对新的直方图进行加噪，从而得出满足差分隐私的直方图分布，最终再对处理后直方图进行发布。

鉴于以上的阐述，下面对结构优先直方图发布进行具体操作：

3.1 原始直方图的优化处理

由图1给出的数据及其对应的原始直方图分布，采用动态的分组方法，并计算动态分组后的直方图计数与原始计数间的误差，将对应误差计入二维表内。

问题1 给定计数序列D，箱的分组数K，找到所有可能分组的直方图中误差最小的，且仅含K个箱的最优直方图H′。

如图3所示为动态分组后产生的最小误差储存数据表，每个表格是所有可能分组中最小的误差计数。它的误差计数采用平方误差和的公式（4）计算的。

通过以上方法最终得出分组后的最优直方图，如图4所示。

3.2 对优化直方图的加噪处理

对图4的直方图统计数据添加拉普拉斯噪音，设隐私预算ε=1，随机选取近似最优值ε1=0.06和ε2=0.94，给图4中的三个桶分别加拉普拉斯噪音Lap1ε2（rj-ll+1）后，得到新的直方图统计数据组（（2.32，2.32，2.32），（5.28，5.28），（1.95，1.95））如图5所示。

3.3 结构优先的算法

结构优先的优点是具有较小的分组误差，敏感度低，支持长区间查询。在此部分，我们使用Di代表部分数据集Di={x1，x2，…，xn}，H（Di，j）代表数据集Di上含有j个箱的最优分组直方图。其具体的算法如下：

4 结束语

在本文中，主要阐述了基于混合机制下，凭借直方图发布技术，提出一种能支持任意范围数据集查询结构优先算法，通过指数机制在数据集中随机选取符合差分隐私的直方图边界问题。在结构优先算法及混合机制下，有效的降低了敏感度，减少了结构误差及噪音添加量，从而提高数据发布的精确性。

参考文献：

[1]Sweeney L.K-anonymity：A model for protecting privacy[J]. International Journal of Uncertainty，Fuzziness and Knowledge-Based System，2002，10（5）：557-570.

[2]Machanavajjhala A，Kifer D，Gehrke J，Venkitasubramaniam M. l-diversity：Privacy beyond" K-anonymity[J]. ACM Transactions on Knowledge Discovery from Data（TKDD），2006，1（1）：7695-2570.

[3]C. Dwork. Differential privacy[J]. In Automata，languages and programming，2006，33：10-14.

[4]Dwork C，McSherry F，Nissim K，Smith A. Calibrating noise to sensitivity in private data analysis[C]. Third Theory of Cryptography Conference，New York， USA， 2006：265-284.

[5]何贤芒，王晓阳，陈华辉，董一鸿，等.差分隐私保护参数ε的选取研究[J]. 通信学报， 2015， 12：124-130.

[6]McSherry F，Talwar K，Mechanism design via differential privacy[J]. Foundations of Computer Science， 2007，66：94-103.

[7]Xu J，Zhang Z，Xiao X，et al. Differentially private histogram publication[C]. International Conference on Data Engineering，Washington，USA， 2013，22（6）：797-822.

[8]李杨，郝志峰，温雯，等. 差分隐私保护k-means聚类方法研究[J]. 计算机科学， 2013， 40（3）：287-290.

[9]Xiao X，Wang G，Gehrke J. Differential privacy via wavelet transforms[J]. Knowledge and Data Engineering，2011，23（8）：1200-1214.

[10]Li C，Hay M，Rastogi V，et al. Optimizing linear counting queries under differential privacy[J]. Principles of Database Systems， 2010，24（6）：123-134.

[11]Roth A，Roughgarden T，Interactive privacy via the median mechanism[J]. Theory of Computing， 2010，353：765-774.

[12]Hardt M，Rothblum G N. A multiplicative weights mechanism for privacy-preserving data analysis[J]. Foundations of Computer Science， 2010，23（3）：61-70.

（责任编辑：江 龙）