Additive noise mechanisms
Adding controlled noise from predetermined distributions is a way of designing differentially private mechanisms. This technique is useful for designing private mechanisms for real-valued functions on sensitive data. Some commonly used distributions for adding noise include Laplace and Gaussian distributions.
Let be a collection of all datasets and be a real-valued function. The sensitivity  of a function, denoted , is defined by
where the maximum is over all pairs of datasets and in differing in at most one element. For functions with higher dimensions, the sensitivity is usually measured under or norms.
Throughout this article, is used to denote a randomized algorithm that releases a sensitive function under the - (or -) differential privacy.
Mechanisms for Real-Valued Functions
where is the expectation of the Laplace distribution and is the scale parameter. 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 ).
To argue that the mechanism satisfies -differential privacy, it suffices to show that the output distribution of is close in a multiplicative sense to everywhere.
A discrete variant of the Laplace mechanism, called the geometric mechanism, is universally utility-maximizing. 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. No such universal mechanism exists for multi-variate loss functions.
Analogous to Laplace mechanism, Gaussian mechanism adds noise drawn from a Gaussian distribution whose variance is calibrated according to the sensitivity and privacy parameters. For any and , the mechanism defined by:
provides -differential privacy.
Note that, unlike Laplace mechanism, only satisfies -differential privacy with . To prove so, it is sufficient to show that, with probability at least , the distribution of is close to . The proof is a little more involved (see Appendix A in Dwork and Roth).
Mechanisms for High Dimensional Functions
For high dimensional functions of the form , where , the sensitivity of is measured under or norms. The equivalent Gaussian mechanism that satisfies -differential privacy for such function (still under the assumption that ) is
where represents the sensitivity of under norm and represents a -dimensional vector, where each coordinate is a noise sampled according to independent of the other coordinates (see Dwork and Roth for proof).
- Dwork, Cynthia; McSherry, Frank; Nissim, Kobbi; Smith, Adam (2006). "Calibrating Noise to Sensitivity in Private Data Analysis". Theory of Cryptography. Lecture Notes in Computer Science. 3876: 265–284. doi:10.1007/11681878_14. ISBN 978-3-540-32731-8.
- Ghosh, Arpita; Roughgarden, Tim; Sundararajan, Mukund (2012). "Universally Utility-maximizing Privacy Mechanisms". SIAM Journal on Computing. 41 (6): 1673–1693. arXiv:0811.2841. doi:10.1137/09076828X.
- Gupte, Mangesh; Sundararajan, Mukund (June 2010). "Universally optimal privacy mechanisms for minimax agents". Proceedings of the Twenty-ninth ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS): 135–146. arXiv:1001.2767. doi:10.1145/1807085.1807105. ISBN 9781450300339.
- Brenner, Hai; Nissim, Kobbi (January 2014). "Impossibility of Differentially Private Universally Optimal Mechanisms". SIAM Journal on Computing. 43 (5): 1513–1540. arXiv:1008.0256. doi:10.1137/110846671.
- Dwork, Cynthia; Roth, Aaron (2013). "The Algorithmic Foundations of Differential Privacy" (PDF). Foundations and Trends in Theoretical Computer Science. 9 (3–4): 211–407. doi:10.1561/0400000042. ISSN 1551-305X.