差分隐私#

学习目标

阅读本章后,您将能够:

  • 定义差分隐私

  • 解释\(\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)
14238.272439932305

可以试着多次运行此代码,查看噪声对问询结果造成的影响。虽然每次代码的输出结果都会发生变化,但在大多数情况下,输出的结果都与真实结果(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)
3.6318610474714244

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