差分隐私#

学习目标

阅读本章后，您将能够：

  • 定义差分隐私

  • 解释\(\epsilon\)这一重要的隐私参数

  • 应用拉普拉斯机制实现满足差分隐私的计数问询

与\(k\)-匿名性类似，差分隐私（Differential Privacy） [3, 4]也是一个用数学语言描述的隐私定义（即可以用数学方法证明发布数据满足此性质）。然而，与\(k\)-匿名性不同，差分隐私不是数据所具有的属性，而是算法所具有的属性。也就是说，我们可以证明一个算法满足差分隐私。如果想证明一个数据集满足差分隐私，我们需要证明的是产生此数据集的算法满足差分隐私。

定义

一般将满足差分隐私的函数称为一个机制（Mechanism）。如果对于所有临近数据集（Neighboring Dataset）\(x\)和\(x'\)和所有可能的输出\(S\)，机制\(F\)均满足

(1)#\[\begin{equation} \frac{\mathsf{Pr}[F(x) = S]}{\mathsf{Pr}[F(x') = S]} \leq e^\epsilon \end{equation}\]

则称机制\(F\)满足差分隐私。

如果两个数据集中只有一个个体的数据项不同，则认为这两个数据集是临近数据集。请注意，\(F\)一般是一个随机函数。也就是说，即使给定相同的输入，\(F\)一般也包含多个可能的输出。因此，\(F\)输出的概率分布一般不是一个点分布。

这个定义所蕴含的一个重要含义是，无论输入是否包含任意特定个体的数据，\(F\)的输出总是几乎相同的。换句话说，\(F\)所引入的随机性应该足够大，使得观察\(F\)的输出无法判断输入是\(x\)还是\(x'\)。假设我的数据在\(x\)中，但不在\(x'\)中。如果攻击者无法确定\(F\)的输入是\(x\)还是\(x'\)，则攻击者甚至无法判断输入是否包含我的数据，更无法判断出我的数据是什么了。

一般将差分隐私定义中的参数\(\epsilon\)称为隐私参数（Privacy Parameter）或隐私预算（Privacy Budget）。\(\epsilon\)提供了一个旋钮，用来调整差分隐私定义所能提供的”隐私量”。\(\epsilon\)较小时，意味着\(F\)需要为相似的输入提供非常相似的输出，因此提供更高等级的隐私性。较大的\(\epsilon\)允许\(F\)给出不那么相似的输出，因此提供更少的隐私性。

我们在实际中应该如何设置\(\epsilon\)，差分隐私才能提供足够的隐私性呢？没人知道这个问题的答案。一般的共识是：将\(\epsilon\)设置为约等于1或者更小的值；大于10的\(\epsilon\)取值意味着大概率无法提供足够的隐私性。但实际上，这个经验法则下的\(\epsilon\)取值过于保守了。我们后续将会进一步展开讨论这个问题。

拉普拉斯机制#

差分隐私一般用于回复特定的问询。我们来考虑一个针对人口普查数据的问询。我们首先不使用差分隐私。

“数据集中有多少个体的年龄大于等于40岁？”

adult[adult['Age'] >= 40].shape[0]

14237

使这个问询满足差分隐私的最简单方法是：在回复结果上增加随机噪声。这里的关键挑战是：既需要增加足够大的噪声，使问询满足差分隐私，但噪声又不能加得太多，否则问询结果就无意义了。为了简化这一过程，差分隐私领域的学者提出了一些基础机制。这些基础机制具体描述了应该增加何种类型的噪声，以及噪声量应该有多大。最典型的基础机制是拉普拉斯机制（Laplace Mechanism） [4]。

定义

根据拉普拉斯机制，对于可以输出一个数值型结果的函数\(f(x)\)，按下述方法定义的\(F(x)\)满足\(\epsilon\)-差分隐私：

(2)#\[\begin{equation} F(x) = f(x) + \textsf{Lap}\left(\frac{s}{\epsilon}\right) \end{equation}\]

其中\(s\)是\(f\)的敏感度（Sensitivity），\(\textsf{Lap}(S)\)表示以均值为0、放缩系数为\(S\)的拉普拉斯分布采样。

函数\(f\)的敏感度是指，当输入由数据集\(x\)变化为临近数据集\(x'\)后，\(f\)的输出变化量。计算函数\(f\)的敏感度是一个非常复杂的问题，也是设计差分隐私算法时所需面临的核心问题，我们稍后会更进一步展开讨论。我们现在只需要指出，计数问询（Counting Query）的敏感度总为1：当问询数据集中满足特定属性的数据量时，如果我们只修改数据集中的一个数据项，则问询的输出变化量最多为1。

因此，我们可以根据我们所选择的\(\epsilon\)，在计数问询中使用敏感度等于1的拉普拉斯机制，从而使我们的样例问询满足差分隐私性。现在，我们取\(\epsilon = 0.1\)。我们可以用Numpy的random.laplace函数实现拉普拉斯分布采样。

sensitivity = 1
epsilon = 0.1

adult[adult['Age'] >= 40].shape[0] + np.random.laplace(loc=0, scale=sensitivity/epsilon)

14229.451851778285

可以试着多次运行此代码，查看噪声对问询结果造成的影响。虽然每次代码的输出结果都会发生变化，但在大多数情况下，输出的结果都与真实结果（14,235）很接近，输出结果的可用性相对较高。

需要多大的噪声？#

我们如何知道拉普拉斯机制是否已经增加了足够的噪声，可以阻止攻击者对数据集中的个体实施重标识攻击？我们可以先尝试自己来实施攻击！我们构造一个恶意的计数问询，专门用于确定凯莉·特鲁斯洛夫的收入是否大于$50k。

karries_row = adult[adult['Name'] == 'Karrie Trusslove']
karries_row[karries_row['Target'] == '<=50K'].shape[0]

1

此回复结果给出了凯莉所在数据行的收入值，显然侵犯了凯莉的隐私。由于我们知道如何应用拉普拉斯机制使计数问询满足差分隐私，我们可以这样回复问询：

sensitivity = 1
epsilon = 0.1

karries_row = adult[adult['Name'] == 'Karrie Trusslove']
karries_row[karries_row['Target'] == '<=50K'].shape[0] + \
  np.random.laplace(loc=0, scale=sensitivity/epsilon)

4.328174037376989

真实结果是0还是1呢？因为增加的噪声比较大，我们已经无法可靠地判断真实结果是什么了。这就是差分隐私要实现的目的：哪怕可以判定出此问询是恶意的，我们也不会拒绝回复问询。相反，我们会增加足够大的噪声，使恶意问询的回复结果对攻击者来说变得毫无用处。