肖林聲，錢慎一

（鄭州輕工業(yè)大學(xué)，河南 鄭州 450007）

0 引言

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

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

本文的主要貢獻(xiàn)在于兩個(gè)方面。一方面，將STC和并行同態(tài)加密應(yīng)用到聯(lián)邦學(xué)習(xí)方案。與不加密的明文相比，準(zhǔn)確性沒(méi)有降低；與現(xiàn)有的加密工作相比，通信開銷極大降低，且顯著提升了計(jì)算效率。另一方面，本文使用了一種驗(yàn)證聚合結(jié)果有效性的方案，有效避免了服務(wù)器惡意篡改訓(xùn)練結(jié)果的情況。

1 理論基礎(chǔ)

下面主要介紹本文使用的聯(lián)邦學(xué)習(xí)算法、STC算法、同態(tài)加密算法以及消息驗(yàn)證碼。

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

聯(lián)邦學(xué)習(xí)的結(jié)構(gòu)如圖1所示。

圖1 聯(lián)邦學(xué)習(xí)系統(tǒng)結(jié)構(gòu)

模型訓(xùn)練過(guò)程如下：

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

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

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

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

式中，α是學(xué)習(xí)率。

在一輪訓(xùn)練完成后，用戶需要檢測(cè)本地模型的準(zhǔn)確率是否滿足要求。如果滿足要求，則停止訓(xùn)練并輸出訓(xùn)練好的模型；如果沒(méi)有滿足要求，則繼續(xù)迭代進(jìn)行下一輪訓(xùn)練，直到滿足要求為止。

1.2 STC算法

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

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

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

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

1.3 并行同態(tài)加密算法

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

圖2 稀疏三元壓縮算法

1.4 消息驗(yàn)證碼

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

算法Sign和Verify需要滿足：

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

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

本文基于并行同態(tài)加密和STC算法，針對(duì)聯(lián)邦學(xué)習(xí)算法中的隱私安全和通信開銷問(wèn)題，提出了安全且高效的訓(xùn)練協(xié)議。一方面提出協(xié)議πHEFL，使得誠(chéng)實(shí)用戶的梯度信息受到加密算法的保護(hù)，而攻擊者無(wú)法獲得。另一方面，提出了可以在保護(hù)用戶梯度隱私的前提下抵抗惡意篡改攻擊的協(xié)議，以保證聚合結(jié)果的可用性。

假設(shè)用戶的數(shù)目m≥3且服務(wù)器被半誠(chéng)實(shí)攻擊者腐化，而所有的用戶中有被半誠(chéng)實(shí)攻擊者腐化的用戶存在。

2.1 協(xié)議πHEFL

協(xié)議πHEFL是在半誠(chéng)實(shí)的攻擊者威脅下保護(hù)單個(gè)用戶梯度的隱私性。該協(xié)議流程如圖3所示。

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

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

協(xié)議的形式如下。

輸入：隱私數(shù)據(jù)集Di、待訓(xùn)練模型θ

輸出：訓(xùn)練完成的模型θ

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

②每個(gè)用戶在本地生成隨機(jī)數(shù)；

③用戶使用私有數(shù)據(jù)訓(xùn)練模型；

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

⑤用戶對(duì)選出的并已經(jīng)量化的梯度調(diào)用并行同態(tài)加密算法生成密文C；

⑥用戶將加密好的梯度密文和索引信息的集合傳輸?shù)椒?wù)器；

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

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

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

⑩若未達(dá)到要求，則跳轉(zhuǎn)③進(jìn)行下一輪訓(xùn)練，或者達(dá)到要求停止訓(xùn)練。

協(xié)議πHEFL可以很好地保護(hù)誠(chéng)實(shí)用戶的梯度和隱私信息。

圖3 協(xié)議πHEFL的流程

2.2 協(xié)議

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

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

從而使得最終聚合的結(jié)果受到噪聲r(shí)的干擾。

利用梯度的索引和量化的梯度值來(lái)構(gòu)造驗(yàn)證碼MAC來(lái)抵抗惡意攻擊者的攻擊。

這里要修改安全性假設(shè)：需要兩個(gè)服務(wù)器，且這兩個(gè)服務(wù)器不可同時(shí)被惡意攻擊者腐化，其中一個(gè)服務(wù)器S1負(fù)責(zé)聚合梯度，另一個(gè)服務(wù)器S2負(fù)責(zé)計(jì)算和存儲(chǔ)驗(yàn)證碼MAC。

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

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

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

對(duì)于梯度值，使用密文運(yùn)算算法Eval(evk,C,c1,…,cn)，并使用式（2）來(lái)聚合梯度。

聚合完成后，服務(wù)器將聚合結(jié)果的密文、對(duì)應(yīng)的索引信息INDS以及各個(gè)服務(wù)器中的MACS返回用戶。

用戶在本地解密聚合梯度的真實(shí)值gS，并在本地進(jìn)行驗(yàn)證：

（1）兩個(gè)服務(wù)器的MACS都相等；

（2）用戶計(jì)算：

并檢驗(yàn)MAC′S=MACS。

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

圖4 協(xié)議的工作流程

輸入：數(shù)據(jù)集Di和模型θ；

輸出：訓(xùn)練完成的模型θ；

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

②每個(gè)用戶在本地生成隨機(jī)數(shù)；

③用戶在本地訓(xùn)練模型，計(jì)算梯度；

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

⑤用戶使用式（7）計(jì)算驗(yàn)證碼MAC；

⑥調(diào)用并行同態(tài)加密算法分別加密梯度和驗(yàn)證碼；

⑦將梯度的密文C上傳到服務(wù)器S1，將驗(yàn)證碼MAC分別發(fā)給服務(wù)器S1和S2；

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

⑨用戶下載并恢復(fù)梯度，同時(shí)下載所有服務(wù)器的MACS；

⑩如果通過(guò)所有的驗(yàn)證，則用戶更新本地模型；否則，廣播錯(cuò)誤并終止訓(xùn)練進(jìn)行下一輪訓(xùn)練，達(dá)到要求的情況下停止訓(xùn)練并輸出模型。

下面分析過(guò)程的正確性。

（1）如果服務(wù)器沒(méi)有進(jìn)行任何惡意篡改，那么兩個(gè)服務(wù)器所接收的MAC相同，那么得到的MACS也相同。

（2）這里假設(shè)只有兩個(gè)用戶（為了方便，此處先不考慮隱私保護(hù)P1、P2，且記P1、P2選擇且量化的梯度向量為g1和g2，對(duì)應(yīng)的索引集為IND1和IND2。根據(jù)協(xié)議，INDS=IND1∪IND2。

對(duì)于索引ind來(lái)說(shuō)，?ind∈INDS，有以下3種情況：

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

3 實(shí)驗(yàn)和結(jié)果

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

本文使用預(yù)測(cè)準(zhǔn)確率、通信開銷大小以及單次訓(xùn)練所消耗的時(shí)間來(lái)評(píng)判協(xié)議的有效性。

3.1 模型的準(zhǔn)確率

為了證明協(xié)議的可用性，需要計(jì)算準(zhǔn)確率。若準(zhǔn)確率達(dá)到了明文條件下的水平或者沒(méi)有較大的下降，說(shuō)明提出的協(xié)議對(duì)訓(xùn)練模型的預(yù)測(cè)性能沒(méi)有太大影響。因?yàn)轵?yàn)證訓(xùn)練結(jié)果的過(guò)程對(duì)模型的準(zhǔn)確性并沒(méi)有影響，所以這一部分只考慮明文和πHEFL協(xié)議兩種情況。

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

表1 模型最終準(zhǔn)確率

3.2 通信開銷

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

表2 一次迭代訓(xùn)練中上傳和下載的通信開銷

從實(shí)驗(yàn)結(jié)果可以看出，采用STC稀疏三元壓縮法可以很好地解決通信開銷問(wèn)題。將STC選擇的選擇梯度的比率從10%到1%，通信性能有了明顯優(yōu)化，上傳的開銷相比于明文優(yōu)化了約50倍，而下載的開銷則優(yōu)化了約4.9倍。由第3.1章節(jié)和文獻(xiàn)[5]可知，STC稀疏三元壓縮選擇的比率不會(huì)對(duì)模型的性能造成太大影響，且相比于Top-K梯度選擇算法，STC在減小通信開銷的同時(shí)可以提高訓(xùn)練精度。此外，增加驗(yàn)證信息并沒(méi)有增加額外的通信開銷。可見(jiàn)，STC算法在聯(lián)邦學(xué)習(xí)領(lǐng)域擁有巨大的發(fā)展?jié)摿Α?/p>

3.3 時(shí)間開銷

在訓(xùn)練過(guò)程中，測(cè)量了協(xié)議πHEFL和各個(gè)階段的時(shí)間開銷。需要說(shuō)明，這里的PWH直接使用同態(tài)加密而沒(méi)有并行化處理。在協(xié)議的用戶端和服務(wù)器端中分別加入了處理驗(yàn)證碼的時(shí)間開銷。在STC下選擇梯度的比率為1%、5%和10%進(jìn)行實(shí)驗(yàn)，并與明文狀態(tài)和未使用并行化而直接使用同態(tài)加密的PWH方案進(jìn)行對(duì)比，結(jié)果如表3和表4所示。

表3 一次迭代訓(xùn)練中的訓(xùn)練和傳輸時(shí)間開銷

表4 一次迭代訓(xùn)練中的服務(wù)器端，預(yù)處理和總體的時(shí)間開銷

結(jié)果表明，和明文訓(xùn)練相比，加入的并行化同態(tài)加密安全協(xié)議在訓(xùn)練時(shí)引入了一定的時(shí)間開銷，但是和直接使用同態(tài)加密相比，引入的時(shí)間開銷小了很多。隨著梯度選擇的比率上升，同態(tài)加密算法所消耗的時(shí)間也在快速上升?？梢园l(fā)現(xiàn)，用戶端的計(jì)算時(shí)間、服務(wù)器端的計(jì)算時(shí)間以及明文的計(jì)算時(shí)間增加的幅度很小，且這種增幅在實(shí)際應(yīng)用中是可以接受的。除了同態(tài)加密所花費(fèi)的時(shí)間開銷以外，主要的時(shí)間開銷來(lái)自于傳輸梯度的時(shí)間開銷，這是目前限制安全聯(lián)邦學(xué)習(xí)應(yīng)用的主要原因。

4 結(jié)語(yǔ)

聯(lián)邦學(xué)習(xí)中隱私安全、時(shí)間開銷和通信開銷是其重要的瓶頸，而這些問(wèn)題在安全聯(lián)邦學(xué)習(xí)中的影響正在變得更加嚴(yán)重。本文使用STC稀疏三元壓縮算法和并行同態(tài)加密算法結(jié)合起來(lái)，一定程度上在時(shí)間開銷、通信開銷和隱私保護(hù)之間取得了平衡。此外，參考文獻(xiàn)[16]構(gòu)造了驗(yàn)證碼，但隨著系統(tǒng)的增大，安全聯(lián)邦學(xué)習(xí)效率低下依舊是重要的研究課題。未來(lái)的工作重點(diǎn)將著重研究進(jìn)一步提升安全聯(lián)邦學(xué)習(xí)的效率。