论文标题
差异隐私的离散高斯人
The Discrete Gaussian for Differential Privacy
论文作者
论文摘要
构建不同私有系统的关键工具是在敏感数据集上评估的函数的输出中添加高斯噪声。不幸的是，使用连续分配提出了一些实际的挑战。首先，有限的计算机不能准确地表示连续分布中的样本，并且先前的工作表明，看似无害的数值错误可以完全破坏隐私。此外，当基础数据本身是离散的（例如，人口计数）时，添加连续噪声会使结果不容易解释。 考虑到这些缺点，我们在差异隐私的背景下介绍和分析离散的高斯。具体而言，我们从理论上和实验上表明，添加离散的高斯噪声基本上提供了与添加连续高斯噪声相同的隐私和准确性。我们还提出了一种简单有效的算法，用于从该分布中进行精确采样。这证明了其适用于私人回答计数查询的适用性，或更一般的低敏化整数值查询。
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.
