你需要的数学
为什么重要 这个模块里的隐私工具,比如在不交换名单的情况下找出共同的客户,或者发布能保护每个人的统计数据,都建立在三小块数学之上。你不需要数学学位。你需要的是时钟算术、对概率的一点感觉,以及随机噪声会在大群体中相互抵消这个想法。这一课正好给你这些,还配有可以尝试的 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)。 - 求一个秘密的幂在一个方向上很容易,而要撤销它实际上是不可能的,而且两个秘密幂的顺序无关紧要。
- 独立事件的概率相乘;期望值是长期的平均值。
- 随机噪声能隐藏个人,却会在大群体中相互抵消,这就是随机化回答的原理。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。