A Firm Foundation for Private Data Analysis

1.私有数据分析
在信息领域中，隐私的丧失通常与无法控制对信息的访问，无法控制信息的流量或无法控制使用信息的目的有关。即使解决了所有这些控制问题，确保隐私也是一个挑战的环境中出现了隐私保护数据的统计分析。
统计披露控制的问题 -- 在保护个人隐私的同时揭示一组受访者的准确统计数据 -- 有着悠久的历史，广泛的文献涵盖了统计、理论计算机科学、安全、数据库和密码学 (例如，参见优秀的调查 [1]，[2] 和《社会统计杂志》9 (2) 中相关工作的讨论，致力于确认和披露控制)。这悠久的历史证明了这个问题的重要性。统计数据库可能具有巨大的社会价值; 它们用于分配资源，评估医学疗法，了解疾病的传播，提高经济效用以及告知我们自己作为一个物种。
数据可以通过不同的方式获得。一些数据，如人口普查、税收和其他类型的官方数据，是被迫的; 其他数据是机会收集的，例如，从互联网上的tra?c、亚马逊上的交易和搜索引擎查询日志; 其他数据是无私地提供的，受访者希望分享他们的信息将帮助其他人避免特殊的不幸，或者更普遍地说，增加公共利益。利他的数据捐赠者通常被承诺他们的个人数据将被保留，简而言之，他们被承诺 “隐私”。同样，医疗数据和法律强制数据，如人口普查数据、纳税申报单数据，有法律隐私授权。
我们认为，道德要求机会性获得的数据不应受到不同的对待，尤其是当没有合理的替代方法来从事产生相关数据的行动时。
问题仍然存在: 即使数据加密，密钥管理，访问控制以及数据策展人的动机都是无可指责的，保护隐私意味着什么，如何实现？
1.1 “如何” 很难
让我们考虑一些常见的建议以及它们可以包含的一些大型查询集。
一个常见的建议是禁止对特定个体或一小部分个体的查询。一个著名的论点证明了这一建议的不足。假设已知X先生在某个医学数据库中。综合起来，两个大问题的答案是 “数据库中有多少人具有镰状细胞特征？” 和 “数据库中有多少人 (不叫X) 具有镰状细胞特征？” 产生了X先生的镰状细胞状态。该示例还表明，加密数据 (另一个常见的建议) 将毫无帮助。隐私损害源于数据库的正确操作。

在查询审核中，对数据库的每个查询都在查询历史的上下文中进行评估，以确定响应是否会公开; 如果是，则拒绝查询。例如，可以使用查询审核来阻止刚刚描述的有关镰状细胞特征的一对查询。这种方法是有问题的，有几个原因，其中包括查询监控在计算上是不可行的 [15]，拒绝响应查询本身可能是公开的 [14]。

我们将数据库视为行的集合，每一行都包含不同受访者的数据。在二次采样中，随机选择并释放行的子集。然后可以在子样本上计算统计数据，如果子样本非常大，则这些可以代表整个数据集。如果子样本的大小与数据集的大小相比非常小，则这种方法具有每个受访者都不太可能出现在子样本中的属性。然而，这显然是不明智的: 假设出现在子样本中有可怕的后果。然后每次子采样发生时，都会有一些人可怕地进行采样。

在输入扰动中，在生成响应之前对数据或查询进行修改。这个广泛的类别包括子采样的概括，其中，策展人首先基于查询的秘密，随机，函数，从数据库中选择一个子样本，然后返回通过将查询应用到子样本而获得的结果 [4]。这种方法的一个很好的功能是，重复相同的查询会产生相同的答案，而语义上等效但在语法上不同的查询是在本质上不相关的子样本上进行的。然而，离群值可能只会受到不可能出现在.

在传统上称为随机响应的情况下，数据本身是一次随机的，并且从噪声响应中计算出统计数据，并考虑到扰动的分布 [22]。术语 “随机回答” 来自这样一种做法，即让受访者参加一项调查，并根据结果回答是/否问题或回答情绪上更中立的问题。在计算机科学文献中，由硬币控制的选择通常是在诚实地报告一个人的价值和随机响应之间，通常是通过?ipping第二枚硬币和报告结果。随机响应是针对个人不信任策展人的环境而设计的，因此我们可以将随机响应视为简单的发布。隐私来自如何解释报告价值的不确定性。对于复杂的数据，这种方法变得站不住脚。

将随机噪声添加到输出中是有希望的，我们稍后将返回。在这里，我们指出，we point out that if done na¨?vely this approach will fail.。要看到这一点，假设噪声的平均值为零，并且在生成每个响应时都使用了新鲜的随机性。在这种情况下，如果重复询问相同的查询，则可以对响应进行平均，并且最终会出现真正的答案。这是灾难性的: 敌对的分析师可以利用这一点来实施上述的不同攻击。该方法不能通过记录每个查询并在每次重新发出查询时提供相同的响应来 “固定”。这有几个原因。例如，语法上不同的查询可能在语义上是等效的，并且，如果查询语言非常丰富，则对等问题本身是无法确定的，因此策展人甚至无法对此进行测试。

3. DIFFERENTIAL PRIVACY

差分隐私将确保攻击对手对信息和通信技术的伤害(或好处)--任何种类的、任何一组人--的能力本质上应该是相同的，无论是任何个人选择加入还是退出数据集。我们将间接地做到这一点，同时解决所有可能的危害和好处，方法是关注隐私机制的任何给定输出的概率，以及该概率如何随着任何行的添加或删除而改变。
因此，我们将专注于只在一行中对数据库(D，D0)进，这意味着一个数据库是另一个数据库的子集，而较大的数据库只包含一个附加行。最后，为了处理最坏的数据库对，我们的概率将超过隐私机制做出的随机选择。

7.结论
差分隐私前沿研究边界正在迅速扩大，这里不能列出社区目前正在调查的所有有趣的方向。我们确定了其中的几个。
1、Geometry of Di?erential Privacy.。通过理解查询序列的几何[13]，可以获得实现针对线性查询序列的差分隐私所需的噪声的更清晰的上界和下界[13]。在某些情况下，管理员可以利用查询之间的依赖关系来显着提高响应的准确性。将这一调查推广到非线性和交互的案例中将是非常有意义的。不会感兴趣的。
2、算法复杂性。到目前为止，我们忽略了计算复杂性的问题。这里描述的许多(但不是全部)技术都实现。例如，存在在标准密码假设下没有多项式时间实现的合成数据生成问题的实例[10]。因此，在某些情况下，指数机制没有有效实现。这个强大的工具什么时候可以科学地实现？如何实现？
3、Di?隐私保护的替代方案？有没有一种替代方案，“ad Omnia”，保证自动写作，并允许比差分隐私更高的准确性？密码学在这方面能有所帮助吗[19]？

这里描述的工作首次将私有数据分析建立在强大的数学基础上。这些文献将差异隐私与决策论、经济学、稳健统计学、几何学、加法组合学、密码学、复杂性理论学习理论和机器学习联系起来。隐私之所以蓬勃发展，是因为它是自然的，它不是特定于领域的，而且它与其他领域有着卓有成效的相互作用。这种的灵活性为在传统的加密安全概念不合适或不切实际的情况下(如私人数据分析)提供了一种原则性的隐私方法带来了希望。