局部敏感度和全局敏感度实现的差分隐私的区别

差分隐私是一种保护个人数据隐私的方法，它通过向输入数据添加随机噪声来保护数据隐私。其中，局部敏感度和全局敏感度是两种计算噪声大小的方法。

局部敏感度是指对于输入数据集中的某个个体，当它被删除或替换时，算法输出结果的变化程度。而全局敏感度是指对于输入数据集中的任意两个不同个体，当其中一个个体被删除或替换时，算法输出结果的变化程度。

因此，局部敏感度更加局限于个体数据的影响，而全局敏感度则更加综合考虑了整个数据集的影响。在实现差分隐私时，选择局部敏感度还是全局敏感度取决于具体的应用场景和数据集特点。

相关问题

基于局部敏感度实现的差分隐私和基于全局敏感度实现的差分隐私有什么区别

差分隐私是一种广泛应用于隐私保护的方法，其基本思想是通过向随机噪声中添加一定的扰动来保护原始数据的隐私。差分隐私的实现方式有多种，其中局部敏感度和全局敏感度是两种常见的实现方式。

基于局部敏感度实现的差分隐私指的是在随机噪声中添加的扰动大小与每个个体数据的敏感度相关。具体来说，对于每个数据点，都会计算其敏感度，并根据其敏感度确定添加的扰动大小，这样可以保证每个数据点的隐私得到保护。

而基于全局敏感度实现的差分隐私则是指在随机噪声中添加的扰动大小与所有数据的敏感度相关。具体来说，全局敏感度是指对于所有可能的数据集，其查询结果的最大变化量。全局敏感度较大，可以保证在多个查询中都有较好的隐私保护效果，但是添加的噪声可能会比基于局部敏感度添加的噪声更大。

总之，基于局部敏感度实现的差分隐私更加细粒度，可以对每个个体数据进行个性化的处理，但可能会导致噪声较小，隐私保护效果较差；而基于全局敏感度实现的差分隐私，可以在多个查询中都有较好的隐私保护效果，但可能会导致噪声较大，数据的准确性可能会受到影响。

给出高斯机制的(ε,δ)-差分隐私数学证明。

高斯机制是一种差分隐私的实现方式，它在查询结果中添加了服从高斯分布的噪声。对于一个查询函数 $f$，它的 $(\epsilon, \delta)$-差分隐私机制 $\mathcal{M}$ 通过以下方式计算查询结果：

$$\mathcal{M}(f) = f(D) + \mathcal{N}(0, \sigma^2)$$

其中 $D$ 是数据集，$\mathcal{N}(0, \sigma^2)$ 表示均值为 $0$，方差为 $\sigma^2$ 的高斯分布。$\sigma$ 的取值与 $\epsilon$ 和 $\delta$ 的关系为：

$$\sigma = \sqrt{2\ln(1.25/\delta)} \cdot \frac{s}{\epsilon}$$

其中 $s$ 是查询函数 $f$ 的全局敏感度，即 $s = \max_{D,D'} ||f(D)-f(D')||_1$。

为了证明高斯机制满足 $(\epsilon, \delta)$-差分隐私，我们需要证明对于任意相邻的数据集 $D$ 和 $D'$，以及任意子集 $S \subseteq Range(f)$，有：

$$\Pr[\mathcal{M}(D) \in S] \leq e^\epsilon \Pr[\mathcal{M}(D') \in S] + \delta$$

假设 $D$ 和 $D'$ 只有一条记录不同，不失一般性地设为 $D = (x_1, x_2, ..., x_n)$ 和 $D' = (x_1, x_2, ..., x_i', ..., x_n)$，其中 $x_i' \in \mathcal{X}$。我们可以计算出 $\mathcal{M}(D)$ 和 $\mathcal{M}(D')$ 的概率分布函数（PDF），分别为 $f_D(x)$ 和 $f_{D'}(x)$，然后证明：

$$\frac{f_D(x)}{f_{D'}(x)} = e^{\frac{(f(D')-f(D))x - \frac{x^2}{2\sigma^2}}{\sigma^2}}$$

为了证明上式，我们可以令 $y = f(D')-f(D)$，然后将 $\mathcal{M}(D)$ 和 $\mathcal{M}(D')$ 的表达式代入高斯分布的 PDF 中，得到：

$$\begin{aligned} \frac{f_D(x)}{f_{D'}(x)} &= \frac{1}{\sqrt{2\pi}\sigma} \frac{e^{-\frac{(x-f(D))^2}{2\sigma^2}}}{e^{-\frac{(x-f(D')+y)^2}{2\sigma^2}}} \\ &= e^{\frac{(f(D')+y-f(D))x - \frac{x^2}{2\sigma^2}+\frac{(f(D')-f(D))^2}{2\sigma^2}} \\ &= e^{\frac{(f(D')-f(D))x - \frac{x^2}{2\sigma^2}}{\sigma^2}} \cdot e^{\frac{(f(D')-f(D))y + (f(D')-f(D))^2}{2\sigma^2}} \end{aligned}$$

由于 $y$ 的取值只有 $1$ 和 $-1$，所以 $e^{\frac{(f(D')-f(D))y}{\sigma^2}} \leq e^\epsilon$。同时，由于 $\mathcal{N}(0, \sigma^2)$ 的 PDF 是单峰的，所以 $e^{\frac{(f(D')-f(D))^2}{2\sigma^2}} \leq 1$。因此，我们可以得到：

$$\frac{f_D(x)}{f_{D'}(x)} \leq e^{\frac{(f(D')-f(D))x - \frac{x^2}{2\sigma^2}}{\sigma^2}} \cdot e^\epsilon$$

接下来，我们需要将上式右边的指数部分分解成 $x$ 的一次项和二次项，即：

$$\frac{(f(D')-f(D))x - \frac{x^2}{2\sigma^2}}{\sigma^2} = \frac{x(f(D')-f(D))}{\sigma^2} - \frac{x^2}{2\sigma^4}(f(D')-f(D))^2$$

由于 $(f(D')-f(D))^2 \leq s^2$，所以：

$$\frac{(f(D')-f(D))x - \frac{x^2}{2\sigma^2}}{\sigma^2} \leq \frac{x(f(D')-f(D))}{\sigma^2} - \frac{x^2s^2}{2\sigma^6}$$

因此，我们可以得到：

$$\frac{f_D(x)}{f_{D'}(x)} \leq e^{\frac{x(f(D')-f(D))}{\sigma^2} - \frac{x^2s^2}{2\sigma^6} + \epsilon}$$

令 $a = \frac{f(D')-f(D)}{\sigma^2}$，$b = \frac{s^2}{2\sigma^4}$，则上式可以进一步化简为：

$$\frac{f_D(x)}{f_{D'}(x)} \leq e^{ax - bx^2 + \epsilon}$$

我们需要证明的不等式可以转化为：

$$\int_S f_D(x)dx \leq e^\epsilon \int_S f_{D'}(x)dx + \delta$$

根据上述式子，我们可以得到：

$$\begin{aligned} \int_S f_D(x)dx &= \int_S f_{D'}(x) \cdot \frac{f_D(x)}{f_{D'}(x)} dx \\ &\leq \int_S f_{D'}(x) \cdot e^{ax - bx^2 + \epsilon} dx \\ &= e^\epsilon \int_S f_{D'}(x) \cdot e^{ax - bx^2} dx + \delta \int_S f_D(x)dx \end{aligned}$$

移项得到：

$$\int_S f_D(x)(1-\delta)dx \leq e^\epsilon \int_S f_{D'}(x) e^{ax - bx^2}dx$$

因此，我们可以证明：

$$\Pr[\mathcal{M}(D) \in S] = \int_S f_D(x)dx \leq e^\epsilon \int_S f_{D'}(x) e^{ax - bx^2}dx + \delta$$

这就证明了高斯机制满足 $(\epsilon,\delta)$-差分隐私。