Epsilon-Differential Privacy (ε-DP)

The parameter ε (epsilon) quantifies the privacy loss bound. A smaller ε provides stronger privacy. It bounds the multiplicative difference in the probability of any output between neighboring datasets. For example, with ε = 0.1, the output probabilities differ by at most a factor of e^0.1 ≈ 1.105, making outcomes nearly indistinguishable. This provides a concrete, tunable knob for the privacy-utility trade-off.

A defining resilience property. Any arbitrary computation applied to the output of an ε-differentially private mechanism cannot weaken the privacy guarantee. An adversary cannot 'reverse-engineer' privacy by performing post-hoc analysis. The output remains ε-differentially private regardless of downstream processing. This ensures that data released once with a privacy guarantee remains protected forever, enabling safe sharing with untrusted third parties.

Formal rules for tracking cumulative privacy loss across multiple queries. Sequential composition states that applying k mechanisms, each with ε_i privacy, results in a total privacy loss of Σε_i. Advanced composition provides tighter bounds for adaptive queries. This allows a privacy budget to be allocated across an entire analysis workflow, preventing death by a thousand cuts where individually harmless queries combine to reveal sensitive data.

A corollary that extends protection to groups. If a mechanism provides ε-differential privacy for individuals, it provides kε-differential privacy for groups of size k. This means protecting a family of four under ε=0.1 individual privacy requires a group privacy budget of 0.4. This property quantifies the inherent degradation of privacy when defending against adversaries targeting correlated records or entire households in a dataset.

The guarantee holds against adversaries with arbitrary external knowledge. Unlike syntactic anonymization techniques like k-anonymity, which catastrophically fail when linked with public datasets, differential privacy makes no assumptions about an attacker's background information. The mathematical bound remains valid even if the adversary knows every other record in the database, preventing linkage attacks like those that re-identified Netflix Prize and AOL search data.

The formal guarantee provides a rigorous form of plausible deniability for any individual. For any output, the probability it was produced from a dataset containing a specific person's record is nearly identical to the probability it was produced from a dataset without it. This means an individual can credibly deny that their data influenced a published statistic, as the outcome is almost equally likely regardless of their participation.