TY - JOUR
AU - Dwork, Cynthia
AU - McSherry, Frank
AU - Nissim, Kobbi
AU - Smith, Adam
PY - 2017/05/30
Y2 - 2021/04/13
TI - Calibrating Noise to Sensitivity in Private Data Analysis
JF - Journal of Privacy and Confidentiality
JA - JPC
VL - 7
IS - 3
SE - Articles
DO - 10.29012/jpc.v7i3.405
UR - https://journalprivacyconfidentiality.org/index.php/jpc/article/view/405
SP - 17-51
AB - <p>We continue a line of research initiated in Dinur and Nissim (2003); Dwork and Nissim (2004); and Blum et al. (2005) on privacy-preserving statistical databases.</p><p>Consider a trusted server that holds a database of sensitive information. Given a query function $f$ mapping databases to reals, the so-called {\em 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.</p><p>Previous work focused on the case of noisy sums, in which $f = \sum_i g(x_i)$, where $x_i$ denotes the $i$th row of the database and $g$ maps database rows to $[0,1]$. We extend the study to general functions $f$, proving that privacy can be preserved by calibrating the standard deviation of the noise according to the {\em 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.</p><p>The first step is a very clean definition of privacy---now known as differential privacy---and measure of its loss. We also provide a set of tools for designing and combining differentially private algorithms, permitting the construction of complex differentially private analytical tools from simple differentially private primitives.</p><p>Finally, we obtain separation results showing the increased value of interactive statistical release mechanisms over non-interactive ones.</p>
ER -