 Laplace mechanism

The Laplace mechanism releases a numerical query with added Laplace distribution noise scaled to the query's sensitivity. For $f(D)\in {\mathbb{R}}^k$, define its sensitivity under the chosen dataset adjacency byFor $\epsilon >0$ and positive finite sensitivity, release $f(D)+(Y_1,\dots ,Y_k)$ with independent noise coordinates of density $p(y)=(2b{)}^{-1}{e}^{-|y|/b}$, where $b={\Delta }_{1}f/\epsilon$. The ratio of output densities for adjacent inputs is bounded by $\exp (\Vert f(D)-f(D^{\prime }){\Vert }_1/b)\le e^{\epsilon }$, by the triangle inequality. Integrating over any measurable output event proves $(\epsilon ,0)$ differential privacy.^[ref]

For a count with add/remove sensitivity one and $\epsilon =0.5$, the noise scale is two and its variance is $2b^2=8$. Smaller privacy parameters increase uncertainty in this mechanism. A fixed output when sensitivity is zero needs no noise. The adjacency convention is essential: changing what one person can contribute changes the required sensitivity bound.