The Discrete Gaussian for Differential Privacy

Clément L. Canonne; Gautam Kamath; Thomas Steinke

Source-linked AI summary

The Discrete Gaussian for Differential Privacy

Clément L. Canonne, Gautam Kamath, Thomas Steinke

arXiv:2004.00010v6Mar 31, 2020cs.DScs.CRstat.ML

TL;DR

Continuous Gaussian noise is difficult to represent exactly on finite computers, and numerical errors can destroy differential privacy. This paper introduces and analyzes discrete Gaussian noise, showing comparable privacy and accuracy while providing exact finite-computer sampling. The result supports its use for counting and other low-sensitivity integer-valued queries.

Problem
Continuous Gaussian noise cannot be exactly represented on finite computers, and finite-precision errors can catastrophically compromise differential privacy.
Method
The paper theoretically and experimentally analyzes the discrete Gaussian’s privacy, utility, and sampling, including exact sampling and comparisons with continuous Gaussian noise.
Results
The discrete Gaussian provides almost identical privacy guarantees and the same or slightly better accuracy than the continuous Gaussian, with an exact efficient sampler.
Takeaways & Limitations
Discrete Gaussian noise is applicable to privately answering counting queries and other low-sensitivity integer-valued queries on finite computers.
Takeaways & Limitations
The similarity between discrete and continuous Gaussians is technically non-trivial to prove, and basic linear-combination stability does not directly hold for the discrete counterpart.

Abstract

from arXiv · show

A key tool for building differentially private systems is adding Gaussian noise to the output of a function evaluated on a sensitive dataset. Unfortunately, using a continuous distribution presents several practical challenges. First and foremost, finite computers cannot exactly represent samples from continuous distributions, and previous work has demonstrated that seemingly innocuous numerical errors can entirely destroy privacy. Moreover, when the underlying data is itself discrete (e.g., population counts), adding continuous noise makes the result less interpretable. With these shortcomings in mind, we introduce and analyze the discrete Gaussian in the context of differential privacy. Specifically, we theoretically and experimentally show that adding discrete Gaussian noise provides essentially the same privacy and accuracy guarantees as the addition of continuous Gaussian noise. We also present an simple and efficient algorithm for exact sampling from this distribution. This demonstrates its applicability for privately answering counting queries, or more generally, low-sensitivity integer-valued queries.

1 Introduction

The paper introduces the discrete Gaussian as a finite-computer alternative to continuous Gaussian noise, addressing privacy risks from numerical approximations and interpretability issues for discrete queries. It shows that the discrete Gaussian retains essentially the continuous Gaussian’s privacy and utility while allowing exact, efficient sampling.

Motivation: Finite-precision implementations of continuous noise can catastrophically fail privacy, potentially revealing the noiseless value and enabling dataset reconstruction.The issue arises because continuous samples cannot be exactly represented on finite computers and low-order output bits may leak information.
Motivation: Discrete noise is natural for integer-valued queries such as counts, avoiding accuracy loss from adding noise to already-discrete outputs.If the query is not discrete, its value must be rounded before noise is added.
Contribution: The discrete Gaussian is designed to preserve the continuous Gaussian’s privacy and utility properties while being supported on the integers.The distribution is defined on integer outcomes and is presented as the paper’s central object of study.
Scope: The paper studies privacy, utility, and sampling, concluding that the discrete Gaussian addresses continuous noise’s finite-computer shortcomings.The investigation includes theoretical and empirical analyses and a comparison with discrete Laplace under composition.
Results: The paper reports that discrete Gaussian noise provides almost identical privacy guarantees to continuous Gaussian noise, including the same concentrated guarantee for sensitivity-1 integer-valued queries.For large scales, the approximate privacy guarantees are virtually the same; at smaller scales, discretization can make either distribution marginally stronger depending on parameters.
Results: Its variance is at most the corresponding continuous Gaussian variance, with comparable sub-Gaussian tails and numerically better utility than rounding continuous Gaussian samples.These utility results are stated for the analogous discrete and continuous Gaussian distributions.
Sampling: The paper gives a simple exact sampler using only uniform random bits, without real arithmetic or non-trivial function evaluations.The authors describe the sampler as efficient and provide open-source code, while noting that sampling is not considered a primary contribution.
Technical scope: The qualitative similarity between discrete and continuous Gaussians is technically non-trivial to establish and relies on tools including Poisson summation and Fourier analysis.Basic stability properties under linear combinations do not directly hold for the discrete counterpart, requiring involved approximate results.

2 Privacy

The paper establishes that discrete Gaussian noise provides concentrated and approximate differential privacy guarantees essentially matching those of continuous Gaussian noise. It also develops exact privacy bounds and computational approaches for evaluating multivariate guarantees, while noting practical and analytical limitations.

2.1 Concentrated Differential Privacy: The discrete Gaussian provides the same concentrated differential privacy guarantees as the continuous Gaussian.The result follows for sensitivity-bounded integer-valued queries and matches the continuous Gaussian bound.
2.2 Approximate Differential Privacy: Theorem 7 gives a tight approximate differential privacy bound for discrete Gaussian noise, including the smallest possible δ.For large σ, its guarantees are almost identical to the continuous Gaussian; discretization creates small differences at smaller scales.
2.2 Approximate Differential Privacy: Analytic upper bounds and Figure 1 show that discrete and continuous Gaussian guarantees are nearly identical for large σ.The comparison includes the optimal discrete-Gaussian δ, the continuous-Gaussian bound, analytic bounds, and concentrated-privacy bounds.
2.4 Sharp Approximate Differential Privacy Bounds for Multivariate Noise: The multivariate extension gives concentrated privacy guarantees governed by Euclidean sensitivity when coordinate scales match, or weighted Euclidean sensitivity otherwise.The analysis assumes independent Gaussian coordinates and also provides an exact approximate-privacy characterization.
2.4 Sharp Approximate Differential Privacy Bounds for Multivariate Noise: Direct evaluation of multivariate privacy-loss distributions can be impractical because truncated infinite sums grow exponentially with dimension.The paper proposes fast Fourier transforms to avoid repeated numerical integration; the transform computes the full modular distribution in nearly linear time.

3 Utility

The discrete Gaussian provides utility comparable to the continuous Gaussian while improving on rounded Gaussian noise, especially at small scales. Its variance is no larger, its tails have closely related bounds, and finer discretization reduces rounding error for non-integer queries.

Comparison with rounded Gaussian: The discrete Gaussian has strictly better utility than the rounded Gaussian, whose tail stochastically dominates the discrete Gaussian.The improvement is small for reasonable values of σ but more pronounced when σ is very small.
Variance and tails: The discrete Gaussian is subgaussian, with variance at most σ2 and tail bound P[X ≥ λ] ≤ e^(-λ2/2σ2) for λ ≥ 0.These bounds follow from its moment-generating-function bound and match the corresponding continuous Gaussian bounds except that the continuous case has equality.
Normalization constant: The normalization constant approaches the continuous Gaussian approximation for large σ, while both refined bounds approach 1 for small σ.The lower bound is empirically nearly tight across all σ > 0.
Variance and tails: Its variance is strictly smaller than that of the corresponding continuous Gaussian and asymptotically the same, with the largest improvements at small σ.The paper notes that small-scale improvements are not typical in differential-privacy applications but may be independently useful.
Variance and tails: Up to a small shift or a (1 + o(1)) multiplicative factor, discrete and continuous Gaussians have the same tails.Symmetry supplies analogous lower-tail bounds from the stated upper-tail result.
Discretization: For queries not naturally discrete, rounding before adding discrete noise introduces error, and choosing a smaller discretization step α reduces that error.The discrete Gaussian over αZ converges in distribution to the continuous Gaussian as α approaches zero.

4 Discrete Laplace

The section compares discrete Gaussian and discrete Laplace noise, emphasizing composition and privacy–utility trade-offs. Discrete Gaussian generally performs better under approximate privacy and many-query workloads, while Laplace retains advantages for pure privacy or few queries.

Discrete Laplace noise is supported on integers and provides pure (ε, 0)-differential privacy for sensitivity-1 values.
Discrete Gaussian noise has lighter tails and lower scale under high-degree composition, while discrete Laplace has subexponential tails and pure privacy.
Asymptotically, discrete Gaussian noise has half the variance of discrete Laplace noise for the same concentrated-privacy level.
For 100 counting queries with variance 50^2 per answer, discrete Gaussian privacy guarantees are better except when δ < 10^-45.
At approximate (1, 10^-6)-differential privacy, discrete Laplace has lower variance for k ≤ 10, but requires 69% more variance at k = 100.
Overall, discrete Gaussian offers the better privacy–utility trade-off except for few queries or requirements close to pure differential privacy.

5 Sampling

The paper presents exact discrete-Gaussian sampling on finite computers using uniformly random bits and rational or integer arithmetic. Its algorithms have constant expected operation counts and concentrated runtime, though deterministic termination weakens privacy guarantees.

The sampling procedure exactly samples a discrete Gaussian on a finite computer using only uniformly random bits.
Algorithm 3 outputs one sample from NZ(0, σ^2) using a constant number of operations in expectation.
The method first samples discrete Laplace noise and converts it to a discrete Gaussian through rejection sampling.
The Bernoulli(exp(−γ)) and discrete-Laplace subroutines each produce exact samples with constant expected operation counts.
The algorithms use rational arithmetic, basic field operations, and comparisons without evaluating exponentials or square roots.
Runtime is subexponential and highly concentrated, but enforcing deterministic termination changes the guarantee to approximate privacy with an additional failure term.