Laplace Mechanism

The scale of noise is directly proportional to the global sensitivity (Δf) of the query function. Sensitivity measures the maximum absolute difference in the query output when a single record is added or removed from the dataset.

• Counting queries: Δf = 1 (adding a user changes the count by at most 1)
• Sum queries: Δf = max value in the dataset
• Averaging queries: Δf = (max - min) / n Higher sensitivity requires more noise to mask the influence of any single individual.

The privacy parameter epsilon (ε) controls the strength of the guarantee. A smaller ε enforces stricter privacy by requiring the output distributions on neighboring datasets to be nearly indistinguishable.

• ε = 0.1: Strong privacy, high noise
• ε = 1.0: Moderate privacy
• ε = 10: Weak privacy, low noise Epsilon quantifies the privacy loss budget—the maximum amount of information an adversary can gain about any individual from the query result.

Noise is drawn from the Laplace distribution with scale parameter b = Δf / ε. The probability density function is: f(x | μ, b) = (1/2b) * exp(-|x - μ| / b)

• The distribution is symmetric around the mean (μ = 0 for centered noise)
• It has heavier tails than a Gaussian, providing stronger privacy guarantees
• The variance is 2b², meaning noise magnitude grows quadratically as sensitivity increases or epsilon decreases

When multiple queries are executed on the same dataset, the privacy budgets sum linearly. If k queries each use ε_i, the total privacy loss is Σ ε_i.

• Example: 3 queries with ε = 0.5 each consume a total budget of ε = 1.5
• This property forces careful budget accounting across an entire analysis session
• Advanced composition theorems provide tighter bounds for adaptive query sequences, but the linear bound remains the safe default for the Laplace mechanism

Any arbitrary computation applied to the noisy output of the Laplace mechanism cannot weaken the privacy guarantee. Once a result satisfies ε-differential privacy, no downstream analysis—filtering, rounding, machine learning, or visualization—can increase the privacy loss.

• This property is closed under composition
• Enables safe release of privacy-protected statistics to untrusted third parties
• Contrasts with de-identification techniques like k-anonymity, which are vulnerable to linkage attacks after release

The Laplace mechanism satisfies pure ε-differential privacy—the strongest formal definition. It does not require a delta (δ) failure probability parameter.

• Pure DP (ε): Absolute worst-case guarantee; no probability of catastrophic failure
• Approximate DP (ε, δ): Allows a small δ probability that the guarantee is violated; used by the Gaussian mechanism
• Pure DP is preferred for high-assurance applications like census data release, where even a tiny chance of exposure is unacceptable