Adding Laplace or Gaussian noise to database for privacy
In the previous two posts we looked at a randomization scheme for protecting the privacy of a binary response. This post will look briefly at adding noise to continuous or unbounded data. I like to keep the posts here fairly short, but this topic is fairly technical. To keep it short I'll omit some of the details and give more of an intuitive overview.
Differential privacyThe idea of differential privacy is to guarantee bounds on how much information may be revealed by someone's participation in a database. These bounds are described by two numbers, I (epsilon) and I (delta). We're primarily interested in the multiplicative bound described by I. This number is roughly the number of bits of information an analyst might gain regarding an individual. (The multiplicative bound is exp(I) and so I, the natural log of the multiplicative bound, would be the information measure, though technically in nats rather than bits since we're using natural logs rather than logs base 2.)
The I term is added to the multiplicative bound. Ideally I is 0, that is, we'd prefer (I, 0)-differential privacy, but sometimes we have to settle for (I, I)-differential privacy. Roughly speaking, the I term represents the possibility that a few individuals may stand to lose more privacy than the rest, that the multiplicative bound doesn't apply to everyone. If I is very small, this risk is very small.
Laplace mechanismThe Laplace distribution is also known as the double exponential distribution because its distribution function looks like the exponential distribution function with a copy reflected about the y-axis; these two exponential curves join at the origin to create a sort of circus tent shape. The absolute value of a Laplace random variable is an exponential random variable.
Why are we interested this particular distribution? Because we're interested in multiplicative bounds, and so it's not too surprising that exponential distributions might make the calculations work out because of the way the exponential scales multiplicatively.
The Laplace mechanism adds Laplacian-distributed noise to a function. If I"f is the sensitivity of a function f, a measure of how revealing the function might be, then adding Laplace noise with scale I"f/I preserves (I 0)-differential privacy.
Technically, I"f is the l1 sensitivity. We need this detail because the results for Gaussian noise involve l2 sensitivity. This is just a matter of whether we measure sensitivity by the l1 (sum of absolute values) norm or the l2 (root sum of squares) norm.
Gaussian mechanismThe Gaussian mechanism protects privacy by adding randomness with a more familiar normal (Gaussian) distribution. Here the results are a little messier. Let I be strictly between 0 and 1 and pick I > 0. Then the Gaussian mechanism is (I, I)-differentially private provided the scale of the Gaussian noise satisfies
It's not surprising that the l2 norm appears in this context since the normal distribution and l2 norm are closely related. It's also not surprising that a I term appears: the Laplace distribution is ideally suited to multiplicative bounds but the normal distribution is not.
RelatedPrevious related posts:
- Randomized response, privacy, and Bayes theorem
- Quantifying privacy loss in a statistical database
- Quantifying the information content of personal data
- HIPAA de-identification
- Information theory
- Database anonymization