Laplace Mechanism

The L1 sensitivity of a query is the maximum absolute difference in the output when a single record is added or removed. It directly determines the scale parameter b of the Laplace noise: b = Δf / ε. A query that counts records has a sensitivity of 1; a sum query bounded by M has a sensitivity of M. Calibrating noise to sensitivity is what makes the mechanism adaptive and prevents over-perturbation.

The Laplace mechanism achieves pure ε-differential privacy, the strongest and most interpretable form of the guarantee. For any two neighboring datasets D and D', and any output set S, the probability ratio Pr[M(D) ∈ S] / Pr[M(D') ∈ S] ≤ e^ε. The Laplace distribution's exponential tail shape is the unique distribution that satisfies this multiplicative bound exactly, making it the optimal mechanism for L1-sensitive queries.

While the Laplace mechanism provides pure ε-DP, the Gaussian mechanism provides the relaxed (ε, δ)-DP guarantee. The key trade-off: Gaussian noise decays faster in the tails, adding less noise for high-confidence queries, but introduces a failure probability δ. Use Laplace when you need the strictest possible guarantee; use Gaussian when composing many queries and tighter composition under the Central Limit Theorem is beneficial.

When you apply the Laplace mechanism k times to the same dataset, the total privacy loss accumulates. Under basic sequential composition, the total epsilon is k * ε. Under advanced composition, it grows proportionally to √(k * ln(1/δ)). This is why tracking a privacy budget is critical: each Laplace query consumes a portion of the total allowable epsilon, and the budget must be enforced by a privacy odometer.

A crucial property: any computation applied to the noisy output of the Laplace mechanism cannot weaken the privacy guarantee. You can round, threshold, or transform the result arbitrarily without consuming additional privacy budget. This means you can safely post-process a noisy count to ensure it's non-negative or an integer, or feed it into a visualization, without any privacy loss. The guarantee is future-proof against any downstream analysis.

The Laplace mechanism is designed for numerical queries. When you need to select a discrete option—like the best split point in a decision tree or a category label—use the Exponential Mechanism. It assigns selection probabilities proportional to exp(ε * utility / (2 * sensitivity)). Both mechanisms are foundational, but Laplace handles continuous outputs while the Exponential Mechanism handles categorical selection with a defined utility function.