Differential Privacy

ε-Differential Privacy is the original, strongest definition. It provides a worst-case, multiplicative bound on how much the probability of any output can change if a single individual's data is added or removed from the dataset.

• Formal Guarantee: For any two adjacent datasets (D, D') differing by one record, and for any output set S, Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S].
• Interpretation: The parameter ε (epsilon) is the privacy budget. A smaller ε (e.g., 0.1) offers stronger privacy but adds more noise, reducing output utility. ε=0 offers perfect privacy but useless outputs.
• Example: A counting query (e.g., 'How many patients have disease X?') under ε-DP adds Laplace noise scaled to 1/ε.

(ε, δ)-Differential Privacy is a relaxed, more practical variant that allows a small additive probability δ of the privacy guarantee failing completely.

• Formal Guarantee: Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S] + δ.
• The δ Parameter: This represents a catastrophic failure probability. A typical, very small value is δ << 1/n, where n is the dataset size (e.g., δ = 10^-9). It is often interpreted as the probability that plain ε-DP is violated.
• Utility Advantage: This relaxation often enables the use of Gaussian noise instead of Laplace noise, which is more amenable to analysis in complex algorithms like deep learning. Many practical implementations, including those in TensorFlow Privacy, use (ε, δ)-DP.

Composition is the cornerstone of building complex DP algorithms from simpler ones. It quantifies how privacy loss accumulates when multiple queries are answered on the same data.

• Sequential Composition: If mechanism M1 is ε1-DP and M2 is ε2-DP, then releasing both results on the same data is (ε1 + ε2)-DP. Privacy budgets add up linearly.
• Advanced Composition: For (ε, δ)-DP, the composition is sub-linear. Running k mechanisms each with (ε, δ)-DP yields an overall (ε√(2k log(1/δ')), kδ + δ')-DP guarantee for a chosen δ'. This is far more efficient for many queries.
• Practical Implication: This allows system designers to track a privacy budget over the lifetime of a dataset (e.g., in a machine learning training loop) and halt queries when the budget is exhausted.

The Post-Processing Immunity property states that any function applied to the output of a differentially private mechanism cannot weaken its privacy guarantee.

• Formal Rule: If M is (ε, δ)-DP, and F is any arbitrary, data-independent function (deterministic or randomized), then F(M(D)) is also (ε, δ)-DP.
• Critical Implication: This makes differential privacy future-proof. Once data is released via a DP mechanism, analysts can freely analyze, transform, and combine it with other data without risk of violating the privacy of individuals in the original dataset.
• Example: If a DP algorithm releases a noisy average salary, an analyst can square that number, convert it to another currency, or use it as input to another public formula. None of these actions can leak more information about the original private records.

Group Privacy extends the core guarantee to protect the privacy of small groups within the dataset, not just individuals.

• Formal Guarantee: For datasets (D, D') differing by k records (a group of size k), an ε-DP mechanism provides kε-DP for that group. An (ε, δ)-DP mechanism provides (kε, δ')-DP for certain δ'.
• Interpretation: The privacy guarantee degrades linearly with group size. Protecting a group of 10 people requires a 10x stricter privacy budget (ε/10) to achieve the same per-person guarantee.
• Limitation & Design Consideration: This property highlights that DP is less effective at hiding information about large, correlated groups (e.g., all residents of a small town). System design must account for this, often by setting ε sufficiently small.

The Privacy Loss Random Variable is a precise tool for tracking the actual privacy cost of a complex, randomized algorithm. The Moments Accountant is a powerful technique built upon it.

• Privacy Loss (L): For a specific output o, L is defined as ln[Pr[M(D)=o] / Pr[M(D')=o]]. Its distribution captures the actual leakage.
• Moments Accountant: Instead of bounding L directly, this method bounds the log moments of its distribution (its moment generating function). This leads to much tighter composition bounds, especially for iterative algorithms like DP-Stochastic Gradient Descent.
• Result: It is the key innovation that made training deep neural networks with differential privacy feasible, converting a naive linear privacy budget explosion into a manageable, sub-linear growth.

These are the two primary models for applying differential privacy.

• Local Differential Privacy: Noise is added to individual data points before they are collected or sent to a central server. This provides the strongest privacy guarantee, as the curator never sees raw data. Used in scenarios like web browser telemetry collection (e.g., Google's RAPPOR).
• Central Differential Privacy: Trusted curator collects raw data, then adds noise to the output of an analysis (like a query or model update). This is more common in federated learning and statistical database releases, offering a better utility-privacy trade-off but requiring trust in the curator.

Epsilon (ε) is the single most important parameter in differential privacy, quantifying the privacy loss or privacy guarantee. It's a non-negative real number.

• Interpretation: A smaller ε means stronger privacy (more noise, less accurate outputs). A larger ε means weaker privacy (less noise, more utility).
• Composability: The privacy budget is consumable. Running multiple queries on the same dataset consumes ε. Advanced composition theorems track the total cumulative privacy loss across an entire analysis.
• Typical Values: In practice, ε values often range from 0.1 to 10, with values below 1 considered very strong privacy.

The Laplace Mechanism is the foundational algorithm for achieving differential privacy for numeric queries (e.g., counts, sums, averages).

• How it works: It adds noise drawn from a Laplace distribution to the true query result. The scale of the noise is proportional to the query's sensitivity (Δf) and inversely proportional to the desired ε.
• Sensitivity (Δf): The maximum possible change in the query's output when a single individual is added or removed from the dataset. High-sensitivity queries require more noise.
• Example: Releasing a differentially private average salary by adding Laplace noise calibrated to the salary range and chosen ε.

The Exponential Mechanism is used to achieve differential privacy for non-numeric, discrete outputs, like selecting the best candidate from a set of options.

• How it works: Instead of adding noise, it randomly samples an output from the set of all possible outputs. The probability of selecting any particular output is exponentially weighted by its utility score and the privacy parameter ε.
• Utility Function: A user-defined function that assigns a score to each possible output, measuring its quality or desirability.
• Example: Selecting the most common disease diagnosis from a set of medical records while protecting patient privacy. The mechanism will probabilistically favor high-utility (common) diagnoses.

Federated Learning is a decentralized training paradigm where models are trained across many devices (clients) holding local data, and only model updates (gradients) are shared. Differential Privacy is a critical enhancement.

• DP-SGD (Differentially Private Stochastic Gradient Descent): The standard algorithm. During training on each client, gradients are clipped to bound sensitivity, and Gaussian noise is added before the updates are sent to the central server for aggregation.
• Privacy Guarantee: This ensures that the final aggregated model does not reveal whether any specific data point was present on any participating device.
• Use Case: Training a next-word prediction model on user smartphones without accessing individual typing histories.

Homomorphic Encryption (HE) is a complementary cryptographic technique to differential privacy for privacy-preserving ML. It allows computations to be performed directly on encrypted data.

• Core Difference: While DP adds noise to protect individuals in aggregate outputs, HE provides a computational guarantee—the server performing the computation learns nothing about the underlying data or the result.
• Synergy with DP: HE can be used to securely aggregate data from multiple parties before applying DP. For example, clients can send encrypted model updates; the server aggregates them in encrypted form, decrypts the sum, then adds DP noise.
• Trade-off: HE provides stronger privacy in theory but is currently far more computationally intensive than DP, limiting its use in large-scale deep learning.