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.

本研究探讨了在差分隐私框架下，使用离散高斯噪声可以提供与连续高斯噪声相同的隐私性和准确性保证，而且还提出了可用于准确采样的简单高效算法，表明其适用于私密回答计数查询或低敏感度整数值查询。

差分隐私的离散高斯

The Discrete Gaussian for Differential Privacy

The problem of drawing samples from a discrete distribution can be converted
into a discrete optimization problem. In this work, we show how sampling from a
continuous distribution can be converted into an optimization problem over
continuous space. Central to the method is a stochastic process recently
described in mathematical statistics that we call the Gumbel process. We
present a new construction of the Gumbel process and A* sampling, a practical
generic sampling algorithm that searches for the maximum of a Gumbel process
using A* search. We analyze the correctness and convergence time of A* sampling
and demonstrate empirically that it makes more efficient use of bound and
likelihood evaluations than the most closely related adaptive rejection
sampling-based algorithms.

本文研究了从连续分布中进行采样的优化问题，利用 Gumbel 过程提出了 A * 采样算法，对其正确性和收敛时间进行了分析，并与现有算法进行比较实验。