安全聚合
为什么重要 一个健身应用想知道一座城市里步行的总步数;一家键盘制造商想知道一个词在所有手机上被输入的频率。在每种情况下,公司需要的都是来自许多台设备的一个数字。安全聚合让它在从不看到任何一个人的值的情况下了解到那个总数,而且它出奇地简单。
教学用的密码学,并不安全:这个模块实验里的数字小到可以读懂,而随机数是带种子的,好让评分可以重复。真正的系统使用经过审查的库和大得多的数字。永远不要把教学代码复制到一个产品里。
工资的诀窍
三位朋友想知道他们的平均工资,又不想让任何人透露自己的工资。第一位把一个很大的随机数加到她的工资上,然后把结果悄悄告诉第二位。他加上他的工资,再悄悄传下去。第三位加上她的工资,再传回去。第一位减去她的随机数,总数就出来了。每一句悄悄话,在听到它的人看来都像一个随机数。
安全聚合:计算许多人的值的总数(或平均值),而不向任何人透露任何一个单独的值,包括收集它们的服务器。
加法秘密分享:把一个秘密数字切成好几个份额,它们单独看起来都是随机的,加起来却等于那个秘密。任何一个份额,或者任何一组缺少至少一个份额的份额,都不会透露关于这个秘密的任何东西。
份额是怎样运作的
要把数字 7,350 分成三个份额,就挑两个随机数,再选出第三个,让三者加起来等于 7,350。使用回绕的算术(模数 M,这里是 2 的 32 次方,略多于 40 亿),每一个份额单独看都是一个均匀分布的随机数:
M = 2 ** 32
s1, s2 = 3919211450, 120775123 # random
s3 = (7350 - s1 - s2) % M # whatever makes it add up
print((s1 + s2 + s3) % M) # 7350
为什么要回绕?没有回绕的话,一个份额有时会是负数,或者可疑地接近那个秘密。有了回绕,无论秘密是什么,每一个份额值出现的可能性都一样,所以单个份额不携带任何信息。
许多台设备,好几台服务器
现在每部手机都把它的步数分成每台服务器一个份额,把份额 1 发给服务器 1,份额 2 发给服务器 2,以此类推。每台服务器把它收到的份额加起来。每台服务器的总数看起来仍然是随机的。只有当把各台服务器的总数加在一起时,真正的城市总数才会出现。只要各台服务器不把同一部手机的原始份额汇集在一起,就没有任何一部手机的值会被看到。
现实世界中的版本
那些用来在许多手机上训练模型的系统(叫作联邦学习)使用一个只需一台服务器的更巧妙的变体:成对的设备商定一些随机掩码,它们在把一切加起来时会相互抵消,外加一些额外的步骤来应对中途掉线的手机。核心思想就是你将要构建的那个:看起来随机、只有合在一起才有意义的碎片。
安全聚合做不到什么
总数会被准确地揭示出来。如果只有两个人做了贡献,而其中一个知道自己的值,他们就可以把它减掉,从而知道另一个人的值。如果总数本身是敏感的,就再给它加上差分隐私噪声。这两种工具能很好地配合:聚合隐藏输入,DP 隐藏每个人对输出的影响。
用其他语言实现
用 JavaScript 进行切分,借助 >>> 0 实现 32 位回绕,并使用浏览器的安全随机源:
function split(value, n) {
const shares = Array.from(crypto.getRandomValues(new Uint32Array(n - 1)));
const sum = shares.reduce((a, b) => (a + b) >>> 0, 0);
shares.push((value - sum) >>> 0);
return shares;
}以及用 Rust,在那里 u32 上的 wrapping_sub 会替你完成回绕:
let last = value.wrapping_sub(shares.iter().fold(0u32, |a, &b| a.wrapping_add(b)));回顾
- 安全聚合会揭示一个总数,但不会揭示任何一个单独的贡献。
- 加法秘密分享使用回绕的算术,把一个值切成看起来随机、加起来等于它的份额。
- 每台服务器只能看到看起来随机的份额;只有把所有服务器的总数合在一起,才能得到答案。
- 总数本身会被准确地揭示出来,所以当总数可能暴露某人时,要把它和 DP 噪声搭配使用。
使用练习世界中的 M(2 的 32 次方),编写三个函数。split(value, n, rng) 返回一个由 n 个份额组成的列表:前 n - 1 个来自 rng.randrange(M),最后一个等于 (value - sum(shares)) % M。combine(shares) 返回 sum(shares) % M。aggregate(values, n_servers, rng) 用 split 切分每一个值,把份额 j 加进 server_totals[j](对 M 取模),并返回一个元组 (total, server_totals),其中 total = combine(server_totals)。
这个练习即将开放
完成它前面的那一课,这一课就会解锁。整门课程免费,无需账号,而且你现在就可以阅读这节课。
这个浏览器屏蔽了 learn.floati.life 的 Cookie,所以你在这里完成的课程无法按顺序打开。请允许这个网站使用 Cookie,然后重新加载。