Laplace Mechanism

The Laplace mechanism provides pure ε-differential privacy (ε-DP), a strong guarantee with no failure probability (δ = 0). This means the output distribution changes by at most a multiplicative factor of e^ε when a single individual's data is added or removed. The guarantee is unconditional and holds for all possible outputs and all possible neighboring datasets.

The mechanism adds noise drawn from a Laplace distribution centered at zero. The critical parameter is the scale (b) of this distribution, calculated as b = Δf / ε, where:

• Δf is the L1 sensitivity of the function f.
• ε is the privacy budget. The L1 sensitivity (Δf) is the maximum absolute change in f's output over all neighboring datasets: Δf = max_{D, D'} ||f(D) - f(D')||₁. Higher sensitivity or a stricter privacy budget (smaller ε) requires larger noise (larger b).

The mechanism is designed for real-valued or vector-valued functions. For a function f that outputs a number or a d-dimensional vector, the private output is computed as: M(D) = f(D) + (Y₁, Y₂, ..., Yₙ) where each Yᵢ is an independent random variable drawn from Laplace(0, Δf/ε). This additive structure makes it simple to implement and analyze. It is ideally suited for counting queries, sums, averages (after sensitivity adjustment), and histograms.

A critical property inherited from differential privacy is post-processing immunity. Any further computation performed on the output of the Laplace mechanism, without access to the original raw data, cannot weaken its privacy guarantee. Formally, if M(D) is ε-differentially private, then for any arbitrary function g (deterministic or randomized), g(M(D)) is also ε-differentially private. This allows for safe secondary analysis, transformation, or visualization of the noised results.

The Laplace mechanism is often contrasted with the Gaussian mechanism.

• Privacy Type: Laplace provides pure (ε, 0)-DP; Gaussian provides approximate (ε, δ)-DP (δ > 0).
• Sensitivity Norm: Laplace uses L1 sensitivity; Gaussian uses L2 sensitivity.
• Noise Distribution: Laplace noise has heavier tails (double-exponential decay); Gaussian noise has lighter tails (quadratic exponential decay).
• Use Case: Laplace is the default for one-shot queries with pure DP guarantees. Gaussian is often preferred for high-dimensional queries or iterative algorithms like DP-SGD, where its L2 sensitivity and composition properties via Rényi DP are more favorable.

In federated learning, a Laplace mechanism variant can be applied to provide client-level differential privacy. The core steps are:

1. Local Clipping: Each client clips their model update (e.g., weight delta) using an L1 norm bound C.
2. Noise Addition: The client adds Laplace(0, C/ε_client) noise to each coordinate of their clipped update.
3. Secure Aggregation: The noised updates are sent to the server for aggregation. This ensures that the server's view of the aggregate update satisfies ε-DP, protecting the participation of any single client. The privacy budget ε is consumed per training round and must be accounted for across rounds via privacy composition.

Differential privacy is the rigorous mathematical framework that defines and quantifies privacy loss. It provides a formal guarantee that the inclusion or exclusion of any single individual's data from a dataset has a negligible effect on the output of an analysis algorithm. The Laplace mechanism is one specific algorithm designed to satisfy this definition.

• Core Guarantee: An algorithm is (ε)-differentially private if for any two adjacent datasets differing by one record, the probability of any output is within a multiplicative factor of e^ε.
• Adversarial Model: Protects against an attacker with arbitrary auxiliary information.
• Post-Processing Immunity: Any computation on the output of a DP mechanism remains differentially private.

L1 Sensitivity is the maximum absolute change in the output of a function when a single individual's data is added or removed from the dataset. It is the crucial parameter that determines the scale of Laplace noise.

• Formal Definition: For a function f: D → ℝ^k, its L1 sensitivity Δf is Δf = max_{D, D'} ||f(D) - f(D')||₁, where D and D' are adjacent datasets.
• Noise Scaling: In the Laplace mechanism, noise is drawn from Laplace(0, Δf/ε). Higher sensitivity requires more noise to mask the contribution of any single record.
• Example: The query "count of patients with a condition" has an L1 sensitivity of 1, as adding/removing one patient changes the count by at most 1.

The Gaussian mechanism is the primary alternative to the Laplace mechanism for achieving (ε, δ)-differential privacy, a slightly relaxed guarantee. It adds noise drawn from a Gaussian (normal) distribution calibrated to the function's L2 sensitivity.

• Noise Distribution: Adds noise ~ N(0, σ²) where σ = (Δ₂f * √(2ln(1.25/δ)))/ε.
• L2 Sensitivity: Uses the maximum L2 norm (Euclidean distance) change in the function's output.
• Practical Use: Favored in high-dimensional settings like DP-SGD for machine learning because the sum of Gaussian noises remains Gaussian, simplifying composition analysis.

The privacy budget, parameterized by epsilon (ε), is a finite resource that quantifies the total allowable privacy loss across multiple queries or training steps. The Laplace mechanism consumes a portion of this budget.

• Interpretation: Smaller ε implies stronger privacy (more noise). A typical range for aggregate analyses is 0.1 to 10.
• Composition: Sequential applications of DP mechanisms consume the budget. Basic sequential composition states that k mechanisms each with (ε_i)-DP yield a total guarantee of (Σε_i)-DP.
• Management: Privacy accounting systems track cumulative ε expenditure to prevent exceeding the total allocated budget.

Differentially Private Federated Averaging is the direct application of mechanisms like Laplace or Gaussian noise within the federated learning paradigm. It provides client-level differential privacy, protecting whether a specific device participated in training.

• Client-Side Procedure: Each client clips their local model update (e.g., weight delta) to bound its sensitivity, adds calibrated noise, and sends the noised update to the server.
• Server-Side Aggregation: The server averages the noised client updates. The entire process satisfies DP due to the noise addition and the post-processing property.
• Key Trade-off: Increased noise (stronger privacy) reduces final model accuracy, creating a privacy-utility trade-off.

Local differential privacy is a distributed model where each data owner perturbs their own data before sending it to an untrusted curator. It is a stronger, client-side model compared to the central model assumed by the standard Laplace mechanism.

• Trust Model: No trusted central curator is needed; privacy is enforced on the user's device.
• Mechanisms: Often uses randomized response for categorical data or specialized LDP protocols for numeric queries.
• Comparison to Central DP: LDP typically requires significantly more noise per user to achieve the same ε guarantee, as the curator sees only already-noised data.