Differential Privacy

The parameter epsilon (ε) is the central metric of privacy loss. A smaller ε (e.g., 0.1) provides stronger privacy by adding more noise, making outputs less dependent on any single record. A larger ε (e.g., 10) provides weaker privacy but higher accuracy. This budget is finite and consumed with each query.

• ε = 0: Perfect privacy, zero utility (pure noise).
• ε < 1: Strong privacy guarantee, suitable for sensitive data.
• ε > 10: Weak guarantee, high risk of information leakage.

When multiple differentially private queries are performed on the same dataset, the total privacy loss is the sum of the individual ε values. If you run query A with ε=0.5 and query B with ε=0.3, the total privacy cost is ε=0.8. This property forces careful accounting of the cumulative budget.

• Enables privacy accounting across complex workflows.
• Prevents unlimited querying from eroding protections.
• Requires a privacy accountant module in production systems.

When queries operate on disjoint, non-overlapping subsets of data, the total privacy cost is the maximum of the individual ε values, not the sum. Partitioning data by user ID and querying each partition independently incurs only the cost of a single query.

• Critical for scaling privacy to large, sharded databases.
• Enables efficient federated analytics across isolated data silos.
• Relies on strict guarantees of data disjointness.

Any computation or transformation applied to the output of a differentially private mechanism cannot weaken the privacy guarantee. An adversary cannot reverse-engineer the noise or extract additional information through arbitrary post-processing. The privacy protection is future-proof.

• Outputs can be safely published, visualized, or used in ML training.
• No need to control downstream analysis once noise is calibrated.
• A foundational property for safe release of aggregate statistics.

Differential privacy naturally extends to protect groups of correlated individuals. If a mechanism provides ε-differential privacy for a single record, it provides k·ε privacy for a group of size k. This quantifies the increased risk when multiple family members or linked records are in the dataset.

• Explicitly models correlation risk in genomic or household data.
• Guides budget allocation when protecting clusters, not just individuals.
• Highlights the trade-off between group size and privacy strength.

The amount of noise required is determined by the sensitivity of the query function—the maximum change in output caused by adding or removing a single record. A query computing a sum has bounded sensitivity; a query returning a max value has unbounded sensitivity.

• L1 sensitivity: Used for Laplace mechanism, sum of absolute differences.
• L2 sensitivity: Used for Gaussian mechanism, Euclidean distance.
• Low-sensitivity queries consume less privacy budget for the same accuracy.

The privacy loss parameter that quantifies the maximum information leakage allowed by a differential privacy mechanism. A lower epsilon (e.g., ε = 0.1) provides stronger privacy guarantees but introduces more noise, reducing data utility. The budget is consumed cumulatively across queries—once exhausted, no further queries can be answered without risking re-identification. This composability property is fundamental to designing privacy-preserving systems that remain mathematically bounded over time.

The foundational noise-injection algorithm for achieving ε-differential privacy on numerical queries. It adds random noise drawn from a Laplace distribution calibrated to the query's sensitivity—the maximum change in output when a single record is added or removed. For a query with sensitivity Δf, the mechanism adds noise scaled by Δf/ε, ensuring that outputs from neighboring datasets become statistically indistinguishable. This mechanism is optimal for L1 sensitivity queries like counts and sums.

An alternative noise-addition mechanism that draws from a Gaussian (normal) distribution rather than Laplace. It provides (ε, δ)-differential privacy, a relaxed definition where the pure ε-guarantee can fail with probability δ. The Gaussian mechanism is preferred for high-dimensional queries and iterative algorithms like differentially private stochastic gradient descent (DP-SGD) because its noise scales better with dimensionality under L2 sensitivity bounds.

A deployment model where noise is added on the user's device before data is transmitted to a central aggregator. Unlike the central model—which requires a trusted curator with raw data access—local DP ensures that no party ever sees the true data. This is the model used by Apple and Google for telemetry collection. The trade-off is significantly higher noise levels for equivalent privacy guarantees, as the randomization is applied per-user rather than across an entire dataset.

The process of determining a query's maximum output change when a single record is modified or removed. - Global sensitivity: Worst-case change across all possible neighboring datasets - Local sensitivity: Change specific to a given dataset instance - Smooth sensitivity: A smoothed upper bound on local sensitivity Sensitivity directly determines noise magnitude—queries with high sensitivity (e.g., median) require more noise than low-sensitivity queries (e.g., count).

A relaxation of pure differential privacy based on Rényi divergence rather than max-divergence. RDP provides tighter composition bounds when tracking privacy loss across multiple adaptive queries, making it especially useful for analyzing the privacy guarantees of DP-SGD training loops. It uses a continuous parameter α to interpolate between pure ε-DP and (ε, δ)-DP, offering more precise accounting than advanced composition theorems.