4
$\begingroup$

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 :)

$\endgroup$

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

Certainly! Let's consider a simple example to illustrate how the Laplace distribution can be used to add privacy-preserving noise in differential privacy. Suppose we have a dataset of individuals' ages, and we want to calculate the average age while ensuring privacy. In differential privacy, we need to add noise to the computation of the average age to protect individual privacy.

  1. Calculating the average age without privacy: Let's assume we have a dataset of ages: [25, 30, 35, 40, 45]. The average age without privacy would simply be the sum of all ages divided by the number of individuals: Average age = (25 + 30 + 35 + 40 + 45) / 5 = 35.
  2. Adding Laplace noise for privacy preservation: In differential privacy, we want to add noise to the computation to protect individual ages while still providing useful statistical information. We can use the Laplace distribution to generate the noise to be added. Let's say we choose a privacy parameter, epsilon (ε), to quantify the desired level of privacy. A smaller ε value corresponds to stronger privacy guarantees. The privacy budget determines the amount of noise to be added. For example, if we set ε = 0.5, we can calculate the amount of noise to be added using the sensitivity of the query. Sensitivity refers to the maximum change in the query's output caused by the addition or removal of an individual's data. In this case, the sensitivity of calculating the average age is 1, as the maximum change in the average age can occur when an individual's age is added or removed. The noise can be sampled from the Laplace distribution with a scale parameter (b) determined by the sensitivity and privacy budget: Noise = Laplace(scale = sensitivity / epsilon) = Laplace(scale = 1 / 0.5) = Laplace(scale = 2). Let's say we draw a random sample from the Laplace distribution, and it gives us a noise value of -0.7.
  3. Adding noise to the average age: To preserve privacy, we add the noise to the computed average age: Noisy average age = Average age + Noise = 35 + (-0.7) = 34.3. The noisy average age is the result that is released or used for analysis. It includes the privacy-preserving noise, making it difficult to determine the exact age of any individual in the dataset. By adding Laplace noise, differential privacy provides a level of privacy protection while still allowing for useful statistical calculations. The amount of noise added depends on the privacy parameter (ε) and the sensitivity of the query, ensuring privacy guarantees in the analysis of sensitive data.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.