Calibrating noise to sensitivity in private data analysis
Calibrating noise to sensitivity in private data analysis
复制标题
DOI：
10.1007/11681878_14
复制
发表时间：
2006-01-01
期刊：
影响因子：
--
通讯作者：
Smith, Adam
中科院分区：
文献类型：
--
作者：
Dwork, Cynthia;McSherry, Frank;Smith, Adam
我们继续在[10，11]中发起的关于隐私保护统计数据库的研究。考虑一个拥有敏感信息数据库的可信服务器。给定一个查询函数f，将数据库映射到实数，所谓的真答案是将f应用于数据库的结果。为了保护隐私，真实的答案被根据仔细选择的分布产生的随机噪声干扰，这个响应，真实的答案加上噪声，被返回给用户。以前的工作集中在噪声和的情况下，其中f Sigma（i）g（x（i）），其中x（i）表示数据库的第i行，g将数据库行映射到[0，1]。我们将研究扩展到一般函数，证明可以通过根据函数f的灵敏度校准噪声的标准差来保护隐私。粗略地说，这是f的任何单个参数可以改变其输出的量。新的分析表明，对于几个特定的应用程序，所需的噪音比以前理解的要少得多。第一步是非常清晰地描述隐私，即转录本的不可复制性。此外，我们得到的分离结果显示增加的价值，互动的消毒机制，非互动。
We continue a line of research initiated in [10, 11] on privacypreserving statistical databases. Consider a trusted server that holds a database of sensitive information. Given a query function f mapping databases to reals, the so-called true answer is the result of applying f to the database. To protect privacy, the true answer is perturbed by the addition of random noise generated according to a carefully chosen distribution, and this response, the true answer plus noise, is returned to the user.Previous work focused on the case of noisy sums, in which f Sigma(i)g(x(i)), where x(i) denotes the ith row of the database and g maps database rows to [0, 1]. We extend the study to general functions proving that privacy can be preserved by calibrating the standard deviation of the noise according to the sensitivity of the function f. Roughly speaking, this is the amount that any single argument to f can change its output. The new analysis shows that for several particular applications substantially less noise is needed than was previously understood to be the case.The first step is a very clean characterization of privacy in tern-is of indistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms over non-interactive.