背景

機器學習模型對數(shù)據(jù)的分析具有很大的優(yōu)勢，很多敏感數(shù)據(jù)分布在用戶各自的終端。若大規(guī)模收集用戶的敏感數(shù)據(jù)具有泄露的風險。
對于安全分析的一般背景就是認為有n方有敏感數(shù)據(jù)，并且不愿意分享他們的數(shù)據(jù)，但可以分享聚合計算后的結(jié)果。
聯(lián)邦學習是一種訓練數(shù)據(jù)在多方訓練，然后聚合結(jié)果得到最終的中心化模型。其中的關鍵就是多方結(jié)果的安全聚合。

風險模型

有很多用戶，假設用戶都是誠實但好奇的，即會遵守協(xié)議規(guī)則，但會通過拼湊數(shù)據(jù)獲取敏感信息。換句話說就是惡意的，很可能執(zhí)行不好的行為。

安全聚合

問題的定義、目標和假設

風險模型假設用戶和中心服務器都是誠實且好奇的。如果用戶是惡意的，他們有能力在不被監(jiān)測的情況下影響聚合結(jié)果。
安全聚合協(xié)議：

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$都需要產(chǎn)生他們的秘鑰$s_{u,v}$
2. 如果任何一個用戶drop out，對于${\sum }_{?i}{y}_i$都會變成垃圾數(shù)據(jù)，從而本次不能聚合。

利用Diffie-Hellman秘鑰交換改進二次通信

所有的用戶商定一個大素數(shù)$p$和一個基本數(shù)$g$。用戶將自己的公鑰（$g^{a_u}\mathrm{mod}p$，其中$a_u$是用戶的秘鑰）發(fā)送給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$發(fā)給server，然后server詢問其他用戶是否包含drop out的用戶，是的話則取消他們的秘密綁定。如下圖:

該方法的缺點：

1. 在recovery階段發(fā)生額外的用戶drop out，這將要求新drop out的用戶也需要recovery，在大量用戶的情況下，輪詢次數(shù)將增加。
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秘密分享的閾值。每個用戶發(fā)送他們DH秘鑰的shares給其他用戶，只要符合閾值條件，允許pairwise secrets被recovered，即使是recovery期間新dropped用戶。協(xié)議可以總結(jié)如下：

1. 每個用戶$u$將他的DH秘鑰$a_u$分享成n-1個部分$a_{u1},a_{u2},..,a_{u(n?1)}$，并發(fā)送給其他$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因為通信延遲問題獲取用戶的數(shù)據(jù)問題。

最后一次嘗試：雙重掩碼

雙重掩碼的目標就是為了防止用戶數(shù)據(jù)的泄露，即使當server重構出用戶的masks。首先，每個用戶產(chǎn)生一個額外的隨機秘鑰$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不能還原數(shù)據(jù)，server需要從所有dropped的用戶中聚合至少t個$s_{u,v}$的shares或者所有在線用戶中t個$a_u$的shares。之后，server便可以減去剩余的masks還原數(shù)據(jù)。
該方法整個過程中的計算和通信數(shù)量級還是$n_2$，n表示參與計算的用戶數(shù)。一個新的問題：當$t<\frac{n}{2}$時，server可以分別詢問用戶的$s_{u,v}$和$a_u$，來解密用戶的數(shù)據(jù)。

參考文獻：
[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.