Differential Privacy

The Laplace Mechanism is the canonical algorithm for achieving epsilon-differential privacy for real-valued queries. It works by adding noise drawn from a Laplace distribution, scaled to the query's sensitivity.

• Sensitivity (Δf): The maximum possible change in the query's output when a single individual's data is added or removed from the dataset. Noise scale is set to Δf / ε.
• Example: For a count query (sensitivity = 1) with ε = 0.1, noise is drawn from Laplace(scale=10). The true count of 150 might be reported as 147 or 152.
• Use Case: Ideal for aggregations like sums, averages, and counts where outputs are numeric.

The Gaussian Mechanism achieves (ε, δ)-differential privacy by adding noise drawn from a Gaussian (normal) distribution. It is used when the Laplace mechanism's noise is too heavy-tailed or when composing many mechanisms.

• Sensitivity & Scaling: Noise scale is proportional to the L2-sensitivity and a function of ε and δ. The formula is more complex than Laplace's.
• (ε, δ)-DP: This is a slightly relaxed guarantee, allowing a small probability δ (e.g., 1e-5) of a privacy violation. This often enables adding less noise than pure ε-DP.
• Use Case: Common in deep learning and iterative algorithms like DP-SGD (Differentially Private Stochastic Gradient Descent), where many queries are made on the same dataset.

The Exponential Mechanism is used for queries with non-numeric outputs, such as selecting the best item from a set. It provides epsilon-differential privacy by randomizing the selection process.

• Utility Function: A function that scores each possible output based on the dataset. A higher score means the output is more "useful" or accurate.
• Probability Distribution: The mechanism selects an output with a probability exponentially proportional to its utility score. High-scoring outputs are exponentially more likely to be chosen, but any output has a non-zero probability.
• Example: Choosing the most common medical diagnosis from a private dataset. The mechanism will strongly favor the true most common diagnosis but has a small chance of outputting a different one, providing privacy.

Composition theorems quantify how privacy guarantees degrade when multiple differentially private mechanisms are applied to the same data. They are essential for analyzing complex, multi-step algorithms.

• Sequential Composition: If mechanism M1 is ε1-DP and M2 is ε2-DP, then applying both sequentially satisfies (ε1 + ε2)-DP. The privacy budgets add.
• Advanced Composition: Provides tighter bounds for many compositions, especially with (ε, δ)-DP. The privacy loss grows roughly with the square root of the number of compositions.
• Parallel Composition: If mechanisms are applied to disjoint subsets of the data, the overall privacy guarantee is only the maximum of the individual ε values, not the sum. This is key for federated learning across clients.

Privacy loss accounting is the practice of meticulously tracking the cumulative privacy budget (ε, δ) consumed throughout an analysis. Tools like the Moments Accountant or Gaussian Differential Privacy (GDP) provide tight, implementable bounds.

• Moments Accountant: Used in DP-SGD, it allows for a much tighter composition bound than basic theorems by tracking the log moments of the privacy loss random variable.
• Renyi Differential Privacy (RDP): A different privacy definition that often enables cleaner composition. RDP guarantees can be converted to (ε, δ)-DP for final reporting.
• Use Case: Critical for iterative training algorithms. Without careful accounting, the final privacy guarantee would be too weak to be meaningful.

This distinction defines where the noise is added in the data pipeline, leading to different trust models and noise levels.

• Central DP (Trusted Curator Model): A trusted server holds the raw dataset. Noise is added to the outputs of queries on this dataset. This model allows for higher accuracy (utility) for the same privacy guarantee.
• Local DP: Each individual adds noise to their own data before sending it to the server. The server never sees true data. This requires no trusted central party but needs much more noise per individual, reducing utility.
• Federated Learning Context: Federated learning with a secure aggregation server often implements a central DP model. The server adds noise to the aggregated model update after receiving encrypted contributions from clients.

A cryptographic protocol that enables multiple parties to jointly compute a function over their private inputs while revealing nothing but the final output.

• Privacy Goal: Input privacy. No party learns anything about another's private data beyond what can be inferred from the function's output.
• Application in FL: Used for secure aggregation, where the server learns only the sum of client updates, not any individual contribution. This prevents the server from performing gradient leakage attacks.
• Key Difference from DP: SMPC is a cryptographic guarantee about the computation process, while DP is a statistical guarantee about the output's disclosure risk. They address different threat models.

A privacy attack aimed at determining whether a specific data sample was part of the training set of a machine learning model.

• Threat Model: An adversary with query access to a trained model attempts to infer if a given record was in its training data.
• Connection to DP: A primary risk DP is designed to mitigate. By formalizing and bounding privacy loss, DP provides provable protection against membership inference. A model satisfying (ε, δ)-DP limits the attacker's advantage in this attack.
• Real-World Impact: Successful attacks can reveal sensitive information, such as a patient's health condition being used to train a diagnostic model.

The fundamental tension in privacy-preserving machine learning where increasing the level of privacy protection typically comes at the cost of reduced model utility or accuracy.

• Mechanism: Adding more noise (for stronger DP guarantees) increases variance in model updates, which can slow convergence and reduce final model performance.
• Quantification: The privacy budget (ε) directly controls this trade-off. A smaller ε (stronger privacy) requires more noise, often hurting accuracy. The parameter δ represents a small probability of privacy failure.
• Engineering Challenge: A core task is to design algorithms that maximize accuracy for a given (ε, δ) privacy budget, using techniques like privacy amplification via subsampling or advanced composition theorems.

A variant of DP where each data owner perturbs their own data before sending it to a data curator, providing privacy even against the curator itself.

• Contrast with Central DP: In central DP, trusted curator applies noise after collecting raw data. In LDP, no entity ever sees the true raw data.
• Use Case: Ideal for high-trust-distrust scenarios, like telemetry collection from user devices (e.g., Google's RAPPOR). Each device adds noise locally.
• Trade-off: Typically requires more noise per individual to achieve the same privacy guarantee as central DP, as the curator cannot perform post-processing that reduces noise.