Calibrating Noise to Sensitivity in Private Data Analysis

We continue a line of research initiated in [10,11]on privacy-preserving 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

= ∑

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

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 terms of indistinguishability of transcripts. Additionally, we obtain separation results showing the increased value of interactive sanitization mechanisms over non-interactive.