2.2 基于差分隐私的安全机制
差分隐私（图2-2）采用了一种随机机制，使得当输入中的单个样本改变之后，输出的分布不会有太大的改变[12，24]。例如，对于差别只有一条记录的两个数据集，查询它们获得相同的输出的概率非常接近。这将使用户即使获取了输出结果，也无法通过结果推测出输入数据来自哪一方。
图2-2 差分隐私
在现有的隐私保护方法中，由于差分隐私对隐私损失进行了数学上的定义，并且其实现过程比较简捷，系统开销更小，所以得到了广泛的应用。差分隐私最开始被开发用来促进在敏感数据上的安全分析。随着机器学习的发展，差分隐私再次成为机器学习社区中一个活跃的研究领域。来自差分隐私的许多令人激动的研究成果都能够被应用于面向隐私保护的机器学习[91，94]。
2.2.1 差分隐私的定义
差分隐私是由Dwork在2006年首次提出的一种隐私定义[91]，是在统计披露控制的场景下发展起来的。它提供了一种信息理论安全性保障，即函数的输出结果对数据集里的任何特定记录都不敏感。因此，差分隐私能被用于抵抗成员推理攻击。
按照数据收集方式的不同，当前的差分隐私可以分为中心化差分隐私和本地化差分隐私，它们的区别主要在于差分隐私对数据处理的阶段不同。中心化差分隐私依赖一个可信的第三方来收集数据，用户将本地数据发送到可信第三方，然后在收集的数据中进行差分隐私处理。但可信的第三方在现实生活通常是很难获得的，因此本地化差分隐私将数据隐私化的工作转移到每个参与方，参与方自己来处理和保护数据，再将扰动后的数据发送到第三方，由于发送的数据不是原始数据，因此也就不要求第三方是可信的。下面我们分别介绍这两种差分隐私的定义。图2-3展示的是中心化差分隐私和本地化差分隐私在处理流程上的区别。
图2-3 中心化差分隐私（左）与本地化差分隐私（右）的区别
中心化差分隐私
我们首先给出中心化差分隐私的（ϵ，δ）-差分隐私定义。
定义2-3 （ϵ，δ）-差分隐私[92] 对于只有一个记录不同的两个数据集D和D′，一个随机算法M，以及对于任意的输出S ⊂ Range（M），我们称随机算法M提供（ϵ，δ）-差分隐私保护，当且仅当其满足：
式中，ϵ表示隐私预算（privacy budget），δ表示失败概率。当δ=0时，便得到了性能更好的ϵ-差分隐私。
在差分隐私定义中，隐私保护预算ϵ用于控制算法M在邻近数据集D和D′上获得相同输出的概率比值。式（2.5）表明，ϵ的值越小，那么算法M在邻近数据集D和D′上获得相同输出的概率就越接近，因此，用户通过输出结果，无法区分输入数据到底是来自数据集D还是来自数据集D′，即无法察觉数据集的微小变化，从而达到隐私保护的目的。特别地，当ϵ=0时，算法M在D和D′上得到相同的输出的概率是一样的。反之，ϵ的值越大，其隐私保护的程度就越低。
中心化差分隐私在实际的应用中，有两个非常重要的性质：串行组合和并行组合。
定义2-4 串行组合[202] 设有n个算法M1，M2，· · ·，Mn，算法Mi满足ϵi-差分隐私性质，对于同一个数据集D，将这些算法串行作用于D上，构成新的组合算法
满足
-差分隐私保护。
定义2-5 并行组合[202] 设有n个算法M1，M2，· · ·，Mn，算法Mi满足ϵi-差分隐私性质，对于数据集D，将其拆分成n个集合，分别记为D1，D2，· · ·，Dn，将算法Mi独立作用于数据集Di上，构成新的组合算法
满足maxi{ϵi}-差分隐私保护。
这两个性质非常有用，比如根据定义2-4，如果一个攻击者想试图攻破一个差分隐私安全系统，那么最简单直接的方法是对该系统进行多次查询访问。从系统角度看，这样相当于增大了隐私保护预算值，从而降低了系统的隐私性；从攻击者的角度看，将多次查询访问获取的结果进行平均，根据大数定理，查询次数越多，这个均值的结果和真实值就越接近。这也是当前很多安全系统都设置查询上限的原因，目的就是为了防止恶意攻击。
本地化差分隐私
本地化差分隐私（Local Differential Privacy，LDP）[43，9]可以将数据隐私化的工作转移到每个参与方，参与方自己来处理和保护数据，进一步降低了隐私泄露的可能性，它的定义如下。
定义2-6 本地化差分隐私 [43，9]对于一个任意本地化差分隐私函数f（•），其定义域（domain）为Dom（f），值域（range）为Ran（f），对任意的输入x，x′ ∈Dom（f），输出y∈Ran（f），我们称函数f提供（ϵ）-本地化差分隐私保护，当前仅当其满足：
在本式中，ϵ表示隐私预算。
比较定义2-6和定义2-3，我们不难发现，中心化差分隐私是定义在任意两个相邻数据集的输出相似性上的，而本地化差分隐私是定义在本地数据任意两条记录的输出相似性上的。此外，本地化差分隐私同样继承了组合特性，即它同样满足并行组合和串行组合的性质。
这种差异性，导致其实现方法也有很大的不同。中心化差分隐私需要保护全体数据的隐私，具有全局敏感性的概念，采用的扰动机制可以包括高斯噪声机制、拉普拉斯噪声机制、指数噪声机制等[201]。在本地化差分隐私中，数据隐私化的工作转移到每个参与方，而每一个参与方并不知道其他参与方的数据，因此它并没有全局隐私敏感性的概念，它采用的扰动机制一般通过随机响应实现（Randomized Response，RR）[43，9]。
我们注意到，本地化差分隐私的概念与联邦学习有点相似。事实上，在联邦学习的实现中，可以结合本地化差分隐私的思想，比如给每一参与方的上传梯度或者模型参数加上噪声来更好地保护模型参数。我们将在15.2节详解如何利用差分隐私技术来实现联邦学习。
2.2.2 差分隐私的实现机制
目前实现差分隐私保护的主流方法是添加扰动噪声数据。前面提到，差分隐私可以分为中心化差分隐私和本地化差分隐私，其中：中心化差分隐私采用的扰动机制可以包括拉普拉斯噪声机制、指数噪声机制等；而本地化差分隐私一般通过随机响应（Randomized Response）[277]来实现（随机响应是1965年由Warner提出的一种隐私保护技术）。限于篇幅，本节主要针对中心化差分隐私的三种机制进行分析，对于本地化差分隐私的随机响应算法，读者可以参考文献[277]了解更多细节。
要想知道不同算法函数M需要添加多少噪声才能提供（ϵ，δ）-差分隐私保护，就需要先定义该算法在当前数据上的全局敏感度。全局敏感度根据计算距离的方式不同，一般可以区分为L1全局敏感度和L2全局敏感度。
定义2-7 L1全局敏感度[92] 对于一个算法函数M，D和D′为任意两个相邻的数据集，L1全局敏感度定义如下：
即L1全局敏感度反映了一个函数M在一对相邻数据集D和D′上进行操作时变化的最大范围。
当使用2-范数（即欧氏距离）来衡量函数在相邻数据集上的输出变化时，我们得到如下的L2全局敏感度定义。
定义2-8 L2全局敏感度[92] 对于一个算法函数M，D和D′为任意两个相邻的数据集，L2全局敏感度定义如下：
不管是L1敏感度还是L2敏感度，它的结果与提供的数据集无关，只由函数本身决定。从直观上理解，当全局敏感度比较大时，说明数据集的细微变化可能导致函数M的输出有很大的不同，我们需要添加较大的噪声数据，才能使函数M提供（ϵ，δ）-差分隐私保护；相反，当全局敏感度比较小时，说明数据集的细微变化不会对函数M的输出产生很大的影响，我们只需要添加较小的噪声数据，就能使函数M提供（ϵ，δ）-差分隐私保护。下面介绍在差分隐私中常用的三种添加噪声的机制。
定义2-9 拉普拉斯机制[91] 给定数据集D，设有函数f，其L1敏感度为∆f（定义2-7），那么随机算法M=f（D）+L提供（ϵ，0）-差分隐私保护，其中L～
为添加的随机噪声概率密度函数，即服从参数µ=0，λ=
的拉普拉斯分布。
拉普拉斯机制实现非常简单，被广泛应用于数值型查询的隐私保护机制。对于查询结果，只需要加入一个满足拉普拉斯分布
的噪声数据，就能实现（ϵ，0）-差分隐私保护。
高斯机制为数值型查询结果隐私保护提供了另一种实现。与拉普拉斯机制不同，高斯机制的定义使用的是L2全局敏感度，其定义如下。
定义2-10 高斯机制[95，90] 给定数据集D，设有函数f，其L2敏感度为∆f（定义2-8），对于任意的δ∈（0，1），
，那么随机算法M=f（D）+L提供（ϵ，δ）-差分隐私保护，其中L～Gaussian（0，σ2）为添加的随机噪声概率密度函数，即服从参数µ=0，
的高斯分布。
指数机制是用于非数值型差分隐私保护的一种实现方式，它使用L1敏感度作为参数构造，其定义如下。
定义2-11 指数机制[201] 给定数据集D，设有函数q，输出为结果为r，记为q（D，r），其敏感度为 ∆q，随机算法M以正比于
的概率输出r，那么随机算法M提供（ϵ，0）-差分隐私保护。
在定义2-11中，∆（q）表示L1敏感度，若D和D′表示的是任意两个相邻数据集，r表示的是任意的一个输出，其定义为
差分隐私的实现方式还有很多种，有兴趣的读者可以参考文献[92]。表2-1总结了常用的三种机制，包括它们各自的函数形式以及适用范围等。
表2-1 差分隐私常用的三种机制
前面介绍的是在查询状态下对输出结果实现差分隐私保护的机制。在机器学习中应用差分隐私技术，其情况会更加复杂，因为我们要保护的信息，不仅包括输入数据和输出数据，还包括算法模型参数、算法的目标函数设计等。因此，在机器学习领域应用差分隐私算法，一个关键的问题是何时、何阶段添加噪声数据。为此，差分隐私算法根据噪声数据扰动使用的方式和使用阶段的不同，将其划分为下面几类。
（1）输入扰动：噪声数据被加入训练数据。
（2）目标扰动：噪声数据被加入学习算法的目标函数。
（3）算法扰动：噪声数据被加入中间值，例如迭代算法中的梯度。
（4）输出扰动：噪声数据被加入训练后的输出参数。
在不同阶段，采用的扰动机制也有不同的考虑。鉴于本书的写作目的和篇幅，我们不在这里继续展开，有兴趣的读者可以参考差分隐私相关的文献[92，95，94，28]，更加深入地理解差分隐私的详细实现过程。