UNIVERSALLY UTILITY-MAXIMIZING PRIVACY MECHANISMS
UNIVERSALLY UTILITY-MAXIMIZING PRIVACY MECHANISMS
复制标题
DOI：
10.1137/09076828x
复制
发表时间：
2012-01-01
影响因子：
1.6
通讯作者：
Sundararajan, Mukund
中科院分区：
文献类型：
--
作者：
Ghosh, Arpita;Roughgarden, Tim;Sundararajan, Mukund
一个公布关于含有敏感数据的统计数据库的信息的机制必须解决实用性和隐私性之间的权衡问题。发布完全准确的信息可以最大限度地提高效用，同时最大限度地减少隐私，而发布随机噪音则相反。隐私可以使用差分隐私的框架来严格量化，该框架要求无论是否包括给定的数据库行，机制的输出分布都几乎相同。本文的目标是制定和提供强有力的和一般的效用保证，受到不同的隐私。我们追求的机制，保证接近最佳的效用，每一个潜在的用户，独立于它的边信息（建模为查询结果的先验分布）和偏好（通过对称和单调损失函数建模）。我们的主要结果如下：对于每个固定计数查询和差分隐私级别，有一个几何机制M*-一个离散的变种的简单和良好的研究机制，增加随机噪声从一个拉普拉斯分布，同时预期损失最小化的每一个可能的用户，受到差分隐私约束。这是一个非常强大的效用保证：每个潜在用户u，不管它的边信息和偏好是什么，从M* 获得的效用与从与最适合u的差分私有机制Mu交互获得的效用一样多。更准确地说，对于每个用户u，都有一个最佳机制Mu，它分解为用户独立的部分（几何机制M*）和用户特定的后处理步骤，该步骤仅取决于几何机制的输出，而不取决于底层数据库。我们证明这一结果的第一部分的特点是最佳差分隐私机制为用户作为一个特定的用户特定的目标函数和用户独立的约束，编码差分隐私的线性规划的某种基本可行的解决方案。第二部分表明，所有的相关顶点的可行区域（范围在所有可能的用户）是来自几何机制通过适当的重映射其范围。
A mechanism for releasing information about a statistical database with sensitive data must resolve a trade-off between utility and privacy. Publishing fully accurate information maximizes utility while minimizing privacy, while publishing random noise accomplishes the opposite. Privacy can be rigorously quantified using the framework of differential privacy, which requires that a mechanism's output distribution is nearly the same whether a given database row is included. The goal of this paper is to formulate and provide strong and general utility guarantees, subject to differential privacy. We pursue mechanisms that guarantee near-optimal utility to every potential user, independent of its side information (modeled as a prior distribution over query results) and preferences (modeled via a symmetric and monotone loss function). Our main result is the following: for each fixed count query and differential privacy level, there is a geometric mechanism M*-a discrete variant of the simple and well-studied mechanism that adds random noise from a Laplace distribution-that is simultaneously expected loss-minimizing for every possible user, subject to the differential privacy constraint. This is an extremely strong utility guarantee: every potential user u, no matter what its side information and preferences, derives as much utility from M* as from interacting with a differentially private mechanism Mu that is optimally tailored to u. More precisely, for every user u there is an optimal mechanism Mu for it that factors into a user-independent part (the geometric mechanism M*) and a user-specific postprocessing step that depends only on the output of the geometric mechanism and not on the underlying database. The first part of our proof of this result characterizes the optimal differentially private mechanism for a user as a certain basic feasible solution to a linear program with a user-specific objective function and user-independent constraints that encode differential privacy. The second part shows that all of the relevant vertices of the feasible region (ranging over all possible users) are derivable from the geometric mechanism via suitable remappings of its range.