Differential Privacy (DP)

The parameter ε (epsilon) quantifies the privacy loss. A smaller ε (e.g., 0.1) provides stronger privacy by injecting more noise, while a larger ε (e.g., 10) provides weaker privacy but higher accuracy.

• Composition: Privacy loss accumulates across multiple queries; the total budget is the sum of individual ε values.
• Typical range: Real-world deployments often use ε between 0.1 and 1.0 for sensitive data.
• Interpretation: With ε = 0.1, an adversary can update their belief about any individual by at most a factor of e^0.1 ≈ 1.105.

Global sensitivity measures the maximum change in a query's output when a single record is added or removed from the dataset. This determines the scale of noise required.

• Counting queries: Sensitivity = 1 (a single record changes the count by at most 1).
• Sum queries: Sensitivity = the maximum absolute value a single record can contribute.
• Clipping: Bounding individual contributions reduces sensitivity, enabling less noise for the same privacy guarantee.

Calibrated random noise is drawn from specific probability distributions to achieve the formal guarantee:

• Laplace Mechanism: Adds noise from the Laplace distribution scaled by sensitivity/ε. Optimal for L1 sensitivity and pure ε-differential privacy.
• Gaussian Mechanism: Adds Gaussian noise scaled by L2 sensitivity. Provides the relaxed (ε, δ)-differential privacy guarantee, where δ is a small failure probability.
• Exponential Mechanism: For non-numeric outputs, selects results with probability proportional to exp(ε × utility / 2 × sensitivity).

A critical property: any computation applied to the output of a differentially private algorithm does not degrade the privacy guarantee. An adversary cannot increase privacy loss by post-processing the released results.

• Enables safe release of noisy statistics, model weights, or synthetic data.
• Allows downstream analysts to apply arbitrary transformations without consuming additional privacy budget.
• This holds regardless of the complexity of the post-processing function.

Differential privacy naturally extends to protect groups of correlated individuals. If a mechanism provides ε-differential privacy for a single record, it provides kε-differential privacy for any group of size k.

• Implication: Protecting a family of 4 under ε = 0.1 provides group privacy of ε = 0.4.
• Trade-off: Stronger group protection requires a smaller per-individual ε budget.
• Relevance: Critical for genomic data where relatives share genetic information.

Two deployment architectures define where the noise is injected:

• Central DP (Curator Model): A trusted server collects raw data and adds noise to query responses. Provides high accuracy with a given ε.
• Local DP (LDP): Each user randomizes their own data before transmission. No trusted server is required, but accuracy degrades significantly for the same ε.
• Shuffle Model: An intermediate approach where a shuffler permutes randomized reports, amplifying privacy through anonymity.

The privacy loss parameter that quantifies the maximum divergence between outputs from neighboring datasets. A smaller epsilon (e.g., ε=0.1) provides stronger privacy guarantees by limiting information leakage.

• Composition: Sequential queries consume the budget additively
• Advanced composition: Allows for a tighter bound using the square root of k
• Practical ranges: ε=0.01-1 for high privacy; ε=1-10 for moderate utility

Once the cumulative ε exceeds a predefined threshold, the data access must be terminated to maintain the provable guarantee.

The maximum influence a single record can have on a query's output. Global sensitivity measures the worst-case change across all possible neighboring datasets.

• L1 Sensitivity: Maximum absolute difference in query results; used for Laplace noise calibration
• L2 Sensitivity: Euclidean distance between query outputs; used for Gaussian mechanism calibration
• Smooth sensitivity: A data-dependent relaxation that avoids worst-case noise for typical datasets

Sensitivity directly scales the noise magnitude: higher sensitivity requires more noise to achieve the same ε guarantee.

The foundational DP mechanism that adds noise drawn from a Laplace distribution calibrated to the L1 sensitivity and privacy budget. It satisfies pure ε-differential privacy.

• Noise scale: b = Δf / ε
• Optimal for: Counting queries, histograms, and low-dimensional linear queries
• Limitation: Adds excessive noise for high-sensitivity queries

For a count query with sensitivity 1 and ε=0.5, the mechanism adds Laplace(2) noise, ensuring the output distribution changes by at most a factor of e^0.5 between neighboring datasets.

A relaxed DP mechanism adding Gaussian noise calibrated to L2 sensitivity, satisfying (ε, δ)-approximate differential privacy where δ represents a small failure probability.

• Noise scale: σ = (Δf * √(2*ln(1.25/δ))) / ε
• Advantage: Tighter composition properties than Laplace for iterative algorithms
• Use case: Gradient perturbation in DP-SGD for deep learning

The δ parameter allows a tiny probability (e.g., 10^-5) of catastrophic privacy failure, enabling significantly better utility than pure ε-DP for high-dimensional data.

The workhorse algorithm for training deep learning models with differential privacy guarantees. It clips per-example gradients and adds calibrated Gaussian noise before each parameter update.

• Gradient clipping: Bounds the L2 norm of each sample's gradient to limit sensitivity
• Noise multiplier: Determines the privacy-utility tradeoff per training step
• Moments accountant: Tracks the cumulative privacy loss across iterations with tight bounds

DP-SGD enables training generative models like GANs and VAEs on sensitive patient data while providing formal privacy guarantees against membership inference.

A relaxation of pure DP based on Rényi divergence that provides tighter composition analysis for iterative algorithms. It interpolates between pure ε-DP and (ε, δ)-DP.

• Order α: Controls the moment of the privacy loss random variable
• Conversion: RDP guarantees can be converted to (ε, δ)-DP bounds
• Advantage: Significantly tighter privacy accounting for DP-SGD compared to the moments accountant

RDP has become the standard privacy accounting framework in modern libraries like Opacus and TF Privacy, enabling more efficient use of the privacy budget.