Differential Privacy

The parameter epsilon (ε) quantifies the privacy loss permitted by a mechanism. A smaller ε (e.g., 0.1) provides stronger privacy guarantees by injecting more noise, while a larger ε (e.g., 10) allows greater accuracy at the cost of weaker privacy.

• ε = 0: Perfect privacy, but zero utility—output is pure noise.
• ε < 1: Strong privacy regime, suitable for sensitive census or medical data.
• ε > 1: Weaker guarantees; risk of information leakage increases.

The choice of ε is a policy decision balancing utility against the theoretical risk of re-identification.

When multiple differentially private queries are executed on the same dataset, the total privacy loss accumulates additively. If query A satisfies ε₁-differential privacy and query B satisfies ε₂-differential privacy, the combined release satisfies (ε₁ + ε₂)-differential privacy.

• This property forces a hard limit on the total number of queries allowed against a dataset.
• A privacy accountant tracks cumulative ε consumption to prevent budget exhaustion.
• Without composition theorems, an attacker could average multiple noisy outputs to reconstruct the underlying record.

Any arbitrary computation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. Once noise has been calibrated and injected, no downstream analysis—whether statistical modeling, visualization, or machine learning—can reverse the privacy protection.

• This property is resilience to arbitrary post-processing.
• It holds regardless of the complexity or adversarial nature of the post-processing function.
• Enables safe sharing of privatized data with untrusted third parties for analysis.

Standard differential privacy protects against the presence or absence of a single individual's record. Group privacy extends this guarantee to cohorts of size k: a mechanism that is ε-differentially private for one individual is kε-differentially private for a group of k individuals.

• Protecting a family of four requires a privacy budget 4× larger than protecting an individual.
• This linear degradation highlights the difficulty of hiding correlated or clustered records.
• Critical consideration when datasets contain multiple records per entity (e.g., longitudinal health data).

The foundational implementation of differential privacy for numeric queries. Given a query function f and sensitivity Δf (the maximum change in output when one record is added or removed), the Laplace mechanism adds noise drawn from a Laplace distribution centered at zero with scale Δf/ε.

• Sensitivity (Δf): For a counting query, Δf = 1; for a sum query, Δf = the maximum possible value.
• Higher sensitivity demands more noise to achieve the same ε guarantee.
• Optimal for low-sensitivity, real-valued queries like counts and averages.

An alternative noise injection method that adds Gaussian (normal) noise instead of Laplace noise. It satisfies a relaxed definition called (ε, δ)-differential privacy, where δ represents a small probability of catastrophic privacy failure.

• Allows tighter composition bounds over many queries compared to pure ε-differential privacy.
• δ is typically chosen to be cryptographically small (e.g., 10⁻⁶) and much smaller than 1/N, where N is dataset size.
• Preferred in high-dimensional machine learning applications like differentially private stochastic gradient descent (DP-SGD).

The privacy loss parameter that quantifies the strength of the differential privacy guarantee. A lower epsilon (e.g., ε=0.1) provides stronger privacy by injecting more noise, while a higher epsilon (e.g., ε=10) provides weaker privacy but greater accuracy.

• Composition theorems track cumulative privacy loss across multiple queries
• The privacy budget is exhausted when the total epsilon reaches a pre-defined threshold
• Typical enterprise deployments use ε values between 0.1 and 1.0 for sensitive data

Two architectural models for implementing differential privacy. Local differential privacy adds noise on the user's device before data collection, ensuring the raw data never leaves the device. Central differential privacy relies on a trusted curator to collect raw data and add noise to query results.

• Apple uses local DP for emoji and typing suggestions in iOS
• The US Census Bureau uses central DP for the 2020 Census
• Local DP requires more noise to achieve the same privacy level as central DP

The maximum influence a single record can have on a query's output. Sensitivity determines how much noise must be added to satisfy a given epsilon guarantee.

• Global sensitivity: The worst-case change across all possible datasets
• Local sensitivity: The maximum change for a specific dataset instance
• Low-sensitivity queries (e.g., counts) require less noise than high-sensitivity queries (e.g., medians)

The two primary noise-injection algorithms used to achieve differential privacy. The Laplace mechanism adds noise drawn from a Laplace distribution and is optimal for ε-differential privacy. The Gaussian mechanism adds noise from a normal distribution and is used for (ε, δ)-differential privacy, which allows a small failure probability δ.

• Laplace noise scales with L1 sensitivity (Δf/ε)
• Gaussian noise scales with L2 sensitivity
• The Gaussian mechanism is preferred for high-dimensional queries

A privacy-preserving machine learning architecture that combines federated learning with differential privacy. Models are trained on decentralized data, and differentially private noise is added to the gradient updates before aggregation.

• Google's Gboard uses this technique for next-word prediction
• Provides both data minimization (raw data stays local) and provable privacy (gradients are DP-protected)
• The DP-FedAvg algorithm clips and noises model updates before central aggregation

A relaxation of pure differential privacy based on Rényi divergence that provides tighter composition bounds. RDP is particularly useful for tracking privacy loss during iterative algorithms like stochastic gradient descent.

• Offers tighter sequential composition than standard DP
• Converts to standard (ε, δ)-DP for final reporting
• Widely adopted in deep learning privacy libraries like Opacus and TensorFlow Privacy