= Differential privacy
A randomized mechanism $M$ satisfies <differential privacy> with parameters $(\varepsilon,\delta)$ if, for every ordered pair of adjacent datasets $D,D'$ and measurable output event $S$,
$$
\mathbb P(M(D)\in S)\leq e^\varepsilon\mathbb P(M(D')\in S)+\delta.
$$
Adjacency specifies the contribution of one individual, such as adding or removing one record. The <probability> is over the mechanism's randomness.
For an integer count query with sensitivity one under add/remove adjacency, releasing the count plus <independent> <Laplace distribution> noise of scale $1/\varepsilon$ gives $(\varepsilon,0)$ privacy. The ratio of output densities is at most $e^\varepsilon$ by the triangle inequality. The guarantee limits distinguishability between neighboring inputs; it does not require publishing identical results or certify that every statistical estimate is accurate.<The Algorithmic Foundations of Differential Privacy by Cynthia Dwork and Aaron Roth>[Definition 2.4 and Theorem 3.6, Laplace mechanism for counting queries]{ref}
Back to article page
