差分隐私合成数据集发布研究

安徽理工大学计算机学院 刘文龙 方贤进



差分隐私合成数据集发布研究

安徽理工大学计算机学院 刘文龙 方贤进

【摘要】差分隐私保护模型框架中，合成数据集发布是差分隐私保护的一个重要应用，也是一个重要研究热点。本文主要研究和分析了差分隐私保护在合成数据集发布中的应用，重点介绍该领域的研究进展，并展望未来的研究方向。

【关键词】差分隐私；数据合成；数据发布

差分隐私保护技术是2006年由来自微软研究院的德沃柯(Dwork)等人提出的针对统计数据库的保护模型。差分隐私保护模型作为一个严格定义的、可证明的隐私保护模型，近年来受到各学术界越来越多的重视和研究。

合成数据集的发布是差分隐私保护研究中的难点。研究主要集中于对数据集统计特征的发布机制，如直方图发布。由于这些发布机制仅能描述数据集的一部分特征，因此在应用场景上存在很大的局限性。现实的需求促进了研究者对净化数据集发布的研究。

1　隐私保护概述

最早出现的k-匿名隐私保护技术要求对数据表中的每一条记录不能区分于其它k-1条记录，即对数据中的所有元组进行泛化处理，使得其不能再与其他任何人相对应，如表1数据匿名化前后对比可以看出泛化后的数据不再像原数据一样准确，泛化对数据进行了更为概括的描述，并保留了有用信息，从而使得数据依然具有可用性。

k-匿名和l-多样技术不足之处都在于没有严格定义攻击模型，没有对攻击者的背景知识作出定量化定义。这样使得从k-匿名刚开始的工作就陷入一个“新隐私保护模型不断被提出但又不断被攻破”的循环之中。直到Dwork等人提出差分隐私保护模型，类似问题才得到有效解决。

表1　数据匿名化前后对比

2　差分隐私

2.1差分隐私定义

差分隐私严格定义了攻击者的背景知识：除了某一条记录，假定攻击者知晓原数据集中的所有信息，这样的攻击者几乎是最强大的，而差分隐私依然能够在这种情况下有效保护个人隐私信息。差分隐私保护模型拥有严谨的统计学模型，方便了数学工具的使用以及定量分析和证明。正是由于差分隐私的诸多优势，使其一出现便迅速取代了之前的隐私模型，成为隐私研究的核心。

2.2差分隐私统计学模型

差分隐私保护的数学表达为：对于任意一对相邻数据库D1和D1，任意一个可能的带噪中间件S，一个提供ε-差分隐私保护的算法A 必须满足：

也就是说，由于对于输入D1和D2，算法A 输出S 的概率是相近的，所有即使攻击者已经知道了原数据中的绝大部分元组，他依然无法对剩余的元组做出准确的推断。对于任意一个可能的带噪中间件S，Pr[A(D1)=S] 和Pr[A(D2)=S] 的比率总是被约束在[exp(-ε)，exp(ε)] 之间，即：

差分隐私保护模型的参数描述了上述两个概率分布的相似性ε越小，概率的相似性越高，也就越难区分D1和D2，从而达到更高程度的隐私保护。

2.3差分隐私核心算法

德沃柯等人最先提出了差分隐私的通用随机算法：拉普拉斯机制，其核心思想是通过向中间件加入拉普拉斯噪音来满足定义一中的约束条件。对于一个数据查询F，拉普拉斯机制首先生成真实结果F (D) 作为中间件，然后通过发布带噪结果F(D)+η 来回答查询，其中噪音η服从拉普拉斯分布。

德沃柯等人证明了当λ≥ ΔF/ε时，拉普拉斯机制就能满足ε- 差分隐私。

McSherry 和Tulwar所提出的指数机制也是差分隐私的经典通用算法。该机制与拉普拉斯机制最大的不同在于，后者适用于当数据查询的返回值为实数值的场合，而前者则适用于数据查询的范围值域为离散值域的场合。现有的许多差分隐私算法在很大程度上都可以认为是拉普拉斯机制与指数机制的组合与应用。

3　差分隐私数据合成应用

最早的数据合成算法的思路是首先从数据库生成列联表，然后通过拉普拉斯机制随机加噪生成带噪列联表，最后还原出一个带噪的合成数据库。但是，这一思路在面向高维数据时会产生严重的问题：(1)列联表的大小是数据维度的指数倍，这导致高维带噪列联表很难被计算出来；(2)由于列联表的大小远大于数据库，因此信息在列联表中的分布极其稀疏，在加入噪音后，列联表的信噪比将变得非常低，使得其无法反映原数据库的有用信息。PrivBayes算法通过建立一个贝叶斯网络找到一系列低维边界图来较好地逼近高维列联表，然后将所有计算和加噪都在低维空间中进行，从而有效解决高维列联表带来的计算复杂度高和信噪比低的问题。

4　结束语

正是由于差分隐私的诸多优势，使得其一出现便很快取代了之前的隐私保护模型，成为隐私研究的核心，并在计数查询、数据挖掘和机器学习等多个领域得到了广泛应用。然而，当前仍有很多需要深入开展研究工作，如攻击模型的进一步优化、隐私保护与数据可用性的权衡等。

参考文献

[1]陈德诚,丘平珠,唐炳莉.广西气象数据集设计与制作[J].气象研究与应用,2007(04).

[2]赵凤英,王崇骏,陈世福.用于不均衡数据集的挖掘方法[J].计算机科学,2007(09).

[3]孟小峰,张啸剑.大数据隐私管理[J].计算机研究与发展,2015(02).