Differential Privacy (DP)

The privacy budget, denoted by epsilon (ε), is the single most important parameter in Differential Privacy. It quantifies the maximum allowable privacy loss for any individual in the dataset. A smaller ε provides a stronger privacy guarantee but typically reduces the utility (accuracy) of the query's output. The budget is tracked and consumed across multiple queries; once exhausted, no further queries can be answered under the same DP guarantee. This enforces a fundamental privacy-utility trade-off.

The Laplace Mechanism is the canonical algorithm for providing ε-Differential Privacy for numeric queries (e.g., counts, sums, averages). It works by adding carefully calibrated noise drawn from a Laplace distribution to the true query result. The scale of the noise is proportional to the query's sensitivity (the maximum possible change in the output when a single individual's data is added or removed) and inversely proportional to ε. For a query with sensitivity Δ, adding noise from Lap(Δ/ε) guarantees ε-DP.

• Example: Publishing the average salary in a company with DP. The sensitivity is bounded by the maximum possible salary. Noise from Lap(max_salary/ε) is added to the true average before release.

The Gaussian Mechanism is an alternative to the Laplace Mechanism that adds noise drawn from a Gaussian (Normal) distribution. It is often preferred in practice, especially for high-dimensional queries like gradient computations in machine learning, because the sum of Gaussian noises remains Gaussian, simplifying analysis. It provides (ε, δ)-Differential Privacy, a slightly relaxed guarantee that allows a small probability δ of privacy failure. The noise variance is scaled by the sensitivity and the parameters (ε, δ).

The Exponential Mechanism is used for non-numeric queries where the output is a discrete object, such as selecting the best candidate from a set (e.g., "which item is most frequent?" or "which hyperparameter is optimal?"). Instead of adding noise, it randomizes the selection process. The mechanism assigns a probability to each possible output, where the probability is exponentially higher for outputs that are more "useful" or have higher quality scores. The probability distribution is skewed by the privacy parameter ε and the sensitivity of the quality score function.

This distinction defines where the privacy mechanism is applied.

• Global Differential Privacy (Central DP): A trusted curator holds the entire raw dataset. The curator applies a DP mechanism (like Laplace or Gaussian) to the query results before releasing them. This model is common in organizational settings where aggregated statistics are released.

• Local Differential Privacy (LDP): Each individual user perturbs their own data on their device before sending it to an untrusted server. This provides a stronger privacy guarantee as the server never sees true data. LDP is used in scenarios like Google's RAPPOR for browser telemetry collection or Apple's emoji suggestions, where the data collector is not fully trusted.

Composition is the mathematical rule for calculating the total privacy cost when multiple differentially private mechanisms are applied to the same dataset. It is essential for designing complex, multi-step algorithms (like training a model over many iterations).

• Sequential Composition: If you run mechanisms with guarantees ε₁ and ε₂, the total privacy cost is at most ε₁ + ε₂.
• Advanced Composition: Provides a tighter (better) bound for the composition of many mechanisms, especially with the Gaussian mechanism, where the privacy loss grows more slowly than a simple sum.
• Parallel Composition: If mechanisms are applied to disjoint subsets of the data, the overall privacy cost is only the maximum of the individual ε values, not the sum. This is a powerful tool for efficient algorithm design.

The strength of a Differential Privacy guarantee is quantified by a parameter called epsilon (ε), known as the privacy budget. It is a mathematical bound on how much the probability of any output can change if a single individual's data is added or removed from the dataset.

• Lower ε = Stronger Privacy: An ε of 0.1 provides a very strong guarantee, while an ε of 10 is weaker but may allow for more accurate model outputs.
• Composition: The privacy budget is consumed with each query or training step. Advanced composition theorems track the total ε spent across multiple operations.
• Trade-off: There is an inherent privacy-utility trade-off. Adding more noise (lower ε) increases privacy but can reduce the accuracy or utility of the model's outputs.

The Laplace Mechanism is a fundamental algorithm for achieving Differential Privacy for numerical queries. It works by adding carefully calibrated noise drawn from a Laplace distribution to the true output of a computation.

• Noise Scale: The amount of noise added is proportional to the sensitivity of the query (the maximum change a single data point can cause) and inversely proportional to the desired ε.
• Example: Calculating the average salary in a company with DP. The mechanism would compute the true average, then add Laplace noise. An analyst sees a plausible, slightly perturbed figure, but cannot confidently determine if any specific individual's salary influenced the result.

Differentially Private Stochastic Gradient Descent (DP-SGD) is the primary algorithm for training deep neural networks with DP guarantees. It modifies standard SGD to bound each individual's influence on the model.

• Gradient Clipping: Per-sample gradients are clipped to a maximum norm, limiting any single data point's impact.
• Noise Injection: Gaussian noise is added to the aggregated, clipped gradients before the model weights are updated.
• Privacy Accounting: A formal accountant (like the Moments Accountant) tracks the cumulative privacy loss (ε) across all training iterations, ensuring the total does not exceed the pre-defined budget.

DP can be applied in two primary trust models, defining where the noise is added.

• Central Differential Privacy: Trusted curator (server) collects raw data, applies DP algorithms, and releases results. This model offers better utility for a given privacy budget but requires trusting the data aggregator.
• Local Differential Privacy (LDP): Each user adds noise to their own data before sending it to the server. This provides a stronger, trust-minimized guarantee (the server never sees true data) but typically requires more noise, reducing utility. LDP is common in industry for data collection (e.g., Apple's iOS, Google's Chrome).

DP is a critical enhancement to Federated Learning (FL), which trains models on decentralized devices. While FL keeps raw data local, the shared model updates can still leak information.

• DP-FL: Clients add DP noise to their local model updates (gradients or weights) before sending them to the central server for aggregation.
• Enhanced Guarantee: This combines the data minimization of FL with the formal, mathematical guarantee of DP, creating a robust privacy-preserving machine learning pipeline suitable for highly sensitive domains like healthcare (Healthcare Federated Learning).
• Secure Aggregation: Often used in conjunction with Secure Aggregation protocols, which allow the server to compute the sum of noisy updates without seeing individual values.

Implementing DP effectively requires navigating several practical challenges.

• Privacy-Utility Trade-off: Finding the right ε balance for the application is crucial. Too much noise renders the model useless.
• Hyperparameter Tuning: Parameters like clipping norm and noise multiplier in DP-SGD require careful tuning, often via privacy-preserving hyperparameter optimization.
• Composition & Budget Management: For complex, multi-stage ML pipelines, tracking the total privacy expenditure across data preprocessing, training, and evaluation is non-trivial.
• Verification: Unlike encryption, DP guarantees are statistical and probabilistic, making external verification of an implementation's correctness challenging.

A specific cryptographic protocol used in Federated Learning that allows a central server to compute the sum of client model updates without being able to inspect any individual client's contribution.

• Core Mechanism: Clients encrypt their updates in a way that only their sum can be decrypted by the server. If a client drops out, their secret share can be recovered by the remaining clients.
• Role in Privacy: Prevents the server from performing model inversion or membership inference attacks on individual updates. It is a complementary technique to DP, which adds noise to the aggregated result.
• Primary Benefit: Provides input privacy during the aggregation phase of FL.

The quantifiable limits on privacy loss in Differential Privacy, defined by the parameters epsilon (ε) and delta (δ).

• Epsilon (ε): The primary privacy parameter. A smaller ε means stronger privacy (more noise), as it bounds the log-likelihood ratio of any output occurring with or without an individual's data. Often called the privacy loss parameter.
• Delta (δ): A small probability that the pure ε-DP guarantee might fail. It accounts for a tiny chance of catastrophic privacy leakage. For rigorous guarantees, δ should be cryptographically small (e.g., less than the inverse of the dataset size).
• Management: The budget is consumed each time a query is answered on the data. A key challenge is budget accounting across multiple queries or training steps to prevent exhaustion.