2.3 形式化差分隐私（2）

2.3.1 差分隐私的承诺

经济观点 ：差分隐私承诺保护个人信息免受任何额外的损害，这种损害的出现是因为他们的数据在私有数据库 $x$ 中。如果他们的数据不是 $x$ 的一部分，他们就不会遭到这些损害。尽管一旦差分隐私机制 $\mathcal{M}$ 的结果 $\mathcal{M}(x)$ 发布，个人信息确实可能会面临伤害。差分隐私承诺，他们选择参与数据发布并不会显著增加伤害的可能性。这是一个非常功利的隐私定义，因为当一个人决定是否将她的数据包含在差分隐私数据库中时，她会考虑这种差异：与不参与数据发布相比，她的个人信息在参与后遭到损害的概率。因为她无法控制数据库的其余内容，所以考虑到了差别隐私的承诺，她能确信从未来的损害来看，参与与不参与数据发布造成的影响几乎没什么差别。如果给予任何激励———从利他主义到金钱回报——差分隐私可能会说服她允许使用她的数据。这种直觉可以在效用理论的意义上被形式化，我们在这里简单地描述一下。

考虑一个对所有可能的未来事件集合有任意偏好的个体 $i$ ，我们用 $\mathcal{A}$ 来表示。这些偏好由一个效用函数 $u_i$ 来表示 $u_i:\mathcal{A} \to \mathbb{R}_{\geqslant0}$ ，我们说个体$i$在 $a \in \mathcal{A}$ 的情况下,其效用为 $u_i(a)$。假设 $x \in \mathbb{N}^{|\mathcal{X}|}$ 是一个包含个体 $i$ 的私有数据的数据集，$\mathcal{M}$ 是一个 $\varepsilon$- 差分隐私算法。设 $y$ 与 $x$ 为相邻的数据集，它不包括个体 $i$ 的数据（$\Vert x-y\Vert _1 \leq 1$）。并设 $f:Range(\mathcal{M} ) \to \Delta(\mathcal{A})$ 为（任意）函数，该函数决定未来事件 $\mathcal{A}$ 的分布，以机制M的输出为条件（注：此处$\Delta(\mathcal{A})$函数为定义 2.1（概率单纯形）函数）。通过差分隐私的保证以及 命题 2.1 保证的任意后处理的弹性，我们可以有： $\begin{aligned} \mathbb{E}_{a \backsim f(\mathcal{M}(x))}[u_i(a)] &= \sum_{a \in \mathcal{A}}u_i(a) \cdotp \underset{f(\mathcal{M}(x))}{\text{Pr}}[a] \\ &\leq \sum_{a \in \mathcal{A}} u_i(a) \cdotp exp(\varepsilon) \underset{f(\mathcal{M}(y))}{\text{Pr}}[a] \\ &= exp(\varepsilon)\mathbb{E}_{a \backsim f(\mathcal{M}(y))}[u_i(a)] \end{aligned}$ 同理， $\mathbb{E}_{a \backsim f(\mathcal{M}(x))}[u_i(a)] \geqslant exp(-\varepsilon)\mathbb{E}_{a \backsim f(\mathcal{M}(y))}[u_i(a)]$

因此，通过保证 $\varepsilon$- 差分隐私，数据分析师可以向个人保证，其预期的未来效用不会受到超过 $exp(\varepsilon) \approx (1+\varepsilon)$ 因子的损害。（注：由 $e^x$ 的泰勒展开得到的近似值）注意，这个承诺独立于个人的是效用函数 $u_i(a)$，同时适用于可能具有完全不同效用函数的多个人。

【注：在哈弗大学的差分隐私课程中，将上述概括为：

• 攻击者从差分隐私提供的数据中知道关于个体什么信息，它都可以从其他个体的数据中学到一样的信息。
• 机制不能泄漏“个人特定”信息。
• 且不受对手所拥有辅助信息或计算能力的影响。

】

2.3.2 差分隐私不能保证什么

正如我们在吸烟导致癌症的例子中所看到的，尽管差分隐私是一个非常有力的保证，但它并不能保证无条件的免受伤害。它也不会在以前没有存在的地方创造隐私。更确切的说，差别隐私并不能保证一个人认为是自己秘密的东西仍然是秘密的。它只是确保一个人参与数据的发布本身不会被泄露，也不会导致泄露任何一个人参与的具体情况。从数据中得出的结论很可能反映了个人的统计信息。一项旨在发现特定疾病早期指标的健康调查可能会产生强有力的、甚至是结论性的结果；这些结论对于特定的个人来说并不是差分隐私被攻击的证据；这个人的个人信息甚至可能没有参与到数据集中（再次，差分隐私确保无论个人是否参与调查，这些结论性结果都以非常相似的概率获得。）特别是，如果调查告诉我们，特定的私人属性与公共可观察属性密切相关，那么这并不是对差分隐私的攻击，因为这种相同的相关性将以几乎相同的概率被观察到，而不受任何被调查者的存在或不存在的影响。

差分隐私的性质 引入并正式定义了差分隐私之后，我们将概括说明其关键的性质。

• 1.防范任意风险，防止个人数据被重新识别。
• 2.自动消除链接攻击，包括尝试使用所有过去，现在和将来的数据集以及其他形式和辅助信息源进行的所有攻击。
• 3.量化隐私损失。 差分隐私不是二元概念，它具有一定程度的隐私损失。这允许在不同技术之间进行比较：对于固定的隐私损失，哪种技术可以提供更好的准确性？ 对于固定的数据精度，哪种技术可以提供更好的隐私？
• 4.差分隐私合成。也许最关键的是，损失的量化还允许对多次计算中的累积隐私损失进行分析和控制。了解合成下的差分隐私机制的行为，可以让我们从较简单的差分隐私模块设计到分析复杂的差分隐私算法。
• 5.群隐私。差分隐私允许对诸如家庭之类的群体造成的隐私损失进行分析和控制。
• 6.后处理中的闭包差异隐私不受后处理的影响：数据分析师在没有其他有关隐私数据库的知识的情况下，无法计算差分隐私算法$\mathcal{M}$ 的输出函数，也就无法使其具有差分隐私性。也就是说，无论有什么辅助信息，无论是在形式上的定义上，还是在任何直觉上，数据分析师都无法通过简单地坐在角落里思考算法的输出来增加隐私损失。

这些是差分隐私的性质。我们可以证明这些性质可逆吗？ 也就是说，这些性质或其中的某些子集是否暗含差分隐私？差分隐私能否在这些方面被削弱并且仍然有意义？这些是悬而未决的问题。

【注：在哈弗大学的差分隐私课程中，将上述概括为：

• 差分隐私无法保证对手不会推断出敏感属性。
• 差分隐私不保证分析结果不会“损害”个体。
• 差分隐私对于未定位到哪几行的信息不提供保护。

】

2.3.3 定义注解

隐私的粒度。 应当仔细审查有关差分隐私的声明，以确保承诺的保密性级别。差分隐私保证即使修改数据库中的单个条目，算法的行为也将大致保持不变。但是，什么构成数据库中的单个条目？考虑例如采用图数据库。 这样的数据库可能会编码一个社交网络：每个个体 $i \in [n]$ 由图中的一个顶点表示，而个体之间的联系则由边表示。

我们可以在与个体相对应的粒度级别上考虑差分隐私：也就是说，我们可能要求差分隐私算法对从图中添加或删除任何顶点不敏感。这提供了强大的隐私保证，但实际上在图中添加删除节点可能会造成比想象中更大的影响。 单个顶点的添加或删除可以在图中最多添加或删除 $n$ 条边。我们希望从图中学习到信息，但是去除 $n$ 条边不敏感性可能导致无法学习到有效信息。

另一方面，我们可以在对应于边的粒度级别上考虑差分隐私，并要求我们的算法仅对从图中添加或删除单个或少量边不敏感。当然，这是较弱的保证，但对于某些目的可能仍然足够。简单来说，如果我们承诺在每条边上具有 $\varepsilon$- 差分隐私，那么任何数据分析人员都不能得出关于图中 $1/\varepsilon$ 条边的任何子集存在与否的结论。在某些情况下，大批社交联系人可能不会被视为敏感信息：例如，一个人可能没有必要隐藏一个事实，即他的大部分联系对象都是他所在城市或工作场所中的某个人，因为他的住所和住所他工作的地方是公共信息。另一方面，可能存在少数高度敏感的社会联系人（例如，潜在的新雇主或亲密朋友）。在这种情况下，边隐私应足以保护敏感信息，同时也能比顶点隐私数据得到更全面地分析。假设一个人的朋友少于 $1/\varepsilon$ 个，边隐私将保护此类个人的敏感信息。

作为另一个示例，可以设计差分性私人电影推荐系统，以在单个电影的“事件”级别保护训练集中的数据，隐藏任何单个电影的观点/打分，而不是隐藏个人对于电影的热情。（如美国人对西部牛仔或血腥牛仔的热情），或对于“用户”级别数据来说，不隐藏个人整体观点和打分历史。

小$\varepsilon$差分隐私机制都很相像。当 $\varepsilon$ 较小时，$(\varepsilon,0)$- 差分隐私 断言，对于所有成对的相邻数据库 $x,y$和所有输出 $o$，对手无法根据观察 $o$ 来区分哪个是真正的数据库。当 $\varepsilon$ 较小时，未能成为$(\varepsilon,0)$- 差分隐私没必要惊讶。例如，该机制可能是$(2\varepsilon,0)$- 差分隐私。差分隐私的性质保证了具有不同但都很小的$\varepsilon$时，机制的表现是相似的。

但是 $\varepsilon$ 设置多大的值算大？未能满足 $(15,0)$- 差分隐私仅表示存在相邻数据库，并且输出 $o$ 的情况下，基于对数据库 $x,y$ 的观察，输出 $o$ 的概率大。而且$o$ 的输出可能不太相同（这被 $(\varepsilon,\delta)$- 差分隐私解决）；数据库$x$和$y$可能设计得很复杂，很可能出现在“现实世界”中；攻击者可能没有正确的辅助信息来识别已经发生了泄露的输出；攻击者也可能对数据库了解得不够多，无法确定其对称差异的值。因此，就像弱密码系统可能泄漏从消息的最低有效位到完整的解密密钥的任何东西一样，未能满足$(\varepsilon,0)$- 或 $(\varepsilon,\delta)$- 差分隐私可能导致从有效的无意义隐私泄露到整个数据库的完全泄漏。一个大的$\varepsilon$ 以它自己的方式是大的。

其他形式 除了数据库之外，我们的隐私机制 $\mathcal{M}$ 通常还会将一些辅助参数 $w$ 作为输入。 例如，$w$ 可以在数据库 $x$ 上指定查询 $q_w$ 或查询集合$\mathcal{Q}_w$。 机制 $\mathcal{M}(w,x)$ 可能（分别）对 $q_w(x)$ 或 $\mathcal{Q}_w$ 中某些或所有查询进行差分隐私响应。 对于所有 $\delta \geqslant 0$，我们说如果每个$w,\mathcal{M}(w,\cdot)$ 都满足$(\varepsilon,\delta)$- 差分隐私，则机制$\mathcal{M}(\cdot,\cdot)$ 满足 $(\varepsilon,\delta)$- 差分隐私。

$w$ 参数中可能包含的参数的另一个示例是控制 $\delta = \delta(k)$ 应该多小的安全性参数 $k$。也就是说，对于所有 $k$ ，$\mathcal{M}(k,\cdot)$ 应该是 $(\varepsilon,\delta(k)$- 差分隐私的。通常，在本专论中，我们要求 $\delta$ 在 $k$ 中的作用可以忽略不计，即 $\delta = k^{-w(1)}$。因此，我们认为 $\delta$ 在密码学意义上较小，而 $\varepsilon$ 通常被认为是中等较小的常数。

在辅助参数 $w$ 指定集合 $\mathcal{Q}_w=\{q: \mathcal{X}^n \to \mathbb{R} \}$ 的情况下，我们将机制 $\mathcal{M}$ 称为摘要生成器。摘要生成器输出一个（差分隐私）摘要 $\mathcal{A}$，该摘要 $\mathcal{A}$ 可用于计算 $\mathcal{Q}_w$ 中所有查询的答案。也就是说，我们需要有一个重构过程 $R$，以便对于指定查询 $q_v \in \mathcal{Q}_w$ 的每个输入 $v$，重构过程输出 $R(\mathcal{A},v) \in \mathbb{R}$。通常，我们将要求高概率 $\mathcal{M}$ 产生一个摘要 $\mathcal{A}$，以便使用 $\mathcal{A}$ 的重构过程可以计算出准确的答案。也就是说，对于全部或大部分（通过某种分布加权）查询 $q_v \in \mathcal{Q}_w$，误差 $|R(\mathcal{A},v)-q_v(x)|$ 将受到限制。我们有时会滥用表示法，并参考重构过程，以实际查询 $q$（而不是其某些重新表示的 $v$ ）作为输入，并输出$R(\mathcal{A},q)$。

摘要的一个特殊情况是综合数据库。顾名思义，合成数据库的行与原始数据库的行具有相同的类型。合成数据库的优点是可以使用分析人员将在原始数据库上使用的相同软件进行分析，从而无需特殊的重构过程 $\mathbb{R}$。

备注2.1 由于浮点数实现的微妙之处，在编程诸如 Laplace 机制之类的有价机制时，必须格外小心。否则，差分隐私可能会被破坏，因为数据库 $x$ 上具有非零概率的输出，由于四舍五入的缘故，相邻数据库 $y$ 上的概率可能为零。这只是在差异性隐私的情况下需要仔细检查浮点实现的一种方式，并且它不是唯一的。

(个人理解：多参数的输入机制的引入对查询及其查询子集作出更多操作，其中机制 $\mathcal{M}(w,x)$ 中的参数要与 $(\varepsilon,\delta)$- 差分隐私中的隐私预算区分开来。对于后面的摘要生成器我的理解是对原始数据集的差分隐私化处理，将结果重新映射到数据集上。这有待后期深入理解和学习。)