Laplace Mechanism

The mechanism scales noise proportionally to the L1 sensitivity (Δf) of the query function. Sensitivity is the maximum absolute difference in the query's output caused by adding or removing a single record from the dataset.

• Formula: Noise ~ Lap(0, Δf/ε)
• Intuition: Queries with high sensitivity (e.g., counting a single outlier) require more noise to mask the impact of one individual.
• Example: A counting query has Δf = 1. A sum query on a bounded attribute has Δf = the bound.

Unlike approximate mechanisms, the Laplace Mechanism satisfies the strictest definition of pure ε-differential privacy with δ = 0. This provides an unqualified, worst-case guarantee.

• Guarantee: For any two neighboring datasets D and D', the probability ratio of any output is bounded by e^ε.
• No Failure Probability: There is zero chance of a catastrophic privacy breach, unlike (ε, δ)-mechanisms.
• Gold Standard: This is the foundational building block for all composable privacy-preserving queries.

For real-valued queries with a single output, the Laplace Mechanism is minimax-optimal for pure ε-differential privacy. No other mechanism can achieve a lower expected error while satisfying the same privacy guarantee.

• Error Bound: Expected absolute error is Δf/ε.
• Trade-off: Accuracy improves linearly as ε increases (weaker privacy) or as sensitivity decreases.
• Limitation: Optimality holds for L1 error metrics; other mechanisms may be superior for different loss functions or high-dimensional outputs.

The privacy loss of multiple Laplace queries on the same dataset accumulates linearly under basic composition. This necessitates careful privacy budget management.

• Rule: k queries, each with privacy parameter ε_i, consume a total budget of Σ ε_i.
• Advanced Composition: Tighter bounds exist but may introduce a small δ, transitioning to approximate DP.
• Strategy: Analysts must pre-allocate a finite privacy budget and halt queries once it is exhausted to prevent total privacy loss.

Any arbitrary computation applied to the noisy output of the Laplace Mechanism cannot weaken the privacy guarantee. This post-processing immunity is a defining property of differential privacy.

• Implication: Results can be rounded, normalized, or visualized without additional privacy cost.
• Safety: Even if an attacker obtains the noisy output, no downstream transformation can reverse the noise injection.
• Contrast: This property does not hold for ad-hoc anonymization techniques like k-anonymity.

The Laplace Mechanism is the standard primitive for releasing differentially private histograms and contingency tables. Each bin count is independently perturbed.

• Sensitivity: Adding or removing a user changes at most one bin count, so Δf = 1 per bin.
• Sparsity Issue: For high-dimensional histograms, adding independent noise to many empty bins destroys utility. Smoothing or post-processing is often required.
• Use Case: The U.S. Census Bureau uses this mechanism for releasing noisy tabulations in the 2020 Decennial Census.

A double-exponential probability distribution centered at zero with scale parameter b. Its heavy tails ensure that extreme noise values occur with non-negligible probability, masking outliers.

• PDF: (1/2b) * exp(-|x|/b)
• Why Laplace?: It is the optimal distribution for L1 sensitivity; no other distribution provides pure ε-DP with less expected noise
• Calibration: Noise ~ Lap(0, Δf/ε)

The formal rule governing cumulative privacy loss when multiple queries are answered. Under basic sequential composition, querying k times with the Laplace Mechanism consumes kε total budget.

• Sequential Composition: ε_total = Σ ε_i
• Parallel Composition: Queries on disjoint data partitions incur no additional cost
• Advanced Accounting: Moments Accountant and RDP provide tighter bounds than naive summation, but the Laplace Mechanism's pure ε-DP simplifies analysis

A resilience property guaranteeing that any computation applied to a Laplace-noised output cannot degrade the privacy guarantee. This is a critical advantage for practical system design.

• Implication: Analysts can round, clamp, or transform noisy results arbitrarily without consuming additional privacy budget
• Contrast: This holds for pure ε-DP but requires care under approximate (ε, δ)-DP
• Use case: Safely post-processing census counts into percentages or visualizations

The alternative noise mechanism that adds Gaussian noise calibrated to L2 sensitivity. It achieves only approximate (ε, δ)-DP, not pure ε-DP like the Laplace Mechanism.

• Key difference: Gaussian tails decay faster, adding less noise for high-dimensional queries but introducing a δ failure probability
• When to prefer Laplace: When pure ε-DP is required for regulatory compliance or when L1 sensitivity is naturally low
• When to prefer Gaussian: For high-dimensional vector queries where L2 sensitivity is significantly smaller than L1