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

私有集合求交

为什么重要 公司常常想知道它们共有哪些客户,为了一次联合优惠,或者为了衡量一则广告是否有效。简单的办法是交换客户名单,这意味着你的电子邮件会落进另一家公司的数据库。私有集合求交让它们能在任何一方都不交出自己名单的情况下找到重叠的部分。了解它是怎样工作的,能让你分辨真正的隐私和“我们只分享了哈希过的电子邮件”。

教学用的密码学,并不安全:这个模块实验里的数字小到可以读懂,而随机数是带种子的,好让评分可以重复。真正的系统使用经过审查的库和大得多的数字。永远不要把教学代码复制到一个产品里。

问题

一家商店和一个应用各有一份客户电子邮件名单。它们想要的是两份名单上都有的电子邮件,别的都不要:商店不能知道应用的其他用户,应用也不能知道商店的其他客户。

集合求交:两份名单共有的条目。私有集合求交(PSI):一种让双方计算出交集、同时不透露关于各自名单的任何其他信息的方法。

为什么“直接做哈希”会失败

哈希:一种把文本变成固定长度乱码的函数(SHA-256 是一种常见的哈希)。同样的输入总是得到同样的输出,而你没法直接把它倒过来运行。

“我们交换的是哈希过的电子邮件,所以没有人能看到真实的地址”,这听起来很安全。但电子邮件是可以猜的。任何持有一份可能的电子邮件列表的人,都可以把每一个猜测都做一遍哈希,然后寻找匹配,就像在一大串钥匙上逐一试每一把。你的 naive_reverse 函数会用练习世界里的 200 个合成电子邮件,恰恰做到这一点。只有当输入猜不到时,哈希才能隐藏数据,而电子邮件、电话号码和名字都是可以猜的。

两把锁的诀窍

还记得数学那一课吗:先加上秘密 a,再加上秘密 b,和先 b 后 a 的结果一样。把每一个电子邮件都想象成一个箱子。Alice 给她的每个箱子都加上她自己的锁,然后发给 Bob。Bob 加上他的锁,再发回去。Bob 也给他自己的箱子上锁,发给 Alice,Alice 再加上她的锁。现在每个箱子都有两把锁,而里面装着同一个电子邮件的两个箱子看起来完全一样,无论哪把锁先加上去。

用数字来说,使用来自 watched.leg7a_privacy 的练习群(P、hash_to_group、random_secret):

  1. Alice 发送 blind(alice_items, a):每一项都被哈希进群里,然后求 a 次幂。
  2. Bob 把它们求 b 次幂(reblind),并按同样的顺序发回去。
  3. Bob 发送 blind(bob_items, b)。
  4. Alice 把 Bob 的值求 a 次幂。她那些加了两把锁的值中,任何一个出现在 Bob 加了两把锁的集合里的,就是一个共有的条目。因为她保留了顺序,她知道每一个对应的是她的哪一项。

为什么在哈希失败的地方这样做是安全的?要检验一个猜测,你需要两个秘密,而每一方都保留着自己的秘密。Bob 永远只能看到带着 Alice 秘密的 Alice 的值,而它们看起来就像随机数。

Diffie-Hellman PSI:这个协议的名字,来自它所借鉴的 1976 年的密钥交换思想(双方组合秘密的指数)。真正的版本使用椭圆曲线(另一种群,具有同样的“顺序无关紧要”的性质,而数字要短得多)以及谨慎的哈希。

答案本身就是一种披露

即使是完美的 PSI,也会告诉 Alice 某一个特定的人是 Bob 的客户。如果 Bob 是一家诊所或一位债务顾问,这就很敏感。一家公司常常只需要知道共有的客户有多少。在 PSI 基数版本中,Bob 会在第 2 步打乱他的回复,这样 Alice 能统计匹配的数量,却分辨不出它们属于她的哪些条目。只索要能回答问题的最少信息。

用其他语言实现

用 JavaScript 和 BigInt 实现盲化这一步(使用一个像数学那一课里那样的 powMod 辅助函数):

const blind = (items, secret) => items.map(x => powMod(hashToGroup(x), secret, P));
const reblind = (values, secret) => values.map(v => powMod(v, secret, P));

以及用 Go 和 math/big:

func reblind(values []*big.Int, secret, p *big.Int) []*big.Int {
    out := make([]*big.Int, len(values))
    for i, v := range values {
        out[i] = new(big.Int).Exp(v, secret, p)
    }
    return out
}

对于真正的产品,请使用一个经过审计的 PSI 库,而不是自己编写。

回顾

  • 哈希过的电子邮件用一份猜测列表就很容易还原,所以“我们只分享了哈希”并不是隐私。
  • Diffie-Hellman PSI 用两个顺序无关紧要的秘密给每一项都加上两把锁,所以匹配会显现出来,而任何一份名单都不会暴露。
  • 保留顺序会暴露哪些条目匹配;打乱顺序(PSI 基数)只会暴露有多少个匹配。
  • 交集本身就是个人数据,所以只索要能回答问题的最少信息。
轮到你了

编写五个函数。naive_reverse(hashes, candidates) 返回那些 SHA-256 十六进制摘要(hashlib.sha256(c.encode()).hexdigest())在 hashes 中的候选项组成的排好序的列表。blind(items, secret) 返回 [pow(hash_to_group(x), secret, P) for x in items]。reblind(values, secret) 把每个值求 secret 次幂再对 P 取模,保持顺序。psi(alice_items, bob_items, a_secret, b_secret) 用 blind 和 reblind 按照课程里的四个步骤进行,并返回 Bob 也有的 Alice 的条目组成的排好序的列表。psi_cardinality(alice_items, bob_items, a_secret, b_secret, rng) 做同样的事,但用 rng.shuffle 打乱 Bob 的回复,并只返回共有条目的数量。

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

这个练习即将开放

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