Differential Privacy

The parameter ε (epsilon) quantifies the maximum privacy loss. A smaller epsilon enforces stronger privacy by limiting how much any single record can influence the output.

• ε = 0: Perfect privacy, but zero utility (output is pure noise).
• ε = 0.1–1: Strong privacy, suitable for highly sensitive census data.
• ε = 1–10: Moderate privacy, common for internal analytics.
• ε > 10: Weak privacy, approaching non-private release.

The budget is consumed with each query. Once exhausted, no further access to the raw data is permitted under the same guarantee.

The fundamental guarantee: an adversary cannot determine whether any specific individual's record was included in the dataset, regardless of external knowledge.

For any two datasets differing by one record, the probability of observing a particular output is nearly identical. This holds even if the attacker possesses all other records in the database. The mechanism injects calibrated noise—typically drawn from a Laplace or Gaussian distribution—scaled to the sensitivity of the query function.

Privacy loss accumulates additively across multiple queries. If you run k independent ε-differentially private mechanisms on the same dataset, the total privacy guarantee degrades to kε.

This forces careful budgeting. A data scientist cannot simply run unlimited queries. Strategies to manage this include:

• Setting a hard cap on total queries.
• Using advanced composition theorems that provide tighter bounds.
• Employing a privacy accountant to track cumulative loss during iterative processes like DP-SGD training.

Any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. Once noise is injected, no amount of post-processing—filtering, rounding, normalization, or even machine learning—can reverse the protection.

This is a crucial property for practical deployment. Analysts can freely transform the noisy, private output into visualizations, summary statistics, or model parameters without ever risking re-identification of the source records.

The standard definition protects against singling out one individual. Group privacy extends this to cohorts of size g. If a mechanism provides ε-differential privacy for a single record, it provides gε-differential privacy for a group of g records.

This means protecting a family of four requires a budget four times smaller than protecting an individual. It highlights the inherent trade-off: defending against broader correlation attacks demands significantly more noise.

Differential privacy makes no assumptions about an attacker's background knowledge. The guarantee holds even if the adversary possesses:

• Complete demographic data from public records.
• Social network graphs.
• Previous data releases.
• Knowledge of all other records in the target database.

This is a critical distinction from syntactic anonymization techniques like k-anonymity, which catastrophically fail when linked with external datasets.

A quantifiable limit on the total privacy loss allowed over a series of queries or releases, parameterized by epsilon (ε). Lower epsilon values enforce stronger formal privacy guarantees by injecting more noise, while higher values permit greater accuracy. Once the budget is exhausted, no further queries can be answered without risking re-identification. Composition theorems track cumulative privacy loss across multiple analyses, making the budget a finite, consumable resource that must be carefully allocated by privacy engineers.

The probability that an attacker can successfully link anonymized or synthetic records back to the specific real-world individual they describe by using auxiliary information. Even statistically faithful synthetic data can leak identity if outliers are reproduced too precisely. Differential privacy provides a formal bound on this risk by guaranteeing that the output distribution is nearly identical whether or not any single individual is included. K-anonymity and l-diversity are complementary, weaker privacy models that address specific re-identification vectors.