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

你需要的数学

为什么重要 这个模块里的隐私工具,比如在不交换名单的情况下找出共同的客户,或者发布能保护每个人的统计数据,都建立在三小块数学之上。你不需要数学学位。你需要的是时钟算术、对概率的一点感觉,以及随机噪声会在大群体中相互抵消这个想法。这一课正好给你这些,还配有可以尝试的 Python。

1. 时钟算术

现在是 22:00。5 小时之后是几点?不是 27:00:时钟会绕回来,所以是 03:00。你算了 22 + 5 = 27,然后保留了除以 24 之后的余数。

模运算:一种数字在达到一个固定大小(也就是模数)之后会绕回来的算术。“27 mod 24”是 3,也就是 27 除以 24 之后的余数。在 Python 里,取余运算符是 %:27 % 24 是 3。

无论你加多少、乘多少,绕回都能让数字保持固定的大小,这正是它在密码学中有用的原因。Python 还有一个快速的内置函数,用来做“先求幂,再绕回”:pow(base, exponent, modulus)。

print((22 + 5) % 24)       # 3
print(pow(3, 4, 7))        # 3*3*3*3 = 81, and 81 % 7 = 4
print(pow(5, 200, 23))     # instant, even though 5 to the 200 is huge

2. 一个方向容易,另一个方向很难

把黄色和蓝色的颜料混成绿色很容易。把绿色重新分离成确切的黄色和蓝色,实际上是不可能的。有些数学也是这样运作的。

挑一个很大的质数模数 P 和一个数 h。为一个秘密的 a 计算 pow(h, a, P) 是瞬间完成的。但只给出答案,要重新找出 a,在数字足够大时会慢到没有人能做到。这种单向的性质叫作离散对数问题。

还有一个事实,它驱动着接下来的实验。先求 a 次幂再求 b 次幂,和先求 b 次幂再求 a 次幂得到的结果相同,因为两者都等于 h 的 a 乘以 b 次幂:

P = 1019                     # a small prime: fine for learning, useless for security
h, a, b = 42, 123, 456
print(pow(pow(h, a, P), b, P) == pow(pow(h, b, P), a, P))    # True

就像一个箱子上的两把锁,你上锁的顺序无关紧要。两个人可以各自加上自己的秘密,最终到达同一个地方,而永远不必透露他们的秘密。

3. 一段话讲清楚概率

概率是一个从 0(永远不会)到 1(总是会)的数字。一枚公平的硬币正面朝上的概率是 0.5。当两件事相互独立时,两者都发生的概率是它们的乘积:连续两次正面是 0.5 × 0.5 = 0.25。期望值是长期的平均值:把一个公平的骰子掷很多次,平均值会接近 3.5。

4. 噪声会在人群中相互抵消

噪声:故意加到一个真实值上的一个随机量,这样确切的值就被隐藏起来了。如果噪声向上和向下的可能性一样大,在许多值上平均起来它就是零。

下面是一个经典的调查技巧,叫作随机化回答。你想知道有多少人做过某件尴尬的事。每个人都偷偷抛一枚硬币。正面:如实回答。反面:再抛一次,正面就回答“是”,反面就回答“否”。任何一个“是”都可能只是硬币的结果,所以没有任何人的回答能证明关于他们的任何事情。

然而人群的总数仍然是有用的。如果真实的比例是 p,你期望的回答“是”的比例就是 0.5 x p + 0.25。所以如果有 35% 的人说是,p 就大约是 (0.35 - 0.25) / 0.5 = 0.2,也就是 20%。人群越大,估计就越接近,因为随着人群的增长,随机噪声相对于总数会越来越小。

import random
rng = random.Random(1)               # seeded: the same "random" numbers every run
truth = [rng.random() < 0.2 for _ in range(10000)]   # 20% really did it
answers = []
for did_it in truth:
    if rng.random() < 0.5:
        answers.append(did_it)             # heads: tell the truth
    else:
        answers.append(rng.random() < 0.5) # tails: random yes or no
yes = sum(answers) / len(answers)
print(round((yes - 0.25) / 0.5, 3))       # close to 0.2

差分隐私中使用的噪声叫作拉普拉斯噪声,它是同一个想法的一个平滑版本:通常很小,偶尔会大一些,向上和向下的可能性一样。它的尺度决定了它通常有多大。

用其他语言实现

对于正数,JavaScript 的 % 也以同样的方式工作,而大数使用 BigInt(写的时候带一个 n)。它没有内置的模幂运算,所以下面是标准的循环写法:

function powMod(base, exp, mod) {
  let result = 1n;
  base %= mod;
  while (exp > 0n) {
    if (exp & 1n) result = (result * base) % mod;
    base = (base * base) % mod;
    exp >>= 1n;
  }
  return result;
}
console.log(powMod(3n, 4n, 7n));   // 4n

在 Go 里,来自 math/big 的 new(big.Int).Exp(base, exp, mod) 做同样的工作。

一个常见的误解

“加入噪声会让数据变得毫无用处。”对一个人的值来说是的,而这正是目的所在。对一个大群体来说,噪声在很大程度上会相互抵消,所以总数和平均值依然有用。隐私技术就生活在这个缝隙里:对个人模糊,对人群清晰。

回顾

  • 模运算让数字绕着一个模数回绕;Python 使用 % 和 pow(b, e, m)。
  • 求一个秘密的幂在一个方向上很容易,而要撤销它实际上是不可能的,而且两个秘密幂的顺序无关紧要。
  • 独立事件的概率相乘;期望值是长期的平均值。
  • 随机噪声能隐藏个人,却会在大群体中相互抵消,这就是随机化回答的原理。

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

这个练习即将开放

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