阅读此文之前，请先阅读 安全计算方法概览，并一直向上追溯直至到达根节点或已访问节点。
差分隐私，英文名为differential privacy，顾名思义，保护的是数据源中一点微小的改动导致的隐私泄露问题。比如有一群人出去聚餐，那么其中某人是否是单身狗就属于差分隐私。
为了更形式化地描述差分隐私，我们需要先定义相邻数据集。现给定两个数据集D和D’, 若它们有且仅有一条数据不一样，那我们就称此二者为相邻数据集。以上面数据集为例：假定有 n 个人，他们是否是单身狗，形成一个集合 \{a_1,a_2, …, a_n\} （其中 a_i = 0或1），那么另一个集合当中只有一个人改变了单身状态，形成另一个集合 \{a_1’, a_2’, …, a_n’\} ，也就是只存在一个 i 使得 a_i \ne 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.