Additive noise differential privacy mechanisms

Additive noise differential privacy mechanisms are a class of techniques used to ensure differential privacy when releasing the results of computations on sensitive datasets.

They work by adding carefully calibrated random noise, drawn from specific probability distributions, to the true output of a function.

This added noise obscures the influence of any single individual's data, thereby protecting their privacy while still allowing for meaningful statistical analysis.

Common distributions used for noise generation include the Laplace and Gaussian distributions.

These mechanisms are particularly useful for functions that output real-valued numbers.

Both mechanisms require that the sensitivity of a query function first be determined.

The sensitivity is the amount that the result of the query can be changed by adding or removing a person's data from the dataset, where "a person" is any possible person.

For queries that count the number of people who meet a requirement, the sensitivity is 1.

, is defined by where the maximum is over all pairs of datasets

For functions with higher dimensions, the sensitivity is usually measured under

is used to denote a randomized algorithm that releases a sensitive function

A Real-valued function is any function that returns a "real" value --- that is, a positive or negative number that can be represented by decimal fraction (e.g. 0.5, or 1.32).

Introduced by Dwork et al.,[1] this mechanism adds noise drawn from a Laplace distribution:where

Roughly speaking, a small-scale noise should suffice for a weak privacy constraint (corresponding to a large value of

), while a greater level of noise would provide a greater degree of uncertainty in what was the original input (corresponding to a small value of

-differential privacy, it suffices to show that the output distribution of

is close in a multiplicative sense to

A similar argument gives a lower bound of

A discrete variant of the Laplace mechanism, called the geometric mechanism, is universally utility-maximizing.

[2] It means that for any prior (such as auxiliary information or beliefs about data distributions) and any symmetric and monotone univariate loss function, the expected loss of any differentially private mechanism can be matched or improved by running the geometric mechanism followed by a data-independent post-processing transformation.

The result also holds for minimax (risk-averse) consumers.

[3] No such universal mechanism exists for multi-variate loss functions.

[4] Analogous to Laplace mechanism, Gaussian mechanism adds noise drawn from a Gaussian distribution whose variance is calibrated according to the sensitivity and privacy parameters.

Note that, unlike Laplace mechanism,

To prove so, it is sufficient to show that, with probability at least

See Appendix A in Dwork and Roth for a proof of this result[5]).

For high dimensional functions of the form

The equivalent Gaussian mechanism that satisfies

-dimensional vector, where each coordinate is a noise sampled according to

independent of the other coordinates (see Appendix A in Dwork and Roth[5] for proof).