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 poi

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.