差分隐私Differential Privacy介绍

差分隐私，英文名为differential privacy，顾名思义，保护的是数据源中一点微小的改动导致的隐私泄露问题。比如有一群人出去聚餐，那么其中某人是否是单身狗就属于差分隐私。

为了更形式化地描述差分隐私，我们需要先定义相邻数据集。现给定两个数据集D和D’, 若它们有且仅有一条数据不一样，那我们就称此二者为相邻数据集。以上面数据集为例：假定有 $n$ 个人，他们是否是单身狗，形成一个集合 ${a_1,a_2, …, a_n}$ （其中 $a_i = 0$ 或 $1$ ），那么另一个集合当中只有一个人改变了单身状态，形成另一个集合 ${a_1’, a_2’, …, a_n’}$ ，也就是只存在一个 $i$ 使得 $a_i e a_i’$ ，那么这两个集合便是相邻集合。

那么对于一个随机化算法 $A$ （所谓随机化算法，是指对于特定输入，该算法的输出不是固定值，而是服从某一分布），其分别作用于两个相邻数据集得到的两个输出分布难以区分。差分隐私形式化的定义为：

$Pr{A(D) = O} ≤e^epsilon cdot Pr{A(D’) = O}$

也就是说，如果该算法作用于任何相邻数据集，得到一个特定输出 $O$ 的概率应差不多，那么我们就说这个算法能达到差分隐私的效果。也就是说，观察者通过观察输出结果很难察觉出数据集一点微小的变化，从而达到保护隐私的目的。

那如何才能得到差分隐私呢？最简单的方法是加噪音，也就是在输入或输出上加入随机化的噪音，以期将真实数据掩盖掉。比较常用的是加拉普拉斯噪音（Laplace noise）。由于拉普拉斯分布的数学性质正好与差分隐私的定义相契合，因此很多研究和应用都采用了此种噪音。还是以前面那个数据集为例，假设我们想要知道到底有多少人是单身狗，我们只需要计算 $sum a_i$ ，那么为了掩盖具体数值，实际输出值应为 $O=sum a_i + r_{lap}$ ，相应地，另一个数据集输出的是 $O’= sum a_i’+r_{lap}’$ 。这使得观察者分不清最终的输出是由哪个数据集产生的。

前面描述的是差分隐私的严格定义。还有一种稍微放宽一点的定义为：

$Pr{A(D) = O} le e^epsilon cdot Pr{A(D’) = O} + delta$

其中 $delta$ 是一个比较小的常数。要获取这种差分隐私，我们可以使用高斯噪音（Gaussian noise）。

当然，对输入或输出加噪音会使得最终的输出结果不准确。而且由于噪音是为了掩盖一条数据，所以很多情况下数据的多少并不影响加的噪音的量。那么在数据量很大的情况下，噪音的影响很小，这时候就可以放心大胆地加噪音了，但数据量很小的情况下，噪音的影响就显得比较大，会使得最终结果偏离准确值较远而变得不可用。也有些算法不需要加噪音就能达到差分隐私的效果，听起来很美好，但这种算法通常要求数据满足一定的分布，这一点在现实中通常很难满足。

[1] Dwork, Cynthia, et al. "Our data, ourselves: Privacy via
distributed noise generation." Annual International Conference on the Theory and Applications of
Cryptographic Techniques. Springer, Berlin, Heidelberg, 2006.

[2] Dwork, Cynthia, and Aaron Roth. "The algorithmic
foundations of differential privacy." Foundations and Trends® in Theoretical Computer Science 9.3–4 (2014):
211-407.

[3] Bhaskar, Raghav, et al. "Noiseless database
privacy." International Conference on
the Theory and Application of Cryptology and Information Security. Springer, Berlin,
Heidelberg, 2011.