基于差分隐私的隐私保护数据发布研究综述

高明珠，徐庭锐，刘洋廷，陈彦如

（1.四川大学计算机学院，成都610065；2.四川虹微技术有限公司，成都610000）

0 引言

我们在享受着推荐算法、图像识别、语音识别等智能技术发展带来的红利的同时，数据在其背后承担着推动技术不断迭代的关键角色。

互联网快速发展时期，各种信息数据正呈现爆发式增长，海量数据包含了企业的关键数据和个人的各类隐私数据，数据共享、数据发布、数据挖掘等变得越来越容易，这引起了企业和个人对隐私安全的担忧。目前，社交网络、互联网巨头、各类App 等热衷于收集海量用户数据，这些数据包含着大量的用户隐私，如医疗记录、用户喜好、位置信息、教育程度等。数据爆发式增长的同时也促进了数据分析技术的快速发展，企业通过使用这些数据分析技术进一步挖掘出高价值的用户信息。与此同时，用户的隐私面临着更加巨大的威胁。由此可见，收集并分析用户数据是一把双刃剑。由第三方来收集用户数据可能使用户的隐私数据安全得不到保障，如果收集的数据不够精准又不利于企业对用户数据进行分析，这无法帮助企业提高企业服务质量或支持企业事件决策。虽然这可以给用户提供个性化的服务，提高服务质量和精度，但是在数据收集、使用以及发布的过程中，用户隐私不可避免地暴露在外。尽管有些数据集被分享或被发布出来之前，数据集中的较敏感的标识符属性已经被删除了，具有一定背景知识的攻击者还是可以通过找到数据集之间的联系来获取用户的个人信息，用户的隐私安全也就得不到充分的保障。历史上就有很多公开数据暴露用户隐私的案例，例如AOL 和Netflix 隐私泄露事件。

现有隐私保护技术主要包括：基于k-anonymity 的隐私保护、基于l-diversity 的隐私保护、基于t-close⁃ness 的隐私保护、ε-differential privacy（差分隐私）等保护技术。其中，虽然最早提出来的k-匿名、l-多样化、t-closeness 等隐私保护方法能够在一定程度上较好地保护敏感数据，但它们均难以抵抗新出现的组合攻击、前景知识攻击等手段。而差分隐私是具有严格的数学基础和对背景知识弱依赖。

差分隐私的概念最初是由Dwork C 等人[1]在2006年提出。该方法与其他隐私保护方法不同，差分隐私最主要的贡献在于提供了个人隐私泄露的数学定义，其最主要的目的就是在大大降低隐私泄露的同时提供最大数据可用性，并且保证个人隐私泄露不超过预先设定的隐私预算ε。

1.1 差分隐私定义和相关概念

其中，ε为隐私预算，用于量化算法A输出结果或一个用户的隐私保护程度。ε的值越大，隐私泄露的风险就越大。反之，ε越小，隐私泄露的风险就越小。它适用于中心化差分隐私模型和本地化差分隐私模型。在现实中，个人用户的隐私还会有随着查询的次数增加的风险。

定义3（（ε，δ）-LDP）随机算法A 满足（（ε，δ）-LDP），当且仅当所有用户端数据对x1和x2，对于算法A所有可能的输出结果S⊆Range（A）满足不等式：

当δ=0 时，式（2）为ε-LDP。

定义4 对于任意一个函数ƒ:D→Rd，则函数的全局敏感度为：

1.2 组合原理

差分隐私机制的组合有两种类型，一种是串行组合，另一种是并行组合。

定理2 并行组合原理：M1（D1），M2（D2），M3（D3），…，Mn（Dn）分别表示输入数据集为D1，D2，D3，…，Dn的一系列满足ε-差分隐私。

1.3 两种实现机制

目前，差分隐私主要有两种实现机制：Laplace 机制[3]与指数机制[4]。

（1）拉普拉斯（Laplace）机制

Laplace 机制是向真实的查询结果中添加服从La⁃place 分布的噪声以实现满足ε的差分隐私保护，适用于数值型输出。对于非连续型数据，例如性别、种族等，拉普拉斯会输出无效的数据。对于这样的非连续型数据，我们需要借助于指数算法（Exponential algo⁃rithm）。

定义5 Laplace 机制：给定一个数据集D，设有函数ƒ:D→R，设函数的全局敏感度为Δf，等式（4）随机算法M提供ε-差分隐私。

（2）指数（Exponential）机制

对于非数字查询，差分隐私使用指数（Exponential）机制对差分结果进行随机化，并与得分函数q(D,φ)，

该函数评估输出ƒ的质量。定义得分函数取决于应用程序，并且不同的应用程序会产生不同的得分函数。

定义6 指数机制令q(D,φ)作为数据集D的得分函数，并且得分函数测量输出φ∈φ的质量，Δq表示φ的灵敏度，指数机制M满足ε-差分隐私。

2 研究现状

隐私保护数据发布是差分隐私的一个重要研究方向，差分隐私保护最早是应用在数据库领域。大数据时代下，工业和互联网数据呈现爆发式增长，如何对海量数据进行发布与分析，从海量数据中挖掘出最大价值的同时保护数据和个人隐私安全，已经成为数据库应用、数据挖掘、机器学习、数据发布等领域的研究热点。

2006 年，Dwork C[1]首次提出了差分隐私的概念和拉普拉斯机制，并在后来的文献中，进一步研究和完善差分隐私保护理论。

Xiao 等人[5]提出了Privelet 小波树算法，采用哈尔小波（Haar Wavelet）变换对原始等宽直方图进行转换，即使用Haar 变换对属性取值进行变换，然后添加一定规模的噪声到变换获得的哈尔小波系数，并满足ε差分隐私。最后使用带噪的哈尔小波系数和逆变换得到属性值对应的带噪计数值。

Xiao 等人[6]提出了一种多维差分隐私直方图发布算法DPCube，可支持多维的单位长度与较长范围计数查询。该算法首先是使用单元划分技术，对原始数据集进行分割，并给每个单元的统计信息添加适量的拉普拉斯噪声，然后使用kd-树结构对所有添加噪声后的单元进行后置处理，即重新划分，最后获得多维V-优化直方图。

Hay 等人[7]描述了一种有效的算法，用于发布网络度分布的可证明的私有估计。这是第一次将差分隐私保护应用到图结构中对结点的度进行约束。

Rastogi 等人[8]提出的FPA 是一种基于有损压缩的离散傅立叶变换方法，该方法可以较好地支持单位长度的范围计数查询，只用于一维直方图转换且查询精度低。

2012 年，Acs 对Rastogi 的FPA 提出了一种改进地具有自适应的傅立叶变换算法EFPA，通过添加打分函数和差分隐私指数机制，保证了数据发布的准确性。

Acs 等人[9]对FPA 进行改进和优化，提出了具有自适应性的傅立叶变换算法EFPA。该方法将傅立叶变换应用于直方图，并通过使用指数机制去除高频分量来对其进行压缩，通过为指数机制设计更精确地得分函数并利用实值直方图的傅立叶系数之间的内在相关性来提高FPA 的性能。该文献还提出了P-HPartition，它使用可分割的分层聚类（分区）方案来压缩直方图。

Xu 等人[10]提出两个方法，即NoiseFirst 和Struc⁃tureFirst，用于计算符合DP 的直方图，并且均支持较长范围计数查询，并且查询精度较高。它们主要的区别是噪声注入的顺序和直方图结构的计算步骤。Noise⁃First 首先向原始数据或其统计信息中添加适量的噪声，然后对含噪数据集运用规划策略。StructureFirst 则是先对原始直方图进行转换或有损压缩，并得到V-优化直方图，再向转换后的数据集添加噪声。

Fan 等人[11]提出了FAST，这是一种基于过滤和自适应采样在差分隐私下发布实时聚合统计信息的新颖框架。为了最大程度地降低总体隐私成本，FAST 根据检测到的数据动态自适应地对长时间序列进行采样。为了提高每个时间戳的数据发布准确性，FAST 预测了非采样点的数据值，并校正了采样点的噪声观测值。

Su 等人[12]提出了PrivPfC，这是一种用于发布数据以进行分类的新的差分私有方法。

Yan 等人[13]提出了一种用于大位置数据发布的自适应采样机制和隐私保护方法，并设计了一种基于比例积分微分（PID）控制器的自适应采样机制。为了确保已发布数据的隐私，他们又提出了一种启发式四叉树划分方法以及相应的隐私预算分配策略。在2020年，他们又提出了一种基于有前途的深度学习范式的集中发布大位置数据的发布间隔预测方法[14]。

3 其他研究方向

目前差分隐私保护还应用在推荐系统、社交网络等方面的数据发布。

（1）基于差分隐私保护的推荐系统。

推荐系统是使用数据挖掘、机器学习等技术，首先收集用户的历史行为数据，如购物记录、商品评论、搜索记录等个人信息，从这些数据中挖掘有价值的信息进行分析和建模，最后当用户浏览信息时实现精准地向不同用户推荐个性化的信息。个人历史行为等数据的采集过程中，用户隐私存在数据泄露的安全隐患。为了解决这一问题，差分隐私开始在推荐系统中广泛应用，但是目前的研究都是基于降低推荐精度为代价来提高隐私保护强度。因此，如何在实现隐私保护和推荐质量之间的平衡是今后的一个研究重点。

（2）基于差分隐私保护的社交网络。

互联网的飞速发展使得现实个体之间的联系加强，个人在网络中形成了不同的社交网络，而这些社交网络中包含了很多敏感信息，例如个人信息和朋友关系等，现有攻击者可以通过个体之间的联系来推测朋友关系和其他敏感信息。目前，差分隐私开始成为解决社交网络隐私保护方法之一，但是它对于数据集中记录之间的关联关系保护程度较低。因此，基于差分隐私设计更好地保护关联数据间的敏感信息成为今后研究的一个重要方向。

4 结语

差分隐私保护是一种通用且具有坚实理论基础的隐私保护方法，它解决了很多传统加密等方法无法解决的问题，可以防止基于背景知识的攻击，目前其引起了众多学者的研究兴趣，应用领域也越来越广泛。

本文简要介绍了差分隐私保护在数据发布领域的研究历程和其他研究点，随着机器学习等技术的发展，差分隐私保护将会在更多领域保护用户个人隐私数据安全。