# The Discrete Gaussian for Differential Privacy

arXiv: https://arxiv.org/abs/2004.00010 · HTML: https://mlsanity.com/paper/2004.00010/

## Key facts

- Cited by 135 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Mar 2020.

## Built on by (most cited first, 30 of 135)

- [Practical and Private (Deep) Learning without Sampling or Shuffling](https://mlsanity.com/paper/2103.00039/) (2021)
- [CrypTen: Secure Multi-Party Computation Meets Machine Learning](https://mlsanity.com/paper/2109.00984/) (2021)
- [The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation](https://mlsanity.com/paper/2102.06387/) (2021)
- [Hyperparameter Tuning with Renyi Differential Privacy](https://mlsanity.com/paper/2110.03620/) (2021)
- [Optimal Accounting of Differential Privacy via Characteristic Function](https://mlsanity.com/paper/2106.08567/) (2021)
- [The Skellam Mechanism for Differentially Private Federated Learning](https://mlsanity.com/paper/2110.04995/) (2021)
- [Private Convex Optimization via Exponential Mechanism](https://mlsanity.com/paper/2203.00263/) (2022)
- [Composition of Differential Privacy & Privacy Amplification by Subsampling](https://mlsanity.com/paper/2210.00597/) (2022)
- [Leveraging Public Data for Practical Private Query Release](https://mlsanity.com/paper/2102.08598/) (2021)
- [The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning](https://mlsanity.com/paper/2203.03761/) (2022)
- [On the Convergence and Calibration of Deep Learning with Differential Privacy](https://mlsanity.com/paper/2106.07830/) (2021)
- [On Privacy and Personalization in Cross-Silo Federated Learning](https://mlsanity.com/paper/2206.07902/) (2022)
- [Stronger Privacy Amplification by Shuffling for R'enyi and Approximate Differential Privacy](https://mlsanity.com/paper/2208.04591/) (2022)
- [Conformal Prediction for Federated Uncertainty Quantification Under Label Shift](https://mlsanity.com/paper/2306.05131/) (2023)
- [Taming Cross-Domain Representation Variance in Federated Prototype Learning with Heterogeneous Data Domains](https://mlsanity.com/paper/2403.09048/) (2024)
- [Shuffle Private Linear Contextual Bandits](https://mlsanity.com/paper/2202.05567/) (2022)
- [Goal-guided Generative Prompt Injection Attack on Large Language Models](https://mlsanity.com/paper/2404.07234/) (2024)
- [Private prediction for large-scale synthetic text generation](https://mlsanity.com/paper/2407.12108/) (2024)
- [Differentially Private Quantiles](https://mlsanity.com/paper/2102.08244/) (2021)
- [Learning to Generate Image Embeddings with User-level Differential Privacy](https://mlsanity.com/paper/2211.10844/) (2022)
- [Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions](https://mlsanity.com/paper/2301.12250/) (2023)
- [Privacy Amplification via Compression: Achieving the Optimal Privacy-Accuracy-Communication Trade-off in Distributed Mean Estimation](https://mlsanity.com/paper/2304.01541/) (2023)
- [Breaking the Trilemma of Privacy, Utility, Efficiency via Controllable Machine Unlearning](https://mlsanity.com/paper/2310.18574/) (2023)
- [Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT](https://mlsanity.com/paper/2102.12412/) (2021)
- [Individual Privacy Accounting with Gaussian Differential Privacy](https://mlsanity.com/paper/2209.15596/) (2022)
- [Locally Private k-Means in One Round](https://mlsanity.com/paper/2104.09734/) (2021)
- [Practical Differentially Private Hyperparameter Tuning with Subsampling](https://mlsanity.com/paper/2301.11989/) (2023)
- [Shuffle Private Stochastic Convex Optimization](https://mlsanity.com/paper/2106.09805/) (2021)
- [Privacy-Aware Compression for Federated Data Analysis](https://mlsanity.com/paper/2203.08134/) (2022)
- [Differential Privacy Meets Federated Learning under Communication Constraints](https://mlsanity.com/paper/2101.12240/) (2021)

## Abstract (arXiv)

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.