Laplace Mechanism

The Laplace Mechanism satisfies the strictest definition of differential privacy—pure ε-differential privacy—with no δ failure probability. This means the privacy loss random variable is absolutely bounded by ε, providing an ironclad mathematical guarantee that an adversary cannot distinguish between outputs from neighboring datasets. Unlike approximate mechanisms such as the Gaussian Mechanism, there is zero probability of catastrophic privacy failure.

Noise magnitude is calibrated to the L1 sensitivity (Δf) of the query function—the maximum absolute difference in output when a single record changes, measured as the sum of absolute changes across all output dimensions. For a counting query, Δf = 1. For a histogram with k bins, Δf = 2. The scale parameter b = Δf/ε directly determines the variance of the Laplace distribution: larger sensitivity or tighter privacy budgets demand more noise.

Random noise is drawn from the Laplace distribution centered at zero with scale b = Δf/ε. The probability density function is f(x|b) = (1/2b)exp(-|x|/b), producing heavier tails than a Gaussian. This exponential tail behavior is precisely what guarantees pure ε-differential privacy—the ratio of probabilities for any two outputs differing by at most Δf is bounded by exp(ε).

When multiple Laplace mechanisms are applied to the same dataset, the privacy budgets compose linearly: querying k times with ε₁, ε₂, ..., εₖ consumes a total budget of Σεᵢ. This is a fundamental property of pure differential privacy. A privacy accountant must track cumulative expenditure to ensure the total ε does not exceed the organization's predefined privacy budget threshold.

Any arbitrary computation applied to the noisy output of a Laplace Mechanism cannot weaken the privacy guarantee. An adversary with unlimited auxiliary information and computational power cannot reverse-engineer the noise or extract additional private information from the published result. This closure under post-processing makes the mechanism composable with downstream analytics, visualizations, and machine learning pipelines without additional privacy risk.

For real-valued queries with bounded L1 sensitivity, the Laplace Mechanism is optimal in terms of minimizing expected L1 error while satisfying ε-differential privacy. No alternative mechanism can achieve lower expected absolute error for the same privacy guarantee. This makes it the definitive choice for releasing differentially private counts, sums, and histograms in clinical research and federated analytics.

Epsilon (ε) is the privacy loss parameter that directly controls the magnitude of Laplace noise. A smaller ε (e.g., 0.1) forces the mechanism to add more noise, yielding a stronger privacy guarantee but lower data utility. The privacy budget is the total ε allocated across all queries on a dataset. Sequential composition causes budgets to sum: querying with ε=0.5 twice consumes a total budget of 1.0. Once the budget is exhausted, no further queries are permitted to prevent cumulative leakage.

The calibration constant that determines the scale of Laplace noise. Formally, it is the maximum L1 distance between the outputs of a query function on any two datasets differing by exactly one record. For a counting query, the sensitivity is 1. For a sum query on bounded data, it is the range of possible values. A higher sensitivity requires proportionally more noise to mask the impact of a single individual.

An alternative noise-adding mechanism that draws from a Gaussian (normal) distribution instead of Laplace. It satisfies the relaxed (ε, δ)-differential privacy, where δ is a small probability of catastrophic privacy failure. The Gaussian Mechanism is calibrated to the L2 sensitivity and is often preferred in high-dimensional settings or when composing many queries, as its noise scales more favorably under advanced composition theorems.

A deployment model where noise is added on the individual's device before data is transmitted to an untrusted aggregator. Unlike the central model where the Laplace Mechanism runs on a trusted server, LDP guarantees privacy even against a malicious data curator. Google's RAPPOR and Apple's iOS data collection use LDP. The trade-off is significantly higher noise magnitude for the same ε compared to the central model.

A fundamental property of differential privacy: any arbitrary computation applied to the output of an ε-differentially private mechanism does not degrade the privacy guarantee. Once the Laplace Mechanism releases a noisy statistic, an adversary can perform any analysis—machine learning, visualization, filtering—without reducing the ε protection. This ensures that privacy is a property of the mechanism, not the downstream use.