What is the purpose of using a Laplacian distribution in adding noise for Differential Privacy?

Question

I am reading up on Differential Privacy and it is mentioned that the technique relies on adding some controlled noise to the release of responses to queries towards a statistical database. This is done so as to preserve the privacy of the owners whose data are stored in the database and still retaining utility of the latter. This make sense to me as it is in plain text. However, I am unable to understand the statistics behind the method and would be grateful if someone would have some explanation to the following:

1. Is it so that in order to add randomness to the response in a controlled manner one would have to pick values from a distribution like Laplace because it provides the structure for gaining that control (e.g. able to calculate the amount of disturbance)? If so what would the statistical structure be ?
2. As stated here for instance, noise from the Laplace distribution is used. Does someone understand what makes the Laplace distribution so useful for this particular situation? Why not use some other symmetric distribution like Gaussian?

Thanks in advance :)

Answer 1

The Laplace distribution is useful because it satisfies a simple translation property. The density function of a 0-centered standard Laplace distribution is $h(x)=\frac 1 2 \exp(-|x|)$. For all translations $z\in \mathbb{R}$, it satisfies $$\frac{h(x+z)}{h(x)} \leq \exp(|z|)\, .$$ That property matches up almost perfectly with the definition of differential privacy, since if you consider to neighboring data sets $D$ and $D'$ on which you compute a function $f$ (with sensitivity $1$) and add Laplace noise, you will get two distributions with densities $\epsilon * h(\epsilon |x-f(D)|)$ and $\epsilon * h(\epsilon |x-f(D')|)$. Their ratio is thus bounded by $\exp(\epsilon |f(D)-f(D')|)\leq \exp(\epsilon)$. This is enough to prove differential privacy.