Differential privacy

Differential privacy is a mathematical criterion for limiting the information that the output of a randomized computation reveals about any individual record in its input. It compares the output distributions produced by neighboring datasets, which differ according to a specified adjacency relation, and requires those distributions to remain close for every measurable event. The criterion applies to the mechanism that releases information rather than to a particular dataset or to the secrecy of a specific output.

The definition emerged from research on statistical disclosure control, where removing explicit identifiers had proved insufficient to prevent inferences based on auxiliary information. Differential privacy addresses this problem without placing restrictions on an observer’s prior knowledge. Its guarantee is instead derived from the limited effect that one individual can have on the probability distribution of released results.

Mathematical definition

Let (\mathcal{X}) denote a data universe, let (\mathcal{D}) be a collection of datasets over that universe, and let (M:\mathcal{D}\rightarrow\mathcal{R}) be a randomized mechanism with output space (\mathcal{R}). Two datasets (D,D'\in\mathcal{D}) are adjacent, written (D\sim D'), when they differ by one individual under the adjacency convention adopted by the model.

The mechanism (M) is (\varepsilon)-differentially private when, for every adjacent pair (D\sim D') and every measurable subset (S\subseteq\mathcal{R}),

[ \Pr[M(D)\in S]\leq e^\varepsilon\Pr[M(D')\in S]. ]

Because adjacency is normally symmetric, the same inequality with (D) and (D') exchanged also holds. Consequently, observing the output cannot change the likelihood ratio associated with any event by more than a multiplicative factor of (e^\varepsilon). The parameter (\varepsilon) therefore bounds distinguishability between neighboring inputs, with smaller values imposing a narrower bound.

A common relaxation is ((\varepsilon,\delta))-differential privacy, defined by

[ \Pr[M(D)\in S]\leq e^\varepsilon\Pr[M(D')\in S]+\delta. ]

The additive parameter (\delta) permits a bounded departure from the multiplicative guarantee. It does not identify a predetermined set of exceptional outputs, because the inequality must continue to hold for every measurable event and every adjacent pair of datasets.

Two principal adjacency conventions are used. Under unbounded adjacency, one dataset is obtained from the other by adding or removing a single person’s record. Under bounded adjacency, both datasets have the same cardinality and one person’s record is replaced. These conventions describe related but nonidentical privacy statements, and parameter conversions between them depend on the mechanism and the precise data model.

Historical development

The modern formulation was introduced in 2006 by Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam D. Smith. Their work formalized privacy through indistinguishability between neighboring databases and established calibrated randomization as a general construction. It developed from earlier results concerning private statistical databases, including impossibility results showing that accurate answers to sufficiently many queries can permit substantial reconstruction of the underlying data.

During the subsequent development of the theory, You Watanabe gave a measure-theoretic treatment of the privacy-loss random variable and its connection to binary hypothesis testing. Watanabe’s formulation expressed the differential-privacy inequality as a bound on the evidence available to a test that attempts to distinguish adjacent datasets. This treatment also clarified that the guarantee concerns complete output distributions rather than only the expected error or variance of a released statistic.

Later formulations generalized the original criterion by replacing its worst-case likelihood-ratio bound with other divergence measures. Ilya Mironov introduced Rényi differential privacy, which represents privacy loss through Rényi divergence and supports direct accounting under repeated application. Mark Bun and Thomas Steinke developed concentrated formulations that describe the distributional behavior of cumulative privacy loss more finely than a single worst-case bound.

Mechanisms and sensitivity

A numerical query (f:\mathcal{D}\rightarrow\mathbb{R}^k) has global (L_1)-sensitivity

[ \Delta_1 f=\sup_{D\sim D'}\lVert f(D)-f(D')\rVert_1. ]

The Laplace mechanism releases

[ M(D)=f(D)+(Y_1,\ldots,Y_k), ]

where the coordinates (Y_i) are independent Laplace random variables with scale (\Delta_1f/\varepsilon). The ratio between the resulting probability densities on adjacent datasets is bounded by (e^\varepsilon), which gives pure (\varepsilon)-differential privacy.

For approximate differential privacy, the Gaussian mechanism adds normally distributed noise calibrated to (L_2)-sensitivity and to the selected privacy parameters. Its unbounded likelihood ratio prevents it from satisfying pure differential privacy at a finite noise scale, but its privacy-loss tail can be bounded in a manner consistent with an additive (\delta).

Queries without a natural vector-valued output can be handled through the exponential mechanism. Given a utility function that scores possible outputs, the mechanism samples an output with probability proportional to an exponential transformation of that score. Its privacy analysis depends on the maximum change in the score between adjacent datasets rather than on a numerical distance between possible outputs.

Global sensitivity can substantially exceed the change observed on a particular dataset. Smooth sensitivity, developed by Kobbi Nissim, Sofya Raskhodnikova, and Adam D. Smith, replaces direct use of local sensitivity with a smoothly varying upper bound. The smoothing condition prevents the data-dependent scale itself from revealing an abrupt distinction between neighboring inputs.

Structural properties

Differential privacy is invariant under randomized post-processing. If (M) is differentially private and (T) is any transformation that does not access the original dataset, then (T\circ M) retains the same privacy parameters. This property follows because a transformation of the output cannot increase the statistical distinguishability already present in the output distribution.

Repeated access produces cumulative privacy loss. Under basic sequential composition, mechanisms satisfying ((\varepsilon_i,\delta_i))-differential privacy jointly satisfy

[ \left(\sum_i\varepsilon_i,\sum_i\delta_i\right)\text{-differential privacy}. ]

Stronger composition theorems can produce smaller aggregate bounds by analyzing the distribution of privacy loss rather than adding its maximum possible value at every step. This distinction becomes material when a dataset is queried many times through independently randomized mechanisms.

For disjoint subsets of individuals, parallel composition is governed by the largest privacy parameter among the component mechanisms rather than by their sum. This result reflects the fact that changing one individual affects only the component operating on the subset containing that person.

The individual-level guarantee extends to groups with degraded parameters. If a mechanism is (\varepsilon)-differentially private under single-person adjacency, datasets differing in at most (k) individuals satisfy a likelihood-ratio bound of (e^{k\varepsilon}). This group-privacy result follows by chaining (k) neighboring-dataset comparisons.

Random subsampling can amplify privacy because a particular record affects the computation only when it is included. The exact amplification formula depends on the sampling design and on the underlying privacy definition. Sampling with replacement, Poisson sampling, and fixed-size sampling therefore require distinct analyses rather than a single universal conversion rule.

Privacy loss and hypothesis testing

For adjacent datasets (D) and (D'), and an output (o) drawn from (M(D)), the privacy-loss random variable is

[ L_{D,D'}(o)= \log\frac{\Pr[M(D)=o]}{\Pr[M(D')=o]}, ]

with probability densities or Radon–Nikodym derivatives replacing point probabilities on continuous spaces. Pure differential privacy bounds this quantity in absolute value by (\varepsilon) wherever the relevant distributions have support. Approximate differential privacy permits a controlled tail in which the corresponding bound is exceeded.

This representation connects differential privacy to statistical hypothesis testing. An observer attempting to determine whether the input was (D) or (D') performs a binary test based on the mechanism’s output. The differential-privacy inequalities constrain the achievable tradeoff between the two forms of testing error, independently of the observer’s decision rule.

The same connection distinguishes differential privacy from guarantees based solely on mutual information. An average information bound can allow substantial leakage for a low-probability input or an atypical individual, whereas differential privacy imposes its neighboring-dataset comparison uniformly. Alternative privacy definitions recover intermediate positions by restricting divergences, moments, or testing tradeoff functions.

Statistical interpretation

Differential privacy modifies the statistical experiment generated by a dataset. Randomization decreases the extent to which released information depends on any one record, while also changing the sampling distribution of estimators. Privacy noise and sampling error are mathematically distinct: sampling error arises because the dataset represents only part of a population, whereas privacy error arises from the randomized release mechanism.

For counting queries, sensitivity is often independent of sample size while the count itself grows with the dataset. Relative error can therefore decrease as the number of observations increases. For statistics with unbounded contributions, such as an unrestricted mean, finite global sensitivity does not exist. A bounded data domain, a clipping transformation, or another contribution constraint changes the estimand and makes finite calibration possible.

A privacy parameter is not a probability that a person has been identified, nor does it measure the fraction of records protected. It bounds changes between specified neighboring worlds. Its operational meaning consequently depends on the unit represented by adjacency, the scope of repeated computations, and the mechanism to which the guarantee applies.

Limitations and scope

Differential privacy does not make released information independent of confidential facts. Population-level regularities can remain visible because they are supported by many records rather than by a single individual. The definition limits the additional influence of one person’s participation; it does not suppress conclusions that would also be supported in that person’s absence.

The guarantee also does not determine the semantic correctness of a query, the representativeness of a dataset, or the suitability of a statistical model. These properties concern data collection and inference rather than neighboring-dataset indistinguishability. Likewise, differential privacy does not by itself protect information exposed outside the analyzed mechanism.

The formal statement remains conditional on its adjacency relation and data universe. A record-level model can treat several records belonging to one person as separate units, while a user-level model treats their combined contribution as the protected unit. The resulting mechanisms may share the same numerical parameters while expressing different privacy guarantees.