3.5.3 拉普拉斯vs高斯

代替添加拉普拉斯噪声的另一种方法是添加高斯噪声。在这种情况下，我们不是将噪声缩放到 $\ell_1$ 灵敏度 $\Delta f$，而是缩放到 $\ell_2$ 灵敏度：

定义3.8（$\ell_2$-敏感度） 一个方法 $f:\mathbb{N}^{|\mathcal{X}|}\to\mathbb{R}^k$ 的 $\ell_2$-敏感度为：

$$\Delta_2(f)=\max_{x,y\in\mathbb{N}^{|\mathcal{X}|},\Vert x-y\Vert _1=1}\Vert f(x)-f(y)\Vert _2$$

参数为 $b$ 的高斯机制在每个 $k$ 协调中添加方差为 $b$ 的零均值高斯噪声。以下定理在附录A中得到了证明。

定理 3.22。设 $\varepsilon\in(0,1)$ 是任意的。当 $c^2>2\ln(1.25/\delta)$ 时，参数 $\sigma\geq c\Delta_2(f)/\varepsilon$ 的高斯机制是 $(\varepsilon,\delta)$-差分隐私的。

高斯噪声的优点之一是为隐私而添加的噪声与其他噪声源具有相同的类型；另外，两个高斯的和是高斯的，因此隐私机制对统计分析的影响可能更容易理解和修正。

这两种机制在组合下产生相同的累积损失，因此即使对于每个单独合成来说,隐私保证较弱，但在许多计算中的累积影响是可比较的。此外，如果 $\delta$ 足够小（例如，亚多项式），在实践中，我们将永远不会遇到差分隐私保证的不足之处。

也就是说，相对于拉普拉斯噪声，高斯噪声在理论上是有缺点的。考虑 Report Noisy Max（带有拉普拉斯噪声）算法下，每个候选输出在数据库 $x$ 上的效用得分与其在相邻数据集 $y$ 上的效用分数相同。该机制产生 $(\varepsilon,0)$-差分隐私，与候选输出的数量无关。如果我们使用高斯噪声并报告最大值，并且如果候选值的数量比 $1/\delta$ 大，那么我们将精确地选择发生概率小于 $δ$ 的具有大高斯噪声的事件。当我们远离高斯分布的尾时，我们不再能保证在 $x,y$ 数据库的观测概率的差别在 $e^{\pm\varepsilon}$ 因子内。