基于同態加密與RingAllreduce的去中心化聯邦學習

張斯杰

摘要：聯邦學習為解決數據的使用權與所有權分離問題提供了一種可能的解決方案，但其依賴一臺中央服務器來編排訓練過程，并接收全部客戶端的貢獻，對網絡帶寬要求高，并易造成單點故障或隱私泄露。該文通過引入RingAllreduce算法構建聯邦學習框架，提出了一套去中心化聯邦學習網絡，同時引入了STC三元稀疏算法和同態加密，在多數據節點場景下實現了隱私數據保護與聯邦學習模型更新，有效提升了通信性能與聯邦學習系統的安全性。

關鍵詞：同態加密;去中心化;聯邦學習;分布式;RingAllreduce

中圖分類號：TP311? ? ? 文獻標識碼：A

文章編號：1009-3044（2021）34-0025-03

由于云計算和云服務的便利性和靈活性，越來越多的用戶選擇將他們的本地數據遷移到基于云的服務器，以此來節省本地數據管理費用和系統維護費用。由于數據存儲在用戶物理控制之外的云中，云服務器管理員和非法用戶（如沒有訪問權限的黑客）可能會試圖訪問數據，試圖獲取其中的信息，這可能導致數據信息和用戶隱私的泄露。因此，在數據所有權和使用權分離的情況下，研究滿足當地法律且合規的數據共享與使用方案，在當前隱私與數據保護日益受到各個國家重視的背景下具有重要意義。聯邦學習[1]在當前場景下提出了一種可能的解決方案。

同態加密[2]是在機器學習與外包計算中最廣泛使用的數據保護技術，因為它支持代數運算，包括對密碼文的加法和乘法。如果一種加密方法支持加法或乘法運算，則稱為部分同態加密，如果它支持無限多的加法和乘法運算，則稱為完全同態加密。

本方案基于聯邦學習與同態加密，針對云計算環境下的數據共享與數據使用構建方案。本方案研究結果有助于解決復雜分布式場景中云計算應用端云環境下的數據所有權與使用權分離造成的隱私保護問題，有效利用了網絡帶寬并解決了單點故障問題，對安全性進行了證明，對進一步推進聯邦學習在實際環境下的算法驗證與應用落地有研究價值與重要意義。

1 知識基礎

1.1 聯邦學習

聯邦學習算法中，每個客戶端均基于其本地數據獨立地計算當前模型的更新，并將此更新傳達給中央服務器，在中央服務器上，客戶端的梯度更新被匯總以計算出一個新的全局模型。在這種情況下，移動通信設備，如手機是典型的客戶端，它可以提高通信效率，同時確保用戶的隱私和安全[3]。Bonawitz K[4]在TensorFlow的基礎上實現了針對移動設備的聯邦學習框架并部署成功了可拓展的生產系統。Kone?ny[5]提出對模型量化壓縮以實現聯邦學習。Yang[6]提出了更全面的聯邦學習框架，包括橫向聯邦學習、縱向聯邦學習和聯邦遷移學習。Liu[7]在聯邦學習與XGBoost上設計了一系列協議與方案，并證明具有一定安全性和高效性。

模型訓練過程如圖1所示：

1）客戶端Ci本地存儲有私有數據集Di，通過全局參數[θ]與Di訓練模型獲取梯度向量 [gi]：

[gi=Trainθ， Di]? ? ? ?   ? ? ? ? ? ? ? ? ? ?（1）

2）中央服務器接收各個梯度向量 [gi]

3）將中央服務器每個獲得的梯度向量聚合：

[gs=i=1ngi]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （2）

4）獲得更新全局模型所需要的聚合梯度向量[gs]，將其廣播給Ci，然后用戶使用[gs]更新本地模型。

[θ←θ? αmgs]? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（3）

其中（3）式中，α是學習率。

經過一個周期的訓練，客戶端驗證本地模型是否滿足準確性要求。如果滿足要求，則終止流程，并輸出本地訓練后的模型;如果不滿足要求，則繼續迭代訓練下一輪，直到滿足要求。

1.2 同態加密

同態加密（Homomorphic encryption）是一種允許直接對密文進行操作的可計算加密技術。云服務中計算方根據密文完成計算后，數據擁有方解密該密文計算結果，即可獲得對應明文的運算結果。如果一種同態加密方法支持計算方對加法或乘法運算，則稱為部分同態加密，如果它支持無限多次的加法和乘法運算，則稱為全同態加密。在不損失安全性和正確性的前提下，同態加密滿足了多方分別使用公鑰和秘鑰對信息進行加密和解密。

同態加密的概念最初提出用于解決云計算等外包計算中的數據機密性保護問題，防止云計算服務提供商獲取敏感明文數據，實現“先計算后解密”等價于傳統的“先解密后計算”。隨著區塊鏈、隱私計算等新興領域的發展及其對隱私保護的更高要求，同態加密的應用邊界拓展到了更為豐富的領域[8]。

1.3 RingAllreduce

RingAllreduce[9]是一種針對分布式場景下多client場景進行數據交換與梯度融合的算法，常被用于gpu集群，在有限帶寬場景下有力地解決了網絡瓶頸的問題。

如圖2所示，client以環狀組成去中心化網絡，每個 client 在Scatter Reduce 階段，接收 N-1 次數據，N 是client 數量;每個client在allgather 階段，接收 N-1 次 數據;每個 GPU 每次發送 K/N 大小數據塊，K 是總數據大小;所以，Data Transferred=2（N?1）*K/N ，隨著 client數量 N 增加，總傳輸量恒定。也就是理論上，隨著client數量的增加，Ring Allreduce有線性加速能力。

2 安全去中心化聯邦學習系統

2.1 數據傳輸

本文所面對的場景中各個節點與信道都存在攻擊可能，因此整個數據傳輸與梯度聚合過程中需要通過同態加密進行隱私保護。但同態加密會導致所需要傳輸的帶寬壓力增加，并且在聯邦學習訓練過程中，如果將全部梯度參數都進行同步，在梯度參數多的場景下，將占用大量的通信資源，成為系統性能的瓶頸。因此我們在數據傳輸中引入了稀疏三元壓縮（STC）[10]算法，STC擴展了現有的top-k梯度稀疏化的壓縮技術，用一種新的機制來實現對數據傳輸中數據的壓縮，更好地利用了通信資源，并一定程度上解決了同態加密所需傳輸帶寬較高的問題。具體來說，每個本地模型計算出梯度g之后，首先將梯度向量中的元素的絕對值應用top-k算法，獲取絕對值最大的k個梯度，之后將這選出的 k 個梯度值量化為包含[?μ，0，μ]的三元張量。

在當前應用場景中，本方案設計了改進后的基于Paillier與STC的同態加密算法，實現了密鑰生成、加密算法、解密算法與密文運算，在去中心化聯邦學習場景下保護隱私數據不被惡意用戶或服務端泄露。

a） 密鑰生成：

隨機獨立選擇兩個大素數p，q，滿足公式（4）

[gcdpq，p?1q?1=1]? ? ? ? ? ? ? ? ? （4）

[計算n=pq， λ=lcm（p?1，q?1）]

[取g∈Z?n2]

[計算μ=（Lgλ mod n2）?1 mod n]

最終得到公鑰[pk = n，g， 私鑰sk=（λ， μ）]

b）加密：

假設要加密的張量三元組為[m]，隨機獨立選擇一個整數[r]

計算出密文[c= gm?rn mod n2]

c） 解密：

需要解密的密文為c

明文公式為[m=Lcλ mod n2?μ mod n]

d）密文運算

[DEm1， r1?Em2， r2 mod n2=m1+m2? mod n]（5）

本方案將隨機數[g]取值為[n+1]，根據二項式定理，將加密運算中的模指數運算簡化為了一次模乘，加速了加密過程。

2.2方案設計

在本文所涉及場景中，我們希望基于一致性哈希環狀組網方式，實現聯邦學習網絡中數據節點以地位對等的環狀扁平化拓撲結構互相連通與交互，每個節點均承擔聯邦學習中服務器端所需的網絡路由與梯度更新職責，最終擺脫聯邦學習里中心服務器對系統的束縛，避免中心服務器帶寬瓶頸、單點故障與隱私泄露，實現基于RingAllreduce的去中心化聯邦學習系統。

整體架構如圖3所示，首先所有客戶端廣播自己位置與IP，通過對IP進行一致性哈希進行環狀組網。之后選舉一個承擔解密工作的client，生成加密公鑰與私鑰，并將私鑰廣播給所有客戶端。用戶在本地讀取私有數據，并訓練模型。在基于RingAllreduce梯度更新與聚合場景中，利用基于STC向量化的同態加密算法，對各個客戶端私有數據進行加密，防止好奇客戶端竊取其他客戶端數據，并保證了數據的準確性與模型的有效性。最終由解密client將解密后梯度廣播給所有client，完成一輪訓練。詳細訓練過程如下：

輸入：各個模型私有數據[dn]，待訓練模型[θ]

輸出：訓練完畢的模型[θ]

①各個client依靠對IP一致性哈希進行環形組網;

②基于raft執行選主，最終選出leader client [c0]作為解密client;

③[c0]生成同態加密公鑰私鑰，將公鑰廣播給網絡內所有client;

④[cn]獲取本地數據[dn]，結合當前待訓練模型[θ]進行訓練;

⑤使用STC稀疏三元算法壓縮選擇并量化梯度元素，利用公鑰將量化后梯度數據加密;

⑥運行RingAllreduce算法將加密后梯度元素數據進行匯總并求和;

⑦[c0]運行解密算法獲取最終梯度[gs]，廣播給網絡里所有client;

⑧client使用[gs]更新本地模型

⑨若未達到要求，由②進行下一輪訓練，或者達到模型要求，停止訓練

3 實驗

本文選用數據集為美國國家標準與技術研究院收集整理的大型手寫數字數據庫（Mixed National Institute of Standards and Technology database，簡稱MNIST），該數據集包含60，000個用于培訓的示例和10，000個用于測試的示例。 這些數字已經標準化，并以固定大小的圖像（28x28像素）為中心，其值為0到1。為簡單起見，每個圖像都被展平并轉換為784個特征（28 * 28）的一維 numpy數組）。

本文使用預測準確率（Acc）、傳輸數據量開銷（Vol）以及訓練總時間（Time）評判模型的有效性。

結果表明，與傳統的有中心聯邦學習方案相比，基于RingAllreduce的去中心化聯邦學習模型在執行速度和模型準確度有微小損失的前提下，大大降低了中心服務器的帶寬開銷，同時一定程度上加快了訓練速度。在引入STC三元稀疏梯度算法后，我們對梯度向量進行同態加密并引入了加密解密步驟，在引入一定時間與傳輸數據量的基礎上實現了對用戶隱私數據的保護。

4 結束語

聯邦學習作為解決數據安全與隱私保護下的端云場景應用起到了重要的作用，但其在工業場景中經常由于中心服務器帶寬瓶頸影響訓練效率與橫向拓展，以及在梯度數據泄露時用戶隱私數據也會受到威脅。本文提出了基于同態加密與RingAllreduce的去中心化聯邦學習模型，利用STC稀疏壓縮算法在不影響模型準確性的前提下提升了同態加密效率與數據傳輸效率，通過使用RingAllreduce實現了去中心化架構，在擺脫單點依賴的同時，有效提升了通信性能與聯邦學習系統的安全性。未來的工作重點應當著重研究進一步提升同態加密與聯邦學習的效率。

參考文獻：

[1] Yang Q，Liu Y，Cheng Y，et al.Federated learning[J].Synthesis Lectures on Artificial Intelligence and Machine Learning，2019，13（3）：1-207.

[2] Gentry C.Fully homomorphic encryption using ideal lattices[C]//Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09.May 31-June2，2009.Bethesda，MD，USA.New York：ACMPress，2009：169-178.

[3] Li T，Sahu A K，Talwalkar A，et al.Federated learning：challenges，methods，and future directions[J].IEEE Signal Processing Magazine，2020，37（3）：50-60.

[4] Bonawitz K，Eichner H，Grieskamp W，et al.Towards federated learning at scale：system design[EB/OL].2019

[5] Kone?ny J，McMahan H B，Yu F X，et al.Federated learning：strategies for improving communication efficiency[EB/OL].2016：arXiv：1610.05492[cs.LG].https：//arxiv.org/abs/1610.05492

[6] Yang Q，Liu Y，Chen T J，et al.Federated machine learning[J].ACM Transactions on Intelligent Systems and Technology，2019，10（2）：1-19.

[7] Liu Y，Ma Z，Liu X M，et al.Boosting privately：privacy-preserving federated extreme boosting for mobile crowdsensing[EB/OL].2019

[8] 李順東，竇家維，王道順.同態加密算法及其在云安全中的應用[J].計算機研究與發展，2015，52（6）：1378-1388.

[9] Sergeev A，Balso M D.Horovod：fast and easy distributed deep learning in TensorFlow[EB/OL].2018

[10] Sattler F，Wiedemann S，Müller K R，et al.Robust and communication-efficient federated learning from non-i.i.d.data[J].IEEE Transactions on Neural Networks and Learning Systems，2019，31（9）：3400-3413.

【通聯編輯：光文玲】