Here is the basic idea of differential privacy in its simplest form.<p>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,<p><pre><code>    (1-eps) * Pr{ A(X2) \in S } &lt;= Pr{ A(X1) \in S } &lt;= (1+eps) * Pr{ A(X2) \in S }. 
</code></pre>
Intuitively speaking, the output <i>distribution</i> of A on X1 and X2 looks roughly the same, only differing by a <i>factor</i> (1 +&#x2F;- 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.