Differential Privacy

The epsilon parameter quantifies the maximum privacy loss allowed by a mechanism. Lower epsilon values provide stronger privacy guarantees.

• ε = 0.1: Very strong privacy, high noise
• ε = 1.0: Moderate privacy, balanced utility
• ε = 10: Weak privacy, minimal noise

Each query against a dataset consumes a portion of the total privacy budget. Once exhausted, no further queries can be answered without risking re-identification. This creates a formal, auditable constraint on data access.

The delta parameter represents the probability that the privacy guarantee fails catastrophically. In pure ε-differential privacy, δ = 0, meaning absolute protection.

In (ε, δ)-approximate differential privacy, a small δ allows for more efficient mechanisms while accepting a negligible chance of privacy breach. Typical values are cryptographically small:

• δ < 1/n² where n is dataset size
• Ensures no individual faces meaningful additional risk
• Enables the Gaussian mechanism for practical deployments

Sensitivity measures how much a single individual's data can change a query's output. It determines the amount of noise required to achieve a given epsilon.

Global Sensitivity (GS): The maximum possible change across all neighboring datasets. Used by the Laplace mechanism.

Local Sensitivity (LS): The maximum change for a specific dataset instance. Enables data-dependent noise calibration but risks leaking information about the dataset itself.

• Low sensitivity queries (counts, averages) require less noise
• High sensitivity queries (medians, maxima) demand more noise
• Smooth sensitivity bridges global and local approaches safely

The Laplace mechanism achieves pure ε-differential privacy by adding noise drawn from a Laplace distribution calibrated to the query's global sensitivity.

Noise scale: b = GS / ε

• Optimal for L1 sensitivity and single numeric queries
• Produces symmetric, exponentially-tailed noise
• Higher ε → tighter distribution → less noise
• Foundation of many privacy-preserving systems

Example: A count query with GS=1 and ε=0.1 adds Laplace(0, 10) noise, meaning the reported answer varies by ±10 from the true value.

The Gaussian mechanism achieves (ε, δ)-approximate differential privacy using normally distributed noise. It is preferred when composing many queries due to tighter cumulative privacy loss bounds.

Noise scale: σ = (GS × √(2 ln(1.25/δ))) / ε

• Optimal for L2 sensitivity and vector-valued queries
• Enables advanced composition theorems
• More efficient than Laplace for high-dimensional outputs
• Standard in deep learning with differential privacy (DP-SGD)

The δ parameter allows a small probability of exceeding the ε bound, trading a negligible failure chance for significantly improved utility.

Composition governs how privacy loss accumulates when multiple differentially private queries are executed on the same dataset. Two fundamental theorems exist:

Basic Composition: Running k mechanisms each with εᵢ-DP yields (Σ εᵢ)-DP total. Privacy loss adds linearly.

Advanced Composition: For (ε, δ)-DP mechanisms, the total privacy cost grows proportionally to √(k ln(1/δ')) rather than linearly, enabling many more queries before budget exhaustion.

• Enables practical iterative analysis workflows
• Critical for machine learning training loops
• Requires careful budget accounting and tracking

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) offers weaker privacy but greater utility.

• ε < 1: Considered strong privacy protection
• ε = 1-10: Moderate privacy, common in practical deployments
• ε > 10: Weak guarantee, approaching raw data release

The budget is consumed cumulatively across all queries against a dataset, requiring careful accounting in production systems.

The maximum possible change in a query's output when a single individual's record is added to or removed from the dataset. Sensitivity determines how much calibrated noise must be added to achieve a given epsilon guarantee.

• Counting queries: Δf = 1 (one person changes count by at most 1)
• Sum queries: Δf = maximum possible value of a single record
• Low sensitivity enables stronger privacy with less noise

Understanding sensitivity is critical for selecting the appropriate noise mechanism (Laplace vs. Gaussian) and calibrating the privacy-utility tradeoff.

The foundational noise injection method for achieving pure ε-differential privacy on numerical queries. It adds random noise drawn from a Laplace distribution scaled by Δf/ε.

• Noise scale: b = Δf / ε
• Larger ε → smaller scale → less noise → weaker privacy
• Larger Δf → larger scale → more noise required

The Laplace mechanism is optimal for low-sensitivity counting queries but can degrade utility for high-sensitivity aggregations, where the Gaussian mechanism with (ε, δ)-differential privacy may be preferred.

Two distinct trust models for where noise is injected in the data pipeline:

Global DP (Central Model)

• A trusted curator collects raw data and adds noise to query outputs
• Provides higher utility at the same epsilon
• Requires trust in the central data holder

Local DP

• Each individual perturbs their own data before sharing
• No trusted curator required
• Requires significantly more noise to achieve the same privacy guarantee
• Used by Apple and Google for telemetry collection

A relaxation of pure differential privacy based on Rényi divergence that provides tighter composition bounds when analyzing the cumulative privacy loss across multiple queries. RDP is the mathematical backbone of modern privacy accounting in systems like TensorFlow Privacy and Opacus.

• Defined by order parameter α > 1
• Converts to (ε, δ)-DP for final reporting
• Enables tighter privacy budget tracking than basic composition theorems
• Critical for deep learning where thousands of training iterations consume budget

The broader category of techniques that enable model training and inference without exposing raw training data. Differential privacy is one pillar alongside:

• Federated Learning: Models train locally, only sharing encrypted gradient updates
• Homomorphic Encryption: Computation directly on encrypted data without decryption
• Secure Multi-Party Computation: Multiple parties jointly compute functions while keeping inputs private
• Synthetic Data Generation: Training on DP-guaranteed artificial data that preserves statistical properties

These methods are often composed together in production healthcare systems to provide defense-in-depth privacy protection.