浅谈数据库中的推理控制技术与差分隐私

发表于 2025-09-06 分类于技术原理，数据库，计算机安全 Waline：阅读次数：本文字数： 8.5k 阅读时长 ≈ 31 分钟

本文简要探讨了数据库为防止推理攻击而采用的隐私保护技术，从经典的 K-匿名讲起，最终详细推导并阐释了现代隐私保护的黄金标准——差分隐私。

上学期数据库课程中，在学到数据库安全时曾经在课程笔记中曾简要提及过一些其他的安全性保护技术，例如「推理控制」，以「防止用户通过组合多个低权限查询结果，推断出其无权访问的高敏感度信息」。我在当时就感到非常惊奇，这是怎么做到的呢？

具体而言这是推断攻击，指攻击者利用公开的聚合数据（例如统计报告、平均值、总和等）结合其已知的辅助信息，来推断出特定个体的敏感信息。即使发布的数据是聚合的，不直接包含个体信息，攻击者也可能通过这种方式「反推出」个体隐私。

例如说包含三个人 A, B, C 的工资的数据库，A 知道自己的工资，通过交流知道了 B 的工资，同时通过查询得到了他们的平均工资，这样一来他就能推断出 C 的工资，因此造成了 C 的隐私泄露。

最初、最朴素的想法就是将所有的查询作为一个闭包，计算出这个闭包，就能得到这些查询可以间接推断出的所有信息，然后再从中根据隐私等级判断是否有密级信息泄露。或者更清楚地说，数据库实时构建一个「能被推断出的所有信息的集合」。

显然这个是相当不现实的：

一个用户可能进行成千上万次查询。要实时计算这些查询的所有可能交集、并集、差集，并判断这些组合是否会泄露隐私，其计算量会随着查询次数的增加呈指数级增长。
即使能做到，每次查询前都进行如此复杂的推演，性能也会大大降低。
此外数据库并不知道攻击者掌握了哪些外部信息，这样的防备一样可能被攻破。

那么应该怎么做呢？

$k$ -匿名

$k$ -匿名（ $k$ -Anonymity）是最经典的匿名化技术之一。其核心思想是，让每一条记录都无法与至少 $k-1$ 条其他记录区分开来。这样一来，攻击者就无法将某条具体信息锁定到某个人身上。

假设有一个公开的医疗数据库，包含邮编、年龄和所患疾病。如果攻击者知道某位重要人物的邮编和确切年龄，他很可能通过查询 (邮编='100084', 年龄=45) 来精确找到这个人的记录，从而得知其所患疾病。

这种情况下，数据库管理员会设置一个 $k$ 值（例如 $k=3$ ）。在发布数据前，系统会自动对数据进行抑制或泛化处理。

数据抑制（Suppression）：将一些属性的值用星号 * 取代。
数据泛化（Generalization）：将一些属性的精确值用更宽泛的类别取代。

例如说原始数据：

姓名	邮编	年龄	疾病
张三	100084	45	心脏病
李四	100085	47	高血压
王五	100084	46	糖尿病

经过 $k$ -匿名处理后，可能变成：

姓名（抑制）	邮编（泛化）	年龄（泛化）	疾病
*	10008*	4*	心脏病
*	10008*	4*	高血压
*	10008*	4*	糖尿病

现在，即使攻击者知道目标人物的邮编是 100084，年龄是 45 岁，当他查询时，会得到三条无法区分的记录。他只能知道目标人物患有这三种疾病之一，但无法确定具体是哪一种，从而保护了个人隐私。

然而， $k$ -匿名并不是万能的。它无法防止同质攻击（Homogeneity Attack），即如果一个匿名组内所有记录的敏感属性值都相同，攻击者仍然可以推断出该属性值。

此外由于攻击者依旧可以探知关于个体的信息，可以获知目标个体患有三种疾病之一，因此也存在背景知识攻击（Background Knowledge Attack）的风险，即攻击者利用其已有的背景知识，结合匿名数据，推断出个体的敏感信息。

查询限制与单元格抑制

除了改造数据本身，数据库还可以在响应查询的环节进行智能控制，拒绝那些可能泄露信息的「危险」请求。

第一种方法是查询限制（Query Restriction）。系统会分析用户的查询请求，如果发现该请求可能导致个体信息暴露，就会拒绝执行或返回一个模糊的结果。

例如说「最小结果集限制」，如果一个聚合查询（如 COUNT, SUM）返回的结果集所包含的记录数过少（例如少于 5 条），系统会拒绝返回结果。因为过小的结果集很容易被用来锁定个体。

第二种方法是单元格抑制（Cell Suppression）。在发布统计表格（如人口普查报告）时，如果某个单元格的数值过小，可能会暴露信息。单元格抑制技术会主动「隐藏」这些危险的单元格。

差分隐私

概括

差分隐私（Differential Privacy）是一种更为先进和数学化的隐私保护技术。其核心思想是，通过在查询结果中添加随机噪声，使得攻击者无法确定某个个体是否包含在数据集中。

其核心直觉在于：如果单个记录的加入或移除对查询结果的影响微乎其微（被随机噪声所掩盖），那么攻击者就无法从查询结果中反推出任何关于该个体的信息。

例如说查询「小区总收入」时，差分隐私机制并不会返回精确的 1,000,000 元。它会在这个真实值上加入一个经过数学方法精确计算的随机噪声，可能返回 1,000,050 元。当某个住户搬离后，再次查询，系统会在新的真实值 900,000 元上加入另一个随机噪声，可能返回 899,970 元。

攻击者得到的两个差值 100,080 元，与那个住户的真实收入 100,000 元有所偏差。

噪声的加入，使得攻击者无法确定这个差值是真实的个人数据，还是仅仅是随机噪声的波动。

通过严格的数学证明，差分隐私可以保证，任何单一个体的数据对最终输出结果的影响都微乎其微，从而在保护个体隐私的同时，不影响整体数据的统计分析价值。

差分隐私中有一个隐私预算（Privacy Budget） $\varepsilon$ 的概念，用来量化允许泄露的隐私程度。每次查询都会消耗一定的隐私预算，当预算耗尽后，系统将拒绝进一步的查询请求。

低隐私预算：意味着隐私保护级别非常高。系统会加入更多的噪声。返回的数据在宏观上依然可用，但会更「模糊」一点。这通常用于向公众或不受信任的第三方发布数据。
高隐私预算：意味着隐私保护级别相对较低。系统会加入更少的噪声。返回的数据会更接近真实值。这通常用于组织内部，由受信任的分析师进行精度要求更高的分析。

下面来用形式化的语言描述差分隐私的核心机制。

基本概念

相邻数据集（Adjacent Database）是差分隐私的基石。假设有两个数据集 $D_1, D_2$ ，如果它们之间仅仅相差一条记录，我们就称它们为相邻数据集。这代表了某条数据在或不在数据集中的两种情况^[1]。

$\varepsilon$ -差分隐私

若机制 $\mathcal{M}$ 满足 $\varepsilon$ -差分隐私，那么对于任意两个相邻数据库 $D_1, D_2$ ，以及 $\mathcal{M}$ 可能输出的任意结果集合 $S$ ，都满足以下不等式：

$\Pr[\mathcal{M}(D_1) \in S] \le \e^{\varepsilon} \times \Pr[\mathcal{M}(D_2) \in S]$

其中：

$\mathcal{M}$ 表示随机算法，可以看作是一次数据库查询。
$\mathcal{M}(D_1)$ 表示在数据集 $D_1$ 上运行算法 $\mathcal{M}$ 的结果。
$\Pr[\cdot ]$ 表示概率。
$\e^{\varepsilon}$ 是一个略大于 1 的数（当 $\varepsilon$ 很小时）。

这个式子的含义是，不管查询到的结果是什么（对任意结果集合 $S$ 都满足），包含某条数据得到该结果的概率，与不包含这条数据得到该结果的概率之比不会超过 $\e^{\varepsilon}$ 。根据相邻数据集的定义， $D_1, D_2$ 是可交换的，因此反之亦然。

换言之，攻击者几乎无法通过查询结果来判断某条数据是否存在于数据集中，因为两种情况下的概率分布实在是太接近了（在 $\e^{\varepsilon}$ 接近 1 的情况下）。

拉普拉斯机制

那么该如何设计算法 $\mathcal{M}$ 满足上述定义呢？最常用的方法是拉普拉斯机制（Laplace Mechanism）。

假设存在一个查询函数（Query Function） $f$ ，它作用于数据集 $D$ 并返回一个实数结果。例如可以是 SQL 中的 COUNT, SUM, AVG 等聚合函数。这是没有隐私保护的真实查询。

而敏感度（Sensitivity） $\Delta f$ 是一个衡量查询函数「脆弱性」的指标，定义为：当数据集中增加或删除一条记录时，查询函数 $f$ 的输出结果可能产生的最大变化量。即

$\Delta f = \max_{D_1, D_2} |f(D_1) - f(D_2)|$

其中 $D_1, D_2$ 是任意两个相邻数据集。

例如说 COUNT 函数的敏感度为 1，因为添加或删除一条记录最多会改变计数结果 1。而查询班级考试总分的敏感度为 100（假设满分为 100），因为添加或删除一个学生的成绩最多会改变总分 100。

为了处理连续输出的场景，我们可以将上述不等式用概率密度函数等价地表示。设任意一个可能的输出结果为 $y$ ，则

$\dfrac{\operatorname{pdf}(\mathcal{M}(D_1) = y)}{\operatorname{pdf}(\mathcal{M}(D_2) = y)} \le \e^{\varepsilon}$

设我们添加的噪声 $z$ 来自一个未知的概率分布，其密度函数为 $p(z)$ ，即 $\mathcal{M}(D) = f(D) + z$ 。

那么查询结果的概率密度就是 $\operatorname{pdf}(\mathcal{M}(D) = y) = p(y - f(D))$ 。

取对数后得到

$\ln\left(p(y - f(D_1))\right) - \ln\left(p(y - f(D_2))\right) \le \varepsilon$

令 $z_1 = y - f(D_1), z_2 = y - f(D_2)$ ，即

$\ln(p(z_1)) - \ln(p(z_2)) \le \varepsilon$

又因为 $|f(D_1) - f(D_2)| \le \Delta f$ ，所以 $|z_1 - z_2| \le \Delta f$ 。

因此我们需要找到一个函数 $g(z) = \ln(p(z))$ ，使得对于任意满足 $|z_1 - z_2| \le \Delta f$ 的 $z_1, z_2$ ，都有 $g(z_1) - g(z_2) \le \varepsilon$ 。

为了让这个不等式对所有情况都成立，我们需要限制函数 $g(z) = \ln(p(z))$ 的变化率。一个简单而有效的选择是让 $g(z)$ 的导数（或其绝对值）为一个常数。

如果我们希望噪声对结果的影响是对称的（即正噪声和负噪声的概率一样），那么我们应该让 $g(z)$ 对称于 $y$ 轴。满足这个条件的、最简单的函数形式就是

$g(z) = \ln(p(z)) = -C|z| + \text{Constant}$

其中 $C$ 是一个正常数，表示斜率的绝对值。

我们希望噪声集中在 0 附近，远离 0 的概率密度应该更小，因此斜率用 $-C$ 。

现在我们来计算 $C$ 的值。对于任意 $z_1, z_2$ 满足 $|z_1 - z_2| \le \Delta f$ ，都有 $C|z_1| - C|z_2| \le \varepsilon$ 。

为了保证最坏情况，取 $|z_1 - z_2| = \Delta f$ ，这时

$\begin{aligned} C|z_1| - C|z_2| &\le C|z_1 - z_2| \\ &= C \Delta f \\ \end{aligned}$

对于所有情况，需要保证 $C \Delta f \le \varepsilon$ ，即 $C \le \dfrac{\varepsilon}{\Delta f}$ 。

为了在满足条件的前提下让噪声尽可能小（即集中在 0 附近）， $C$ 应该尽可能大。于是我们取 $C = \dfrac{\varepsilon}{\Delta f}$ 。

因此 $\ln(p(z)) = -\dfrac{\varepsilon}{\Delta f}|z| + K$ ，即

$p(z) = \e^K \cdot \e^{-C|z|}$

为了让 $p(z)$ 成为一个合法的概率密度函数，必须满足 $\displaystyle \int_{-\infty}^{+\infty} p(z) \d z = 1$ 。

设 $A = \e^K$ 是一个常数，那么

$\begin{aligned} \int_{-\infty }^{\infty } A \cdot \e^{-C|z|} \d z &= 1 \\ A \cdot \left(\int_{-\infty }^{0} \e^{Cz} \d z + \int_{0}^{\infty } \e^{-Cz} \d z\right) &= 1 \\ A \cdot \dfrac{2}{C} &= 1 \\ A &= \dfrac{C}{2} \end{aligned}$

从这也可以看出来为何上面斜率要是 $-C$ ，还有个原因是为了让积分收敛。

代回去，得到

$p(z) = \dfrac{C}{2} \cdot \e^{-C|z|}$

这正是拉普拉斯分布（Laplace Distribution）的概率密度函数，一般形式为

$\operatorname{Lap}(x \mid \mu, b) = \dfrac{1}{2b} \cdot \e^{-\frac{|x - \mu|}{b}}$

其中 $\mu$ 是位置参数，表示分布的中心位置； $b$ 是尺度参数，控制分布的「宽度」。

这里 $\mu = 0, b = \frac{1}{C} = \frac{\Delta f}{\varepsilon}$ 。

因此，拉普拉斯机制的具体实现是：对于查询函数 $f$ ，它的差分隐私保护版本 $\mathcal{M}(D)$ 定义为

$\mathcal{M}(D) = f(D) + \text{Lap}\left(\tfrac{\Delta f}{\varepsilon}\right)$

这个证明告诉我们，加入的噪声大小，是由查询本身的脆弱性（敏感度 $\Delta f$ ）和我们期望的隐私保护水平（预算 $\varepsilon$ ）共同决定的。

查询越敏感（ $\Delta f$ 越大），意味着单个用户的数据对结果影响越大，为了「掩盖」这个影响，我们就必须加入更大范围的噪声。
隐私要求越高（ $\varepsilon$ 越小），意味着我们要求两种情况下的概率比值越接近 1，我们也必须加入更大范围的噪声。

还有一点补充，上面的证明是关于任意单点 $y$ ，可以证明对于任意集合 $S$ 也成立。

具体证明

上面的证明已经得出了对于任意单点 $y$ ，其概率密度函数满足

$\operatorname{pdf}(\mathcal{M}(D_1) \le y) \le \e^{\varepsilon} \times \operatorname{pdf}(\mathcal{M}(D_2) \le y)$

现在要证明对于任意集合 $S$ ，其概率 $\Pr[\mathcal{M}(D_1) \in S]$ 也满足这个关系。

对于连续型随机变量，一个集合的概率是其概率密度函数在该集合上的积分。所以：

$\Pr[\mathcal{M}(D_1) \in S] = \int_{y \in S} \operatorname{pdf}(\mathcal{M}(D_1) = y) \d y$

将点的不等式代入得

$\int_{y \in S} \operatorname{pdf}(\mathcal{M}(D_1) = y) \d y \le \int_{y \in S} \e^{\varepsilon} \times \operatorname{pdf}(\mathcal{M}(D_2) = y) \d y$

于是有

$\begin{aligned} \int_{y \in S} \operatorname{pdf}(\mathcal{M}(D_1) = y) \d y &\le \e^{\varepsilon} \times \int_{y \in S} \operatorname{pdf}(\mathcal{M}(D_2) = y) \d y\\ \Pr[\mathcal{M}(D_1) \in S] &\le \e^{\varepsilon} \times \Pr[\mathcal{M}(D_2) \in S] \end{aligned}$

$\varepsilon$ -差分隐私性质

无界 DP 蕴含有界 DP

一个满足 $\varepsilon$ -无界 DP 的机制 $\mathcal{M}$ ，必然满足 $2\varepsilon$ -有界 DP。反之则不然。

证明

假设机制 $\mathcal{M}$ 满足 $\varepsilon$ -无界 DP，考虑两个大小相同（比如都为 $k$ ）的有界相邻数据集 $D_1 = X \cup \{a\}$ 和 $D_2 = X \cup \{b\}$ 。目标是证明 $\Pr[\mathcal{M}(D_1) \in S] \le e^{2\varepsilon} \Pr[\mathcal{M}(D_2) \in S]$ 。

可以引入一个中间数据集 $X$ （大小为 $k-1$ ）。

$D_1$ 和 $X$ 是无界相邻的。根据无界 DP 的定义： $\Pr[\mathcal{M}(D_1) \in S] \le e^\varepsilon \Pr[\mathcal{M}(X) \in S]$
$D_2$ 和 $X$ 也是无界相邻的。同样有： $\Pr[\mathcal{M}(X) \in S] \le e^\varepsilon \Pr[\mathcal{M}(D_2) \in S]$

将二式代入一式得到

$\Pr[\mathcal{M}(D_1) \in S] \le e^\varepsilon \cdot (e^\varepsilon \Pr[\mathcal{M}(D_2) \in S]) = e^{2\varepsilon} \Pr[\mathcal{M}(D_2) \in S]$

这就证明了 $\varepsilon$ -无界 DP 蕴含了 $2\varepsilon$ -有界 DP。

这个性质表明，无界差分隐私是更强的隐私保护形式。满足无界 DP 的机制在有界 DP 下也能提供一定程度的隐私保护。当然这个转换会使隐私预算翻倍，即代表隐私保护级别降低了一些。

顺序组合性

如果先后执行了 $k$ 个查询，且每个查询的机制是独立的，分别用了 $\varepsilon_1, \dots, \varepsilon_{k}$ 个预算，那么这 $k$ 个查询合在一起，总的隐私预算消耗是 $\varepsilon = \displaystyle \sum_{i=1}^{k} \varepsilon_i$ 。

证明

只需证明两个查询的情况，多个查询可以通过数学归纳法推广。

设两个查询分别是 $\mathcal{M}_1, \mathcal{M}_2$ ，它们分别满足 $\varepsilon_1$ -差分隐私和 $\varepsilon_2$ -差分隐私。

那么对于任意两个相邻数据库 $D_1, D_2$ ，以及任意结果集合 $S_1, S_2$ ，都有

$\left\lbrace\begin{aligned} \Pr[\mathcal{M}_1(D_1) \in S_1] &\le \e^{\varepsilon_1} \times \Pr[\mathcal{M}_1(D_2) \in S_1] \\ \Pr[\mathcal{M}_2(D_1) \in S_2] &\le \e^{\varepsilon_2} \times \Pr[\mathcal{M}_2(D_2) \in S_2] \\ \end{aligned}\right.$

现在考虑联合查询 $\mathcal{M}(D) = (\mathcal{M}_1(D), \mathcal{M}_2(D))$ ，其结果是一个二元组。对于任意结果集合 $S \subseteq \mathcal{O}_1 \times \mathcal{O}_2$ ^[2]，有

$\begin{aligned} \Pr[\mathcal{M}(D_1) \in S] &= \Pr[(\mathcal{M}_1(D_1), \mathcal{M}_2(D_1)) \in S] \\ &= \sum_{(s_1, s_2) \in S} \Pr[\mathcal{M}_1(D_1) = s_1 \land \mathcal{M}_2(D_1) = s_2] \\ &= \sum_{(s_1, s_2) \in S} \Pr[\mathcal{M}_1(D_1) = s_1] \cdot \Pr[\mathcal{M}_2(D_1) = s_2] \quad \text{（独立性）}\\ &\le \sum_{(s_1, s_2) \in S} \e^{\varepsilon_1} \Pr[\mathcal{M}_1(D_2) = s_1] \cdot \e^{\varepsilon_2} \Pr[\mathcal{M}_2(D_2) = s_2] \quad \text{（应用定义）} \\ &= \e^{\varepsilon_1 + \varepsilon_2} \sum_{(s_1, s_2) \in S} \Pr[\mathcal{M}_1(D_2) = s_1] \cdot \Pr[\mathcal{M}_2(D_2) = s_2] \\ &= \e^{\varepsilon_1 + \varepsilon_2} \Pr[(\mathcal{M}_1(D_2), \mathcal{M}_2(D_2)) \in S] \\ &= \e^{\varepsilon_1 + \varepsilon_2} \Pr[\mathcal{M}(D_2) \in S] \end{aligned}$

因此联合查询 $\mathcal{M}$ 满足 $(\varepsilon_1 + \varepsilon_2)$ -差分隐私。

顺序组合性表明了隐私是一种可消耗的、有限的资源。这迫使数据管理者必须有规划地、有节制地批准数据访问请求，确保最有价值的问题被优先回答，防止隐私预算被低价值的查询耗尽。

这也是隐私预算中「预算」的内涵体现。

并行组合性

如果将数据集 $D$ 分割成 $k$ 个互不相交的子集 $D_1, \dots, D_{k}$ ，并在每个子集 $D_i$ 上独立地执行 $\varepsilon_i$ -差分隐私的查询 $\mathcal{M}_i$ ，那么整体的隐私预算消耗是 $\varepsilon = \max\limits_{1 \le i \le k} \varepsilon_i$ 。

证明

依然只需证明两个子集的情况，多个子集可以通过数学归纳法推广。

设两个不相交子集分别是 $D_1, D_2$ ，它们分别满足 $\varepsilon_1$ -差分隐私 $\mathcal{M}_1$ 和 $\varepsilon_2$ -差分隐私 $\mathcal{M}_2$ ，且两个机制是独立的。

即证明联合机制 $\mathcal{M}(D) = (\mathcal{M}_1(D_1), \mathcal{M}_2(D_2))$ 满足 $\varepsilon = \max(\varepsilon_1, \varepsilon_2)$ -差分隐私。

设 $D, D'$ 是一对相邻数据集，它们仅在某个记录 $r$ 上不同。由于 $D_1, D_2$ 互不相交， $r$ 只能存在于其中一个子集中。

若 $r \in D_1$ ，这意味着 $D_1, D_1'$ 相邻，而 $D_2 = D_2'$ ，即 $D_2$ 没有变化。在这种情况下 $\mathcal{M}_2(D_2) = \mathcal{M}_2(D_2')$ 。反之亦然。

对于任意输出结果集合 $S \subseteq \mathcal{O}_1 \times \mathcal{O}_2$ ，有

$\Pr[\mathcal{M}(D )\in S] = \Pr[(\mathcal{M}_1(D_1), \mathcal{M}_2(D_2)) \in S]$

我们希望证明

$\Pr[(\mathcal{M}_1(D_1), \mathcal{M}_2(D_2)) \in S] \le \e^{\max(\varepsilon_1, \varepsilon_2)} \Pr[(\mathcal{M}_1(D_1'), \mathcal{M}_2(D_2')) \in S]$

假设差异数据 $r \in D_1$ ，有

$\begin{aligned} \Pr[(\mathcal{M}_1(D_1), \mathcal{M}_2(D_2)) \in S] &= \sum_{(s_1, s_2) \in S} \Pr[\mathcal{M}_1(D_1) = s_1 \land \mathcal{M}_2(D_2) = s_2] \\ &= \sum_{(s_1, s_2) \in S} \Pr[\mathcal{M}_1(D_1) = s_1] \cdot \Pr[\mathcal{M}_2(D_2) = s_2] \quad \text{（独立性）}\\ &\le \sum_{(s_1, s_2) \in S} \e^{\varepsilon_1} \Pr[\mathcal{M}_1(D_1') = s_1] \cdot \Pr[\mathcal{M}_2(D_2') = s_2] \quad \text{（应用定义）} \\ &= \e^{\varepsilon_1} \sum_{(s_1, s_2) \in S} \Pr[\mathcal{M}_1(D_1') = s_1] \cdot \Pr[\mathcal{M}_2(D_2') = s_2] \\ &= \e^{\varepsilon_1} \Pr[(\mathcal{M}_1(D_1'), \mathcal{M}_2(D_2')) \in S] \end{aligned}$

同理可以得到当 $r \in D_2$ 时有

$\Pr[(\mathcal{M}_1(D_1), \mathcal{M}_2(D_2)) \in S] \le \e^{\varepsilon_2} \Pr[(\mathcal{M}_1(D_1'), \mathcal{M}_2(D_2')) \in S]$

因此无论 $r$ 属于哪个子集，都有

$\Pr[(\mathcal{M}_1(D_1), \mathcal{M}_2(D_2)) \in S] \le \e^{\max(\varepsilon_1, \varepsilon_2)} \Pr[(\mathcal{M}_1(D_1'), \mathcal{M}_2(D_2')) \in S]$

即联合机制 $\mathcal{M}$ 满足 $\max(\varepsilon_1, \varepsilon_2)$ -差分隐私。

并行组合性意味着，只要操作的数据子集互不关联，就可以进行海量的「并行」计算，而无需担心隐私预算爆炸性增长。

对后续过程的稳健性

对于一个已经满足差分隐私的机制，其输出结果无论经过任何形式的数据处理、分析、计算（无论多么复杂），其最终结果仍然满足相同的差分隐私级别。

证明

即证明如果一个机制 $\mathcal{M}: \mathcal{D} \to \mathcal{O}$ 满足 $\varepsilon$ -差分隐私，那么对于任意一个（随机或确定的）函数 $g\colon \mathcal{O} \to \mathcal{O}'$ ，复合机制 $g \circ \mathcal{M}$ 同样满足 $\varepsilon$ -差分隐私。

设 $\mathcal{M}$ 是一个 $\varepsilon$ -DP 机制。设 $g$ 是任意一个后续处理函数。我们定义一个新的机制 $\mathcal{K}(D) = g(\mathcal{M}(D))$ 。我们需要证明 $\mathcal{K}$ 也是 $\varepsilon$ -DP 的。

对于任意两个相邻数据集 $D_1, D_2$ ，以及任意一个最终输出结果的集合 $S' \subseteq \mathcal{O}'$ ，我们需要证明：

$\Pr[\mathcal{K}(D_1) \in S'] \le \e^{\varepsilon} \times \Pr[\mathcal{K}(D_2) \in S']$

考虑不等式左边的 $\mathcal{K}(D_1)$ 的输出在 $S'$ 中的概率

$\Pr[\mathcal{K}(D_1) \in S'] = \Pr[g(\mathcal{M}(D_1)) \in S']$

为了利用 $\mathcal{M}$ 的差分隐私性质，我们需要将关于 $g$ 输出的事件，转换成关于 $\mathcal{M}$ 输出的事件。

定义一个集合 $S \subseteq \mathcal{O}$ ，它包含了所有能通过 $g$ 映射到 $S'$ 的 $\mathcal{M}$ 的中间输出结果。

$S = \{ o \in \mathcal{O} \mid g(o) \in S' \}$

于是「 $g(\mathcal{M}(D_1))$ 的结果在 $S'$ 中」这个事件，就等价于「 $\mathcal{M}(D_1)$ 的结果在 $S$ 中」这个事件。当然对于 $D_2$ 也是一样。

因此可以重写概率：

$\Pr[g(\mathcal{M}(D_1)) \in S'] = \Pr[\mathcal{M}(D_1) \in S]$

应用 $\mathcal{M}$ 的 $\varepsilon$ -差分隐私性质：因为 $S$ 是 $\mathcal{M}$ 输出空间的一个子集，所以

$\Pr[\mathcal{M}(D_1) \in S] \le \e^{\varepsilon} \times \Pr[\mathcal{M}(D_2) \in S]$

最后将上式右边的概率转换回关于 $\mathcal{K}$ 的形式：

$\e^{\varepsilon} \times \Pr[\mathcal{M}(D_2) \in S] = \e^{\varepsilon} \times \Pr[g(\mathcal{M}(D_2)) \in S'] = \e^{\varepsilon} \times \Pr[\mathcal{K}(D_2) \in S']$

将以上步骤连接起来，我们得到：

$\Pr[\mathcal{K}(D_1) \in S'] = \Pr[\mathcal{M}(D_1) \in S] \le \e^{\varepsilon} \times \Pr[\mathcal{M}(D_2) \in S] = \e^{\varepsilon} \times \Pr[\mathcal{K}(D_2) \in S']$

即

$\Pr[\mathcal{K}(D_1) \in S'] \le \e^{\varepsilon} \times \Pr[\mathcal{K}(D_2) \in S']$

得证。

换句话说，数据分析师无法通过更努力地思考或对输出进行更多计算来削弱其隐私保护。一旦数据通过差分隐私机制发布，它就永远是安全的，不会因为后续操作而泄露更多隐私。

组隐私

隐私保护会随着组的大小 $k$ 平滑地衰减。如果保护单个记录的隐私预算是 $\varepsilon$ ，那么保护一个大小为 $k$ 的组的隐私预算就是 $k \varepsilon$ 。

证明

形式化地说明组隐私就是，如果一个机制 $\mathcal{K}$ 满足 $\varepsilon$ -差分隐私，那么对于任意两个数据集 $D_1, D_2$ ，如果它们之间相差 $k$ 条记录，那么对于任意输出集合 $S$ ，有

$\Pr[\mathcal{K}(D_1) \in S] \le \e^{k\varepsilon} \times \Pr[\mathcal{K}(D_2) \in S]$

这个证明可以通过构造一个数据集序列来完成。

设 $D_1$ 和 $D_2$ 是相差 $k$ 条记录的数据集。我们可以构造一个包含 $k+1$ 个数据集的序列 $D^{(0)}, D^{(1)}, \dots, D^{(k)}$ ，使得：

$D^{(0)} = D_1$
$D^{(k)} = D_2$
序列中任意相邻的两个数据集 $D^{(i)}$ 和 $D^{(i+1)}$ 都只相差 1 条记录（即它们是相邻的）。这可以通过从 $D_1$ 开始，逐一添加/删除记录直到变成 $D_2$ 来实现。

现在我们对这个序列应用标准的 $\varepsilon$ -差分隐私定义：

对于 $D^{(0)}$ 和 $D^{(1)}$ ： $\Pr[\mathcal{K}(D^{(0)}) \in S] \le \e^{\varepsilon} \times \Pr[\mathcal{K}(D^{(1)}) \in S]$
对于 $D^{(1)}$ 和 $D^{(2)}$ ： $\Pr[\mathcal{K}(D^{(1)}) \in S] \le \e^{\varepsilon} \times \Pr[\mathcal{K}(D^{(2)}) \in S]$
……
对于 $D^{(k-1)}$ 和 $D^{(k)}$ ： $\Pr[\mathcal{K}(D^{(k-1)}) \in S] \le \e^{\varepsilon} \times \Pr[\mathcal{K}(D^{(k)}) \in S]$

将这些不等式连乘起来，得到

$\begin{aligned} \Pr[\mathcal{K}(D^{(0)}) \in S] &\le \e^{\varepsilon} \times \Pr[\mathcal{K}(D^{(1)}) \in S] \\ &\le \e^{\varepsilon} \times (\e^{\varepsilon} \times \Pr[\mathcal{K}(D^{(2)}) \in S]) \\ &\le \dots \\ &\le \e^{k\varepsilon} \times \Pr[\mathcal{K}(D^{(k)}) \in S] \\ &= \e^{k\varepsilon} \times \Pr[\mathcal{K}(D_2) \in S] \end{aligned}$

得证。

组隐私量化了当攻击者拥有关于一个群体的背景知识时，隐私泄露的风险。它告诉我们， $\varepsilon$ 的值必须足够小，因为实际的隐私损失会随着攻击者目标群体的大小而放大。

通过子抽样实现的隐私放大

设有一个大小为 $n$ 的数据集 $D$ 。以采样率 $p = \frac{m}{n}$ 从 $D$ 中随机抽样（无放回）一个大小为 $m$ 的子样本 $D_{\text{sample}}$ 。

如果机制 $\mathcal{M}$ 在作用于大小为 $m$ 的数据集时满足有界 $\varepsilon$ -差分隐私，那么将抽样和 $\mathcal{M}$ 结合起来的复合机制 $\mathcal{K}(D) = \mathcal{M}(D_{\text{sample}})$ ，对于原始数据集 $D$ 来说，满足更强的 $\ln(1+p(\e^\varepsilon-1))$ -差分隐私。

当 $\varepsilon$ 很小时，这个值约等于 $p\varepsilon$ -差分隐私，即隐私预算被缩小了采样率 $p$ 的倍数。

证明

设有两个在无界意义上相邻的数据集 $D_1, D_2$ ，其中 $|D_1|=n, |D_2|=n-1$ ，且 $D_1 = D_2 \cup \{r\}$ 。

设机制 $\mathcal{M}$ 作用于大小为 $m$ 的数据集时，满足有界意义上的 $\varepsilon$ -差分隐私。即对于任意大小为 $m$ 的、仅相差一个元素（替换关系）的数据集 $D_a, D_b$ ，都有 $\Pr[\mathcal{M}(D_a) \in S] \le e^\varepsilon \Pr[\mathcal{M}(D_b) \in S]$ 。

我们分析复合机制 $\mathcal{K}(D) = \mathcal{M}(D_{\text{sample}})$ 。

我们想要比较 $\Pr[\mathcal{K}(D_1) \in S]$ 与 $\Pr[\mathcal{K}(D_2) \in S]$ ，其中 $S$ 是 $\mathcal{M}$ 的输出空间的一个子集。

从 $D_1$ 抽样时，有两种情况：

抽样包含记录 $r$ 。这种情况发生的概率是 $p = \frac{m}{n}$ 。
抽样不包含记录 $r$ 。这种情况发生的概率是 $1 - p$ 。

于是 $\Pr[\mathcal{K}(D_1) \in S]$ 可以分解为：

$\Pr[\mathcal{K}(D_1) \in S] = p \cdot \Pr[\mathcal{M}(D_{\text{sample}}) \in S \mid r \in D_{\text{sample}}] + (1 - p) \cdot \Pr[\mathcal{M}(D_{\text{sample}}) \in S \mid r \notin D_{\text{sample}}]$

若 $r$ 被抽中，那么样本的其余 $m-1$ 个元素来自 $D_2$ 。这种情况下的概率可以表示为 $\Pr[\mathcal{M}(R \cup \left\lbrace r \right\rbrace) \in S]$ ，其中 $R$ 是从 $D_2$ 中随机抽取的大小为 $m-1$ 的子集。

若 $r$ 未被抽中，则样本全部 $m$ 个元素都来自 $D_2$ 。这种情况下的概率与从 $D_2$ 中抽样完全的概率一样，即 $\Pr[\mathcal{K}(D_2 )\in S]$ 。

因此

$\begin{aligned} \Pr[\mathcal{K}(D_1) \in S] &= p \cdot \Pr[\mathcal{M}(D_{\text{sample}}) \in S \mid r \in D_{\text{sample}}] + (1 - p) \cdot \Pr[\mathcal{M}(D_{\text{sample}}) \in S \mid r \notin D_{\text{sample}}]\\ &= p \cdot \mathbb{E}_{R \sim D_2^{m-1}}[\Pr[\mathcal{M}(R \cup \{r\}) \in S]] + (1 - p) \cdot \Pr[\mathcal{K}(D_2) \in S] \end{aligned}$

其中 $R \sim D_2^{m-1}$ 表示 $R$ 是从 $D_2$ 中随机抽取的大小为 $m-1$ 的子集， $\mathbb{E}$ 表示取期望。

现在，我们来约束第一项的期望值。对于一个固定的、从 $D_2$ 中抽取的 $m-1$ 大小的子集 $R$ ，我们考虑数据集 $R \cup \{r\}$ 。这是一个大小为 $m$ 的数据集。

为了应用 $\mathcal{M}$ 的隐私保证，我们需要将它与另一个在有界意义上相邻的数据集进行比较。我们构造一系列这样的数据集：对于任何 $x \in D_2 \setminus R$ ，数据集 $R \cup \{x\}$ 的大小也为 $m$ ，且与 $R \cup \{r\}$ 仅在 $r$ 和 $x$ 这一个位置上不同。

根据 $\mathcal{M}$ 的有界 $\varepsilon$ -DP 定义，对于任何 $x \in D_2 \setminus R$ ，我们有：

$\Pr[\mathcal{M}(R \cup \{r\}) \in S] \le e^{\varepsilon} \Pr[\mathcal{M}(R \cup \{x\}) \in S]$

由于上式对所有 $n-m$ 个可能的 $x$ 都成立，我们可以对其取平均值，而不会破坏不等式：

$\Pr[\mathcal{M}(R \cup \{r\}) \in S] \le e^{\varepsilon} \cdot \frac{1}{n-m} \sum_{x \in D_2 \setminus R} \Pr[\mathcal{M}(R \cup \{x\}) \in S]$

现在，我们对 $R$ 取期望，利用期望的线性性质：

$\mathbb{E}_{R \sim D_2^{m-1}}[\Pr[\mathcal{M}(R \cup \{r\}) \in S]] \le e^{\varepsilon} \cdot \mathbb{E}_{R \sim D_2^{m-1}}\left[ \frac{1}{n-m} \sum_{x \in D_2 \setminus R} \Pr[\mathcal{M}(R \cup \{x\}) \in S] \right]$

不等式右边的期望项。它描述了这样一个过程：

从 $D_2$ 中随机抽取一个大小为 $m-1$ 的子集 $R$ 。
从剩下的 $n-m$ 个元素中随机抽取一个元素 $x$ 。
将它们合并成一个大小为 $m$ 的数据集 $R \cup \{x\}$ 。
计算 $\mathcal{M}(R \cup \{x\})$ 的输出概率，并对所有可能的 $R$ 和 $x$ 取平均。

这个过程其实等价于直接从 $D_2$ 中随机抽取一个大小为 $m$ 的子集。因此，这个期望值正好就是 $\Pr[\mathcal{K}(D_2) \in S]$ 。即

$\mathbb{E}_{R \sim D_2^{m-1}}\left[ \frac{1}{n-m} \sum_{x \in D_2 \setminus R} \Pr[\mathcal{M}(R \cup \{x\}) \in S] \right] = \Pr[\mathcal{K}(D_2) \in S]$

所以，我们得到了界：

$\mathbb{E}_{R \sim D_2^{m-1}}[\Pr[\mathcal{M}(R \cup \{r\}) \in S]] \le \e^{\varepsilon} \cdot \Pr[\mathcal{K}(D_2) \in S]$

将这个结果代回 $\Pr[\mathcal{K}(D_1) \in S]$ 的表达式中，得到

$\begin{aligned} \Pr[\mathcal{K}(D_1) \in S] &= p \cdot \mathbb{E}_{R \sim D_2^{m-1}}[\Pr[\mathcal{M}(R \cup \{r\}) \in S]] + (1 - p) \cdot \Pr[\mathcal{K}(D_2) \in S] \\ &\le p \cdot (\e^{\varepsilon} \cdot \Pr[\mathcal{K}(D_2) \in S]) + (1 - p) \cdot \Pr[\mathcal{K}(D_2) \in S] \\ &= (p \e^{\varepsilon} + 1 - p) \cdot \Pr[\mathcal{K}(D_2) \in S] \\ &= (1 + p(\e^{\varepsilon} - 1)) \cdot \Pr[\mathcal{K}(D_2) \in S] \\ \end{aligned}$

即

$\Pr[\mathcal{K}(D_1) \in S] \le (1 + p(\e^{\varepsilon} - 1)) \cdot \Pr[\mathcal{K}(D_2) \in S]$

因此，复合机制 $\mathcal{K}$ 满足 $\ln(1 + p(\e^{\varepsilon} - 1))$ -差分隐私。

如果想对一个大型数据集进行差分隐私分析，一个常见的方法就是像上面那样从大数据集中随机抽取一小部分数据（一个子样本），然后在这个子样本上运行一个差分隐私机制。

这个「随机抽样」的步骤本身就提供了额外的隐私保护。因为对于任何一个个体来说，他们的信息有可能根本没有被抽中。这种不确定性放大了原有机制的隐私保护效果。

隐私放大效应使得我们可以在数千次迭代后，总的隐私预算仍然保持在一个合理的范围内，否则隐私预算会因顺序组合性而迅速耗尽。

高斯机制

纯 $\varepsilon$ -差分隐私的定义非常严格，它要求对于所有可能的输出结果，概率比都受到严格限制。这种严格性使得设计满足纯 $\varepsilon$ -差分隐私的机制变得非常困难，可能需要加入过大的噪声，导致数据不可用。

因此引入了一种松弛的版本—— $(\varepsilon, \delta)$ -差分隐私，允许有一小部分输出结果不满足严格的 $\varepsilon$ -差分隐私条件。

$(\varepsilon, \delta)$ -差分隐私定义

机制 $\mathcal{M}$ 满足 $(\varepsilon, \delta)$ -差分隐私，如果对于任意两个相邻数据集 $D_1, D_2$ ，以及任意输出结果集合 $S$ ，都有

$\Pr[\mathcal{M}(D_1) \in S] \le \e^{\varepsilon} \times \Pr[\mathcal{M}(D_2) \in S] + \delta$

其中 $\delta$ 是一个非常小的值，通常远小于 $\frac{1}{|D|}$ 。

类似拉普拉斯机制添加的是拉普拉斯噪声，高斯机制（Gaussian Mechanism）通过向查询结果添加高斯（正态）分布的噪声来实现 $(\varepsilon, \delta)$ -差分隐私：

$\mathcal{M}(D) = f(D) + \mathcal{N}(0, \sigma^2)$

具体的相关证明可能要参考 The Algorithmic Foundations of Differential Privacy (Dwork & Roth, 2014)，暂略。

直接给出结论，对于任意 $\varepsilon \in (0,1)$ 和 $\delta > 0$ ，如果高斯噪声的标准差满足

$\sigma \ge \frac{\Delta_2 f \sqrt{2 \ln(1.25/\delta)}}{\varepsilon}$

那么高斯机制 $\mathcal{M}(D) = f(D) + \mathcal{N}(0, \sigma^2)$ 满足 $(\varepsilon, \delta)$ -差分隐私。

其中 $\Delta_2 f$ 是查询函数 $f$ 的 $\ell_2$ 敏感度，定义为

$\Delta_2 f = \max_{D_1, D_2} \|f(D_1) - f(D_2)\|_2$

高斯机制有关的性质与证明跟概率论与统计课学的知识息息相关，可惜我已经忘得差不多了，相关资料看得吃力，加上上面那本书也没读过，因此这部分就草草结束吧，知道有这么回事就行了。

参考

这里的定义是无界差分隐私（Unbounded Differential Privacy），即数据集大小可变，只能添加或删除记录。另一种定义是有界差分隐私（Bounded Differential Privacy）即数据集大小固定，可以修改记录内容，但不能添加或删除记录。满足无界差分隐私的机制也满足有界差分隐私。 ↩︎
其中 $\mathcal{O}_1, \mathcal{O}_2$ 分别是 $\mathcal{M}_1, \mathcal{M}_2$ 的输出空间，即 $S$ 是联合输出空间 $\mathcal{O}_1 \times \mathcal{O}_2$ 的子集。 ↩︎