【联邦学习之旅】04 不经意传输、秘密共享、密钥交换与差分隐私

上一讲我们学习了同态加密，这一讲我们来继续学习联邦学习中几个重要的基础概念。

不经意传输 Oblivious Transfer

不经意传输对于大部人来说比较陌生，因为它是一个密码学协议。我们首先需要了解，啥是协议。简单来说协议 protocal 是指两个或两个以上的参与者为了完成某项特定任务而采取的一系列步骤。

那么这个协议是做什么的呢？广义来说就是消息发送者从一些待发送的消息中发送某一条给接收者，但并不知道接收者具体收到了哪一条消息。不过这个协议过于宽泛，目前更加实用的版本叫做 1-2 不经意传输，在这个协议中，消息发送方每次发送 2 条消息，消息接收方只能得到其中一条，并且发送方并不知道接收者收到了哪一条。

看到这里可能大家还是一头雾水，这个协议有啥应用场景吗？你别说，还真的有，我们来看下面两个场景：

• 场景一（不经意传输）：子妍和我打牌，我总是输，为了让我的游戏体验好一点，我可以看她的某一张手牌的大小，但是我并不想让她知道我看了哪张，不然很可能还是打不赢！这个场景下，就可以通过广义的不经意传输来传递牌的大小，这样可以保证我只能看到一张的大小，且子妍不知道我看了哪一张牌。
• 场景二（1-2 不经意传输）：某一天我在上班路上碰到一个来自 2022 的穿越者，说 10 块卖给我两注明天就要开奖的双色球头等奖号码，但是我觉得他可能是骗子，只愿意用 5 块钱买一注试一下，而且也不愿意让他知道我选了哪一注。这个场景下，就可以通过 1-2 不经意传输来传递两注彩票，可以保证我只能拿到其中一注，并且这个穿越者不知道我能看到哪一注的号码。

接下来我们就以 1-2 不经意传输为例，介绍一下具体的协议流程（基于 RSA）。设定为发送者 Alice 的秘密是 m0,m1，Bob 想要获取到的秘密是 mb：

1. Alice 产生两对 RSA 公私钥，将两个公钥 pubkey0, pubkey1 都发送给 Bob
2. Bob 生成一个随机数，并用 pubkey0 或 pubkey1 加密这个随机数（想要 m0 就用 pubkey0；想要 m1 就用 pubkey1），并将密文结果发给 Alice
3. Alice 用 privkey0 和 privkey1 分别解密密文，得到两个结果 k0, k1。之后用 k0 与 m0 进行异或，用 k1 与 m1 进行异或，将异或之后的结果 e0, e1 发送给 Bob
4. Bob 用之前生成的随机数与 e0, e1 分别做异或操作，其中一条为真实数据，另外一条是一个随机数

这里我们重点关注第三步，因为 Alice 没办法区分 k0, k1 到底哪个是 Bob 生成的随机数，所以没办法知道 Bob 到底能够获取 m0 还是 m1。而对于 Bob 来说，因为没有私钥，所以也没办法解密另外一条数据。

另外附一张 Wiki 的介绍，非常清晰了：

注：目前在 FATE 的实现的是 Eduard Hauck and Julian Loss 提出的不经意传输，具体参考 这里，具体在 Secure Information Retrieval 模块中使用

秘密共享 Secret Sharing

所谓秘密共享，具体的定义网上很多了，这里暂且不讲，让我先用一个具体的瞎编的场景来进行说明：

经过长达数百年的研究，人类终于掌握了时间旅行的技术，一名穿越者通过时光机来到了 1979 年，找到了一个名为 Adi Shamir 的人（就是 RSA 算法中的 S），跟他说自己正在被其他穿越者追杀，只因为手里的一份绝密情报。这份情报是黑暗森林理论，需要尽快送到红岸基地（参考三体）。穿越者本想找一个可靠的人来送情报，但担心他被干掉导致情报丢失。又想到将情报拆成七份，派七个人去送，但是万一其中一人被抓，依然没办法还原出全部的情报。所以来找 Shamir，让他帮忙出个主意。

Shamir 灵机一动，想到了一个办法，叫做门限秘密共享方案（threshold secret sharing scheme），简称门限方案。这个方案首先需要确定两个数字 n 和 m，其中 n 表示参与秘密信息共享的人数，m 表示至少几个人聚到一起才能恢复出秘密信息。那么问题来了，这个方案至少需要包括几个函数，满足几个条件？

答：需要两个函数，满足一个条件，具体如下

• 函数一：秘密分割函数，用来把秘密信息切分成 n 份
• 函数二：秘密重构函数，用来将 m 个人持有的部分秘密信息组合成完整的秘密信息
• 条件：少于 m 个人，无法正确还原

秘密分割算法

我们先回顾一下两个关键参数 n 和 m，n 是秘密信息要切分为多少份，m 是最少的恢复秘密信息的份数（设秘密信息为 s）。接下来我们需要选择一个大于秘密值 $s$ 和份数 $n$ 的质数 $p$，同时构造一个随机的 m-1 次多项式：

$f(x)=a_{m-1}x^{m-1}+...+a_2x^2+a_1x+a_0\ \ mod\ p$

首先，我们把秘密信息 $a_0$ 设为秘密信息 s，即 $f(0)=a_0=s$，其他系数在有限域中独立均匀随机选取。

接着，需要选择 n 个不相同的整数，满足 $1 \le x_1,x_2,...,x_n \le p-1$，每个人获得 $k_i=f(x_i)$，需要保密自己的 $k_i$（但 $x_i$ 不需要保密，谁知道都行）

最后需要销毁 $f(x)$，就完成了秘密分割！

秘密重构算法

现在安排好的 n 个传递员每个人都有自己的 $k_i,x_i$，现在的问题就是，凑齐 m 个$k_i$ 之后，要怎么样才能还原 $f(x)$，并计算出秘密信息 $s=f(0)=a_0$ 呢？

很简单，可以通过下面的方式来重新构造出 $f(x)$

$f(x)=\sum_{i=1}^{m} k_i\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}\pmod p$

接着我们来计算 $f(0)$ 就可以得到秘密信息 $s$

那么问题来了，为什么可以通过上面的公式来重构 $f(x)$ 呢，这里用到的就是拉格朗日插值多项式的特点，我们可以把 $(x_i,k_i)$ 看作 $f(x)$ 上的一个点，而 $f(x)$ 是 m-1 次多项式，是可通过 m 个点来唯一重构 $f(x)$ 的；在系数均匀随机的前提下，少于 m 份不会泄露秘密值，这也正好满足了前面提到的必备条件！

注：目前在 FATE 中实现的是 SPDZ 版本，主要用于多方安全地共同进行计算任意函数或一类函数的结果（如梯度等信息），参考 文档, 论文 1, 论文 2，

密钥交换

密钥交换是信息安全中最最基础的步骤，也是最需要保证安全的步骤，毕竟一旦密钥泄露，所谓的加密就没有任何意义了。在公开的网络里想要安全地传输信息并不简单，我们同样用一个虚构的场景，来说明密钥交换的难点。

前面提到的穿越者利用秘密共享的方式将秘密信息成功传达给红岸基地后，又面临了新的问题：他的加密时空对讲机坏了。好在他是一个 DIY 达人，用一个地球上的对讲机加上一些加密时空对讲机的零件，临时组装了一个简易时空对讲机。重新和未来的组织取得联系后，通讯员告诉他现在他们的通讯并不安全，因为其他拥有时空信号站接入权限的人都可以看到他们的通讯内容。通讯员要求穿越者之后的消息要加密后才能发送，并且需要事前约定好相同的密钥以便加密解密。问题来了，怎么发送这个密钥成了大问题，因为如果直接发送的话，其他人也能看到这个密钥！

有没有办法在这样的条件下，在不泄露密钥的前提下完成密钥的交换呢？穿越者表示"我太难了"，于是通讯员让穿越者回到 1976 年，去找 Whitfield Diffie 和 Martin Hellman 帮忙。

顺利找到 Diffie 和 Hellman 之后，他们对穿越者表示你这个问题我们刚好能解决，哪怕有窃听者也没问题，按照下面的步骤来就可以：

1. 穿越者需要先找一个很大的质数 $p$，以及 $p$ 的一个原根 $g$（后面会具体说明这个概念），然后通过对讲机告诉通讯员。与此同时，窃听者也能知道 $p$ 和 $g$，但不用紧张，这俩是公开参数，大家都知道也没问题。
2. 穿越者随机选择一个数字 $r_1$，通讯员也随机选择一个数字 $r_2$。注意，这两个数值就是私钥，千万不能通过对讲机提起，不然窃听者知道了就全完了。
3. 穿越者计算 $ret_1=g^{r_1}\ mod\ p$ 并发送给通讯员；通讯员计算 $ret_2=g^{r_2}\ mod\ p$ 并发送给穿越者。这两个计算结果窃听者也可以知道，但不怕，他还原不了 $r_1, r_2$（后面会具体说明）
4. 穿越者计算 $ret_2^{r_1}\ mod\ p = g^{r_1r_2}\ mod\ p$，通讯员计算 $ret_1^{r_2}\ mod\ p = g^{r_2r_1}\ mod\ p$
5. 现在穿越者和通讯员都知道一个相同的密钥 $g^{r_1r_2}\ mod\ p$，并且窃听者完全没办法猜出来，这样就完成了密钥交换，接下来就可以用这个密钥进行通讯了。

那么这个算法是如何保证安全的呢？网上的很多材料都会有这么一句：因为在有限域上计算离散对数非常困难。问题来了，啥是离散对数，为啥非常困难呢？还有前面提到的原根，到底是什么？

我们先来讲一下啥是原根。对于一个质数 $p$，如果有一个数字 $a$，使得 $a\ mod\ p,\ a^2\ mod\ p,...,a^{p-1}\ mod\ p$ 的数值各不相同，且包括了从 $1$ 到 $p-1$ 的所有整数，那么 $a$ 就是 $p$ 的一个原根。

接下来就可以来看看啥是离散对数了。如果对于一个整数 $b$、一个质数 $p$ 和它的原根 $a$，可以找到一个唯一的指数 $i$，使得 $b=a^i\ mod\ p,\ 0 \le i<p-1$，那么指数 $i$ 被称为 $b$ 的以 $a$ 为基数的模 $p$ 的离散对数。

离散对数有一个特点：已知 $p$ 和 $a$ 之后，对于给定的 $b$ 要计算 $i$ 很难，但是对于给定的 $i$ 计算 $b$ 是很容易的。这里的困难来自所选群中的离散对数问题，而不是“取模”运算本身。安全性还依赖参数选择；交换得到的共享秘密通常要经过密钥派生后再用于加密。

注：DH 密钥交换算法易受到中间人攻击，可以通过数字签名进行保护，这里不展开说明，感兴趣的同学可以查看下面的参考链接。在 FATE 中主要用做多方数据表操作的底层安全保护。

安全计算与输出隐私

补充整理自 2019 年《安全计算》笔记。拍卖中，各方希望比较报价，却不愿公开未中标者的报价；跨机构分析中，各方希望得到联合结果，却不能直接交换原始数据。这类任务需要先明确参与者、允许公开的结果以及攻击者能做什么，再选择协议。

秘密共享、混淆电路、同态加密等密码学方法，可以用来构建安全计算协议。它们主要保护计算过程中的输入，安全保证依赖协议假设，例如允许多少参与者串通、是否考虑恶意偏离协议的行为。

即使计算过程安全，公开的精确结果仍可能泄露信息。例如，已知一个班有 5 人中奖，又知道其中 49 人的中奖情况，就能推断第 50 人是否中奖。差分隐私关注的正是发布结果带来的个体信息泄露。因此，安全多方计算和差分隐私可以配合使用，不能简单归为“加噪声”和“不加噪声”两种可互换的方案。

差分隐私 Differential Privacy

原先的生活例子是毕业晚会抽奖：50 名同学中有 5 人中特等奖。如果包括我自己在内的 49 人已有 5 人中奖，那么最后一人没中奖；如果已有 4 人中奖，最后一人就一定中奖。这说明仅发布一个总数，也不代表没有隐私风险。

差分隐私用随机化机制限制单个人的数据变化对输出分布的影响。这里把“只相差一条记录”称为相邻数据集；实际应用还要说明是增加／删除记录，还是替换记录，以及一人是否贡献多条记录。

定义与噪声大小

对于任意相邻数据集 $D,D'$ 和任意可测输出集合 $S$，若随机机制 $M$ 满足

$$\Pr[M(D)\in S]\le e^\epsilon\Pr[M(D')\in S]+\delta,$$

则称它满足 $(\epsilon,\delta)$ 差分隐私。$\delta=0$ 时是纯差分隐私。定义约束的是输出分布，而不是说攻击者绝对无法猜到某人的属性。

加噪声必须与查询敏感度匹配。计数查询在增加或删除一个人的记录时最多变化 1，可使用尺度为 $1/\epsilon$ 的拉普拉斯噪声。若发布平均值，还要约束单条数据的取值范围；不能向任意统计量加一个固定的小噪声，就宣称满足差分隐私。

多次查询要一起计算

反复查询会消耗隐私预算。基本组合定理下，多个机制的 $\epsilon$ 和 $\delta$ 可分别相加作为总预算上界。因此，需要检查整个发布流程，而不是只证明每个步骤单独成立。对已发布差分隐私结果进行不再访问原始数据的后处理，不会额外削弱该保证。

这些定义与机制可参考 Dwork 和 Roth 的 The Algorithmic Foundations of Differential Privacy。噪声、精度和隐私参数之间需要取舍；“数据没有出本地”“删除了姓名”“只发布群体信息”都不能单独证明隐私受到充分保护。

本节保留了原稿的抽奖案例，并结合《安全计算》笔记补充了协议与输出隐私的区别。原科普文章见联邦广告：技术捍卫隐私。

参考材料

• 四、不经意传输oblivious transfer - 中国科学技术大学
• 趣说密码学（五）秘密共享方案——shamir,中国剩余定理,Brickell和Blakley
• 密码学协议举例（二）：秘密共享的门限方案
• Diffie-Hellman密钥交换协议
• FATE 中的 DH 密钥交换
• 差分隐私Differential Privacy介绍