课程大纲 第 134 课,共 156 课 · 拦截之外的隐私技术
拦截之外的隐私技术

真正理解差分隐私

为什么重要 “我们只发布匿名的统计数据”过去听起来很安全。在这门课程前面,你已经看到对一个数据集提出巧妙的问题,仍然能把一个人单独挑出来。差分隐私是给这种情况加上一个严格的、可测量的限制的工具,而它的核心思想,也就是隐私预算,是你一个下午就能实现的东西。

教学代码,不可用于实际:这个模块实验中的随机数都是带种子的,好让评分可以重复,而真正的隐私系统绝不能这样做。真正的系统使用经过审查的差分隐私库,它们还会处理舍入以及其他微妙的泄露。永远不要把教学代码复制到一个产品里。

承诺

想象一份调查,在包含和不包含你的回答的两种情况下都被发布出来。如果两份发布的结果看起来几乎一样,那么读到它们的任何人都没法分辨你是否参加了,更不用说你说了什么。这就是全部的承诺。

差分隐私(DP):一种保证,无论是否包含任何一个人的数据,一项分析的输出都几乎不变。它是通过加入经过仔细确定大小的随机噪声来实现的。

Epsilon:说明“几乎”是多少的那个数字。小的 epsilon(比如 0.1)意味着大量的噪声和强的隐私;大的 epsilon(比如 5)意味着很少的噪声和弱的隐私。对于一个简单的计数,加入尺度为 1 / epsilon 的拉普拉斯噪声就能达到 epsilon-DP,因为一个人最多只能让计数改变 1。

预算

这里有一个问题。把同一个带噪声的问题问很多次,再对答案求平均:正如数学那一课所展示的,噪声会相互抵消,真实的计数就显现出来了。所以每一个答案都会泄露一点点,而这些泄露会累加起来。

组合:当你就同一批人回答好几个问题时,它们的 epsilon 会相加。以 epsilon 0.25 回答四次,总共要花费 1.0。

隐私预算:你为一个数据集允许的总 epsilon。每一个答案都会花掉一些。当预算用完时,你就停止回答,无论分析师问得多么客气。

把它想象成一张预付卡:每个问题都要花费一些,余额只会下降,而一个被拒绝的问题什么都不花。你要构建的正是这套记账。噪声则由练习世界中的 laplace(scale, rng) 现成地提供。

现实世界中的本地 DP 与中心 DP

本地 DP:每台设备在发送任何东西之前先加入噪声,所以公司永远不会持有真实的值(随机化回答就是本地 DP)。中心 DP:一台受信任的服务器持有真实的数据,只在它发布的结果上加入噪声。

苹果在 2016 年宣布,它使用本地差分隐私从设备中了解像流行的新词和表情符号这样的东西,而不收集任何一个人输入的内容。谷歌早期的系统 RAPPOR(2014)也是本地的,用于从它的浏览器收集统计数据。本地 DP 需要给每个人加入大量的噪声,所以它只能为非常大的人群和相当常见的值给出有用的答案。谷歌后来发表的许多工作,比如它的开源差分隐私库(2019),使用的是中心模型,在同样的 epsilon 下需要的噪声少得多,代价是要信任服务器持有原始数据。

两种模型都不是“唯一正确的”。本地 DP 甚至能保护你免受公司的影响;中心 DP 能给出更准确的统计数据。两课之后要讲的安全聚合,是兼得两者部分优点的一种方式。

用其他语言实现

用 JavaScript 实现同样的预算检查:

function spend(budget, epsilon) {
  if (epsilon <= 0) return false;
  if (budget.spent + epsilon > budget.total + 1e-9) return false;
  budget.spent += epsilon;
  budget.log.push(epsilon);
  return true;
}

以及用 Rust,在那里借用规则让“拒绝时什么都不改变”变得明确:

fn spend(b: &mut Budget, eps: f64) -> bool {
    if eps <= 0.0 || b.spent + eps > b.total + 1e-9 { return false; }
    b.spent += eps;
    b.log.push(eps);
    true
}

为什么要有 1e-9?

计算机存储小数是近似的:在 Python 里 0.1 + 0.2 是 0.30000000000000004。如果没有一点点余量,分成许多小步恰好花完整个预算,就可能被错误地拒绝。真正的库会更仔细地处理这个问题;在这里一点小余量就够了。

一个常见的误解

“噪声意味着发布的数字是错的,所以 DP 毫无用处。”噪声的大小是为了隐藏一个人,而不是隐藏趋势。一个 412 的计数被发布成 409 或 415,仍然能告诉商店哪些页面受欢迎,而一个敏感页面的 31 位访客的计数,却没法被用来确认某一个特定的人是其中之一。

回顾

  • DP 承诺无论有没有任何一个人,结果都几乎不变;epsilon 衡量的就是这个“几乎”。
  • 对于一个计数,尺度为 1 / epsilon 的拉普拉斯噪声能达到 epsilon-DP。
  • epsilon 会在多个问题之间累加,所以必须跟踪并强制执行一份预算,而拒绝不花任何东西。
  • 本地 DP(在设备上加噪声)不信任任何人,但需要庞大的人群;中心 DP 更准确,但要信任服务器。
轮到你了

编写四个管理隐私预算的函数。make_budget(total) 返回 {"total": total, "spent": 0.0, "log": []}。remaining(budget) 返回 total 减去 spent。spend(budget, epsilon) 在以下情况下返回 False 并且什么都不改变:epsilon 不是一个大于 0 的有限数字(0、负数、nan 或无穷大:一个漏过去的 nan 会让 spent 变成 nan,之后的每一次检查都会通过,于是预算永远不会用完),或者花掉它会让 spent 超过 total 超过 1e-9;否则它把 epsilon 加到 spent 上,追加到 log 里,并返回 True。noisy_count(true_count, epsilon, budget, rng) 在 spend 拒绝时返回 None,否则返回 true_count + laplace(1 / epsilon, rng)。你的评分依据的是记账,而不是确切的带噪声数字。

发现这节课有问题?报告它 · 就这节课提问

这个练习即将开放

完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。