差分隐私

差分隐私（英语：differential privacy）是密码学中的一种手段，旨在提供一种当从统计数据库查询时，最大化数据查询的准确性，同时最大限度减少识别其记录的机会。1

正式的定义和应用示例假设 是一个正实数，A是一个随机算法，它将数据集作为输入（表示信任方拥有的数据）。imA表示A的映射。对于在非单个元素（即，一个人的数据）的所有数据集D1和D2以及imA的所有子集S，算法A是 -差分隐私，其中概率取决于算法的随机性。2

例如, 假设我们有一个医疗记录数据库 D1 在那里每条记录是一对 (名字, x), 其中 X 是一个布尔值表示一个人是否痪有糖尿病。例如:

|| ||

现在假设一个恶意用户 (通常被称为攻击者) 想知道Chandler是否有糖尿病。假设他知道Chandler在数据库的哪一行。现在攻击者只能使用特定形式的查询Qi返回数据库中前i行中第一列 X 的部分总和。攻击者为了获取Chandler是否有糖尿病的信息。只需要执行两个查询 Q5（D1）和Q4（D1），分别计算前五行和前四行的总和，然后计算两个查询的差别。在本例中Q5（D1）=3，Q4（D1）=2，差是1。攻击者在知道Chandler在第5行的情况下，就会知道他的糖尿病状况是1（有糖尿病）。这个例子显示了即使在没有明确查询特定个人信息的情况下, 个人信息如何被泄露。

继续这个例子，如果我们用（Chandler，0）代替（Chandler，1）构造D2，那么这个恶意攻击者将能够通过计算每个数据集的Q5-Q4来区分D2和D1。 如果攻击者被要求通过 -差分隐私算法接收Qi值，对于足够小的 ，则他将不能区分这两个数据集。

灵敏度d为正整数，D为一个数据集的集合， 为函数。 代表的函数的灵敏度由下式定义:

其中最大值是D中的所有对数据集对应的D1和D2中最差别最大的一对， 表示曼哈顿距离。

在上面医学数据库的例子中，如果我们认为f是函数Qi，那么函数的灵敏度就是1，因为改变数据库中的任何一个条目都会导致函数的输出改变0或 1。

有一些技术（如下所述），我们可以使用这些技术建立低灵敏度差分隐私算法。3

准确性与隐私的均衡通过差分隐私加扰的结果，要在统计数据的准确性和隐私参数之间有权衡.这种均衡也必须考虑到ε参数乘以查询数量(包括预计的查询数量)。

差分隐私的其他概念对很多应用而言, 差分隐私被认为过于严格, 因此建议了许多被弱化的版本。这些包括 (ε, δ)-差分隐私, 随机差分隐私, 以及特定标度的隐私。

差分隐私机制由于差分隐私是一个概率概念，任何差分隐私机制必然是随机的。 下面描述的拉普拉斯机制就依赖于我们对结果添加的受控噪声。 其他的像指数机制和后验抽样依赖于问题的分布族。

拉普拉斯机制许多差分隐私方法以添加受控噪音实现降低查询结果的灵敏度。拉普拉斯机制增加了拉普拉斯噪声（即符合拉普拉斯分布的噪声，其可以用概率密度函数 表示，其均值为0和标准偏差是 ）。 现在在我们的例子中，我们将的输出函数定义为实值函数（称为 的输出副本）为 ，其中 和f是我们计划在数据库上执行的原始实值查询/函数。现在很明显， 可以被认为是一个连续的随机变量，其中 ，最多为 .我们可以认为是隐私因子 .

因此， 遵循不同的隐私机制（从上面的定义可以看出）。 如果我们试图在我们的糖尿病例子中使用这个概念，那么从上面推导出的事实可以看出，为了让 作为 -差分隐私算法，我们需要 。 虽然我们在这里使用了拉普拉斯噪声，但也可以使用其他形式的噪声，例如高斯噪声，但这样可能需要略微放宽差分隐私的定义。

设想一个受信任的机构持有涉及众多人的敏感个人信息（例如医疗记录、观看记录或电子邮件统计）的数据集，但想提供一个全局性的统计数据。这样的系统被称为统计数据库。但是，提供有关数据的综合性统计也可能揭示一些涉及个人的信息。事实上，当研究人员链接两个或多个分别无害化处理的数据库来识别个人信息时，各种公共记录匿名化的特殊方法都失效了。而差分隐私就是为防护这类统计数据库脱匿名技术而形成的一个隐私框架。

Netflix奖举例来说，2006年10月，Netflix提出一笔100万美元的奖金，作为将其推荐系统改进达10%的奖励。Netflix还发布了一个训练数据集供竞选开发者训练其系统。在发布此数据集时，Netflix提供了免责声明：为保护客户的隐私，可识别单个客户的所有个人信息已被删除，并且所有客户ID已用随机分配的ID [sic]替代。

Netflix不是网络上唯一的电影评级门户网站，其他网站还有很多，包括IMDb。个人可以在IMDb上注册和评价电影，并且可以选择匿名化自己的详情。德克萨斯州大学奥斯汀分校的研究员Arvind Narayanan和Vitaly Shmatikov将Netflix匿名化的训练数据库与IMDb数据库（根据用户评价日期）相连，能够部分反匿名化Netflix的训练数据库，危及到部分用户的身份信息。

医疗数据库事件卡内基梅隆大学的Latanya Sweeney的将匿名化的GIC数据库（包含每位患者的出生日期、性别和邮政编码）与选民登记记录相连后，可以找出马萨诸塞州州长的病历。

元数据与流动数据库MIT的De Montjoye等人引入了单一性（意为独特性）概念，显示出4个时空点、近似地点和时间就足以唯一性识别一个150万人流动数据库中的95%用户。该研究进一步表明，即使数据集的分辨率较低，这些约束仍然存在，即粗糙或模糊的流动数据集和元数据也只提供很少的匿名性。

现实世界中对差分隐私的采用至今为止，比较知名的采用差分隐私的应用如下：

美国人口普查局，展示通勤模式。

Google的RAPPOR，用于遥测，例如了解统计劫持用户设置的恶意软件。

Google，分享历史流量统计信息。

2016年6月13日，苹果公司宣布其在iOS10中使用差异隐私，以改进其虚拟助理和建议技术，

在数据挖掘模型中使用差异隐私的实际表现已有一些初步研究。

本词条内容贡献者为:

何星 - 副教授 - 上海交通大学