1997 年，马萨诸塞州开始向医学研究人员提供州雇员的健康记录时，政府删除了患者的姓名、地址和社会安全号码。当时的州长威廉·韦尔德向公众保证，不可能在记录中识别出个别患者。
几天之内，麻省理工学院的一名研究生寄给韦尔德办公室一个信封。里面装着州长的健康记录。
关于支持科学新闻
如果您喜欢这篇文章，请考虑订阅以支持我们屡获殊荣的新闻报道。 订阅。 通过购买订阅，您将有助于确保有关塑造我们当今世界的发现和想法的具有影响力的故事的未来。
尽管该州删除了所有明显的标识符，但它保留了每个患者的出生日期、性别和邮政编码。通过将此信息与选民登记记录进行交叉引用，拉坦娅·斯威尼（Latanya Sweeney）能够精确定位韦尔德的记录。
斯威尼的工作以及过去 15 年中其他引人注目的隐私泄露事件，引发了人们对所谓匿名信息的安全性的质疑。
“我们已经了解到，人类关于什么是隐私的直觉并不是特别好，”位于加利福尼亚州山景城的微软研究院硅谷分部的弗兰克·麦克雪里（Frank McSherry）说，“计算机在从一个天真的人可能认为无害的东西中提取个人数据方面越来越复杂。”
随着人们对这些隐私问题的认识不断提高，许多组织已经收紧了他们的敏感数据，不确定在不危及个人隐私的情况下，他们可以发布什么（如果有的话）。但是，这种对隐私的关注也付出了代价，使研究人员无法获得大量潜在的宝贵数据。
像马萨诸塞州发布的那样的医疗记录，可以帮助揭示哪些基因会增加患阿尔茨海默氏症等疾病的风险，如何减少医院的医疗错误，或哪种治疗方法对乳腺癌最有效。政府持有的来自人口普查局调查和纳税申报表的信息可以帮助经济学家制定最能促进收入平等或经济增长的政策。而来自 Facebook 和 Twitter 等社交媒体网站的数据可以为社会学家提供前所未有地了解普通人如何生活的机会。
问题是：我们如何在不泄露私人信息的情况下获取这些数据？经过十年的发展，现在已经开始提供真正的解决方案。
这种方法被称为“差分隐私”，它允许在发布数据的同时满足高标准的隐私保护要求。差分隐私数据发布算法允许研究人员询问有关敏感信息数据库的几乎任何问题，并提供经过“模糊处理”的答案，以便它们实际上不会泄露任何个人数据——甚至不会泄露个人是否在数据库中。
微软研究院硅谷分部的辛西娅·德沃克（Cynthia Dwork）说：“我们的想法是，如果您允许使用您的数据，您就不会承担额外的风险。”德沃克在 2005 年与麦克雪里、以色列本古里安大学的科比·尼西姆（Kobbi Nissim）和宾夕法尼亚州立大学的亚当·史密斯（Adam Smith）一起提出了差分隐私的概念。
卡内基梅隆大学的阿夫里姆·布鲁姆（Avrim Blum）喜欢说，差分隐私保留了“似是而非的推诿”。他说：“如果我想假装我的个人信息与实际情况不同，我可以这样做。差分隐私机制的输出几乎完全相同，无论它是否包含真实的我和假装的我，所以我可以合理地否认任何我想否认的事情。”
这种隐私标准可能看起来高得无法实现——而且事实上，没有有用的差分隐私算法能够给出完全相同的信息，无论它是否包含真实的您或假装的您。但是，如果我们允许算法在两种情况下给出几乎完全相同的信息，那么确实存在有用且高效的算法。这个“几乎”是一个精确校准的参数，是对隐私的可衡量量化。个人或社会机构可以决定此参数的哪个值代表可接受的隐私损失，然后可以选择差分隐私算法来保证隐私损失小于所选参数。
隐私专家已经开发出各种专门的差分隐私算法来处理不同类型的数据和有关数据的问题。虽然这项工作的很大一部分是技术性的，非专业人士难以理解，但研究人员正在开始构建标准化的计算机语言，这将允许非专业人士通过编写简单的计算机程序，以差分隐私的方式发布敏感数据。
已经有一个实际应用使用了差分隐私：人口普查局的一个名为OnTheMap的项目，该项目允许研究人员访问该机构的数据。此外，差分隐私研究人员还收到了来自 Facebook 和联邦资助的加利福尼亚大学圣地亚哥分校的 iDASH 中心 的初步询问，该中心的主要任务是找到研究人员共享生物医学数据而不损害隐私的方法。
宾夕法尼亚大学的计算机科学家亚伦·罗斯（Aaron Roth）说：“差分隐私是一种有前途且令人兴奋的技术。”
大海捞针
对于隐私问题，一个更简单的解决方案似乎是只发布“汇总”信息——关于大量人群的陈述。但即使是这种方法也容易出现隐私泄露。
假设您想确定我是否患有糖尿病，并且您知道我属于一个健康数据库。您可以通过简单地减去两个汇总级别问题的答案来找到答案：“数据库中有多少人患有糖尿病？”以及“数据库中不叫埃丽卡·克莱里奇的人有多少患有糖尿病？”
显然，这两个问题在组合时会侵犯我的隐私。但并不总是容易发现哪些问题组合会构成隐私泄露。从总体上来说，发现此类组合是计算机科学家所谓的“NP-hard”问题，这意味着可能没有高效的计算机算法可以捕获所有此类攻击。
当攻击者可以访问有关数据库中个人的外部信息时，从汇总统计数据中提取私人信息会变得更加容易。
2008 年，一个研究小组展示了从全基因组关联研究中发布汇总信息的危险，全基因组关联研究是揭示疾病与特定基因之间联系的主要研究工具之一。这些研究通常涉及对 100 到 1,000 名患有相同疾病的患者的测试组进行基因组测序，然后计算该组中大约 100,000 个不同突变的平均频率。如果一个突变在该组中的出现频率远高于一般人群，则该突变被标记为可能导致或促成该疾病的原因。
由当时的加州大学洛杉矶分校研究生尼尔斯·霍默（Nils Homer）领导的研究小组表明，在许多情况下，如果你知道一个人的基因组，你就可以在合理怀疑的情况下弄清楚这个人是否参加了特定的全基因组测试组。在霍默的论文发表后，美国国立卫生研究院推翻了一项政策，该政策是当年早些时候制定的，要求公开张贴所有美国国立卫生研究院资助的全基因组关联研究的汇总数据。
也许更令人惊讶的是，研究人员在 2011 年表明，有可能从亚马逊的产品推荐系统中收集到有关购买的个人信息，该系统以“购买此商品的客户也购买了 A、B 和 C”的形式进行汇总级别陈述。通过观察推荐如何随时间变化，并将它们与客户对购买商品的公开评论进行交叉引用，研究人员在某些情况下能够推断出特定客户在特定日期购买了特定商品——甚至在客户发布该商品的评论之前。
在所有这些案例中，所采取的隐私措施似乎是足够的，直到它们被违反。但是，即使隐私失败的清单不断扩大，一种不同的数据发布方法也正在形成，这种方法带有先验的隐私保证。为了实现这个目标，研究人员已经回归基本：他们问，保护隐私到底意味着什么？
双重世界隐私
如果研究人员研究一个健康数据库并发现吸烟与某种形式的癌症之间存在联系，差分隐私不会保护公众吸烟者被贴上癌症风险升高的标签。但是，如果一个人的吸烟是隐藏在数据库中的秘密，差分隐私将保护该秘密。
麦克雪里说：“‘差分’指的是两个世界之间的差异——一个世界允许您的敏感数据包含在数据库中，另一个世界不允许。”这两个世界不能完全相同，但它们可以足够接近，以至于它们实际上是无法区分的。他说，这就是差分隐私的目标。
差分隐私侧重于信息发布算法，这些算法接收有关数据库的问题并给出答案——不是精确的答案，而是以规定的方式随机更改过的答案。当对一对仅在一个个体（X 人）方面不同的数据库（A 和 B）提出相同的问题时，算法应给出基本相同的答案。
更准确地说，对于算法可能给出的任何答案，对于两个数据库，获得该答案的概率应该几乎完全相同；也就是说，这两个概率的比率应受某个接近 1 的数字 R 限制。R 越接近 1，攻击者就越难弄清楚他获得的是关于数据库 A 还是数据库 B 的信息，并且 X 人将得到更好的保护。毕竟，如果攻击者甚至无法弄清楚他获得的信息是否包含 X 人的数据，他当然就无法弄清楚 X 人的数据是什么。
（差分隐私研究人员通常更喜欢用 R 的对数来表示，他们将其表示为 Ɛ。此参数用于量化执行算法时泄露了多少隐私：Ɛ 越接近 0，该算法在保护隐私方面就越好。）
为了了解如何构建差分隐私算法，让我们来看一个最简单的此类算法。它侧重于提问者仅限于“计数查询”的情况；例如：“数据库中有多少人具有属性 P？”
假设一个此类问题的真实答案是 157。差分隐私算法将对真实答案“添加噪声”；也就是说，在返回答案之前，它将根据预定的概率集随机地从 157 中加上或减去某个数字。因此，它可能会返回 157，但也可能会返回 153、159 甚至 292。提出问题的人知道算法正在使用哪个概率分布，因此她大致了解真实答案可能被扭曲了多少（否则算法给出的答案对她来说将完全无用）。但是，她不知道算法实际添加了哪个随机数。
必须谨慎选择正在使用的特定概率分布。为了了解哪种分布将确保差分隐私，假设一个窥探的提问者试图找出我是否在数据库中。他问：“数据库中有多少人叫 Erica Klarreich？”假设他得到的答案是 100。由于 Erica Klarreich 是如此罕见的名字，提问者知道真实答案几乎肯定是 0 或 1，留下两种可能性
（a）答案是 0，算法添加了 100 的噪声；或
（b）答案是 1，算法添加了 99 的噪声。
为了保护我的隐私，选择 99 或 100 的概率必须几乎完全相同；这样，提问者将无法有意义地区分这两种可能性。更准确地说，这两个概率的比率应最多为预先选择的隐私参数 R。对于 99 和 100 以及任何一对连续数字，都应如此；这样，无论添加什么噪声值，提问者都无法弄清楚真实答案。
实现此目标的概率分布是拉普拉斯分布，它在 0 处达到峰值，并逐渐向两侧递减。拉普拉斯分布恰好具有我们需要的属性：存在某个数字 R （称为分布的宽度），使得对于任何两个连续的数字，它们的概率的比率是 R。
每个可能的宽度都有一个拉普拉斯分布；因此，我们可以调整宽度以获得我们想要的精确隐私度的拉普拉斯分布。如果我们需要高度的隐私，相应的分布将相对较宽且平坦；远离 0 的数字将几乎与接近 0 的数字一样可能，从而确保数据被足够的噪声模糊，以保护隐私。
隐私和效用之间不可避免地存在张力。你想要的隐私越多，你必须添加的拉普拉斯噪声就越多，并且对研究数据库的研究人员来说，答案的效用就越低。对于拉普拉斯分布，添加的噪声的预期量是 Ɛ 的倒数；因此，例如，如果你选择的隐私参数为 0.01，你可以预期算法的答案将被大约 100 的噪声模糊。
数据集越大，给定量的模糊对效用的影响就越小：在数百万的答案中添加 100 的噪声会比在数百的答案中添加 100 的噪声模糊得多。Dwork 说，对于互联网规模的数据集（即数亿个条目），该算法已经为许多实际设置提供了足够好的准确性。
拉普拉斯噪声算法只是差分隐私的开端。研究人员已经提出了许多更复杂的差分隐私算法，其中许多算法在某些情况下比拉普拉斯噪声算法具有更好的效用-隐私权衡。
Dwork 说：“人们不断找到更好的做事方法，并且还有很大的改进空间。”她说，当涉及到比互联网规模更适中的数据集时，“开始有针对许多任务的算法出现。”
使用差分隐私算法，无需仔细分析问题以确定它是否试图侵犯个人的隐私；该保护会自动构建到算法的功能中。由于窥探问题通常归结为与特定人员相关的小数字，而非窥探问题检查大群体的总体行为，因此，使有关个人的答案变得毫无意义的相同添加噪声量将仅对许多合法的研究问题的答案产生微小的影响。
使用差分隐私，困扰其他数据发布的各种问题（例如，攻击者将数据与外部信息交叉引用）消失了。该方法的数学隐私保证不取决于攻击者是否拥有有限的外部信息或资源。
McSherry 说：“差分隐私假设对手是无所不能的。即使攻击者在 100 年后带着 100 年的思想、信息和计算机技术回来，他们仍然无法弄清楚你是否在数据库中。差分隐私具有面向未来的特性。”
一个基本原语
到目前为止，我们一直侧重于有人针对单个数据库提出单个计数查询的情况。但现实世界要复杂得多。
研究人员通常希望提出关于数据库的许多问题。并且在你的一生中，你的个人信息的片段可能会进入许多不同的数据库，其中每个数据库可能会在不咨询其他数据库的情况下发布数据。
差分隐私提供了一种精确而简单的方法来量化如果你所属的数据库的研究人员提出多个问题，你遭受的累积隐私损失。例如，如果你的敏感数据在两个数据集中，并且这两个数据集的管理者分别使用隐私参数为 Ɛ1 和 Ɛ2 的算法发布这些数据，那么你泄露的总隐私量最多为 Ɛ1+ Ɛ2。如果管理者允许对单个数据库提出多个问题，则同样适用此加法关系。如果研究人员针对数据库提出 m 个问题，并且每个问题都使用隐私参数 Ɛ 回答，那么损失的总隐私量最多为 mƐ。
因此，从理论上讲，数据集的管理者可以允许研究人员提出任意多个计数查询，只要他为每个答案添加足够的拉普拉斯噪声，以确保泄漏的总隐私量少于他预先选择的隐私“预算”。
尽管我们将注意力限制在计数查询上，但事实证明，此限制并不重要。研究人员喜欢提出的许多其他问题类型可以根据计数查询重新表达。例如，如果你想生成 2012 年前 100 个婴儿名字的列表，你可以提出一系列形式为“有多少婴儿的名字以 A 开头？”（或 Aa、Ab 或 Ac）的问题，并逐步完成所有可能性。
Roth 说：“机器学习中的早期结果之一是，原则上可以学习的所有内容几乎都可以通过计数查询来学习。计数查询不是孤立的玩具问题，而是一种基本原语”——即可以构建许多更复杂算法的构建块。
但是这里有一个问题。我们希望允许的问题越多，每个问题被允许从隐私预算中使用的隐私就越少，并且必须为每个答案添加的噪声就越多。考虑婴儿名字问题。如果我们确定总隐私预算 Ɛ 为 0.01，并且有 10,000 个名称要询问，则每个问题的个人隐私预算仅为 Ɛ/10,000 或 0.000001。添加到每个答案的预期噪声量将为 10,000/Ɛ 或 1,000,000，这个量将淹没真实答案。
换句话说，独立地为每个问题添加拉普拉斯噪声的朴素方法在它可以提供有用答案的问题数量方面受到限制。为了解决这个问题，计算机科学家开发了一套更强大的原语——算法构建块，它们通过考虑数据库的特定结构和问题类型，可以比朴素方法更准确地回答更多问题。
例如，2005 年，Smith 注意到婴儿名字问题具有特殊的结构：从数据库中删除一个人的个人信息只会更改数据库中 10,000 个名称中的一个的答案。由于此属性，我们可以对每个名称答案仅添加 1/Ɛ 的拉普拉斯噪声，而不是 10,000/Ɛ，结果将保持在我们的 Ɛ 隐私预算内。此算法是一种原语，可以应用于任何“直方图”查询——即询问有多少人属于几个互斥的类别中的每一个，例如名字。
当 Smith 在差分隐私研究的早期将此见解告诉 Dwork 时，“我内心有什么东西在说‘哇！’，”Dwork 说。“我意识到，我们可以利用查询或计算的结构来获得比我意识到的更高的准确性。”
自那时以来，计算机科学家已经开发了大量此类原语库。并且由于加法规则解释了当算法组合时隐私参数会发生什么，因此计算机科学家可以将这些构建块组装成复杂的结构，同时跟踪由此产生的算法使用了多少隐私。
位于加利福尼亚州圣何塞的 IBM Research Almaden 的 Moritz Hardt 说：“该领域的一项成就是提出可以使用相对较小的噪声处理大量查询的算法。”
为了使非专家更容易访问差分隐私，一些小组正在努力创建一种差分隐私编程语言，该语言会将所有算法原语的底层数学抽象到用户不必考虑的层。
McSherry 创建了一种初步的此类语言，名为 PINQ，他说：“如果你是数据集的管理者，只要他们运行使用此语言编写的查询，你就不必担心人们如何处理你的数据集。” “该程序可以证明查询是正确的。”
一种不可再生的资源
由于简单的加法 Ɛ 规则对当你所属的各个数据库以差分隐私方式发布信息时你损失的总隐私量给出了精确的上限，因此加法规则将隐私变成了“可替代的货币”，McSherry 说。
例如，如果你要决定你可接受的终生隐私损失总量，你可以决定如何“花费”它——或许是用它来换取金钱，或者用来支持你钦佩的研究项目。每次你允许你的数据在差异隐私数据发布中使用时，你都会确切知道你的隐私预算还剩下多少。
同样，敏感信息数据集的管理者可以决定如何花费她已决定释放的隐私量——也许通过邀请研究项目的提案，这些提案不仅要描述研究人员想要提出的问题以及原因，还要说明该项目将消耗多少隐私。然后，管理者可以决定哪些项目能够最有效地利用数据集预定的隐私预算。一旦这个预算用完，该数据集就可能停止进一步研究。
“隐私是一种不可再生的资源，”麦克谢里说。“一旦被消耗，它就消失了。”
关于哪个Ɛ值代表可接受的隐私损失的问题，最终是社会的问题，而不是计算机科学家的问题——而且每个人可能会给出不同的答案。尽管给像隐私这样无形的东西定价的前景可能令人望而生畏，但存在一个相关的类比。
“还有另一种具有相同属性的资源——你生命中的时间，”麦克谢里说。“它们是有限的，一旦你使用了它们，它们就消失了。然而，由于我们有货币和劳动力市场，作为一个社会，我们已经弄清楚了如何为人们的时间定价。我们可以想象同样的事情发生在隐私上。”
经允许转载自西蒙斯科学新闻，它是SimonsFoundation.org的一个编辑独立部门，其使命是通过报道数学以及计算、物理和生命科学领域的研究进展和趋势来增进公众对科学的理解。