Gaussian Mechanism

Unlike the Laplace Mechanism which satisfies pure ε-differential privacy, the Gaussian Mechanism satisfies approximate (ε, δ)-differential privacy. The δ parameter represents a small failure probability—a negligible chance that the privacy guarantee is violated by more than a factor of e^ε. This relaxation allows the Gaussian Mechanism to add noise scaled to the L2 sensitivity rather than the L1 sensitivity, resulting in significantly less noise for high-dimensional queries. For a query with d dimensions, Gaussian noise scales with √d while Laplace noise scales with d, making the Gaussian Mechanism the default choice for deep learning gradients.

The Gaussian Mechanism calibrates noise to the L2 (Euclidean) sensitivity of the query function—the maximum change in the output vector's Euclidean norm when a single record is added or removed. This is fundamentally different from the Laplace Mechanism's reliance on L1 sensitivity. For a function f with L2 sensitivity Δ₂(f), the mechanism outputs f(D) + N(0, σ²I) where σ = Δ₂(f) · √(2 ln(1.25/δ)) / ε. The L2 sensitivity is always less than or equal to the L1 sensitivity, and for high-dimensional data, this difference becomes dramatic, enabling practical privacy budgets.

The Gaussian Mechanism composes gracefully under both sequential and parallel composition. Under k-fold adaptive composition, the total privacy loss accumulates according to advanced composition theorems. The moments accountant, introduced by Abadi et al. (2016) for differentially private SGD, tracks the privacy loss random variable's moment-generating function to provide tight (ε, δ) bounds. This enables training deep neural networks with meaningful privacy guarantees over thousands of iterations. The Rényi Differential Privacy (RDP) framework further refines composition analysis by converting Gaussian Mechanism applications to RDP and back.

The Gaussian Mechanism is the foundational building block of Differentially Private Stochastic Gradient Descent (DP-SGD), the dominant algorithm for private deep learning. In each training step:

• Per-example gradients are computed and clipped to a maximum L2 norm C
• Gaussian noise N(0, σ²C²I) is added to the summed clipped gradients
• The model is updated with the noisy gradient This ensures that the contribution of any single training example is masked by calibrated Gaussian noise, protecting against membership inference and gradient leakage attacks while still allowing the model to learn population-level patterns.

A critical property exploited in practice: when the Gaussian Mechanism is applied to a random subsample of the dataset rather than the full dataset, the privacy guarantee is amplified. If each record is included in the batch with probability q, the effective ε is reduced by approximately a factor of q. This privacy amplification by subsampling is essential for DP-SGD, where each step operates on a randomly sampled mini-batch. The combination of subsampling amplification and the moments accountant enables training large models with ε ≈ 8 while maintaining utility, compared to ε ≈ 100+ without subsampling.

The Gaussian Mechanism is asymptotically optimal for queries with bounded L2 sensitivity under (ε, δ)-differential privacy. No other mechanism can achieve lower expected squared error while satisfying the same privacy guarantee. This optimality result, proven through the Gaussian isoperimetric inequality, establishes the Gaussian Mechanism as the canonical choice for vector-valued queries. In federated learning, where model updates are high-dimensional gradient vectors, this optimality directly translates to better model accuracy for a given privacy budget compared to any alternative noise distribution.

The foundational alternative to the Gaussian Mechanism that satisfies pure ε-differential privacy (δ=0). It adds noise drawn from a Laplace distribution calibrated to the L1 sensitivity of the query function.

• Optimal for counting queries and histograms
• Produces stronger privacy guarantees (no δ failure probability)
• Gaussian is preferred for high-dimensional vector outputs due to L2 sensitivity scaling

The privacy loss parameters that define the strength of (ε, δ)-differential privacy. Epsilon bounds the multiplicative divergence between outputs on neighboring datasets. Delta is a failure probability allowing the guarantee to be violated with probability δ.

• Smaller ε = stronger privacy (typical range: 0.1 to 10)
• δ should be cryptographically small (<< 1/n)
• Gaussian Mechanism requires δ > 0; Laplace achieves δ = 0

The maximum change in a query's output when a single record is added or removed. The Gaussian Mechanism uses L2 sensitivity (Euclidean norm), making it ideal for high-dimensional gradient vectors in federated learning.

• L1 sensitivity: Sum of absolute changes (Laplace Mechanism)
• L2 sensitivity: Euclidean distance of change (Gaussian Mechanism)
• Proper calibration prevents both under-noising (privacy violation) and over-noising (utility destruction)

A finite resource tracking cumulative privacy loss across multiple queries. Each invocation of the Gaussian Mechanism consumes budget proportional to ε. Composition theorems (basic, advanced, Rényi) bound total leakage.

• Sequential queries sum their privacy loss
• Rényi DP provides tighter composition for Gaussian noise
• Budget exhaustion requires data access termination

A cryptographic protocol that computes the sum of client model updates in federated learning without revealing individual contributions. When combined with the Gaussian Mechanism, it provides two-layer defense: the server sees only the aggregated, noise-perturbed result.

• Uses secret sharing or homomorphic encryption
• Prevents gradient leakage attacks
• Complements DP by hiding individual updates before noise addition

A relaxation of differential privacy based on the Rényi divergence that provides tighter composition bounds for Gaussian noise mechanisms. RDP is the preferred accounting method for differentially private stochastic gradient descent (DP-SGD).

• Converts to (ε, δ)-DP via a simple lemma
• Avoids the looseness of advanced composition
• Standard in modern DP libraries (Opacus, TF Privacy)