Differential Privacy

The epsilon (ε) parameter is the central metric quantifying the privacy loss in a differentially private analysis. A lower epsilon (e.g., ε=0.1) provides a stronger privacy guarantee but introduces more noise, reducing data utility. A higher epsilon (e.g., ε=10) preserves more accuracy but offers a weaker guarantee. This budget is consumed with every query to a dataset, and once exhausted, no further analysis is permitted without risking re-identification. Managing this budget across complex, multi-step analyses is the primary engineering challenge of differential privacy.

The foundational mechanism for achieving ε-differential privacy on numerical queries. It works by computing the true answer to a query and then adding random noise drawn from a Laplace distribution. The scale of the noise is calibrated by the sensitivity of the query (how much the output can change if one record is added or removed) divided by epsilon.

• Sensitivity (Δf): The maximum possible change in the query's output caused by a single individual's data.
• Noise Scale: b = Δf / ε
• Example: For a counting query with sensitivity 1 and ε=0.5, noise with a scale of 2 is added. This mechanism is optimal for simple, low-sensitivity queries.

An alternative to the Laplace mechanism that adds noise from a Gaussian (normal) distribution. While the Laplace mechanism provides pure ε-differential privacy, the Gaussian mechanism provides a relaxed definition called (ε, δ)-differential privacy. The delta (δ) parameter represents a small probability that the pure ε-guarantee is violated. This mechanism is preferred in high-dimensional applications like differentially private stochastic gradient descent (DP-SGD) because the Gaussian distribution's tail properties compose more gracefully over many iterations of a training loop.

A mechanism designed for non-numerical queries where the goal is to select the 'best' discrete item from a set of options. Instead of adding noise to a value, it defines a utility function that scores how good each possible output is for the dataset. The mechanism then outputs an item with a probability proportional to exp(ε * utility_score / (2 * sensitivity)). This ensures that high-utility items are chosen more frequently, but the probabilistic selection masks the influence of any single record.

• Use Case: Selecting the optimal split point in a decision tree during private machine learning.
• Key Insight: It privatizes the selection process itself, not a computed statistic.

A fundamental theorem governing how the privacy budget degrades over multiple analyses. If you run a mechanism with privacy loss ε₁, followed by a mechanism with ε₂, the total privacy loss is at most ε₁ + ε₂. This is a worst-case bound that assumes the same dataset is used for all queries.

• Budget Accounting: A privacy engineer must track the cumulative epsilon spent.
• Consequence: Answering 10 queries with ε=0.1 each consumes a total budget of ε=1.0.
• Advanced Composition: Tighter bounds exist for Gaussian mechanisms, showing that total loss scales with √(k) * ε rather than k * ε for k queries, enabling more analysis under the same budget.

A powerful property stating that any computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. Once a result is made differentially private, an adversary can perform any arbitrary analysis, mapping, or transformation on that result without reducing the epsilon guarantee. This is a resilience property against linkage attacks and auxiliary information.

• Example: If a differentially private histogram is published, an attacker cannot reverse-engineer the original records by combining it with external datasets.
• Practical Impact: This allows safe, unlimited sharing and visualization of private outputs without further risk.

A cryptographic scheme enabling computation directly on encrypted data. Unlike differential privacy, which protects outputs through statistical noise, homomorphic encryption protects data in use by ensuring plaintext is never exposed to the compute layer. Fully Homomorphic Encryption (FHE) supports arbitrary computations on ciphertexts, producing encrypted results that decrypt to the correct output. This is critical for cloud-based AI inference on sensitive data where the model owner cannot be trusted with raw inputs.

A decentralized training paradigm where a global model is updated by aggregating gradients from distributed clients holding local data. Data never leaves the device; only encrypted model updates are shared. Differential privacy is often layered on top via the DP-FedAvg algorithm, which clips and noises client updates before aggregation to provide formal privacy guarantees against gradient leakage attacks. This combination is the standard for privacy-preserving on-device learning in production systems like Gboard.

The primary threat that differential privacy is mathematically designed to defeat. An adversary queries a trained model and analyzes confidence scores or loss values to determine if a specific record was in the training set. Overfitting exacerbates this vulnerability. Differential privacy provides a provable bound on an attacker's ability to distinguish training members from non-members, quantified by the privacy parameter ε (epsilon). A lower epsilon means stronger protection against this exact attack vector.

A syntactic privacy property ensuring each released record is indistinguishable from at least k-1 other records with respect to quasi-identifiers like ZIP code, age, and gender. While foundational, k-anonymity is vulnerable to homogeneity attacks and background knowledge attacks. Differential privacy supersedes it by providing a semantic, adversary-agnostic guarantee that holds regardless of auxiliary information an attacker possesses. It is often discussed as a historical stepping stone to formal privacy frameworks.

A protocol allowing multiple parties to jointly compute a function over their private inputs without revealing those inputs to each other. SMPC and differential privacy are complementary: SMPC protects inputs during computation, while differential privacy protects outputs from inference. In practice, they are combined in privacy-preserving analytics systems where organizations collaboratively compute aggregate statistics without exposing raw data, and noise is added to the final result before release.

The process of training generative models to produce artificial datasets that mimic the statistical distribution of real data. When trained with differentially private stochastic gradient descent (DP-SGD), the resulting synthetic data inherits formal privacy guarantees, allowing it to be shared freely without exposing individual records. This approach is increasingly used to bypass data access bottlenecks in regulated industries, though utility-privacy trade-offs remain a significant engineering challenge.