C. Canonne, G. Kamath, and T. Steinke. (2020)cite arxiv:2004.00010Comment: New version: better implementation, analysis, and discussion.
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.
Description
[2004.00010] The Discrete Gaussian for Differential Privacy
%0 Journal Article
%1 canonne2020discrete
%A Canonne, Clément L.
%A Kamath, Gautam
%A Steinke, Thomas
%D 2020
%K differential-privacy probability readings theory
%T The Discrete Gaussian for Differential Privacy
%U http://arxiv.org/abs/2004.00010
%X 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.
@article{canonne2020discrete,
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.},
added-at = {2020-06-02T03:56:00.000+0200},
author = {Canonne, Clément L. and Kamath, Gautam and Steinke, Thomas},
biburl = {https://www.bibsonomy.org/bibtex/2f84c5b18170c67711c0f732f8df8807b/kirk86},
description = {[2004.00010] The Discrete Gaussian for Differential Privacy},
interhash = {1c3ba06ad0a0932a832d50c48a0a9b7b},
intrahash = {f84c5b18170c67711c0f732f8df8807b},
keywords = {differential-privacy probability readings theory},
note = {cite arxiv:2004.00010Comment: New version: better implementation, analysis, and discussion},
timestamp = {2020-06-02T03:56:00.000+0200},
title = {The Discrete Gaussian for Differential Privacy},
url = {http://arxiv.org/abs/2004.00010},
year = 2020
}