Differential Privacy Fundamentals

Understanding the mathematical building blocks of differential privacy: the privacy parameters epsilon and delta, noise mechanisms, sensitivity, and how privacy composes across multiple analyses.

Epsilon and Delta

The two parameters that define the strength of a differential privacy guarantee:

• Epsilon (ε): The privacy loss parameter. Smaller epsilon means stronger privacy. Common values range from 0.1 (very private) to 10 (weak privacy). Think of e^ε as the maximum ratio by which the probability of any output can change when one person's data is added or removed.
• Delta (δ): The probability that the privacy guarantee fails. Should be cryptographically small, typically less than 1/n where n is the dataset size. Often set to 10^-5 or smaller.

Sensitivity

Sensitivity measures how much a function's output can change when one person's data is added or removed. It determines how much noise is needed:

import numpy as np

# L1 Sensitivity (for Laplace mechanism)
# Δf = max |f(D) - f(D')| over all neighboring D, D'

# Example: counting query has sensitivity 1
# Adding/removing one person changes count by at most 1
sensitivity_count = 1

# Example: sum of values in range [0, B] has sensitivity B
# One person can contribute at most B to the sum
sensitivity_sum = B  # where B is the upper bound

# Example: mean of n values in [0, B] has sensitivity B/n
sensitivity_mean = B / n

# L2 Sensitivity (for Gaussian mechanism)
# Δf_2 = max ||f(D) - f(D')||_2
# Used when adding multidimensional noise

Noise Mechanisms

Laplace Mechanism

Adds noise drawn from a Laplace distribution. Provides pure ε-differential privacy (no delta):

def laplace_mechanism(true_answer, sensitivity, epsilon):
    """Add Laplace noise for epsilon-DP."""
    scale = sensitivity / epsilon
    noise = np.random.laplace(loc=0, scale=scale)
    return true_answer + noise

# Example: private count with epsilon = 1.0
true_count = 1000
private_count = laplace_mechanism(true_count, sensitivity=1, epsilon=1.0)
# Result: approximately 1000 ± 1 (noise scale = 1/1 = 1)

Gaussian Mechanism

Adds Gaussian noise. Provides (ε, δ)-DP and is often preferred for high-dimensional data:

def gaussian_mechanism(true_answer, sensitivity_l2, epsilon, delta):
    """Add Gaussian noise for (epsilon, delta)-DP."""
    sigma = sensitivity_l2 * np.sqrt(2 * np.log(1.25 / delta)) / epsilon
    noise = np.random.normal(loc=0, scale=sigma)
    return true_answer + noise

# Example: private mean with epsilon=1.0, delta=1e-5
true_mean = 42.5
private_mean = gaussian_mechanism(true_mean,
    sensitivity_l2=0.1, epsilon=1.0, delta=1e-5)

Composition Theorems

When you run multiple DP analyses on the same data, privacy degrades. Composition theorems quantify this:

• Basic composition: Running k analyses each with ε-DP gives kε-DP total. Simple but loose.
• Advanced composition: For k analyses each with ε-DP, the total is approximately ε√(2k ln(1/δ)) + kε(e^ε-1). Tighter for many queries.
• Rényi DP composition: Even tighter accounting using Rényi divergence. Used by modern DP libraries.
• Privacy Loss Distributions (PLD): The tightest known accounting method, tracking the full distribution of privacy loss.

The Privacy Budget

Your total privacy budget is the maximum epsilon you are willing to spend across all analyses. Once exhausted, no more queries can be answered privately. Key considerations:

• Allocate budget across analyses based on their importance
• Use tight composition to maximize the number of queries
• Consider the Sparse Vector Technique for threshold queries
• Track cumulative privacy loss rigorously