《Secure Analytics-Federated Learning and Secure Aggregation》论文阅读

背景

机器学习模型对数据的分析具有很大的优势，很多敏感数据分布在用户各自的终端。若大规模收集用户的敏感数据具有泄露的风险。
对于安全分析的一般背景就是认为有n方有敏感数据，并且不愿意分享他们的数据，但可以分享聚合计算后的结果。
联邦学习是一种训练数据在多方训练，然后聚合结果得到最终的中心化模型。其中的关键就是多方结果的安全聚合。

风险模型

有很多用户，假设用户都是诚实但好奇的，即会遵守协议规则，但会通过拼凑数据获取敏感信息。换句话说就是恶意的，很可能执行不好的行为。

安全聚合

问题的定义、目标和假设

风险模型假设用户和中心服务器都是诚实且好奇的。如果用户是恶意的，他们有能力在不被监测的情况下影响聚合结果。
安全聚合协议：

1. 操作高维向量；
2. 不管计算中涉及到的用户子集，通信是高效的；
3. 用户dropout是robust；
4. 足够安全

第一次尝试：一次填充掩码

对于所有的用户，通过每个用户对$u，v$构建一个secret，具体逻辑：对所有用户进行排序，当用户$u<v$构建一个$+s_{u,v}$，相反则构建一个$-s_{v,u}$，如下图：

当聚合的时候
$$\sum _{i=1}^3=x_1+s_{1,2}+s_{1,3}+x_2-s_{1,2}+s_{2,3}+x_3-s_{1,3}-s_{2,3}$$

缺点：

1. 二次通信，每个用户对$u,v$都需要产生他们的秘钥$s_{u,v}$
2. 如果任何一个用户drop out，对于${\sum }_{\forall i}{y}_i$都会变成垃圾数据，从而本次不能聚合。

利用Diffie-Hellman秘钥交换改进二次通信

所有的用户商定一个大素数$p$和一个基本数$g$。用户将自己的公钥（$g^{a_u}\mathrm{mod}p$，其中$a_u$是用户的秘钥）发送给server，然后server广播一个公钥给其他的用户，其他用户使用自己的秘钥和该公钥进行计算，如：
$$u_1：(g^{a_2}{)}^{a_1}modp=g^{a_1{a}_2}modp=s_{1,2}$$
$$u_2：(g^{a_1}{)}^{a_2}modp=g^{a_1{a}_2}modp=s_{1,2}$$
Diffie-Hellman秘钥交换比上面的方法更简单、更高效。

第二次尝试：可恢复的一次性填充掩码

同上述方法类似，用户将他们加密后的向量$y_u$发给server，然后server询问其他用户是否包含drop out的用户，是的话则取消他们的秘密绑定。如下图:

该方法的缺点：

1. 在recovery阶段发生额外的用户drop out，这将要求新drop out的用户也需要recovery，在大量用户的情况下，轮询次数将增加。
2. 通信延迟导致server以为用户被drop out。因此，会想其他用户recovery秘钥，这导致server在接收到该用户的secret时，解密该用户的$x_u$。如下图
   
   因此，如果server是恶意的，则可以通过此方法获取用户的inputs。

Shamir秘密分享：
允许一个用户将秘密$s$分享成$n$个shares，然后任意$t$个shares都能重构出秘密$s$，而任意$t-1$个shares都不能重构出秘密$s$。

第三次尝试：处理Dropped用户

为了克服在通信轮次之间，新dropped用户增加recovery阶段，用户Shamir秘密分享的阈值。每个用户发送他们DH秘钥的shares给其他用户，只要符合阈值条件，允许pairwise secrets被recovered，即使是recovery期间新dropped用户。协议可以总结如下：

1. 每个用户$u$将他的DH秘钥$a_u$分享成n-1个部分$a_{u1},a_{u2},..,a_{u(n-1)}$，并发送给其他$n-1$个用户。
2. server接收来自在线用户的$y_u$（记为：$U_{online,round1}$）。
3. server计算dropped用户集，表示为$U_{dropped,round1}$
4. server向$U_{online,round1}$询问$U_{dropped,round1}$的shares。在第二轮通信中假设至少还有t个用户在线。
5. server对$U_{dropped,round1}$的秘钥进行recover，并在最后聚合时，remove掉他们。

该方法依然没有解决恶意server因为通信延迟问题获取用户的数据问题。

最后一次尝试：双重掩码

双重掩码的目标就是为了防止用户数据的泄露，即使当server重构出用户的masks。首先，每个用户产生一个额外的随机秘钥$a_u$，并且分布他的shares给其他的用户。生成$y_u$时，添加第二重mask：
$$y_u=x_u+a_u+\sum _{u<v}{s}_{u,v}-\sum _{u>v}{s}_{v,u}modeR$$
在recovery轮次中，对于每个用户，server必须作出精确的选择。从每个在线的成员$v$中，请求$u$的$s_{u,v}$或者$a_u$。对于同一个用户，一个诚实的$v$通过这两种shares不能还原数据，server需要从所有dropped的用户中聚合至少t个$s_{u,v}$的shares或者所有在线用户中t个$a_u$的shares。之后，server便可以减去剩余的masks还原数据。
该方法整个过程中的计算和通信数量级还是$n_2$，n表示参与计算的用户数。一个新的问题：当$t<\frac{n}{2}$时，server可以分别询问用户的$s_{u,v}$和$a_u$，来解密用户的数据。

参考文献：
[1] K. Bonawitz. ”Practical Secure Aggregation for Privacy-Preserving Machine Learning”. 2017.
[2] J. Konecny. ”Federated Learning: Strategies for Improving Communication Efficiency”. 2017.
[3] H. B. McMahan. ”Communication-Efficient Learning of Deep Networks from Decentralized Data”. 2016.
[4] A. Shamir. ”How to Share a Secret”. 1979.