Laplace Mechanism

The mechanism's noise is scaled by the L1 sensitivity (Δf) of the query function. This metric quantifies the maximum absolute difference in the query's output when a single record is added or removed from any possible dataset.

• Definition: Δf = max ||f(D) - f(D')||₁ for adjacent datasets D, D'.
• Counting Queries: A simple count has a sensitivity of 1.
• Sum Queries: A sum bounded by [0, B] has a sensitivity of B.
• Utility Impact: Higher sensitivity requires more noise, reducing output accuracy.

Noise is drawn from the Laplace distribution centered at zero with a scale parameter b = Δf/ε. This specific distribution ensures the pure ε-differential privacy guarantee holds.

• Probability Density: (1/2b) * exp(-|x|/b).
• Sharp Peak: The distribution has a sharp central peak and heavier tails than a Gaussian, making it ideal for L1 sensitivity.
• Scale Parameter: A smaller ε (stricter privacy) increases the scale b, adding more noise.
• Mathematical Guarantee: For any output set S, Pr[M(D) ∈ S] ≤ e^ε * Pr[M(D') ∈ S].

The Laplace Mechanism satisfies pure ε-differential privacy, the strongest and most interpretable form of the privacy definition. It does not rely on the relaxation parameter δ (delta) used in approximate differential privacy.

• Interpretable Bound: The privacy loss is strictly bounded by a multiplicative factor of e^ε.
• Composition: The privacy budget ε is consumed linearly under basic sequential composition.
• Contrast with Gaussian: The Gaussian Mechanism provides (ε, δ)-approximate DP, which allows for a small probability δ of the strict ε bound being violated.

The mechanism is designed for real-valued numerical queries. It is the optimal mechanism for releasing a single scalar statistic under L1 sensitivity constraints.

• Ideal Use Cases: Histogram counts, sums of bounded attributes, and averages (with sensitivity adjustment).
• Non-Ideal Use Cases: Categorical outputs or complex optimization results are better served by the Exponential Mechanism.
• Post-Processing Immunity: Any function applied to the noisy output after the noise is added does not degrade the privacy guarantee.

When multiple Laplace mechanisms are run on the same dataset, the total privacy loss is the sum of the individual ε values. This linear composition property is fundamental to privacy budget accounting.

• Budget Management: A total budget of ε_total = 1.0 can be split into k queries, each with ε_i = 1.0/k.
• Advanced Composition: While pure composition is linear, advanced composition theorems provide tighter bounds for Gaussian mechanisms but do not improve the linear bound for pure ε-DP.
• Parallel Composition: If queries operate on disjoint subsets of the data, the total privacy cost is the maximum ε among the queries, not the sum.

For a single counting query with sensitivity 1, the Laplace Mechanism is provably optimal in minimizing the expected absolute error for a given ε. No other ε-differentially private mechanism can achieve a lower expected error.

• Expected Error: E[|error|] = 1/ε.
• Minimax Optimal: It minimizes the maximum possible error across all possible datasets.
• Practical Implication: For a privacy budget of ε = 0.1, the expected absolute error in a count is ±10 individuals.

The overarching mathematical framework that provides provable privacy guarantees by injecting calibrated statistical noise into computations. The Laplace Mechanism is the canonical instantiation of ε-differential privacy for numerical queries, ensuring the output distribution is nearly identical whether or not any single individual's record is included in the dataset.

An alternative fundamental mechanism that achieves (ε, δ)-differential privacy by adding noise drawn from a Gaussian distribution calibrated to the L2 sensitivity of the query function. Unlike the Laplace Mechanism, which provides pure ε-differential privacy, the Gaussian Mechanism offers relaxed privacy with tighter composition under repeated queries, making it the preferred choice for DP-SGD training.

The critical calibration step that determines the maximum change in a query's output caused by adding or removing a single record from the input dataset. For the Laplace Mechanism, this is the L1 sensitivity—the maximum absolute difference in the query result across all adjacent datasets. The noise scale parameter b is set to Δf / ε, directly linking sensitivity to the privacy guarantee.

A quantifiable limit on the total privacy loss permitted over a series of differentially private operations. Each invocation of the Laplace Mechanism consumes a portion of this budget proportional to its ε value. The budget enforces a hard upper bound on information leakage: once exhausted, no further queries can be answered without violating the privacy guarantee.

A defense strategy that adds calibrated noise directly to a model's output predictions or confidence vectors to mask statistical differences exploited by membership inference attacks. The Laplace Mechanism is the classic output perturbation technique: noise is drawn from Lap(Δf/ε) and added to the true query result before release, ensuring the published value does not betray the presence of any individual.

A relaxation of standard differential privacy based on Rényi divergence that provides tighter composition bounds than the basic Laplace Mechanism composition theorem. While the Laplace Mechanism satisfies pure ε-differential privacy, tracking its cumulative privacy loss under RDP accounting yields more accurate estimates of the total privacy expenditure, enabling more queries within the same effective budget.