差分隐私简介

要点

• 差分隐私可以通过向聚合查询结果添加随机化"噪声"来实现，以保护个人的条目，而不会显著改变查询结果。
• 差分隐私算法保证攻击者能获取的个人数据几乎和他们从没有这个人记录的数据集中能获取的相差无几。
• 最简单的算法之一是拉普拉斯机制，可以对聚合查询的结果进行后期处理。
• 苹果和谷歌分别在 iOS 和 Chrome 中使用差分隐私技术。差分隐私算法也已经在隐私保护分析产品中实现，例如由 Privitar 开发的那些产品。
• 差分隐私算法仍然是一个活跃的研究领域。

去年，差分隐私从研究论文一跃成为科技新闻头条，在 WWDC 主题演讲中，苹果工程副总裁 Craig Federighi 宣布苹果使用这一概念来保护 iOS 用户隐私。

这是一个普遍趋势的最新实例：用户和工程师认识到在软件中保护隐私的重要性。备受瞩目的隐私侵犯事件（如 Uber 的"上帝模式"）充分地说明了公司员工可以轻易滥用从其客户收集的敏感数据。

被数字化记录的敏感数据的数量正在迅速增加。在支付、交通、导航、购物和健康方面，人们现在比以往更多地依靠数字服务。这种新的数据收集产生了越来越多的方式来侵犯隐私。

如果把数据提供给合适的数据科学家和研究人员，这些数据也能创造令人兴奋的机会——改善交通网络、减少犯罪、治愈疾病。保护数据集中的个人隐私，和对数据加以分析利用来创造更美好的世界，二者之间存在着一种自然的紧张关系。

差分隐私算法是一个有前途的技术解决方案，可以缓解这种紧张，允许分析人员执行良性的聚合分析，同时保证个人隐私得到切实的保护。

这个发展中的技术领域在任何试图分析敏感数据的系统中都值得考虑。虽然差分隐私保证的构想仅仅有十年时间，但它在学术界和工业界已经取得了成功。研究人员正在快速发明和改进差分隐私算法，其中一些已经在苹果的 iOS 和谷歌的 Chrome 中采用。

本文讨论了形成当前的差分隐私的历史因素，以及差分隐私的定义和差分隐私算法的示例。然后也讨论了近来一些受到关注的差分隐私算法，这些算法来自谷歌、苹果和其他公司。

背景

数据分析中的隐私保护技术已有数十年的历史，差分隐私算法是这一领域的最新技术。两个早期概念直接影响了差分隐私：

1. 最小查询集大小
2. Dalenius 的统计披露的定义。

因为它们为差分隐私提供了有用的背景，我们将首先解释这些概念。

最小查询集大小 第一个概念是最小查询集大小，像差分隐私算法一样，旨在确保聚合查询的安全性。聚合查询是在数据集中的记录子集上计算返回值的查询，例如计数、平均值或总和。将聚合查询视为以"SELECT SUM"、"SELECT COUNT"或"SELECT AVG"开头的 SQL 查询可能会有所帮助。其他类型的聚合查询包括列联表和直方图。

最小查询集大小是一种约束，旨在确保聚合查询不会泄露有关个人的信息。给定某个配置的阈值量 T，其确保每个聚合查询在至少有 T 个记录的数据集上进行。最小查询集大小会阻止针对少于 T 个记录的聚合查询。例如，如果 T = 2，它将阻止以下查询：

“SELECT AVG(salary) WHERE name = ‘Troy Brown’;”.

因为这个查询会对一个记录进行平均（我们假设只有一个 Troy Brown）。

使用最小查询集大小可以防止某些攻击，但不能保证隐私，实际上熟练的攻击者能够绕开这一防护。例如，攻击者可以用以下方式完成上述攻击：

 
“SELECT SUM(salary);”.
 
“SELECT SUM(salary) WHERE name != ‘Troy Brown’;”.

甚至，如果我们知道 Troy Brown 的年龄（45）和位置（WR）可以唯一地标识他：

 
“SELECT SUM(salary) WHERE position = ‘WR’;”.
 
“SELECT SUM(salary) WHERE position = ‘WR’ AND age != 45;

这种攻击被称为跟踪者攻击，并且它们不能被最小查询集大小的限制所阻止。由于这些攻击，最小查询集大小被认为不足以保护查询系统（见 Denning 的作品）。需要更好的，有保证的手段以确保隐私。

Dalenius 的统计披露定义

1977 年，统计学家 Tore Dalenius提出了一个严格的数据隐私定义：攻击者在使用敏感数据集之前，对他们不认识的人应该一无所知。虽然这种保证失败了（我们将看到是为什么），但它对理解为什么差分隐私被构造成现在的样子是很重要的。

Dalenius 的定义失败了，因为在 2006 年，计算机科学家 Cynthia Dwork证明，这种保证是不可能得到的——换句话说，任何对敏感数据的访问都将违反这一隐私定义。她发现的问题是，某些类型的背景信息总会导致关于个人的新结论。下面的轶事可以说明她的证明：我知道爱丽丝比立陶宛女人平均身高高两英寸。然后我使用一个立陶宛妇女的数据集，计算我以前并不知道的平均身高。即使Alice 不在数据集中，我现在也知道她的确切身高。无法证明的是，在数据集的使用中，所有类型的背景信息都可能导致关于个人的新结论。

Dwork，在证明上述结论之后，提出了一个新的定义：差分隐私。

什么是差分隐私？

差分隐私保证以下内容：攻击者能获取的个人数据几乎和他们从没有这个人记录的数据集中能获取的相差无几。虽然比 Dalenius 对隐私的定义要弱，但是保证是足够强大的，因为它符合现实世界的动机——个人没有动机不参与数据集，因为不论自己在不在数据集中，该数据集的分析者都将得出关于该个人的相同的结论。由于其敏感的个人信息与系统的输出几乎完全不相关，因此用户可以确信处理其数据的组织不会侵犯他们的隐私。

分析者几乎"无法获得个人信息"意味着他们被限制在关于任何个人的看法的微小变化中。（在这里和下面，"变化"是指使用数据集和使用相同的数据集减去任何一个人的记录之间的变化。）这种变化的范围由参数ε控制，对任何可能的结果，该参数设置了变化的边界。ε的低值，例如 0.1，意味着关于任何个人的看法的改变非常少。 ε的高值，例如 50，意味着关于个人的看法的变化更大。正式的定义如下。

当且仅当以下情况下，算法 A 是ε- 差分隐私的：

Pr[A(D) = x] ≤ e^ϵ * Pr[A(D’) = x]

对于所有的 x 和对于所有的数据集对 D 和 D’，缺少任何一条记录的 D 被称为 D’，比如缺少某个人的数据。符号 e 指的是数学常数。注意，这个定义只对随机算法有意义。给出确定性输出的算法都不适合差分隐私。

差分隐私保证的主要吸引力在于其对分析者所能获取的个人信息量的限制。此外，它具有以下有用的属性：

• 可组合性：如果用保证程度分别为ε1 和ε2 的差分隐私来回应两个查询，则该对查询的差分隐私性等同于保证程度（ε1+ε2）。回想一下，较高的ε值意味着较弱的保证。
• 针对任意背景信息的强度：这种保证不以任何方式依赖于攻击者知道的背景信息。该属性是差分隐私强于早期的隐私保证（ k-anonymity ）的主要原因之一。
• 后期处理的安全性：对于差分隐私的结果，没有限制可以做什么——无论它与什么结合或者怎么被转换，它仍然是差分隐私的。

这种保证如何在软件中实现？差分隐私算法是在算法内的关键点处添加噪声的随机算法。最简单的算法之一是拉普拉斯机制，该机制可以后期处理聚合查询（例如，计数、总和和均值）的结果以使它们差分私有。下面是用于计数查询的 Laplace 机制的 Java 代码示例：

import org.apache.commons.math3.distribution.LaplaceDistribution;

double laplaceMechanismCount(long realCountResult, double epsilon) {

LaplaceDistribution ld = new LaplaceDistribution(0, 1 / epsilon);

double noise = ld.sample();

return realCountResult + noise;

}

该函数的关键部分是

1. 实例化以 0 为中心并按 1 /ε缩放的拉普拉斯概率分布（见图 1）。我们使用 Apache Commons 的实现"LaplaceDistribution"，它的构造函数包含两个参数：分布的均值和分布的规模。请注意，较小的ε（更多隐私）导致更大的规模，从而更宽的分布和更多的噪声。
2. 从该分布中抽取一个随机样本。此 sample（）函数采用 0 和 1 之间的随机数，并将拉普拉斯分布的逆累积分布函数（CDF）应用于此数字。该过程产生随机数，随机数具有任何特定值的可能性与分布相匹配。作为一种替代方式来考虑它，如果这个采样函数被调用一百万次以获得一百万个样本，这些样本的直方图形状将非常符合拉普拉斯分布的形状。
3. 通过添加来自步骤 2 的随机值来扰乱实际值。

从攻击者 Eve 的视角让我们来考虑一下为什么这个算法是差分私有的。比如说数据集是关于心理健康的数据，Eve 设想了跟踪者攻击（见上文），这将揭示她的目标，鲍勃，是否接受过酗酒的咨询。如果查询的结果是 48，Eve 就知道 Bob 接受过咨询；如果是 47，Eve 知道结论相反。

无论答案是 47 还是 48，拉普拉斯机制将返回加了噪声的在 47 或 48 附近的结果。它可能返回 49、46 或者甚至是更小的概率 44 或 51（对于直方图，见图 2）。在实际中，Eva 不可能非常确定是否真实的答案就是 47 或 48，因此，这并不足以影响她对 Bob 是否在进行酗酒咨询的看法。

图 1：拉普拉斯分布以 0 为中心，刻度为 1。图中是分布的概率密度函数（PDF）——y 轴是变量取自 x 轴上的值的相对可能性。

图 2：两个场景中的计数查询的可能结果，两种场景分别是真实答案是 47 和 48。少量输出将不足以区分它们来自哪个分布。Epsilon 值设为 0.67。

此时你可能已经观察到，Eva 可以通过重复查询多次，看答案是否集中在 47 或 48，来排除噪音。为了防止这种策略，差分隐私系统必须有一个"隐私预算"，就是对每个查询中使用的ε的和指定上限。这个上限能够起作用是因为上面描述的差分隐私的可组合性。他们可能会发起一些相对低噪声的查询，或者数百个高噪声查询，但无论如何，他们都不能自信地认定真正的答案是 47 还是 48。

最后，请注意，用于计数的拉普拉斯机制仅仅是一个简单的差分隐私算法。拉普拉斯机制可以扩展到求和以及其他聚合查询。此外，存在着一些从根本上不同的算法，它们已经被证明可以保证差分隐私。几个值得探索的是私人乘法权重算法，乘法权重指数机制和 DualQuery 。

差分隐私实践

在 2016 年 6 月，苹果宣布将开始使用差分隐私算法从iPhone 收集行为统计数据。这项公告，除了导致对差分隐私的兴趣的猛增，还表明差分隐私可以帮助主要组织从一些数据中获得新的价值，由于担心隐私问题，他们以前并没有接触这些数据。

虽然苹果公司迄今为止没有公布任何细节，但iPhone 中使用的算法似乎与谷歌的RAPPOR 项目类似。谷歌在Chrome 中实现了一项功能，使用差分隐私随机响应算法从Chrome 浏览器收集行为统计数据。

在随机响应中，在提交给收集者之前，随机噪声被添加到统计数据中。例如，如果实际统计数据为0，浏览器将以某种概率将0 替换为随机选择的0 或1。每个用户在很大程度上可以否定其软件报告的价值，因为它可能是随机值。但从整体上来说，信号会在随机噪声中显现出来，收集统计数据的组织（如谷歌或苹果）可以准确地观察到趋势。

有趣的是，据我们所知，谷歌和苹果都没有揭示在他们的差分隐私保证中用到的ε的值。我们需要这个值来理解该保证所提供的保护。如果他们使用足够高的ε值，分析者仍然可以很自信地获得用户的敏感事实。对于有意义的隐私保护，需要低的ε值。

差分隐私算法也已经在隐私保护分析产品中实现，例如由我的雇主 Privitar 开发的那些产品。这些产品允许使用有价值的、敏感的数据的公司将差分隐私算法纳入其数据架构中，为其用户提供隐私保证，同时仍能对数据进行有意义的分析。

展望未来

对差分隐私来说，工程界和研究界都有其未来的道路。对于工程师，任务是接受差分隐私的培训，并确保在适当的地方使用差分隐私来保护用户隐私。对于研究人员，任务是寻找更多和更好的差分隐私算法，改进我们可以启用隐私保护的数据分析工具集。

我们都从隐私保证的建立和数据分析的成功中获益。由于这两个原因，我们期待更多的组织拥抱差分隐私。

关于作者

Charlie Cabot是 Privitar 的高级数据科学家，Privitar 是一家数据隐私初创公司，构建高性能的数据匿名化软件，包括扰动和泛化算法以及差分隐私机制，以促进敏感数据集的安全使用。Charlie 关注可证明的隐私保证以及匿名化对分析和数据科学的统计影响。以前，Charlie 在网络安全领域工作，他设计了机器学习驱动的恶意软件检测方法，建立了计算机网络上的网络攻击模型。

查看英文原文： An Introduction to Differential Privacy

感谢王纯超对本文的审校。

给InfoQ 中文站投稿或者参与内容翻译工作，请邮件至 editors@cn.infoq.com 。也欢迎大家通过新浪微博（ @InfoQ ， @丁晓昀），微信（微信号： InfoQChina ）关注我们。