Differential Privacy (DP)

The epsilon (ε) parameter is the core mathematical bound that quantifies the maximum possible privacy loss from a single query. It defines the privacy budget.

• Definition: A randomized algorithm M is ε-differentially private if for all datasets D and D' differing by at most one record, and for all outputs S, the probability distributions satisfy: Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S].
• Interpretation: A smaller ε (e.g., 0.1, 1.0) provides a stronger privacy guarantee but typically adds more noise, reducing output utility. A larger ε (e.g., 10.0) allows for more accurate outputs but provides a weaker privacy guarantee.
• Budgeting: In practice, ε is a finite resource that is consumed by each query. The total ε across all queries must be tracked to ensure the overall privacy guarantee is not violated.

Sensitivity measures how much a single individual's data can change the output of a function. It directly determines the amount of noise that must be added to achieve differential privacy.

• Global Sensitivity (L1): For a function f: D → ℝ, the global sensitivity Δf is the maximum absolute change in f's output over all possible neighboring datasets: Δf = max_{D, D'} ||f(D) - f(D')||₁.
• Example: For a counting query (e.g., 'How many users have attribute X?'), the global sensitivity is 1, because adding or removing one record can change the count by at most 1.
• Role in Noise Addition: The scale of noise (e.g., from a Laplace or Gaussian distribution) is proportional to Δf/ε. Higher sensitivity functions require more noise to obscure the impact of any single record.

Composability guarantees that the privacy loss from multiple analyses accumulates in a predictable, linear way. This allows complex programs to be built from simpler differentially private building blocks.

• Sequential Composition: If mechanism M1 is ε₁-DP and M2 is ε₂-DP, then releasing both results on the same dataset satisfies (ε₁ + ε₂)-DP. The epsilons add up.
• Parallel Composition: If mechanisms M1...Mk are each ε-DP and are applied to disjoint subsets of the data, the overall release satisfies ε-DP. The privacy loss does not compound.
• Advanced Composition: Provides tighter bounds for many adaptive queries, showing that the total ε grows roughly with the square root of the number of queries under certain conditions (Gaussian noise).

Post-processing immunity is a critical property stating that any function applied to the output of a differentially private mechanism cannot weaken its privacy guarantee.

• Formal Guarantee: If M is ε-differentially private, then for any arbitrary function g (deterministic or randomized), the composed mechanism g(M(D)) is also ε-differentially private.
• Practical Implication: This allows safe downstream analysis. Once data is released with a DP guarantee, it can be freely analyzed, transformed, visualized, or used as input to another model without requiring new privacy calculations.
• Limitation: This immunity only holds if no additional sensitive data is used in the post-processing step. The guarantee applies only to the original DP output.

Group privacy extends the core definition to quantify the privacy loss when datasets differ by k records instead of just one.

• k-Group Privacy: If a mechanism is ε-differentially private, it is automatically (kε)-differentially private for datasets differing in up to k records.
• Implication: The privacy guarantee degrades linearly with group size. Protecting a family of 4 records requires a budget 4 times smaller (ε/4) to achieve the same per-individual guarantee as for a single person.
• Trade-off: This highlights a fundamental limit: providing strong privacy for large groups (e.g., all residents of a city) while maintaining high data utility is extremely challenging, as the required noise scale grows with k.

Differential privacy is achieved through specific randomized algorithms that add calibrated noise to query results or model training processes.

• Laplace Mechanism: For real-valued queries. Adds noise drawn from a Laplace distribution with scale Δf/ε. The workhorse for many counting and averaging tasks.
• Gaussian Mechanism: Uses Gaussian noise and requires a slightly relaxed (ε, δ)-DP definition. Often preferred for its finite variance and utility in advanced composition.
• Exponential Mechanism: For non-numeric queries (e.g., selecting the best option from a set). It assigns a probability to each output exponentially weighted by a utility score.
• Differentially Private Stochastic Gradient Descent (DP-SGD): The primary algorithm for training deep learning models with DP. It clips per-example gradients to bound sensitivity and adds Gaussian noise to the aggregated gradient updates.

These are the two primary models for applying DP guarantees. Local Differential Privacy (LDP) applies noise directly to individual data points before they are collected by the curator, offering a stronger privacy guarantee as the curator never sees raw data. Common in crowd-sourcing (e.g., Apple's iOS data collection). Central Differential Privacy (CDP) adds noise to the output of an analysis (e.g., a query or model update) after the curator has collected the raw data. This is more common in trusted database settings and allows for higher data utility but requires trust in the curator.

The core quantitative parameter in DP that measures the maximum permissible privacy loss. A smaller ε (e.g., 0.1) provides a stronger privacy guarantee but requires more noise, degrading utility. A larger ε (e.g., 10) allows for more accurate outputs but weakens the privacy guarantee. The budget is consumed with each query; once exhausted, no further queries can be answered under the same DP guarantee. Managing this budget across multiple analyses is a key engineering challenge.

A canonical and simple mechanism for achieving Local Differential Privacy. For a sensitive yes/no question, a respondent:

• Tells the truth with probability p.
• Lies with probability 1-p. The data curator can later statistically correct for the known noise to estimate the true population proportion, but cannot determine any individual's true answer. This is the foundational concept behind many LDP algorithms.

A complementary cryptographic technique to DP. HE allows computations to be performed directly on encrypted data, producing an encrypted result that, when decrypted, matches the result of operations on the plaintext. Unlike DP, which adds noise for privacy, HE provides perfect information-theoretic privacy but with significantly higher computational overhead. They are often used in tandem: DP for broad statistical releases, HE for secure multi-party computation on specific encrypted records.

A primary adversarial threat that DP is rigorously designed to defend against. In this attack, an adversary aims to determine whether a specific individual's data record was part of the training set for a machine learning model. By analyzing the model's outputs (e.g., its confidence scores on predictions), an attacker can sometimes infer membership. DP provides a provable upper bound on the success probability of any such attack, making membership inference effectively no better than random guessing.

A distributed training paradigm where model updates (gradients) are computed on local devices and only the updates—not the raw data—are sent to a central server for aggregation. While FL enhances privacy by keeping data decentralized, it is not inherently private; gradients can leak information. DP is frequently integrated with FL (DP-FL) by adding calibrated noise to the gradients before they leave the local device, providing a rigorous privacy guarantee for the federated training process.