差分隐私分类

• 中心化差分隐私（$\epsilon-DP$ϵ−DP）
• 本地化差分隐私（$\epsilon-LDP$ϵ−LDP）

区别

1. 中心化差分隐私的随机函数运行在服务器上，而本地化差分隐私运行在本地。
2. 服务器上具有全局敏感度，而本地查询中任意用户之间并不知晓其他人的数据记录。
3. 机制选择
   1. 中心化差分隐私一般选择Laplace和指数噪声等方法
   2. 本地化差分隐私主要采用随机响应技术

加噪方式分类

1. 扰动
   • 对输入数据扰动：随机响应
   • 对输出数据扰动：Laplace机制
   • 中间数据：随机响应或Laplace机制
2. 采样
   • 核心思想：将数据集分成k份，对每份数据应用Laplace机制或随机响应的算法。
   • 满足差分隐私的组合性质（串行和并行）

高斯机制（Gaussian机制）

• Laplace机制和指数机制之前有总结过，这里进行补充高斯机制。

• 消除量纲的操作

$l_2-sensitivity$l2​−sensitivity：查询函数$f$f的敏感度表示相邻数据集输出的最大的$l_2$l2​距离：
$\Delta f = \displaystyle \max_{D,D'}||f(D)-f(D')||_2$Δf=D,D′max​∣∣f(D)−f(D′)∣∣2​
高斯机制：对于$\forall \delta \in(0,1)$∀δ∈(0,1)，$\sigma > \frac{\sqrt{2 ln \frac{1.25}{\delta}} \Delta f}{\epsilon}$σ>ϵ2lnδ1.25​​Δf​，有噪声$Y\sim N(0,\sigma^2)$Y∼N(0,σ2)满足$(\epsilon,\delta)-differential privacy$(ϵ,δ)−differentialprivacy.
$P[M(D)\in S] \leqslant P[M(D')\in S] + \delta$P[M(D)∈S]⩽P[M(D′)∈S]+δ
证明：

1. 见https://tintin.space/2019/04/01/DP/
2. 这个证明的前半段至积分部分，是搞懂了。但是后半部分，将问题转换后的证明没搞明白。
3. 尤其那个$c$c的范围，着实不懂，而且下面这个部分也挺奇怪的。待解决。

参考自：

https://tintin.space/2019/04/01/DP/