拥有数据的同时隐藏数据：差分隐私介绍

许多应用程序都依赖用户数据来提供有用的功能。例如，浏览器遥测技术可以通过收集和汇总个人数据来识别网络错误或有缺陷的网站。然而，浏览历史可能很敏感，共享这些信息会带来隐私风险。有趣的是，这些应用程序通常对单个数据点不感兴趣（例如，某一特定用户在尝试访问 Wikipedia 时是否遇到网络错误），而只关心汇总数据（例如，无法连接 Wikipedia 的用户总数）。

分布式聚合协议 (DAP) 允许在不泄露任何个人数据点的情况下聚合数据。对于数据收集器对总体趋势感兴趣但无法访问敏感数据的应用程序来说，它非常有用。DAP 有很多用例，从 COVID-19 暴露通知到 Firefox 中的遥测，再到 iOS 中的个性化相册等等。Cloudflare 正在帮助标准化 DAP 及其底层原语。我们正在致力于 DAP 的开源实施，且正在构建一项与当前和未来合作伙伴一起运行的服务。查看这篇博文，了解有关 DAP 工作原理的更多信息。

DAP 在正确的方向上迈出了重要的一步，但仅靠私人聚合往往不足以保护隐私。在本篇文章中，我们将解释 DAP 的不足之处，以及如何通过添加差分隐私来改进 DAP。

DAP 使用一种称为_多方计算_的加密技术。在高层，多方计算通过将聚合计算分配给多个服务器来提高隐私性，这样任何服务器都不会看到任何个人的数据。（有关多方计算的入门知识，请参阅我们之前关于 DAP 的博客文章。）乍一看，这似乎应该足以保护每个单独用户的隐私：数据收集器仅了解其_需要_的信息（即 ，聚合信息），而不是用于计算它的基础数据。不幸的是，情况往往并非如此，因为聚合信息本身有时会泄露大量私人信息。

8 英尺 11.1 英寸（2.72 米）高的罗伯特·瓦德洛 (Robert Wadlow) 摆姿势拍全家福，1939 年。图片来源：Paille // CC BY-SA 2.0。

举一个简单的例子，假设有一组数字，其中所有的值都相等，那么计算这一组数字的平均值，即可得出这一组数字中每个数的值。但是，知道一些数字的总和也可以得出这一组数字中是否存在特别大或特别小的数字。例如，假设我们正在计算一群人的平均身高。如果这群人中的某个成员特别高（如上图所示），那么知道这群人中有多少人以及预期的平均身高，我们就可以推断出有关该人身高的大量信息。

更普遍地说，如果发布太多有关一个数据库的精确聚合数据，则可能使得攻击者能够重建整个数据库。

这种攻击在现实生活中是存在的。例如，针对美国人口普查的去匿名化攻击已经得到了可靠的证实。大型语言模型（如 ChatGPT）也很容易受到攻击；机器学习模型可以看作是在训练数据集上计算的一种特殊类型的统计集合。下面是一个攻击实例，研究人员给 GPT-2 下达了一条特殊指令，提取了一个真实个体的姓名、地址和电话号码，而这个个体的数据在训练数据集中只出现过一次：

图 1 摘自“Extracting Training Data from Large Language Models”（从大型语言模型中提取训练数据），USENIX Security ‘21，https://arxiv.org/pdf/2012.07805.pdf。

保护模型训练输入的一种方法是称为_联合学习_的技术，其中数据保存在最终用户设备上，模型更新由中央服务器聚合。（聚合步骤甚至可以在 DAP 中完成。）然而，即使这些系统也容易受到巧妙攻击的影响，此类攻击可以利用最终模型以及一些中间版本来重建敏感数据。

我们用下图来说明这一想法，该图来自最近的一篇论文，描述了对正在进行图像分类训练的机器学习模型的攻击。在此示例中，我们从 8 个用户开始，每个用户都有一个带标签的图像（例如，一张被标记为“猫”的猫的图像）。这些起始图像被称为_基本事实_。每个用户都让他们的图像通过图像分类模型，看看它是否可以准确地标记照片中的内容。当模型失败时，它会生成模型更新——一组数据，告诉模型如何自我改进，以便下次更可靠地识别该用户的照片。

所有八个用户都在本地生成自己的模型更新，然后使用联合学习来提取这些模型改进的平均值，这种方式表面上是为了避免提取任何单独的更新或照片。不过，研究人员能够利用这种方法。

攻击的目标是在只能访问联合的平均更新的情况下，重建图中最下面一行的 8 个基本事实图像。攻击者从随机猜测（“初始”）开始，并逐步改进猜测，使其更新方向与真正的平均更新相似。经过足够多的迭代后，我们看到攻击者猜测（“完全泄露”）中的图像与真正的基本事实数据集中的图像接近，尽管顺序可能不同。

图 4 来自“Deep Leakage from Gradients”，NeurIPS ‘19，https://arxiv.org/pdf/1906.08935.pdf。

这些攻击表明私人聚合（使用 DAP 或通过其他方式）不足以保护隐私。幸运的是，有一条前进的道路：包括 Apple、Google、美国人口普查局以及越来越多的行业和政府参与者在内的各种组织现在都在使用差分隐私来保护他们的数据。

差分隐私 (DP) 是一种统计框架，可为安全聚合系统提供额外的数据保护层。它会向聚合数据添加干扰信息，防止攻击者过多地了解任何个人的信息。粗略地说，随机添加的量与隐私参数成反比，隐私参数通常用希腊字母 𝜖（发音为“epsilon”）表示：小 𝜖 值表示隐私性更强，但结果有干扰信息，而大 𝜖 值表示隐私性较差，但更准确。通过这种方式，𝜖 严格量化聚合数据所揭示的信息量。

平心而论，即使没有差分隐私，一些对敏感数据集进行计算统计的部署也已经通过施加某些限制来防止最公然的隐私侵犯。例如，DAP 有一种机制，可以防止数据收集器聚合过小输入批次。在其他情况下，当某些属性在数据集中不常出现时，可以对其进行编辑，或者限制数据点的聚合次数。不过，这种临时性的隐私保护措施很容易对数据做出无效的假设。

首先，这些限制本质上是针对一些明显攻击的“补丁”，但不一定涵盖所有可能的攻击。例如，某些聚合任务对异常值特别敏感，但仍然可能泄漏特别不寻常的测量值是否是聚合集的一部分。此外，虽然简单的聚合（例如总和）更容易通过自定义规则来保护，但多维和结构化统计数据（例如（平均）神经网络更新）可能会泄漏大量信息，如上一节所示。相反，差分隐私是一种通用属性，可以保护复杂的统计数据，甚至可以抵御我们一无所知的对手。

其次，差分隐私的另一个好处是它可以协调跨应用程序的安全参数：隐私保证表示为 𝜖 的特定值，可以在从位数到联合学习的用例之间进行比较。𝜖 的值也可以公开传达或与 DP 专家讨论。虽然设置 𝜖 仍然是一件复杂的事情（见下文），但它至少比设置参数（例如要聚合的测量值数量）更少依赖于应用程序。事实上，差分隐私参数构成了一个额外的自由度，它将隐私与其他特定于应用程序的参数分开，从而更好地控制实用性和隐私之间的权衡（例如，可以先修复 𝜖，然后再独立决定聚合任务的批量大小）。

最后，大多数人工设计的保护和匿名技术无法提供与差分隐私相同的优雅和实用属性。例如，当多组报告相互关联时，或者当相同的基础数据被多次聚合时（这在联合学习等某些应用程序中至关重要），DP 可以保证柔性降级，而临时方法或 k 匿名 (k-anonymity) 等定义在这些情况下可能会灾难性地失败。DP 还具有其他可取的属性，例如抵御边信息的能力（例如，一些现实生活中的隐私攻击可能会利用从数据经纪人处购买的数据集）。

从根本上说，差分隐私将隐私工程的猫捉老鼠游戏转变为严格的数学框架，在该框架中，隐私得到证明，而不仅仅是声称。

作为 Cloudflare 的实习生（2023 年夏季），我的任务是设计一种赋予 DAP 差分隐私的策略，同时针对我们将在本文中探讨的 Cloudflare 的一些 DAP 用例进行优化。有很多方法可以做到这一点。我们重点介绍三种技术，它们具有不同的威胁模型：

• 最简单的方法是照常计算聚合，然后添加干扰信息。DAP 协议定义了一个称为“收集器”的角色，其是聚合结果的预期接收者。收集器本身可以添加干扰信息（我们可以将其称为收集器随机化或 Central DP）。当然，问题是从收集器的角度来看，聚合结果不是 DP。

• 另一种方法称为 Local DP（或 DAP 上下文中的客户端随机化），要求每个客户端在提交报告之前添加干扰信息。这提供了强有力的隐私保证（即使所有聚合器和收集器都是恶意的，DP 仍然有效），但通常会牺牲准确性。这是因为为了实现隐私，必须在每个测量值中添加更多干扰信息。不过，最近的进展使得此类协议在某些情况下变得实用。

• DAP 涉及另一个称为“聚合器”的角色，它计算聚合结果的一部分。（将各聚合器的份额合并即可得到聚合结果。）作为中间方案，我们可以让每个聚合器向其聚合份额添加干扰信息，从而确保从收集器的角度来看聚合结果是 DP。当然，我们必须相信至少有一个聚合器是诚实的，并且会通过正确的分配增加干扰信息。

第三种方法，我们称之为聚合器随机化，是在我实习期间大家决定研究的方法。它实施起来很简单，计算开销与基本 Central DP 大致相同，并且满足与 DAP 相同的威胁模型（稍后会详细介绍！）。聚合器随机化如下图所示。

尽管我们的 DAP 聚合器随机化版本看起来很简单，但我们需要确信它提供了我们期望的隐私保证。这意味着要写下协议，并对其保证进行正式分析。

有趣的是，DP 的传统定义和标准证明技术并不立即适用于我们的设置。事实上，与大多数 DP 机制不同，DAP 是一种交互协议，涉及分布在互联网上的许多方（客户端、聚合器、收集器），其中一些可能是恶意的。此外，DAP 的安全性基于计算假设（我们假设如破解 AES 之类的某些加密问题成本高昂），其中考虑了可能在“合理”时间内运行的对手。DP 的标准概念考虑了具有任意运行时间的对手。

幸运的是，过去已经研究过将差分隐私与多方计算相结合的其他协议，而且在计算差分隐私**的大框架下也有合适的定义。**DP 的这一定义使我们有可能模拟一个计算受限的对手与现实世界中包含加密组件的协议进行交互。然而，我们还需要做更多的工作，才能建立一个通用框架，将 DP 机制与现有的 DAP 子程序（具有经过证明的安全保证）组合起来。

为了使问题具体化并获得一些实验数据，我们寻找了现实生活中的 DAP 使用案例，在这些案例中，差分隐私可能有用，并且可以立即应用。考虑一种协议，它可以私下汇总客户端连接错误并报告给源站，作为网络错误日志记录 (NEL) 的隐私保护替代方案。对于 DAP 而言，这是一个很好的用例，因为收集汇总统计数据（例如，特定域的 tcp.timed_out 的错误数量，或过去 24 小时内错误最多的域）是可取的，但个人报告可能会泄露有关浏览习惯的敏感信息。

为简单起见，让我们重点关注域列表已知的情况，例如，跟踪单个域或一组封闭的付费客户的连接错误。对于博客文章的其余部分，您可以假设我们正在使用 DAP 部署来计算单个域的连接错误直方图（但 DAP 规范中的其他统计数据也具有相同的结构，因此适用于类似的 DP 机制 ）。真正的聚合数据可能看起来像这样：

从图中我们可以看到 1000 份报告中典型的错误分布情况。实际错误类型无关紧要，因此这里只用数字表示。error_type = 8 是目前最常见的错误类型，但我们也观察到一些其他错误类型。

正如我们前面所看到的，这种聚合信息仍有可能泄露敏感信息——例如，如果一种错误类型只出现一次，我们就有可能知道某个用户是否访问了某个网站。现在，我们的目标是修改 DAP，以输出一个略带干扰信息的直方图版本，这样就不会泄露单个报告的信息了。

libprio-rs 是 DAP 中使用的加密原语的广泛使用的 Rust 实现。为了添加 DP，我们首先设计一个任何聚合器随机化方案都应满足的通用 API，并使用对象来表示隐私预算和干扰信息添加。然后，我们为具体的统计聚合实施了 DP API。在回顾了各种 DP 机制之后，我们选择了离散高斯 (discrete Gaussian) 和离散拉普拉斯 (discrete Laplace) 机制，因为它们有明确的保证并且适合模块化环运算。我们利用 OpenDP 库用 Rust 编写的安全干扰信息采样器。在对 DAP 的 Daphne 实现进行调整后，我们能够在网络错误日志记录数据上运行具有差分隐私的 DAP 玩具部署！

回想一下，差分隐私涉及一个参数 𝜖，它决定了我们的系统所能达到的隐私程度。从代码的角度来看，任何正实数都是有效的选择：越小越私人，但也越无用。那么，我们应该如何选择 𝜖 呢？

到目前为止，我们已将 DP 工程视为一门科学，但选择 𝜖 在某种程度上仍是一门艺术。为了说明这一点，让我们回到 NEL 数据，计算一个域上网络错误的 DP 直方图。以下是 𝜖 不同值的干扰信息直方图：

我们观察到，减少 𝜖 会产生包含更多干扰信息的结果，甚至在某些情况下给出负计数——尽管我们始终可以在不失去隐私的情况下截断或舍入结果。由于此示例有许多报告和一些可能的错误，因此很容易掩盖任何单个人的数据。在这里我们可以看到，𝜖 = 1 似乎是这个用例的合理选择。我们仍然可以观察到，罕见事件（例如 error_type = 15）的相对误差高于常见错误（例如 error_type = 8）的相对误差。

让我们重点观察这两个事件，看看 𝜖 如何影响准确性：

越来越明确的是，准确性会随着 𝜖 值的增加而增加——干扰信息较少的聚合结果更不隐私，但更加准确。这种权衡被称为隐私效用权衡。您可以注意到，权衡取决于我们测量的内容。如果我们只对 error_type = 8 感兴趣并且最多可以容忍 2% 的相对误差，那么使用 𝜖 = 0.01 就足够了。如果我们对 error_type = 15 感兴趣，那么我们需要使用 𝜖 = 0.1 才能达到相同的准确度水平。

我们还可以查看其他参数（如批量大小）如何影响固定隐私保证的准确性：

直观地说，如果我们在计算聚合结果之前等待更长的时间，我们就能在相同的隐私级别下得到更准确的结果，因为如果一份数据被淹没在一大批数据中，就更容易被掩盖。如前所述，我们可以预先设置隐私级别，然后再调整聚合参数。如果我们试图针对大小为 1 的批次收集聚合数据，那么 DP 结果将接近随机，从而保护该批次中单个报告的值。在准确性特别重要的应用中，这种柔性降级（针对小批次输出无用的结果，而不是破坏隐私）可能会成为一个问题，但可以通过选择一个满足准确性和隐私性之间舒适权衡的 𝜖 来控制。如果我们愿意付出隐私代价，则始终能够获得更准确的结果。

这让我们回到了这个问题：对于 𝜖 而言，怎样算是一个不错的值？不幸的是，正如 Cynthia Dwork（DP 发明者之一）、Kohli 和 Mulligan 在 2019 年发表的论文中指出的那样，专家们仍未就决定 𝜖 值的正确方法达成共识。事实上，𝜖 的某些值适用于某些部署、算法、数据集或威胁模型，但不适合其他部署、算法、数据集和威胁模型。与迫使攻击者猜测可能具有 2^128 个值的密钥的加密应用不同，𝜖 必须设置为某个不可忽略的值才能从数据中了解到有用的信息。归根结底，是否有用以及怎么样会造成隐私损害取决于应用。

在我们有更好的理解之前，对于非专家来说，一个简单的方法是搜索类似应用中使用的“标准” 𝜖，并在隐私约束下最大限度地提高准确性。如果我们可以访问“𝜖 注册表”（针对各种用例和威胁模型的详细部署列表），那么这种方法就能奏效。美国人口普查局有一个内部注册表，但到目前为止只发布了一些用例。NIST 在这篇非正式博文中给出了一些建议范围（tldr：0 < 𝜖 < 5 是强值，5 < 𝜖 < 20 在实践中可能已经足够）。这篇博文列出了 Apple、Google 和其他公司部署的 𝜖。

还有其他策略可用于设置或评估 𝜖 的经验保证。一种补充方法是确定您愿意接受的最大误差（例如计数上 5% 的相对误差），利用标准 DP 机制的简单属性找到 𝜖 的相应值，并检查它是否在可接受的范围内。

随着 DAP 等安全聚合协议越来越多地部署在现实世界的应用中，我们必须记住，安全聚合并不总是能满足用户对隐私的期望。差分隐私为这些协议增加了一层额外的保护。简而言之，安全聚合保护“方式”（如何根据一组报告计算聚合结果），而 DP 保护“内容”（我们应该发布什么样的含干扰信息聚合结果以避免泄漏过多信息）。

得益于越来越多的开源实现、应用研究以及针对差分隐私和安全聚合的标准化工作，现在有了一条整合 DP 和 DAP 的清晰路径，从而加强了实际测量任务的隐私保证。有趣的是，在分析过程中，我们发现 DAP 协议的某些部分可能会对某些形式的 DP 保证造成问题，例如聚合器可以访问测量次数或客户端的 IP 地址。这些发现以及对协议逻辑的更多思考，促进了 IETF 围绕这一主题和其他主题的讨论。

我们还发现了许多在 DP 文献中经常被忽视的细节，如模块化运算、API 考虑、安全采样或定时攻击。总之，密码学专家和差分隐私专家之间可以就能产生实际影响的协议开展富有成效的合作。

如果您对差分隐私、DAP 或 Cloudflare 的其他隐私项目感兴趣，可以考虑申请研究团队的实习机会。

我要感谢我出色的导师 Christopher Patton 在整个夏天对我进行了指导，从加密细节到 IETF 标准，我学到了很多东西，并且一路上获得了很多乐趣。感谢 Josh Brown 和 Tanya Verma 与我们的讨论，感谢 Avani Wildani 和研究团队其他成员的大力支持！