差分隐私学习笔记。

差分隐私定义

差分隐私技术是最近研究比较多的一种保护方法，其思想是在数据的采集或发布前，对数据进行扰动（Perturbation）添加噪声，从而可以隐藏真实数据，避免具有背景知识的攻击者通过猜测，获取隐私信息。差分隐私保护技术给出了数据隐私保护程度及数据可用性之间的严格数学定义模型：

算法A是满足_ε_的差分隐私算法（ε-DP），其中ε ≧0，当且仅当对于任意两个只相差一个元素的相邻数据集D，D’，都满足如下公式：

对这个定义可以这么理解：如果对于任何一个可能查询结果，算法A对于任何相邻数据集的查询结果都不可区分，那么就说算法A是满足差分隐私机制的。ε称为隐私预算（budget）。通常而言，隐私预算越小，对数据的隐私保护程度越大，但是数据的可用性越差；隐私预算越大，数据的可用性越好，但是隐私保护能力越差。差分隐私实际上也正是隐私保护程度和数据可用性之间的权衡。

注意，这个定义只对随机算法有意义。给出确定性输出的算法都不适合差分隐私。

差分隐私应用场景

下图分别是本地化和中心化差分隐私的处理框架。

差分隐私扰动机制（Perturbation）——拉普拉斯噪声

在中心化差分隐私中，最为常用的扰动机制是拉普拉斯(Laplace)机制，该机制可以后期处理聚合查询（例如，计数、总和和均值）的结果以使它们差分私有。

Laplace分布是统计学中的概念，是一种连续的概率分布。如果随机变量的概率密度函数分布为：

那么它就是拉普拉斯分布。其中，μ是位置参数，b是尺度参数，该分布满足期望为μ，方差为2b^2。

保护数据隐私的方法就是将原有的单一查询结果概率化。Laplace噪声就给我们提供了一个很好的概率化的方法。

比如进行统计查询，一般来说统计查询形如：查询数据集中有多少条记录满足给定的条件。所以直接在查询结果加上Lap(Δf/ε)的噪声即可，其中Δf为敏感度，这里的敏感度为1， ε为隐私预算。敏感度用来定义由于数据集中少一条记录对数据查询的结果造成的影响。

下面是用于计数查询的Laplace机制的Java 代码示例：

该函数的关键部分是

  1. 实例化以 0 为中心并按 1 /ε缩放的拉普拉斯概率分布。我们使用Apache Commons 的实现"LaplaceDistribution"，它的构造函数包含两个参数：分布的均值和分布的规模。请注意，较小的ε（更多隐私）导致更大的规模，从而更宽的分布和更多的噪声。
  2. 从该分布中抽取一个随机样本。此 sample（）函数采用 0 和 1 之间的随机数，并将拉普拉斯分布的逆累积分布函数（CDF）应用于此数字。该过程产生随机数，随机数具有任何特定值的可能性与分布相匹配。作为一种替代方式来考虑它，如果这个采样函数被调用一百万次以获得一百万个样本，这些样本的直方图形状将非常符合拉普拉斯分布的形状。
  3. 通过添加来自步骤 2 的随机值来扰乱实际值。

Python实现count查询的拉普拉斯机制：