Differential Privacy

The core parameter epsilon (ε) quantifies the maximum allowable privacy loss. A smaller ε provides stronger privacy guarantees but typically reduces the utility (accuracy) of the output. The mechanism is designed so that the probability of any output changes by at most a factor of e^ε whether any single individual's data is included or excluded from the dataset.

• ε = 0.1: Very strong privacy, low utility.
• ε = 1.0: Common balance for many applications.
• ε = 10.0: Weaker privacy, higher utility. The budget is consumed with each query; once exhausted, no further queries can be answered without violating the guarantee.

These are the primary randomized algorithms for achieving differential privacy by adding calibrated noise to query outputs.

• Laplace Mechanism: Adds noise drawn from a Laplace distribution. Ideal for counting queries and queries with low sensitivity (the maximum change a single record can cause). The scale of the noise is Δf / ε, where Δf is the sensitivity.
• Gaussian Mechanism: Adds noise from a Gaussian (normal) distribution. Used for high-dimensional queries like machine learning gradients. It requires a slightly relaxed (ε, δ)-differential privacy guarantee, where δ is a small probability of privacy failure.

These rules govern how privacy loss accumulates when multiple differentially private analyses are performed on the same dataset.

• Sequential Composition: The epsilons of k sequential queries add up. Total ε = ε₁ + ε₂ + ... + εₖ. This is why a privacy budget must be managed.
• Advanced Composition: Provides a tighter bound for the cumulative privacy loss, especially for many queries (k is large), often yielding a total ε that grows roughly with √k.
• Parallel Composition: If queries are performed on disjoint subsets of the data, the overall privacy loss is only the maximum ε used on any one subset, not the sum.

Differential privacy can be applied in two fundamental architectural models.

• Local Model: Each user adds noise to their own data before sending it to the data collector. Provides the strongest user-side privacy, as the collector never sees raw data. Used in Google's RAPPOR for browser data collection. Typically requires more noise per user, reducing aggregate accuracy.
• Central Model: Users send raw (or encrypted) data to a trusted curator. The curator applies the differentially private algorithm to the complete dataset and releases the noisy result. This model allows for much higher accuracy for the same ε but requires trust in the curator.

The standard algorithm for training machine learning models with differential privacy guarantees.

Key modifications to standard SGD:

1. Per-example Gradient Clipping: The gradient for each training example is clipped to a maximum L2 norm C. This bounds the sensitivity of the model update.
2. Noise Addition: Gaussian noise is added to the average of the clipped gradients in each training batch.
3. Privacy Accounting: A tool like the Moment Accountant or GDP Accountant is used to precisely track the cumulative (ε, δ) privacy budget spent over all training steps. This is foundational for private model training in frameworks like TensorFlow Privacy.

A crucial property that any function applied to the output of a differentially private mechanism cannot weaken its privacy guarantee.

• Implication: Analysts can freely perform additional computations, create visualizations, or build secondary models on top of a differentially private output without needing further privacy analysis.
• Example: A DP query releases a noisy count of patients with a condition. An analyst can then safely calculate a derived statistic, like a percentage of the total (using another DP total), or feed the noisy count into a non-private forecasting model. The final result remains (ε, δ)-differentially private. This property enables flexible and complex data workflows while maintaining the core guarantee.

A form of encryption that allows computations to be performed directly on encrypted data, producing an encrypted result that, when decrypted, matches the result of operations performed on the plaintext. This enables secure outsourced computation where a cloud server can process data without ever decrypting it.

• Key Use Case: Training machine learning models on encrypted healthcare or financial records.
• Trade-off: Provides stronger privacy guarantees than differential privacy but incurs significant computational overhead, making it less practical for large-scale, iterative training.

A decentralized machine learning approach where the model is trained across multiple client devices (e.g., smartphones, edge sensors) holding local data samples. The central server only receives aggregated model updates (gradients), not raw data.

• Core Mechanism: Clients compute updates on local data; a secure aggregation protocol combines updates to improve the global model.
• Synergy with DP: Often combined with differential privacy by adding noise to the client updates before aggregation, providing a strong privacy guarantee against inference attacks on the update stream.

A cryptographic protocol that enables a group of distrusting parties to jointly compute a function over their private inputs while revealing nothing but the final output. No single party learns another's input.

• Example: Multiple hospitals can compute the average patient treatment cost without sharing any individual patient records.
• Contrast with DP: SMPC provides perfect privacy for a specific computation but is not designed for repeated queries on the same dataset, where differential privacy's privacy budget is a more suitable control mechanism.

The process of creating artificial datasets that mimic the statistical properties and patterns of a real, sensitive dataset. The synthetic data should be privacy-preserving (contain no real individual records) and useful for downstream training or analysis.

• Methods: Often uses generative models like Generative Adversarial Networks (GANs) or diffusion models trained under differential privacy constraints.
• Enterprise Application: Allows data sharing for development and testing without legal or compliance risks, serving as a privacy-enhancing technology (PET).

A quantifiable, cumulative limit on the amount of privacy loss an individual can incur from their data's inclusion in a differentially private analysis. The parameter epsilon (ε) directly controls the strength of the privacy guarantee.

• Mechanism: Each query consumes a portion of the budget. Once exhausted, no further queries are permitted, preventing privacy loss accumulation.
• Engineering Implication: System designers must implement privacy accounting to track budget consumption across all analyses, a critical component of production DP systems.

Two fundamental models defining where noise is added in the data pipeline.

• Local Differential Privacy: Noise is added to an individual's data on their device before it is sent to a central collector. This provides a stronger trust model (untrusted server) but typically requires more noise per individual, reducing aggregate utility.
• Central Differential Privacy: Trusted curator collects raw data and applies noise after aggregation. This provides better utility for the same privacy guarantee but requires trust in the data curator.
• Choice: Dictates system architecture and trust assumptions for multi-agent data collection.