基于同態(tài)加密與RingAllreduce的去中心化聯(lián)邦學(xué)習(xí)

張斯杰

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

關(guān)鍵詞：同態(tài)加密;去中心化;聯(lián)邦學(xué)習(xí);分布式;RingAllreduce

中圖分類號：TP311? ? ? 文獻(xiàn)標(biāo)識碼：A

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

由于云計(jì)算和云服務(wù)的便利性和靈活性，越來越多的用戶選擇將他們的本地?cái)?shù)據(jù)遷移到基于云的服務(wù)器，以此來節(jié)省本地?cái)?shù)據(jù)管理費(fèi)用和系統(tǒng)維護(hù)費(fèi)用。由于數(shù)據(jù)存儲在用戶物理控制之外的云中，云服務(wù)器管理員和非法用戶（如沒有訪問權(quán)限的黑客）可能會試圖訪問數(shù)據(jù)，試圖獲取其中的信息，這可能導(dǎo)致數(shù)據(jù)信息和用戶隱私的泄露。因此，在數(shù)據(jù)所有權(quán)和使用權(quán)分離的情況下，研究滿足當(dāng)?shù)胤汕液弦?guī)的數(shù)據(jù)共享與使用方案，在當(dāng)前隱私與數(shù)據(jù)保護(hù)日益受到各個(gè)國家重視的背景下具有重要意義。聯(lián)邦學(xué)習(xí)[1]在當(dāng)前場景下提出了一種可能的解決方案。

同態(tài)加密[2]是在機(jī)器學(xué)習(xí)與外包計(jì)算中最廣泛使用的數(shù)據(jù)保護(hù)技術(shù)，因?yàn)樗С执鷶?shù)運(yùn)算，包括對密碼文的加法和乘法。如果一種加密方法支持加法或乘法運(yùn)算，則稱為部分同態(tài)加密，如果它支持無限多的加法和乘法運(yùn)算，則稱為完全同態(tài)加密。

本方案基于聯(lián)邦學(xué)習(xí)與同態(tài)加密，針對云計(jì)算環(huán)境下的數(shù)據(jù)共享與數(shù)據(jù)使用構(gòu)建方案。本方案研究結(jié)果有助于解決復(fù)雜分布式場景中云計(jì)算應(yīng)用端云環(huán)境下的數(shù)據(jù)所有權(quán)與使用權(quán)分離造成的隱私保護(hù)問題，有效利用了網(wǎng)絡(luò)帶寬并解決了單點(diǎn)故障問題，對安全性進(jìn)行了證明，對進(jìn)一步推進(jìn)聯(lián)邦學(xué)習(xí)在實(shí)際環(huán)境下的算法驗(yàn)證與應(yīng)用落地有研究價(jià)值與重要意義。

1 知識基礎(chǔ)

1.1 聯(lián)邦學(xué)習(xí)

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

模型訓(xùn)練過程如圖1所示：

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

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

2）中央服務(wù)器接收各個(gè)梯度向量 [gi]

3）將中央服務(wù)器每個(gè)獲得的梯度向量聚合：

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

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

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

其中（3）式中，α是學(xué)習(xí)率。

經(jīng)過一個(gè)周期的訓(xùn)練，客戶端驗(yàn)證本地模型是否滿足準(zhǔn)確性要求。如果滿足要求，則終止流程，并輸出本地訓(xùn)練后的模型;如果不滿足要求，則繼續(xù)迭代訓(xùn)練下一輪，直到滿足要求。

1.2 同態(tài)加密

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

同態(tài)加密的概念最初提出用于解決云計(jì)算等外包計(jì)算中的數(shù)據(jù)機(jī)密性保護(hù)問題，防止云計(jì)算服務(wù)提供商獲取敏感明文數(shù)據(jù)，實(shí)現(xiàn)“先計(jì)算后解密”等價(jià)于傳統(tǒng)的“先解密后計(jì)算”。隨著區(qū)塊鏈、隱私計(jì)算等新興領(lǐng)域的發(fā)展及其對隱私保護(hù)的更高要求，同態(tài)加密的應(yīng)用邊界拓展到了更為豐富的領(lǐng)域[8]。

1.3 RingAllreduce

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

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

2 安全去中心化聯(lián)邦學(xué)習(xí)系統(tǒng)

2.1 數(shù)據(jù)傳輸

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

在當(dāng)前應(yīng)用場景中，本方案設(shè)計(jì)了改進(jìn)后的基于Paillier與STC的同態(tài)加密算法，實(shí)現(xiàn)了密鑰生成、加密算法、解密算法與密文運(yùn)算，在去中心化聯(lián)邦學(xué)習(xí)場景下保護(hù)隱私數(shù)據(jù)不被惡意用戶或服務(wù)端泄露。

a） 密鑰生成：

隨機(jī)獨(dú)立選擇兩個(gè)大素?cái)?shù)p，q，滿足公式（4）

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

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

[取g∈Z?n2]

[計(jì)算μ=（Lgλ mod n2）?1 mod n]

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

b）加密：

假設(shè)要加密的張量三元組為[m]，隨機(jī)獨(dú)立選擇一個(gè)整數(shù)[r]

計(jì)算出密文[c= gm?rn mod n2]

c） 解密：

需要解密的密文為c

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

d）密文運(yùn)算

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

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

2.2方案設(shè)計(jì)

在本文所涉及場景中，我們希望基于一致性哈希環(huán)狀組網(wǎng)方式，實(shí)現(xiàn)聯(lián)邦學(xué)習(xí)網(wǎng)絡(luò)中數(shù)據(jù)節(jié)點(diǎn)以地位對等的環(huán)狀扁平化拓?fù)浣Y(jié)構(gòu)互相連通與交互，每個(gè)節(jié)點(diǎn)均承擔(dān)聯(lián)邦學(xué)習(xí)中服務(wù)器端所需的網(wǎng)絡(luò)路由與梯度更新職責(zé)，最終擺脫聯(lián)邦學(xué)習(xí)里中心服務(wù)器對系統(tǒng)的束縛，避免中心服務(wù)器帶寬瓶頸、單點(diǎn)故障與隱私泄露，實(shí)現(xiàn)基于RingAllreduce的去中心化聯(lián)邦學(xué)習(xí)系統(tǒng)。

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

輸入：各個(gè)模型私有數(shù)據(jù)[dn]，待訓(xùn)練模型[θ]

輸出：訓(xùn)練完畢的模型[θ]

①各個(gè)client依靠對IP一致性哈希進(jìn)行環(huán)形組網(wǎng);

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

③[c0]生成同態(tài)加密公鑰私鑰，將公鑰廣播給網(wǎng)絡(luò)內(nèi)所有client;

④[cn]獲取本地?cái)?shù)據(jù)[dn]，結(jié)合當(dāng)前待訓(xùn)練模型[θ]進(jìn)行訓(xùn)練;

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

⑥運(yùn)行RingAllreduce算法將加密后梯度元素?cái)?shù)據(jù)進(jìn)行匯總并求和;

⑦[c0]運(yùn)行解密算法獲取最終梯度[gs]，廣播給網(wǎng)絡(luò)里所有client;

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

⑨若未達(dá)到要求，由②進(jìn)行下一輪訓(xùn)練，或者達(dá)到模型要求，停止訓(xùn)練

3 實(shí)驗(yàn)

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

本文使用預(yù)測準(zhǔn)確率（Acc）、傳輸數(shù)據(jù)量開銷（Vol）以及訓(xùn)練總時(shí)間（Time）評判模型的有效性。

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

4 結(jié)束語

聯(lián)邦學(xué)習(xí)作為解決數(shù)據(jù)安全與隱私保護(hù)下的端云場景應(yīng)用起到了重要的作用，但其在工業(yè)場景中經(jīng)常由于中心服務(wù)器帶寬瓶頸影響訓(xùn)練效率與橫向拓展，以及在梯度數(shù)據(jù)泄露時(shí)用戶隱私數(shù)據(jù)也會受到威脅。本文提出了基于同態(tài)加密與RingAllreduce的去中心化聯(lián)邦學(xué)習(xí)模型，利用STC稀疏壓縮算法在不影響模型準(zhǔn)確性的前提下提升了同態(tài)加密效率與數(shù)據(jù)傳輸效率，通過使用RingAllreduce實(shí)現(xiàn)了去中心化架構(gòu)，在擺脫單點(diǎn)依賴的同時(shí)，有效提升了通信性能與聯(lián)邦學(xué)習(xí)系統(tǒng)的安全性。未來的工作重點(diǎn)應(yīng)當(dāng)著重研究進(jìn)一步提升同態(tài)加密與聯(lián)邦學(xué)習(xí)的效率。

參考文獻(xiàn)：

[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] 李順東，竇家維，王道順.同態(tài)加密算法及其在云安全中的應(yīng)用[J].計(jì)算機(jī)研究與發(fā)展，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.

【通聯(lián)編輯：光文玲】