Differential Privacy

The privacy budget (ε) is the central parameter controlling the strength of the privacy guarantee. A smaller epsilon enforces stricter privacy by requiring more noise, making adjacent datasets statistically indistinguishable. An epsilon of 0 represents absolute, perfect privacy (output is pure noise), while higher values allow greater accuracy at the cost of increased information leakage. Selecting an appropriate epsilon is a critical policy decision, balancing utility against the risk of membership inference attacks.

Delta (δ) represents the probability that the pure ε-differential privacy guarantee fails. This allows for (ε, δ)-differential privacy, or approximate differential privacy, which is often required for advanced algorithms like the Gaussian Mechanism. Delta should be cryptographically small—significantly smaller than the inverse of the dataset size—to ensure that catastrophic leakage of individual records is practically impossible. A common rule of thumb is δ < 1/N², where N is the number of data subjects.

When multiple differentially private computations are performed on the same dataset, the total privacy loss accumulates linearly. If a first analysis satisfies ε₁-differential privacy and a second satisfies ε₂-differential privacy, the combined release satisfies (ε₁ + ε₂)-differential privacy. This property forces system architects to track a cumulative privacy loss ledger, ensuring the total epsilon across all queries does not exceed the global privacy budget allocated to a data subject.

When differentially private computations are performed on disjoint subsets of a dataset, the total privacy cost is bounded by the maximum epsilon of any single computation, not the sum. For example, partitioning user data into isolated shards and querying each shard independently with ε-differential privacy results in an overall privacy cost of ε, not N×ε. This property is foundational to SISA training and efficient data sharding architectures.

Any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. An adversary with unlimited auxiliary computational power cannot reverse-engineer the private input from a differentially private output. This resilience to post-processing ensures that privacy is not contingent on keeping the output secret; the guarantee holds even if the noisy statistic is published publicly and subjected to arbitrary transformations.

Differential privacy naturally extends to protect groups of correlated individuals, such as a family sharing genomic data. If a mechanism provides ε-differential privacy for a single individual, it provides k×ε-differential privacy for a group of size k. This linear scaling highlights the inherent challenge of protecting clusters of highly correlated records and informs the design of privacy-preserving systems for relational or graph-based datasets.

The privacy loss parameter (ε) that quantifies the maximum allowable information leakage in a differential privacy system. A smaller epsilon (e.g., ε=0.1) provides stronger privacy guarantees but adds more noise, while a larger epsilon (e.g., ε=10) offers higher utility at the cost of weaker privacy. The epsilon budget is cumulative—every query against a dataset consumes a portion of the budget, and once exhausted, no further queries can be answered without risking privacy violations. This concept is central to privacy accounting in systems like the US Census Bureau's 2020 disclosure avoidance system.

The integration of differential privacy into federated learning systems, where models train on decentralized data without raw data leaving local devices. The DP-FedAvg algorithm clips per-client model updates and adds calibrated Gaussian noise before aggregation, providing user-level differential privacy. This ensures the final global model does not memorize any individual client's contribution. Deployed in production by:

• Apple for QuickType keyboard suggestions (ε=4 per user)
• Google for Gboard next-word prediction (ε=0.9 per user)
• Firefox for telemetry analysis with RAPPOR

A cryptographic technique that allows computation directly on encrypted data without decryption, producing encrypted results that decrypt to the correct output. While differential privacy adds noise to outputs, homomorphic encryption protects data during computation. The two are complementary:

• Homomorphic encryption protects data in transit and during processing
• Differential privacy protects against inference from the output itself Combined, they enable end-to-end privacy-preserving computation where neither the raw data nor the output reveals individual records. The trade-off is computational overhead—fully homomorphic operations can be 10,000x slower than plaintext.

A formal guarantee that a machine unlearning algorithm has bounded the influence of deleted data points within a provable mathematical threshold, often derived from differential privacy principles. This extends DP beyond query-time guarantees to post-deletion guarantees:

• Exact unlearning provides a model distribution identical to retraining from scratch
• Certified removal provides a DP-style bound (ε, δ) on the difference between the unlearned model and a retrained model
• Enables compliance with the Right to be Forgotten under GDPR and CCPA without costly full retraining This is an active research area combining DP accounting with efficient model patching.

A privacy principle mandating that only data strictly necessary for a specific purpose be collected and retained. Differential privacy provides the mathematical framework to operationalize this principle:

• Collection minimization: DP noise can be applied at ingestion to limit what raw data enters the system
• Retention minimization: DP guarantees degrade gracefully as data ages, supporting automated expiration
• Usage minimization: The epsilon budget enforces a hard limit on how many queries can extract information This aligns with Article 5(1)(c) of GDPR and forms the technical backbone of privacy-by-design architectures.