The Algorithmic Foundations of Differential Privacy
The Algorithmic Foundations of Differential Privacy
复制标题
DOI：
10.1561/0400000042
复制
发表时间：
2013-01-01
影响因子：
--
通讯作者：
Roth, Aaron
中科院分区：
文献类型：
--
作者：
Dwork, Cynthia;Roth, Aaron
保护隐私的数据分析问题有着悠久的历史，跨越了多个学科。随着有关个人的电子数据变得越来越详细，随着技术使这些数据的收集和管理变得更加强大，对隐私的健壮、有意义和数学上严格的定义的需求增加，以及满足这一定义的计算丰富的算法类。差别隐私就是这样一个定义。在激励和讨论差分隐私的意义之后，本专著的优势是致力于实现差分隐私的基本技术，以及这些技术在创造性组合中的应用，使用查询-释放问题作为一个正在进行的例子。关键的一点是，通过重新考虑计算目标，通常可以获得比系统地将非私有计算的每个步骤替换为差异私有实现所获得的结果要好得多。尽管有一些令人惊讶的强大计算结果，但仍然存在根本性的限制，不仅局限于差分隐私所能达到的效果，而且局限于任何防止隐私完全崩溃的方法所能达到的效果。实际上，本文讨论的所有算法都对任意计算能力的对手保持差分隐私。有些算法是计算密集型的，有些算法是高效的。讨论了对手和算法的计算复杂度。然后，我们从基础转向queryrelease以外的应用，讨论机制设计和机器学习的不同私有方法。关于差分私有算法的绝大多数文献考虑的是一个单一的、静态的、需要进行许多分析的数据库。讨论了其他模型中的差异隐私，包括分布式数据库和数据流计算。
\The problem of privacy-preserving data analysis has a long history spanning multiple disciplines. As electronic data about individuals becomes increasingly detailed, and as technology enables ever more powerful collection and curation of these data, the need increases for a robust, meaningful, and mathematically rigorous definition of privacy, together with a computationally rich class of algorithms that satisfy this definition. Differential Privacy is such a definition.After motivating and discussing the meaning of differential privacy, the preponderance of this monograph is devoted to fundamental techniques for achieving differential privacy, and application of these techniques in creative combinations, using the query-release problem as an ongoing example. A key point is that, by rethinking the computational goal, one can often obtain far better results than would be achieved by methodically replacing each step of a non-private computation with a differentially private implementation. Despite some astonishingly powerful computational results, there are still fundamental limitations not just on what can be achieved with differential privacy but on what can be achieved with any method that protects against a complete breakdown in privacy. Virtually all the algorithms discussed herein maintain differential privacy against adversaries of arbitrary computational power. Certain algorithms are computationally intensive, others are efficient. Computational complexity for the adversary and the algorithm are both discussed.We then turn from fundamentals to applications other than queryrelease, discussing differentially private methods for mechanism design and machine learning. The vast majority of the literature on differentially private algorithms considers a single, static, database that is subject to many analyses. Differential privacy in other models, including distributed databases and computations on data streams is discussed.