The Discrete Gaussian for Differential Privacy

By Clément Louis Canonne, Gautam Kamath, Thomas Steinke. 2020

345 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “We used the conversion in (Canonne et al., 2020) in our experiments.”
The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, methodology): “Privacy is achieved by each client independently adding discrete Gaussian noise (Canonne et al., 2020) to its (appropriately discretized) vector.”
Efficient Differentially Private F0 Linear Sketching (2020, methodology): “Even if a suitable discretization of the mechanism in [26] would be possible (see [10] for a general discussion), it has several drawbacks compared to our method: It only achieves approximate differential privacy as opposed to the pure differential privacy of the noisy KOR sketch.”
CrypTen: Secure Multi-Party Computation Meets Machine Learning (2021, methodology): “CRYPTEN implements sampling algorithms for the Bernoulli, Laplace, and Gaussian distributions (see appendix), which allows for the implementation of randomized response [68], the Laplace mechanism [29], and the Gaussian mechanism [6, 28] (although care must be taken when implementing these mechanism”