基于并行同態加密和STC的高效安全聯邦學習*

肖林聲，錢慎一

（鄭州輕工業大學，河南 鄭州 450007）

0 引言

聯邦學習（Federated Learning）[1-3]最早由HB McMahan團隊提出。聯邦學習在一定程度上保證了隱私的安全，但還存在許多不足，如攻擊者可以使用共享的梯度來逆向推演，從而得到用戶的隱私數據和敏感信息；如果僅適用現有簡單的隱私保護技術如同態加密技術（Homomorphic Encryption，HE）、安全多方計算（Secure Multi-Party Computation，MPC）等會產生大量的額外開銷，給設備帶來巨大的負擔。

為了解決以上問題，本文基于稀疏三元壓縮（Sparse Ternary Compression，STC）技術和并行同態加密算法提出了一種新方法，不僅可以保護用戶隱私，還可極大地減少通信和計算開銷。

本文的主要貢獻在于兩個方面。一方面，將STC和并行同態加密應用到聯邦學習方案。與不加密的明文相比，準確性沒有降低；與現有的加密工作相比，通信開銷極大降低，且顯著提升了計算效率。另一方面，本文使用了一種驗證聚合結果有效性的方案，有效避免了服務器惡意篡改訓練結果的情況。

1 理論基礎

下面主要介紹本文使用的聯邦學習算法、STC算法、同態加密算法以及消息驗證碼。

1.1 聯邦學習

聯邦學習的結構如圖1所示。

圖1 聯邦學習系統結構

模型訓練過程如下：

（1）基于私有數據集，用戶Ci在本地訓練θ，得到梯度向量gi：

（2）服務器S接收從用戶上傳的梯度向量gi；

（3）在服務器S中，將所有獲得的梯度向量聚合：

（4）計算完成后得到聚合梯度向量gS，并將其返回給所有m，然后用戶使用聚合梯度更新本地模型：

式中，α是學習率。

在一輪訓練完成后，用戶需要檢測本地模型的準確率是否滿足要求。如果滿足要求，則停止訓練并輸出訓練好的模型；如果沒有滿足要求，則繼續迭代進行下一輪訓練，直到滿足要求為止。

1.2 STC算法

聯邦學習中，用戶在每次訓練完成后均需要將訓練得到的梯度全部傳輸給服務器。在需要的梯度參數較多的系統中，這將會占用大量的通信資源，成為系統性能提升的瓶頸。本文主要參考Aij[4]等人提出的Top-K梯度選擇方案和Felix Sattler等人[5]提出的Top-K梯度選擇方案的擴展——STC稀疏三元算法。

具體來說，每次用戶C計算得到梯度g后，首先將梯度向量中的元素g[j]的絕對值進行排序，取出排序完成的梯度絕對值最大的K個梯度，后將這選出的K個梯度值量化為三元張量上傳到服務器S。

圖2中TK代表用Top-K方案取出的絕對值最大的K個梯度值，而tmp中存儲的是梯度的索引和梯度的絕對值。將梯度的索引和梯度的絕對值排序，選出絕對值最大的K個梯度值，在稀疏化的同時對稀疏化后的目標向量。在STC算法的作用下，TK∈Rn最終會生成三元張量TK*∈{-μ,0,μ}n。

文獻[5]先使用Top-K算法取出相應的梯度絕對值最大的K個梯度，然后將其梯度值量化為包含{-μ,0,μ}的三元向量。作者用實驗證明，三元化不影響收斂速度，甚至會提高訓練的模型精度，表明對數據稀疏化和量化的結合相比于單純使用Top-K算法稀疏化數據更好地利用了通信資源，且效率更高。作者不僅將STC用在用戶將梯度上傳到服務器的情況，也將STC用到了用戶從服務器下載的情況，進一步減小了通信開銷。

1.3 并行同態加密算法

關于同態加密的研究，先是Rivest等[6]提出RSA加密算法，后又在文獻[7]中提出了同態加密的概念。2009年，Gentry[8]第一次提出了全同態加密方案，并在文獻[9]中對該方案進行了詳細介紹，并已經由Gentry實現[10-11]。2010年，DGHV方案被提出，是一種基于整數的同態加密方案，只滿足加法和乘法的同態加密方案。本文基于胡持等[12]提出的基于DGHV同態加密方案，通過MapReduce框架實現并行加密，在保護個人隱私的同時，通過MapReduce的并行化處理提高數據的加密效率。由于密鑰持有問題，同態加密算法不能直接用于聯邦學習算法，因此采取多密鑰同態加密算法[13]來解決密鑰的持有問題。

圖2 稀疏三元壓縮算法

1.4 消息驗證碼

消息驗證碼（Message Authentication Code，MAC）是確認信息完整性并認證的技術[14]，是一種與密鑰相關聯的單向Hash函數，如文獻[15]中提出的HMAC。(G,Sign,Verify)這3個元素組成了驗證碼，其中生成密鑰的算法為G，密鑰sk←G(1κ)由G生成其中的κ為安全參數，且安全參數是給定的；Sign(sk,x)則使用sk和信息x生成驗證碼MAC=Sign(sk,x)；Verify是將sk、x和MAC集合起來，判斷Verify(sk,x,MAC)=Accept是不是成立。

算法Sign和Verify需要滿足：

本文參考文獻[16]中使用消息驗證碼的思想和梯度選擇的索引信息，驗證聚合結果的有效性。

2 方案設計

本文基于并行同態加密和STC算法，針對聯邦學習算法中的隱私安全和通信開銷問題，提出了安全且高效的訓練協議。一方面提出協議πHEFL，使得誠實用戶的梯度信息受到加密算法的保護，而攻擊者無法獲得。另一方面，提出了可以在保護用戶梯度隱私的前提下抵抗惡意篡改攻擊的協議，以保證聚合結果的可用性。

假設用戶的數目m≥3且服務器被半誠實攻擊者腐化，而所有的用戶中有被半誠實攻擊者腐化的用戶存在。

2.1 協議πHEFL

協議πHEFL是在半誠實的攻擊者威脅下保護單個用戶梯度的隱私性。該協議流程如圖3所示。

首先，每個用戶按照式（1）訓練模型θ，從而得到梯度向量g。其次，用戶調用STC稀疏三元壓縮算法，選出絕對值最大的K個梯度并將其量化為包含{-μ,0,μ}的三元向量。最后，用戶通過并行同態加密算法將選擇并量化的梯度向量加密生成密文向量C，并將加密完成的梯度向量上傳到服務器。注意，梯度的索引信息也要上傳。

服務器在收到用戶上傳的密文后，根據索引的信息，使用全同態加密中的Eval(evk,C,c1,…,cn)密文運算算法，將梯度在加密狀態下進行聚合得到聚合結果gS，后將gS和索引信息的并集返回IND給用戶。

協議的形式如下。

輸入：隱私數據集Di、待訓練模型θ

輸出：訓練完成的模型θ

①用戶均和服務器建立安全的連接；

②每個用戶在本地生成隨機數；

③用戶使用私有數據訓練模型；

④用戶使用STC稀疏三元壓縮算法，選擇并量化梯度元素；

⑤用戶對選出的并已經量化的梯度調用并行同態加密算法生成密文C；

⑥用戶將加密好的梯度密文和索引信息的集合傳輸到服務器；

⑦服務器根據索引信息，使用密文運算算法Eval(evk,C,c1,…,cn)對各個用戶上傳的梯度進行聚合；

⑧用戶下載服務器中聚合結果的密文，并用私密密鑰sk將其還原；

⑨用戶使用還原的結果更新本地模型；

⑩若未達到要求，則跳轉③進行下一輪訓練，或者達到要求停止訓練。

協議πHEFL可以很好地保護誠實用戶的梯度和隱私信息。

圖3 協議πHEFL的流程

2.2 協議

協議πHEFL能夠保護用戶的梯度信息，但是不能阻止攻擊者在不直接泄露用戶隱私的情況下腐化服務器并對結果進行修改。

假設攻擊者腐化服務器S，記S使用Eval(evk,C,c1,…,cn)聚合生成gS，但是攻擊者可能會生成任意的噪聲向量r，之后攻擊者便可以將噪聲和密文一起計算：

從而使得最終聚合的結果受到噪聲r的干擾。

利用梯度的索引和量化的梯度值來構造驗證碼MAC來抵抗惡意攻擊者的攻擊。

這里要修改安全性假設：需要兩個服務器，且這兩個服務器不可同時被惡意攻擊者腐化，其中一個服務器S1負責聚合梯度，另一個服務器S2負責計算和存儲驗證碼MAC。

和協議πHEFL一樣，用戶首先在本地訓練θ并使用STC算法得到量化梯度，記為：

這里的g[ind]是量化完成后的值，后利用索引信息和梯度的量化值g[ind]計算驗證碼MAC：

利用同態加密算法將MAC加密，并上傳MAC的密文M到所有的服務器。服務器收到用戶上傳的MAC密文后，使用密文運算算法Eval(evk,C,c1,…,cn)將所有的MAC求和得到MACS：

對于梯度值，使用密文運算算法Eval(evk,C,c1,…,cn)，并使用式（2）來聚合梯度。

聚合完成后，服務器將聚合結果的密文、對應的索引信息INDS以及各個服務器中的MACS返回用戶。

用戶在本地解密聚合梯度的真實值gS，并在本地進行驗證：

（1）兩個服務器的MACS都相等；

（2）用戶計算：

并檢驗MAC′S=MACS。

如果以上驗證都通過，那么用戶接受gS并更新模型；否則，廣播錯誤并終止協議。圖4為協議的工作流程。

圖4 協議的工作流程

輸入：數據集Di和模型θ；

輸出：訓練完成的模型θ；

①用戶均和服務器建立安全的連接；

②每個用戶在本地生成隨機數；

③用戶在本地訓練模型，計算梯度；

④用戶調用STC稀疏三元壓縮法，選擇Top-K梯度并將其量化為三元向量；

⑤用戶使用式（7）計算驗證碼MAC；

⑥調用并行同態加密算法分別加密梯度和驗證碼；

⑦將梯度的密文C上傳到服務器S1，將驗證碼MAC分別發給服務器S1和S2；

⑧服務器S1聚合梯度，且和服務器S2一起按照式（9）求和得到MACS；

⑨用戶下載并恢復梯度，同時下載所有服務器的MACS；

⑩如果通過所有的驗證，則用戶更新本地模型；否則，廣播錯誤并終止訓練進行下一輪訓練，達到要求的情況下停止訓練并輸出模型。

下面分析過程的正確性。

（1）如果服務器沒有進行任何惡意篡改，那么兩個服務器所接收的MAC相同，那么得到的MACS也相同。

（2）這里假設只有兩個用戶（為了方便，此處先不考慮隱私保護P1、P2，且記P1、P2選擇且量化的梯度向量為g1和g2，對應的索引集為IND1和IND2。根據協議，INDS=IND1∪IND2。

對于索引ind來說，?ind∈INDS，有以下3種情況：

由式（8）可得MACS=MAC1+MAC2，MACS=因此協議在一定程度上抵御了結果不被服務器惡意篡改。

3 實驗和結果

選擇的數據集中有37萬條數據，是2012—2018年的投訴信息，分為78個大類信息和249個小類信息。每一個信息包含78個屬性。每次訓練迭代中用戶需要和服務器交互計算1次，以此完成梯度的安全聚合。直接使用線性支持向量機訓練所得到的準確率為79%。

本文使用預測準確率、通信開銷大小以及單次訓練所消耗的時間來評判協議的有效性。

3.1 模型的準確率

為了證明協議的可用性，需要計算準確率。若準確率達到了明文條件下的水平或者沒有較大的下降，說明提出的協議對訓練模型的預測性能沒有太大影響。因為驗證訓練結果的過程對模型的準確性并沒有影響，所以這一部分只考慮明文和πHEFL協議兩種情況。

探索不同梯度選擇比率對訓練模型的影響。在不同的梯度選擇比率下，迭代100次，選擇1%、5%和10%和明文下100%上傳的方式比較。在表1中可以看到，上傳的梯度的增加對準確度的提升沒有太大影響。

表1 模型最終準確率

3.2 通信開銷

為了提升通信性能，并在有效減少通信開銷的同時保證隱私安全，在STC稀疏三元壓縮的基礎上，結合并行同態加密提出了相對高效的解決方案。實驗中將STC中的梯度選擇的比率控制在1%、5%和10%，且在明文、協議πHEFL和協議下測量了在訓練完成的情況下通信的開銷，結果如表2所示。

表2 一次迭代訓練中上傳和下載的通信開銷

從實驗結果可以看出，采用STC稀疏三元壓縮法可以很好地解決通信開銷問題。將STC選擇的選擇梯度的比率從10%到1%，通信性能有了明顯優化，上傳的開銷相比于明文優化了約50倍，而下載的開銷則優化了約4.9倍。由第3.1章節和文獻[5]可知，STC稀疏三元壓縮選擇的比率不會對模型的性能造成太大影響，且相比于Top-K梯度選擇算法，STC在減小通信開銷的同時可以提高訓練精度。此外，增加驗證信息并沒有增加額外的通信開銷。可見，STC算法在聯邦學習領域擁有巨大的發展潛力。

3.3 時間開銷

在訓練過程中，測量了協議πHEFL和各個階段的時間開銷。需要說明，這里的PWH直接使用同態加密而沒有并行化處理。在協議的用戶端和服務器端中分別加入了處理驗證碼的時間開銷。在STC下選擇梯度的比率為1%、5%和10%進行實驗，并與明文狀態和未使用并行化而直接使用同態加密的PWH方案進行對比，結果如表3和表4所示。

表3 一次迭代訓練中的訓練和傳輸時間開銷

表4 一次迭代訓練中的服務器端，預處理和總體的時間開銷

結果表明，和明文訓練相比，加入的并行化同態加密安全協議在訓練時引入了一定的時間開銷，但是和直接使用同態加密相比，引入的時間開銷小了很多。隨著梯度選擇的比率上升，同態加密算法所消耗的時間也在快速上升。可以發現，用戶端的計算時間、服務器端的計算時間以及明文的計算時間增加的幅度很小，且這種增幅在實際應用中是可以接受的。除了同態加密所花費的時間開銷以外，主要的時間開銷來自于傳輸梯度的時間開銷，這是目前限制安全聯邦學習應用的主要原因。

4 結語

聯邦學習中隱私安全、時間開銷和通信開銷是其重要的瓶頸，而這些問題在安全聯邦學習中的影響正在變得更加嚴重。本文使用STC稀疏三元壓縮算法和并行同態加密算法結合起來，一定程度上在時間開銷、通信開銷和隱私保護之間取得了平衡。此外，參考文獻[16]構造了驗證碼，但隨著系統的增大，安全聯邦學習效率低下依舊是重要的研究課題。未來的工作重點將著重研究進一步提升安全聯邦學習的效率。