The Discrete Gaussian for Differential Privacy

Abstract

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.

Correcting a mistake in the statement of Fact 18: this only applies for μ is a half-integer. (This does not affect the results in the paper, which all used μ=0.)

References in corpus (13)

• Deep Learning with Differential Privacy
• Renyi Differential Privacy
• $f$-divergence Inequalities
• Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising
• Sampling exactly from the normal distribution
• The Skellam Mechanism for Differentially Private Federated Learning
• The Discrete Gaussian for Differential Privacy
• The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation
• Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation
• Permute-and-Flip: A new mechanism for differentially private selection
• Locally Private Bayesian Inference for Count Models
• A Note on Discrete Gaussian Combinations of Lattice Vectors
• An Improved Exact Sampling Algorithm for the Standard Normal Distribution

Cited by in corpus (19)

• CrypTen: Secure Multi-Party Computation Meets Machine Learning
• The Discrete Gaussian for Differential Privacy
• Practical and Private (Deep) Learning without Sampling or Shuffling
• D2P-Fed: Differentially Private Federated Learning With Efficient Communication
• Optimal Accounting of Differential Privacy via Characteristic Function
• On the Convergence and Calibration of Deep Learning with Differential Privacy
• Hyperparameter Tuning with Renyi Differential Privacy
• Differentially Private Mechanisms for Count Queries
• Optimal Private Median Estimation under Minimal Distributional Assumptions
• Efficient Differentially Private $F_0$ Linear Sketching
• Differentially Private Bayesian Neural Networks on Accuracy, Privacy and Reliability
• DP-REC: Private & Communication-Efficient Federated Learning
• Computing Differential Privacy Guarantees for Heterogeneous Compositions Using FFT
• Do I Get the Privacy I Need? Benchmarking Utility in Differential Privacy Libraries
• Differential Privacy Meets Federated Learning under Communication Constraints
• D3p -- A Python Package for Differentially-Private Probabilistic Programming
• Multi-Central Differential Privacy
• Low Influence, Utility, and Independence in Differential Privacy: A Curious Case of $\left(\genfrac{}{}{0ex}{}{3}{2}\right)$
• Optimum Noise Mechanism for Differentially Private Queries in Discrete Finite Sets