Re:Differential privacy for dummies
by alephone on Monday February 08, 2016 @03:32AM
(#11056976)
Here is the basic idea of differential privacy in its simplest form.
Suppose that A is a eps-DP algorithm and X1, X2 are two datasets differing by a single point. Recall that for small eps, exp(eps) is roughly (1+eps) and exp(-eps) is roughly (1-eps), so eps-DP yields the guarantee that (roughly speaking), for all subsets S,
(1-eps) * Pr{ A(X2) \in S } <= Pr{ A(X1) \in S } <= (1+eps) * Pr{ A(X2) \in S }.
Intuitively speaking, the output distribution of A on X1 and X2 looks roughly the same, only differing by a factor (1 +/- eps), with a fudge factor eps that the user gets to control. Note that this is a very strong notion of stability of an algorithm.
Suppose that A is a eps-DP algorithm and X1, X2 are two datasets differing by a single point. Recall that for small eps, exp(eps) is roughly (1+eps) and exp(-eps) is roughly (1-eps), so eps-DP yields the guarantee that (roughly speaking), for all subsets S,
Intuitively speaking, the output distribution of A on X1 and X2 looks roughly the same, only differing by a factor (1 +/- eps), with a fudge factor eps that the user gets to control. Note that this is a very strong notion of stability of an algorithm.