课程大纲 第 54 课,共 156 课 · 诚实地衡量隐私
诚实地衡量隐私

k-匿名

为什么重要 机构常常在“去掉名字”之后分享数据,并称之为匿名的。你将在合成数据上看到,三个普通的事实能多快地把名字找回来。真实的重新识别就是这样发生的,这也是第 56 课里那些防御存在的原因。

闲话测试

有人说:“我们街上有一位 1981 年 3 月 3 日出生的女士,刚刚确诊了。”没有提到名字。但在一条街上,有多少位女士恰好是那一天生日?很可能只有一位。这些细节就是名字。

准标识符:一个本身不是名字、但和其他几个事实结合起来就能指向一个人的事实。邮政编码、完整的出生日期和性别是经典的三个。

重新识别:给那些发布时没有名字的数据重新配上名字,通常是通过把它和另一份有名字的列表连接起来。

Latanya Sweeney 在 2000 年的一项著名研究估计,美国约 87% 的人仅凭邮政编码、出生日期和性别就能被单独认出来。后来一项使用更新人口普查数据的研究(Golle,2006)把这个数字定在接近 63%:更低了,但仍然是大多数人,这才是重点。我们将在编造的数据上看到同样的效果。

练习数据

synthetic_people(2000) 构建一张虚构的健康表:id, name, zip, birth_date, gender, diagnosis。里面没有一个人是真实的。我们用天真的方式“匿名化”它,也就是去掉名字。synthetic_public_roll(people) 构建一份虚构的公开名单,就像一份俱乐部登记簿,有名字、邮政编码、出生日期和性别,但没有诊断。

衡量风险:k

k-匿名:如果准标识符取值的每一种组合都至少被 k 行共享,那么这张表就是 k-匿名的。k = 1 意味着至少有一个人是独处的,并且能被找出来。

要找出 k:按行的准标识符元组分组,统计每一组的数量,取最小的那个计数。只用 ["gender"] 时,k 很大。把邮政编码、出生日期和性别放在一起时,k 就降到了 1。

连接

对公开名单上的每个人,构建他们的键 (zip, birth_date, gender),并在发布的表里查找它。要严格:只有当这个键在发布的数据里恰好出现一次、并且在名单上也恰好出现一次时,才算作一次匹配。这样你才能确定。如果两条记录共享这个键,你就分不清哪条是哪条;如果名单上有两个人共享这个键,你就分不清谁是谁。

reidentify(released, roll)
# {17: 'Mei Patel', 203: 'Omar Novak', ...}   record id -> name

一旦第 17 条记录有了名字,它的诊断也就有了主人。这就是整个攻击:两份看起来无害的列表,一次连接。

一个常见的误解

“去掉名字、电子邮件和电话号码就能让数据变得匿名。”这去掉了明显的标识符,但剩下的列仍然能把人单独认出来。数据是否匿名,取决于外面还有什么能拿来和它连接,这就是为什么第 56 课要改变数据本身。

试一试 通过之后,把名单的 fraction 从 0.6 改成 0.2,再运行一次。匹配的数量下降了,但你重新识别出的名单上的人所占的比例几乎没有变化。每个人是被他们自己的细节暴露的,而不是被名单有多大暴露的。

用其他语言实现

JavaScript:

function reidentify(released, roll, cols) {
  const key = r => JSON.stringify(cols.map(c => r[c]));
  const count = list => list.reduce((m, r) => m.set(key(r), (m.get(key(r)) || 0) + 1), new Map());
  const a = count(released), b = count(roll);
  const byKey = new Map(released.map(r => [key(r), r]));
  const found = {};
  for (const p of roll) {
    if (a.get(key(p)) === 1 && b.get(key(p)) === 1) found[byKey.get(key(p)).id] = p.name;
  }
  return found;
}

用 C#(LINQ)体现 SQL 风格的思路:

var matches =
    from r in released
    join p in roll on new { r.Zip, r.BirthDate, r.Gender }
                   equals new { p.Zip, p.BirthDate, p.Gender }
    select new { r.Id, p.Name };
// then keep only keys that occur once on each side

回顾

  • 准标识符(邮政编码、出生日期、性别)可以在没有名字的情况下把人单独认出来。
  • k 是共享相同准标识符的最小那一组的大小;k = 1 意味着有人暴露了。
  • 把一张没有名字的表和一份有名字的公开名单连接起来,就能重新识别出人。
  • 去掉名字并不是匿名化。这里只用合成数据;防御在下一课。
轮到你了

编写 quasi_key(row, columns)(值组成的元组)、smallest_group(rows, columns)(共享同一个键的最小一组行的大小:也就是 k)以及 reidentify(released, roll, columns=QUASI),返回一个从发布记录的 id 到名单上 name 的字典,包含每一个键在 released 中恰好出现一次、并且在 roll 中也恰好出现一次的名单上的人。

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

这个练习即将开放

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