The Gaussian mechanism is a fundamental tool for achieving epsilon-delta differential privacy by adding Gaussian noise calibrated to the L2 sensitivity of a query. It is presented in Appendix A of DWORK2014 and further analyzed under the Renyi differential privacy framework by MIRONOV2017.
For an arbitrary d-dimensional function f: N^|X| → R^d with L2 sensitivity Delta_2_f = max_{adjacent x,y} ||f(x) - f(y)||_2, the Gaussian mechanism is defined as:
G_sigma(f(D)) = f(D) + (eta_1, …, eta_d), where eta_i ~ N(0, sigma^2) i.i.d.
The mechanism achieves (epsilon, delta)-differential privacy when the noise parameter sigma satisfies sigma >= c * Delta_2_f / epsilon, where c^2 > 2 * ln(1.25 / delta) (Theorem A.1 in DWORK2014). This is often written as sigma >= sqrt(2 * ln(1.25/delta)) * Delta_2_f / epsilon.
Under the RDP framework, the Gaussian mechanism has an especially clean characterization: if f has sensitivity 1, then G_sigma satisfies (alpha, alpha / (2 * sigma^2))-RDP for all alpha >= 1 (Corollary 3 in MIRONOV2017). This yields a straight-line budget curve in alpha, making composition analysis particularly simple — n compositions of Gaussian mechanisms with parameter sigma behave like a single Gaussian mechanism with parameter sigma / sqrt(n).
The Gaussian mechanism is the noise injection method underlying most certified unlearning algorithms. In Certified Machine Unlearning via Noisy Stochastic Gradient Descent, Gaussian noise is added to each SGD step. In Certified Unlearning for Neural Networks, noise is added after gradient clipping or model clipping steps, and the privacy analysis proceeds via the RDP characterization of the Gaussian mechanism combined with privacy amplification by iteration.
Key Details
- Uses L2 sensitivity (not L1 sensitivity as in the Laplace mechanism), which is often much smaller for high-dimensional queries since ||v||_2 ⇐ ||v||_1
- Cannot satisfy pure epsilon-DP (delta = 0) because the Gaussian distribution has unbounded support, so there always exist outputs with non-zero probability under one database and near-zero under another
- The privacy proof partitions the noise space into a “good” region R_1 = {x : |x| ⇐ c * Delta_f / epsilon} where the privacy loss is bounded by epsilon, and a “bad” region R_2 where the tail probability is bounded by delta
- The privacy loss random variable is |1/(2sigma^2) * (2x*Delta_f + Delta_f^2)| where x ~ N(0, sigma^2) is the noise
- For the high-dimensional case, the proof reduces to the 1D case by projecting the noise onto the sensitivity vector v = f(x) - f(y), using the rotational symmetry of the multivariate Gaussian
- Under RDP (Proposition 7 in MIRONOV2017): D_alpha(N(0, sigma^2) || N(mu, sigma^2)) = alpha * mu^2 / (2 * sigma^2), directly yielding the (alpha, alpha / (2*sigma^2))-RDP guarantee for sensitivity-1 queries
- The Gaussian mechanism’s RDP curve is a straight line, in contrast to the Laplace mechanism’s more complex curve (involving log of a sum of exponentials)