2.3.1 差分隐私的基本概念

差分隐私的提出是为了有效地应对差分攻击，我们使用一个虚拟案例介绍一下差分攻击和差分隐私的概念。

假设A公司想给X大学的2000名学生进行消费水平评级，从而决定在该大学投放广告的力度。由于缺乏相关数据，A公司希望与电商公司B合作，查询这2000名学生在B公司2019年的月平均消费金额超过500元的人数，以此作为进一步决策的指标之一。

假设A公司向电商公司B进行了两次查询，第一次查询使用的数据为2000名学生的整体数据（记作D₁），而第二次查询则将最后一位同学Bob删去，使用前1999名同学的数据（记作D₂）。此时得到的两个数据集便可称为该场景中的相邻数据集。

如果电商公司B直接返回查询结果，query（D₁）=900，query（D₂）=899，那么根据这两次查询结果，A公司便可得到额外的信息，即Bob在2019年，在电商公司B的月平均消费金额超过了500元。A公司使用两个仅差一条记录的数据集分别进行查询的行为，便可视为一种差分攻击，旨在分析Bob同学的消费情况。

为了抵抗这种差分攻击，电商公司B可以使用差分隐私的方法对查询结果进行处理，即加入一个随机项r，（r取自离散均匀分布[-1，0，1]）：query_dp（D）=query（D）+r，dp表示差分隐私（Differential Privacy），于是A公司得到的查询结果可能如式（2-3）和式（2-4）所示，即

加入随机项之后的查询结果便达到了掩盖真实结果的目的，但由于所使用的随机项分布过于简单，仍然可能出现极端情况导致真实结果的泄露。所以，可以根据具体的场景，通过修改随机项的分布，对保护隐私的程度进行修改。当然，这里展示的虚拟案例只展示了差分攻击的手段和差分隐私的思想，但所使用的随机项分布和方法都不能满足复杂的真实场景的要求。在接下来的部分，我们会对差分隐私的严格定义和常用的机制进行阐述。

回顾1.6节中对差分隐私的简单介绍，其具体定义如下。

定义2-6 对于任意两个相邻数据集X和X＇，如果一个随机化算法D满足以下条件，那么可认为该算法是满足ε-差分隐私的（隐私程度可通过参数ε进行调节），即

式中，S⊆Range（D）。

我们可以从字面上简单地理解该定义：在两个相邻数据集X和X＇上，算法D获得同一个集合中输出结果的概率相差不大。其中，“相差不大”的定义则通过ε参数来完成，ε越小，对两个数据集输出结果的差距限制就越小，保护隐私的程度就越强。

在ε-差分隐私中，要求，即

也就是说，ε用于控制算法D在邻近数据集上获得“相同”输出结果的概率比值。因此，当ε足够小（比如为0）时，很难找到一个数据集S使得在数据集X上输出该集合内结果的概率明显高于数据集X＇，也就无法区分两个数据集，从而达到较高的隐私保护程度，但是，当ε足够小时，意味着数据的可用性非常低，所以参数ε也称为隐私预算（Privacy Budget）。在实际应用中，该参数通常取很小的值，例如0.01或者0.1，我们应该根据具体的业务场景和隐私保护的期望要求，对该参数进行合理的设置。

正如前文所述，差分隐私通过增加噪声来掩盖真实数据，防止有一定背景知识的敌手分析出额外的信息。值得一提的是，差分隐私关注的不只是隐私，数据的可用性也是非常重要的一个指标。如果为了防止敌手进行分析，导致数据的可用性丧失，就失去了传输数据的意义，隐私保护的前提条件也就不复存在。因此，只有添加合适的干扰噪声，才能在保证数据可用性的同时，还能为数据的安全性提供一定的保护，防止数据被敌手进一步分析。

为了更清晰地确定添加噪声的大小，可以使用敏感度（Sensitivity）的概念对噪声进行衡量[55]。与差分隐私相似，敏感度的概念也是建立在某个算法（或函数）上的。我们所说的“是否满足差分隐私”的对象便是一个算法。同样，敏感度的概念也如此，是指某算法在相邻数据集上的输出结果的最大差异。在差分隐私中定义了两种敏感度，即全局敏感度和局部敏感度。其中，局部敏感度是在固定了相邻数据集中某个数据集（D或者D＇）的情况下，计算某算法输出结果的最大差异，而全局敏感度则是对所有相邻数据集的组合进行计算。

定义2-7 对任意两个相邻数据集X和X＇，称为一个算法D的全局敏感度（Global Sensitivity）。其中，||D（X）-D（X＇）||₁为输出的两个结果的曼哈顿距离。

定义2-8 对于给定数据集X及其任意相邻数据集X＇，称为一个算法D的局部敏感度（Local Sensitivity）。

全局敏感度在通常情况下要大于局部敏感度，二者的关系可表示如下

对哈希函数比较熟悉的读者，也可以用哈希函数中“强抗碰撞性”和“弱抗碰撞性”概念的区别来理解全局敏感度和局部敏感度的区别。

在知晓了隐私预算和敏感度的概念之后，我们可以更清晰地确定差分隐私中所使用的噪声的大小。在实际应用中，添加噪声的不同方法称为不同的“机制”，最基础的两种噪声添加机制分别是拉普拉斯机制（Laplace Mechanism）和指数机制（Exponential Mechanism）[50]。

我们先介绍拉普拉斯机制中使用的拉普拉斯分布。位置参数为l、尺度参数为s的拉普拉斯分布（Lap（l，s））的概率密度函数为

当位置参数l=0时，，我们使用图2-2帮助读者更直观地理解。

定义2-9 拉普拉斯机制是指通过向原始算法D的真实输出结果添加服从拉普拉斯分布的噪声来实现ε-差分隐私，即D_dp（X）=D（X）+r。其中，r服从拉普拉斯分布Lap（0，Δf/ε），而Δf为算法D的敏感度。

从图2-2中可以观察到，在算法D的敏感度保持不变的情况下，隐私预算越小，添加噪声越大，这与差分隐私的直观要求是一致的。

拉普拉斯机制经常被用在输出域为数值类型的算法上，比如在班长选举的投票环节，用于计算每个候选者得票数的算法D₁。假设投票结果如下，为了使选举过程达到ε-差分隐私，班主任在公布结果之前使用拉普拉斯机制对算法D₁进行噪声添加。显然，算法D₁的敏感度Δf=1，当隐私预算ε分别选择0.01、0.1、1时，我们计算了对应的噪声以及添加噪声之后的输出结果。

计算了不同隐私预算对应的噪声（简单起见，对结果进行了舍入处理），分别将噪声添加到对应的数据上得到了以下结果（见表2-1）。

根据以上结果可以观察到，如果令ε=0.01，那么噪声过大，使得最终的结果无法用于选举；如果令ε=1，那么最终的结果可以保证选举的正确性，但加入噪声的最终结果与真实结果相差不大，可能会泄露真实结果中的隐私。也就是说，当隐私预算过大时，可能很难保证数据的安全性；当隐私预算太小时，数据的可用性便会急剧下降。所以，我们应该根据具体的业务场景，对隐私预算进行严格、合理的设置，以达到可用性和安全性的折中。

对于输出域为数值类型的算法，可以使用拉普拉斯机制达到差分隐私的要求。但是对于输出域为枚举类型的算法，拉普拉斯机制则很难正常应用，比如用于计算获得票数最多的候选者名称的算法。对于这种输出域为一些实体对象集合的算法，则需要使用指数机制实现差分隐私。

由于输出域为枚举类型的算法很难衡量其敏感度，所以在指数机制的实现过程中使用可用性函数来代替算法进行敏感度的衡量。我们一般将可以区分不同输出结果之间优劣性的函数指定为可用性函数，记为q（X，res）→R，其输出值一般为实数，代表着输出结果res的优劣程度。比如，在班长选举活动中，如果想输出得票数最多的候选者名称，那么可将不同候选者（res）的得票数（R）作为可用性函数。

定义2-10 指数机制指的是，设算法D的输出结果res=D（X）为枚举类型，即res∈Set_res，Set_res为全部res可能结果的集合，可用性函数为q（X，res），Δq为其敏感度。如果算法D以正比于的概率输出res，那么认为算法D满足ε-差分隐私。

我们同样考虑班长选举活动的场景，如果算法D₂输出的结果为得票数最多的候选者名称，那么根据示例中的数据，D₂应该输出的结果是C₁。

由于D₂的输出集合为候选者的名称集合，为了达到ε-差分隐私，需要使用指数机制实现。在此，将每个候选者的得票数作为有效性函数，可以通过该函数对各个候选者的优秀程度进行评价，其敏感度则为1。我们将指数机制应用到该示例中，计算了在不同的隐私预算下输出各个候选者的概率（如表2-2所示）。

根据结果可以看出，指数机制没有直接向输出结果添加具体的噪声，而将算法D₂修改成了随机化算法，其输出结果不是固定的，而是以某种固定的概率进行输出。数据的可用性要求正确结果总能以较大概率输出，隐私预算越大，正确结果的输出概率就越大；安全性则要求输出结果不能是确定性的，必须存在一定的“出错”概率，隐私预算越小，“出错”的概率就越大。因此，与拉普拉斯机制相同，必须严格、合理地选择隐私预算，才能实现安全性和可用性的平衡。

从以上两个例子中可以看出，差分隐私的主要思想就是保证最终输出的结果是经过噪声扰动的。因此，在差分隐私中扰动可以添加在任一阶段。根据扰动添加的位置，可以将扰动分为以下几类：输入扰动、目标扰动、优化扰动和输出扰动。本节的两个例子均为输出扰动。