Laplace mechanism privacy

Suppose ${\mathrm{\Delta }}_{1}f>0$ and put $b={\mathrm{\Delta }}_{1}f\mathrm{/}\epsilon$. By [F2]–[F4], the output law at database $D$ has Lebesgue density $p_D(x)=(2b{)}^{-d}\exp (-\mathrm{\parallel }x-f(D){\mathrm{\parallel }}_1\mathrm{/}b)$, since [F4] translates the product noise density from [F3] by $f(D)$.

For every $x\in {\mathbb{R}}^d$, coordinatewise triangle inequalities give $\mathrm{\parallel }x-f(D^{\mathrm{\prime }}){\mathrm{\parallel }}_1-\mathrm{\parallel }x-f(D){\mathrm{\parallel }}_1\le \mathrm{\parallel }f(D)-f(D^{\mathrm{\prime }}){\mathrm{\parallel }}_1\le {\mathrm{\Delta }}_{1}f$. The densities in [F3] are positive, and [F6] gives $\exp (-u)\mathrm{/}\exp (-v)=\exp (v-u)$ for real $u,v$. Therefore $p_D(x)\mathrm{/}{p}_{D^{\mathrm{\prime }}}(x)=\exp ((\mathrm{\parallel }x-f(D^{\mathrm{\prime }}){\mathrm{\parallel }}_1-\mathrm{\parallel }x-f(D){\mathrm{\parallel }}_1)\mathrm{/}b)\le \exp ({\mathrm{\Delta }}_{1}f\mathrm{/}b)=e^{\epsilon }$, where the inequality uses monotonicity from [F6]. Interchanging $D,D^{\mathrm{\prime }}$ proves the reverse pointwise ratio bound; integrating both bounds over $A$ yields the two event inequalities.

If ${\mathrm{\Delta }}_{1}f=0$, [F1] forces $\mathrm{\parallel }f(D)-f(D^{\mathrm{\prime }}){\mathrm{\parallel }}_1=0$ for every neighboring pair, hence $f(D)=f(D^{\mathrm{\prime }})$. The deterministic output laws are identical, so both event inequalities hold with $\delta =0$ (and $\epsilon \ge 0$). Combining this case with step 2.1 and applying [F5] proves the result.