物聯網環境下魯棒的源匿名聯邦學習洗牌協議

陳景雪 高克寒 周爾強 秦 臻

（電子科技大學信息與軟件工程學院 成都 610054）

（網絡與數據安全四川省重點實驗室（電子科技大學） 成都 610054）

物聯網的研究工作是目前信息技術中的一個重要領域[1]，隨著物聯網（Internet of things,IoT）的快速發展，各種物聯網設備被用于各種不同的用途，如智能電網[2]、車聯網[3]等，為日常生活提供了便利.物聯網利用并進一步擴展了互聯網的優勢，如數據共享等，便于數據采集，實現更精準的管理.但由于來自物聯網設備的數據包含敏感信息，同時，由于協議的標準是公開的，物聯網系統正面臨越來越多的攻擊.尤其隨著人工智能[4]技術的發展，大量來自物聯網設備的原始數據被收集并集中到一個中心服務器進行訓練.因為這些來自物聯網設備的原始數據包含大量敏感信息[5]且物聯網終端用戶不信任中心服務器，導致很多物聯網終端用戶不愿意分享收集到的數據.因此，解決物聯網數據共享時的數據隱私問題十分重要[6].如何在充分保護數據和隱私安全的前提下，實現數據價值的轉化和釋放是一個重要的問題，即，需要在保證數據本身不被泄露的前提下，實現對數據價值的獲取，達到對數據“可用、不可見”的目的[7].

聯邦學習（federated learning,FL）是當前跨機構數據協同的主流技術，由谷歌公司最先提出[8].聯邦學習允許多個物聯網終端用戶，即參與者，與參數服務器合作來訓練模型.在訓練過程中，每個參與者在本地數據集上訓練自己的本地模型，只需要將相應的本地模型或梯度數據上傳到參數服務器.參數服務器接收到參與者發送的梯度后，可以聚合這些梯度以更新全局模型.由于本地原始數據不需要上傳到不受信任的參數服務器，聯邦學習已被廣泛應用于隱私敏感領域，如醫學圖像分析[9]、自動駕駛[10]和5G[11].

然而，聯邦學習仍面臨安全和隱私挑戰，主要包括推理攻擊和投毒攻擊.為了抵抗推理攻擊，聯邦學習需要在模型聚合的過程中保護參與者上傳的梯度數據或本地模型的隱私[12].最常見的方法是采用梯度安全聚合[13-14]，該類方案通過安全多方計算[15]（secure muti-part computation,SMC）或同態加密[16]（homophnic encryption,HE）等密碼學手段對梯度數據加密，并確保參數服務器在參與者的梯度數據聚合結束之前無法對單個參與者的梯度數據解密.但由于梯度數據為密文形式，導致參數服務器無法在聚合過程中區分惡意參與者的模型或梯度，因此無法檢測投毒攻擊[17]，這使得同時實現隱私保護和投毒攻擊檢測成為一個難題.

源匿名數據收集方法可以為聯邦學習中保護參與者模型隱私提供另一個方向.具體而言，源匿名數據收集[18]可以實現在參數服務器獲取每個參與者的原始模型的同時無法得知模型或梯度數據的具體來源，即，參數服務器無法得知原始的本地模型或梯度數據具體來自于哪一個參與者.這種方式通過切斷梯度數據與參與者的聯系來保護梯度數據的隱私性和原始性.由于可以收集到原始的梯度數據，參數服務器能夠使用目前流行的投毒攻擊檢測方案[19]來檢測梯度數據是否被毒化.

盡管如此，將源匿名數據收集方案應用于聯邦學習仍然存在一些問題.首先，由于在聯邦學習場景通常難以找到完全可信的服務器，所以基于可信機構的數據收集方案[18]難以應用于實際的聯邦學習場景.為解決中心依賴問題，Liu 等人[20]提出了不依賴可信機構的數據收集方案PPDC.該方案通過在卡槽位中加入可消除的掩碼保護數據的隱私性，在卡槽聚合后可以收集到原始數據.但該類方案通常難以解決參與者掉線的問題.原因在于當某個參與者掉線，那么所有參與者的位置將無法解密.另外，在聚合過程中，消去的掩碼是基于不同參與者之間交換的會話密鑰生成的.若在列表聚合階段參與者掉線，參數服務器將無法獲得所有的原始數據.

為解決上述問題，本文結合n-out-of-k不經意傳輸（oblivious transfer,OT）協議及Shamir 秘密分享（Shamir’s secrete sharing,SSS）協議等安全多方計算技術，提出了一種支持掉線恢復的源匿名聯邦學習洗牌協議Re-Shuffle.其中n-out-of-k不經意傳輸協議可以在沒有可信第三方的情況下實現原始本地模型上傳位置的隨機化生成，并保證生成的位置不能被其他任何實體獲取.秘密分享技術則在收集原始梯度數據的同時巧妙解決了用戶掉線的問題.本文的主要貢獻包括3 個方面:

1）本文提出了一個物聯網環境下魯棒的源匿名聯邦學習洗牌協議 Re-Shuffle，該方案在無需第三方可信機構的前提下同時實現了梯度數據收集的隱私性和原始性.因此可以同時實現隱私保護和投毒攻擊檢查.

2）本文方案構造了基于秘密分享的單掩碼協議，通過引入可恢復的掩碼，在實現高效的原始梯度數據收集的同時，解決了傳統洗牌協議中參與者掉線的問題，使其更適用于物聯網環境.

3）本文給出了該方案的安全性證明和在2 種投毒攻擊[19，21]下將本文方案與基線方案的準確性對比，評估了方案的計算開銷.結果表明，本文方案能夠在可接受的時間消耗下提供更高的安全性.

1 相關工作

1.1 隱私保護的聯邦學習

隱私保護的聯邦學習的重點在于保護訓練參與者的隱私，Bonawitz 等人[13]基于秘密共享的思想，提出了一種用于聯邦學習的安全聚合協議.具體地說，每個參與者通過執行Diffie-Hellman 密鑰交換協議與其他參與者生成成對密鑰，并且每個參與者基于該密鑰屏蔽其梯度數據.當參數服務器執行梯度聚合算法時，不同參與者的掩碼將相互抵消，從而服務器可以獲得原始梯度的聚合.Xu 等人[22]提出了一種基于雙屏蔽協議的可驗證聯邦學習系統.該系統可以驗證聚合結果的完整性，在確保參數服務器不會修改聚合值的同時保護參與者的梯度.Aono 等人[12]提出了一種基于HE 的安全聚合方案.在該方案中，每個參與者將加密的梯度上傳到參數服務器.然后，參數服務器可以在不解密的前提下聚合所有加密的梯度.Zhang 等人[23]利用掩碼、同態加密等密碼原語保護局部模型，防止攻擊者通過模型重構攻擊、模型反轉攻擊等各種攻擊手段推斷出隱私數據.最近，Liu等人[14]提出了一種隱私增強型聯邦學習（privacyenhanced federated learning,PEFL）.在該方案中，可消除掩碼被巧妙地添加到模型梯度中.PEFL 不僅可以保護梯度的隱私，還可以檢測投毒攻擊.然而，PEFL中沒有考慮非獨立同分布（non-independent identically distributed,Non-IID）數據集[24]，并且PEFL 中采用的HE 也帶來了沉重的計算負擔，這使其不適合實際的聯邦學習環境.Warnat-Herresthal 等人[25]引入了群體學習（swarm learning）的概念.他們將邊緣計算、基于區塊鏈的對等網絡和機器學習協調統一起來，形成一種去中心化的機器學習方法，能夠在不違反隱私法的情況下促進來自世界各地任何數據所有者的任何醫療數據的整合.Feng 等人[26]認為雖然聯邦學習可以通過大量設備之間的人工智能模型的協作學習來保護數據隱私，但是其效率低下且易受投毒攻擊.因此，提出了一種基于區塊鏈的異步聯邦學習（blockchain-based asynchronous federated learning,BAFL）框架，以保證聯邦學習所需的安全性和效率.其中區塊鏈確保模型數據不會被篡改，而異步學習則可以加快全局模型聚合.為了解決惡意客戶端或中心服務器對全局模型或用戶隱私數據的持續攻擊，Li 等人[27]提出了一種基于區塊鏈的分布式聯邦學習框架，使用區塊鏈進行全局模型存儲和局部模型更新交換.此外，還設計了一種創新性的委員會共識機制，可以有效地減少共識計算量和惡意攻擊，使所提的分布式聯邦學習框架成為可能.Geyer 等人[28]提出了一種客戶端級差分隱私算法，可以有效地保護全局模型.對于基于深度學習的方法，Yang 等人[29]提出了一個深度學習框架，該框架通過干擾目標模型分類器來降低對全局模型推理攻擊的準確性.

1.2 源匿名數據收集

匿名數據收集是云計算中常用隱私保護手段之一，允許在隱藏個人身份信息（personally identifiable information,PII）的情況下收集和分析數據.匿名數據收集的目標是通過刪除或隱藏任何可用于識別的PII 來保護個人隱私.Zhang 等人[18]提出基于可信機構（trusted authority,TA）的源匿名數據收集方案.該方案中TA 隨機混淆參與者的位置，并秘密告訴每個參與者其獲得的位置信息，隨后每個參與者根據所接受的位置向數據收集服務器傳遞數據.由于找到一個受到所有參與者信任的TA 是困難的，因此該方案在實際的應用場景中局限性較大.洗牌（shuffle）是數據匿名收集的另一種解決方案，該方案于1993 年基于公鑰加密的投票方案被提出[30]，在該方案中每個參與者的投票通過多層加密，保證每個參與者的投票信息不會透露給其他參與者.隨后一種基于參與者之間交互的洗牌協議被提出[31-32].每個參與者都可以根據自己隨機數的位置獲得位置而不需要TA，這使shuffle 具有良好的魯棒性.Liu 等人[20]在原始數據收集協議中應用了這種shuffle 方案.但是復雜的過程會讓shuffle 效率降低，特別是需要反復進行位置的洗牌.此外，當某個參與者掉線后，協議將無法繼續進行，需要重新執行整個協議.Zhao 等人[33]提出了一種隨機選擇數據匿名收集方案.該方案中每個參與者都選擇一個數據位置并用數據填充.然后，所有參與者都嘗試使用該位置上傳數據.如果沒有沖突，則每個參與者都獲取到自己選擇的位置；否則，有沖突的參與者重新選擇一個位置，并要求參與者再次進行沖突檢測，直到所有參與者都獲得一個位置.該方法不需要TA，具有良好的魯棒性.然而，該方案需要進行多次的聚合，并且還需要復雜的網絡結構用于參與者的通信，這導致了巨大的通信成本和計算成本.

2 預備知識

2.1 Shamir 秘密分享

Shamir 秘密共享[34]是一種常用的密碼學原語，它允許秘密所有者將1 個秘密s分成n份，并分給n個不同的實體.只有將不少于閾值份的秘密共享值組合在一起才可以用來恢復原始的秘密s.該方案由2種算法組成，分別是秘密分享算法S S.S hare(s,t,xi)→yi，以及秘密重構算法S S.Recon({x1,y1},…,{xi,yi}),i≥t.其中xi是公開數值，yi是對應的秘密分享值，t是閾值.

1）S S.S hare的算法

隨機選擇t個數a0,a1,…,at-1，在有限素數域下生成一個秘密分享多項式f(x)：

對給定的公開數值xi,秘密所有者計算對應的秘密分享值yi=f(xi)，并發送給對應的接收者.

2）S S.Recon的算法

對于t個秘密分享值y1,y2,…,yt,秘密分享多項式可以利用拉格朗日插值法進行重構：

因為s=f(0),因此秘密s可以表示為：

基于相同公開數值xi及閾值t生成的不同秘密分享多項式滿足加法同態性，給出一個加法同態的例子：

對于相同的秘密分享多項式及公開參數xi,i∈[1,t]，分別對秘密s0,s1生成對應的t個秘密分享值：

由式（1）可知：

由此得，

因此，s0+s1可以通過不小于t個秘密分享值之和yi+gi恢復出來，即秘密分享具有加法同態性.

2.2 不經意傳輸協議

n-out-of-k不經意傳輸常用于安全多方計算的場景中.在OT 協議中存在2 個實體：消息發送者S擁有一個秘密集合M={m1,m2,…,mn}，消息接收者R擁有一個選擇集合l={a1,a2,…,ak}.消息請求者根據自己的選擇集合向消息發送者S請求數據

本文采用了Lai 等人[35]提出的n-out-of-k不經意傳輸協議，SP為系統參數，R的選擇集合為l,|l|=k，私鑰為skr.S的秘密集合為M,|M|=n.具體的算法為：

1）令牌生成算法OT.Token(S P,skr,l)→{P(l),h}.其中P(l)為包含接收者選擇信息的令牌，h為選擇數的驗證信息.

2）信息加密算法OT.Enc(M,P(l),h,k)→{C0,C1,…,Cn}.其中M={C0,C1,…,Cn}為經過選擇令牌及驗證信息加密后的秘密列表.

3）信息解密算法OT.Dec({C0,C1,…,Cn},l,skr,SP)→Mr.

上述算法滿足安全需求：

1）發送者不能知曉接收者選擇了哪些秘密，即不能獲取l.

2）接收者能夠正確地獲取并解密自己的請求數據Mr.

3）接收者不能獲取請求列表數據以外的其他秘密，即不能獲取M-Mr.

3 系統實體及威脅模型

本節主要討論系統實體和威脅模型.符號定義見表1.

Table 1 Notations Definition表1 符號定義

3.1 系統實體

本文協議Re-Shuffle 共涉及3 類實體，即證書頒發機構CA、訓練參與者Pi,i∈[1,NP]及參數服務器PS.本文系統確保每個Pi的訓練模型都可以在沒有第三方可信機構的情況下匿名上傳到參數服務器.

1）證書頒發機構CA.CA負責生成初始化參數以保證公鑰的真實性，具體任務包括將公鑰與Pi綁定，并為實體頒發公鑰證書.

2）參與者Pi.每個參與者Pi會在本地進行模型訓練.為了保證隱私性，Pi在訓練結束后需要將她/他的本地模型生成加密列表并匿名發送到PS以進行后續的模型毒化攻擊檢測.在Re-Shuffle 中，Pi會與參數服務器PS以及其他參與者進行通信.

3）參數服務器PS.PS需要為每個參與者準備數據上傳位置，并通過與參與者之間的交互實現數據位置的隨機化分配.之后，在參與者匿名化的加密模型上上傳結束后，PS需要對模型解密以恢復參與者原始梯度數據.

3.2 威脅模型

PS被認為是誠實且好奇的，它遵守協議，不主動發起攻擊，但可能會試圖通過收到的信息，如參與者上傳的匿名模型列表、協議中間參數等來推斷參與者的模型位置.系統中的參與者被分為誠實參與者和惡意參與者.誠實參與者和惡意參與者都會遵守協議，但是惡意參與者會出于某種目的對本地梯度數據或本地模型投毒來降低全局模型的準確性.另外，惡意參與者可能與惡意參與者或參數服務器共謀以推測誠實參與者的上傳位置.威脅模型如圖1所示.

Fig.1 Threat model圖1 威脅模型

4 設計目標

本文的設計目標是提供一個隱私保護的聯邦學習安全聚合協議.該協議允許參與者匿名上傳加密的模型到參數服務器，為參與者的本地模型提供匿名化隱私保護.與此同時，由于參數服務器最終可以通過解密收集到原始梯度數據，所以在保證梯度數據匿名性的同時保證了梯度數據的原始性.因為可以收集到原始的梯度，進而可以對本地梯度數據進行毒化攻擊檢測，解決現階段難以同時實現隱私保護以及毒化攻擊檢測的問題.具體而言我們的目標有3 個.

1）原始性.PS能夠獲取到參與者的原始訓練梯度.相較于其他隱私保護聯邦學習協議，PS僅能獲取聚合模型或加密模型.Re-Shuffle 協議能夠保證PS獲取原始梯度數據，因此能夠輕易地被應用到現有的毒化攻擊檢測方案中，具有更好的可擴展性.

2）不可鏈接性（匿名性）.保證已上傳的模型無法與其數據源進行鏈接，即：系統中的任何實體都不能夠推測出參與者上傳的模型是哪一個，同時最終收集到的梯度也無法鏈接到具體參與者，這保證了參與者的隱私.

3）參與者掉線容錯.在訓練的任何階段，少量參與者的掉線不會影響到Re-Shuffle 協議的正常執行，這更適用于真實的物聯網環境，保證了協議的容錯性，增加了協議的魯棒性.

5 方案構造

為了實現第4 節中提到的目標，本文設計了一種支持掉線恢復的數據源匿名聯邦學習洗牌協議 Re-Shuffle.該協議在不引入第三方可信機構的前提下實現了參與者模型的隨機上傳.具體來說，Re-Shuffle 包括3 個部分：初始化、數據位置的生成以及數據匿名收集，每個實體之間的交互流程見圖2.

Fig.2 Protocol process of Re-Shuffle圖2 Re-Shuffle 協議流程

初始化階段的系統實體之間生成必要參數，包括密碼學相關參數以及聯邦學習初始模型等.數據位置生成階段會為Pi生成若干個可選擇的模型上傳位置.具體地，Pi之間通過隨機通信以確定互不沖突的位置請求參數.

隨后任意Pi都能根據其請求參數利用n-out-of-k不經意傳輸協議向PS請求互不沖突的數據上傳位置.OT 保證Pi能夠在PS無法得知其請求的前提下獲取互不沖突的數據到相應上傳位置，防止惡意參與者與參數服務器之間的合謀攻擊造成的隱私泄露，進一步保護參與者隱私.在數據匿名收集階段，Pi生成一個上傳列表，將訓練模型插入獲取的數據上傳到相應位置中.隨后通過隨機掩碼對整個上傳列表加密，并將隨機掩碼的秘密分享份額發送給在線參與者.當參數服務器將所有參與者上傳列表聚合后，通過不小于t個在線參與者的秘密分享份額之和減去聚合列表中的掩碼之和，從而計算得到原始梯度列表.由于在執行上傳列表聚合之前參數服務器無法消去列表掩碼，而當列表聚合之后參數服務器無法獲取每個參與者模型的位置信息，因此Re-Shuffle 實現了模型的匿名化上傳.Re-Shuffle 的具體方案為：

1）初始化階段.本階段生成密碼學相關的必要參數，以及聯邦學習訓練所需的模型參數和超參數.PS初始化全局模型和學習率 α.PS將和 α發送給所有參與者.此外，PS發布param={G,g,h,p,a}作為系統參數，其中g,h∈G；p,a∈.參與者Pi,i∈[1,NP]，生成自己的私鑰ski=xi,xi∈,公鑰pki=.Pi將pki發送給其他所有參與者Pj.PS隨機生成k·NP個數據位置s1,s2,…,，其中k為每個參與者可選擇的位置個數，并生成自己的私鑰skp∈,公鑰pkp=gskp.PS將pkp發送給每個參與者.

2）數據位置生成階段.為降低計算開銷，采用Lai 等人[35]的高效OT 協議，具體流程為：

①第1 輪（請求參數選擇）：

PS：

ⅰ）可以參與本輪工作的參與者通知參數服務器,參數服務器將本輪參與者列表U1發送給所有的參與者Pi,i∈U1.

ⅱ）隨機選擇一個參與者Pi,i∈U1作為初始發送方，然后將位置數量k·NP發送給Pi.本輪NP=|U1|.

Pj：

ⅰ）接受到來自其他參與者的密文.如果已經進行過參數選擇，則通知發送方重新選擇.

ⅱ）如果第一次進行參數選擇，使用自己的私鑰解密獲得選擇列表Lch-Li，并選擇請求參數Lj={l1,l2,…,lD},D∈[1,k].

ⅲ）在本地，對時間戳的生命周期減1：Timestep=Timestep/(gb)uj.

ⅳ）判斷Timestep是否等于1.如果不相等，則執行初始參與者Pi相同的操作；如果相等，則通知所有參與者進行位置選擇.

經過請求參數選擇后，每個參與者都可以得到互不沖突的1～k個請求參數，為了便于理解，圖3 給出了請求參數選擇的一個例子，其中，k=3,Np=4.

Fig.3 Parameter selection圖3 參數選擇

②第2 輪（位置選擇）：

Pi收到開始信號后，每個參與者利用令牌生成算法計算選擇令牌及驗證信息{Toki,hi}←OT.Token(param,ski,Li)，其具體計算過程見公式：

圖4 給出了數據位置獲取的一個例子.

Fig.4 Data location generation圖4 數據位置生成

3）數據匿名收集階段.本階段Pi向PS發送模型上傳列表.PS聚合所有接收的上傳列表，通過秘密分享協議恢復參與者的原始模型，并得到一個無序的參與者訓練模型列表.整個階段中參與者掉線人數不超過|U1|-t則不會影響模型的上傳，否則需要重新執行數據位置生成.本階段的協議描述為：

①第1 輪（秘密分享）

如果LG中存在的非空位數等于|U2|，則對列表中所有原始梯度或生成的本地模型進行投毒攻擊檢測，并聚合生成全局模型，否則終止協議.關于投毒攻擊防御的部分，我們在第7 節擴展.

6 安全分析

本節分析了Re-Shuffle 協議在第3 節所假設的威脅模型下的安全性.具體而言，所有的實體都誠實地執行協議，但是服務器可以獲取協議執行過程中全部接收到的中間數據，并推測收集階段每個模型所屬的參與者.此外，允許t-1個惡意參與者共謀，以推測誠實參與者的上傳模型.我們證明在存在攻擊者的前提下，Re-Shuffle 協議可以保證誠實參與者上傳模型的原始性、匿名性以及允許參與者掉線的魯棒性.

6.1 原始性

本節給出協議的正確性證明，以及主要驗證Re-Shuffle 能夠在數據匿名列表恢復階段聚合得到原始的參與者模型參數.

由Re-Shuffle 描述可知，每個參與者Pi模型列表的上傳位置為si，其具體匿名列表為：

其中，第si個位置為自己的本輪訓練模型，其余位置填充的構造數據為:

由于每個參與者Pi將自己的掩碼ri的秘密分享值yi,j發送給在線的其他參與者Pj,j∈|U2|，因此ri可以通過秘密分享恢復算法計算：

其中，Ut?U2,|Ut|=t.然而，由于需要保證列表聚合之前PS不能直接通過秘密分享獲取掩碼ri的值，因此U2中的參與者在本地執行秘密分享值的聚合，Pj可以計算聚合值為：

隨后在匿名列表恢復階段PS執行列表聚合后sn位置對應的匿名列表表項為：

因此對第n個匿名列表表項可以消去掩碼，得到原始模型梯度：

假設第n個表項沒有參與者選擇，那么消去掩碼后，該位置參數值為空：

綜上所述，我們的方案可以保證最后PS能夠成功計算匿名列表聚合后每個參與者的梯度信息，且無參與者選擇位置的聚合結果為空.

6.2 不可鏈接性（匿名性）

本文采用了與Bonawitz 等人[13]相同的標準混合論證來證明Re-Shuffle 的安全性，實體的視圖由內部狀態的參數和從其他實體接收到的所有消息組成.為便于表述，我們首先給出所使用的符號描述，給定U4?U3?U2?U1?U表示在每一輪中參與者在線集合，其中U為初始參與者集合（|U|=NP）.我們用U2U3表示為第2 輪中在線的參與者而第3 輪中掉線的參與者集合,用Wi表示參與者Pi的模型i∈U，WU′={Wi}i∈U′表示參與者集合U′包含的模型集合.為便于表示，我們規定每個實體的輸入數據、接收數據以及其在協議運行過程所觀察到的所有數據作為該實體的視圖.給定對手集合C?P′∪{PS},其中P′表示惡意參與者的集合（|P′|＜t）(WU,U1,U2,U3,U4)表示在實際執行Re-Shuffle 過程中C中實體的聯合視圖.其中k表示由PS初始化的安全參數，t表示秘密分享要求的閾值.基于符號定義，給出定理1.

證明.我們采用了標準混合論據[31-32]來證明該定理.S IM將對進行一系列的修改.修改的內容為Re-Shuffle 執行期間的數據和參數.如果S IM的輸出與難以區分，則說明敵手不能獲取關于參與者的任何信息，即Re-Shuffle 可以保護參與者的模型匿名性.我們以Hybi,i∈[1,7]，表示每一輪交互過程中S IM對系統參數的一次修改.

1）Hyb1.在這個混合模式中，S IM生成隨機列表Lch={b1,b2,…,bi},i∈[1,NP]替換所有誠實用戶Pi∈U1C的選擇列表Lch.其中，任意選擇b＜NP，且兩兩不相等.隨后，模擬器將Lch及Timestep發送至Pi.由于每個參與者對列表Lch的選擇是隨機的，因此Hyb1與是不可區分的.

2）Hyb2.在這個混合模式中，SIM生成隨機數θ i∈，以替換所有誠實參與者Pi∈U1C的私鑰ski.S IM計算令牌及驗證信息為：

由OT 安全性假設可知，敵手無法恢復參與者的密鑰θ i，此外，敵手執行令牌驗證仍可以得到：

與Hyb2類似，由于參與者選擇列表隨機生成，根據OT 安全假設[36]，敵手無法獲取參與者的選擇列表.此外敵手執行令牌驗證可得到：

由于參與者的分配位置對PS是不可見的，并且梯度在掩碼加密下是不可區分的，因此Hyb5與是不可區分的.

6）Hyb6.在這種混合模式中，S IM使用隨機數替換所有誠實參與者Pi∈U2C關于掩碼ri的所有秘密分享yi,j.顯然，單個敵手無法獲取ri的原始值.當|U3|＜t,由Shamir 秘密分享的安全性[28]可知，敵手無法恢復ri；當|U3|≥t，且|U3C|-|U3|＜t時，根據誠實參與者與敵手之間的非共謀設置，以及Shamir 秘密分享的安全性可知敵手無法獲取ri的原始值.因此Hyb6與是不可區分的.

7）Hyb7.在這種混合模式中，S IM使用隨機數替換所有誠實參與者Pi∈U3C關于秘密分享聚合，同理于Hyb6根據誠實參與者與敵手之間的非共謀設置以及Shamir 秘密分享的安全性可知，Hyb7與是不可區分的.證畢.

綜上所述，可以采樣出一個模擬器S IM，并且S IM的輸出與實際視圖的輸出是不可區分的.因此，在誠實參與者的上傳列表參與聚合消除掩碼之前，敵手無法獲取關于參與者上傳模型列表的任何信息，包括真實的模型數據位置以及模型參數.當聚合結束后，敵手可以獲取聚合列表，匯總所有參與者的原始模型，但是無法獲取每個參與者模型在列表中的位置.即 Re-Shuffle 可以保護模型匿名性.

6.3 魯棒性（容錯性）

定理2：在Re-Shuffle 中，如果存在系統的參與者掉線的情況，無需進行數據上傳位置的重新選擇，且當參與者在線數量 |U|高于閾值t時，該輪次的匿名模型列表恢復階段可以正常執行.

證明.我們將對Re-Shuffle 協議中每一輪可能的參與者掉線情況作分析，并給出的執行情況，以證明其對用戶掉線的魯棒性.

1）數據位置生成階段（第2 輪）.在此階段，在線參與者集合為U1.當|U1|≥t時，參與者可以與PS交互，并利用OT 協議獲取若干模型上傳位置.當參與者掉線時，由于OT 協議執行過程無需與其他參與者交互，剩余參與者向PS請求自己的數據上傳位置.因此，該過程參與者掉線不會影響協議的正常執行.

2）匿名模型收集階段（第1 輪）.在此階段，在線參與者集合為U2.當|U2|≥t時,每個參與者Pi,i∈|U2|上傳自己的匿名模型列表LWi，并將加密的掩碼ri的秘密分享值的密文ci,j,j∈U2上傳至PS.PS將所有參與者上傳的加密掩碼分享發送給對應且仍然在線的參與者Pj,j∈{U3U2}.由于參與者的匿名模型列表及其加密后的掩碼秘密分享在本輪一并發送至PS，如果本輪參與者掉線，則該參與者的匿名模型列表不會上傳.因此無需在第2 輪恢復列表掩碼.綜上，該過程參與者掉線不會影響協議的正常執行.

3）匿名數據收集階段（第2 輪）.在此階段，在線參與者集合為U3.當|U3|≥t時,每個參與者Pj,j∈|U3|會根據上一輪在線參與者集合U2聚合所有接受的秘密分享并上傳該聚合分享值至PS.當參與者掉線時，由Shamir 秘密分享的同態性可知，PS可以通過不小于t個聚合值,j∈U3計算上一輪中掩碼的聚合值.因此該過程參與者掉線不會影響協議的正常執行.綜上，當參與者在線數量 |U3|高于t時，Re-Shuffle 的執行不會受參與者掉線影響.證畢.

6.4 抗合謀攻擊

定理3：在Re-Shuffle 中，除了參與者Pi外，只要有1 個誠實參與者Pj，即使參數服務器與其他參與者合謀也無法獲取參與者Pi的梯度數據的位置.

證明.在Re-Shuffle 中，每個參與者Pi可以選擇k個位置，參與者Pj也可以選擇k個位置.隨后，在使用了n-out-of-k不經意傳輸協議后，所有的位置被隨機化.在這種情況下，即使參數服務器與除Pj外的其他參與者合謀也無法推斷出Pi的具體位置.一般情況下，我們考慮超過一半的參與者為誠實參與者，在這種假設下，即使參數服務器與其他少數惡意參與者一起合謀也無法得到Pi的梯度數據的具體位置. 證畢.

7 性能評估

本節從功能性、毒化攻擊檢測，以及計算開銷3個方面對Re-Shuffle 進行了分析，并與相關隱私保護方案進行了對比：隱私保護數據收集（privacypreserving data collection,PPDC）[20]、隱私保護深度學習（privacy-preserving deep learning,PPDL）[25]、隱私保護機器學習（privacy-preserving machine learning,PPML）[13]以及高效隱私保護聯邦深度學習（efficient and privacypreserving federated deep learning，EPFDL）[36].

7.1 功能對比

本節對Re-Shuffle 方案以及前述方案進行功能性對比.其中，分別從梯度隱私性、毒化防御可擴展性、抗共謀、隱私保護方法以及參與者掉線可恢復性這5 個方面進行了對比分析.對比的結果見表2.

Table 2 Comparison of Existing Work表2 現有工作對比

1）梯度隱私.對比方案都可以對上傳梯度進行一定程度上的隱私保護.PPDC 與Re-Shuffle 類似，都是通過源匿名的方式進行梯度隱私保護.兩者的區別在于，Re-Shuffle 通過不經意傳輸協議以及秘密分享協議，而PPDC 利用分層加密實現數據源的混淆.PPDL 利用同態加密實現參與者梯度的安全聚合，雖然通過本地多次更新的方式減少了加密的開銷，然而在需要大規模訓練模型的場景下仍然會產生較高的計算開銷.PPML 是基于秘密分享的雙掩碼協議，該方案通過引入在聚合過程中可消除的掩碼，以實現參與者梯度的隱私保護.EPFDL 基于同態加密以及差分隱私技術實現了參與者梯度的隱私保護，但是需要在協議的安全性及全局模型性能方面作權衡.

2）投毒攻擊可擴展性.現階段的毒化攻擊檢測方案通常基于模型評估、準確度審計以及梯度統計數據分析3 種方式，且都需要參與者的原始梯度或原始模型.而PPDL、PPML 及EPFDL 采用的隱私保護方法破壞了參與者梯度數據的原始性，因此難以支持毒化攻擊檢測.PPDC 與Re-Shuffle 通過匿名化原始梯度數據保證了梯度的原始性，可以在隱私保護的基礎上支持毒化攻擊檢測.

3）抗共謀性.PPML 通過門限方案抵抗共謀攻擊.EPFDL 使用基于拉普拉斯機制的差分隱私技術來擾亂用戶的原始本地梯度，從而防止云服務器和多個參與者之間的合謀.在PPDC 中，參與者之間對上傳模型位置信息進行逐層解密并洗牌.因此只要存在1 個以上的誠實參與者即可保證上傳模型的匿名性，且惡意參與者與服務器之間無法通過共謀攻擊推測參與者的梯度.Re-Shuffle 通過不經意傳輸機制隨機保證參與者僅能獲取自己的上傳位置，且參數服務器無法獲取參與者選擇的信息.在PPDL 中，所有的參與者在聚合過程中采用同態加密方式以實現參與者隱私保護，由于所有的參與者使用相同的私鑰對模型加密，因此一旦攻擊者與任意參與者共謀，誠實參與者的梯度就會暴露.

4）掉線魯棒性.PPML 與Re-Shuffle 在模型上傳至服務器的過程中，每個參與者為模型添加可消除的掩碼.當不超過閾值數量的參與者掉線后，可以通過秘密分享恢復掉線參與者對應的模型掩碼，保證了協議對參與者掉線的穩定性.PPDL 與EPFDL 在聚合階段通過同態加密保證模型的隱私.因此參與者掉線不會影響全局模型的聚合結果，但會產生更高的開銷.在PPDC 中，在模型上傳階段每個參與者會上傳原始模型的列表，且該參與者的模型只占據列表的一個固定位置.當某參與者掉線后，對應位置的參與者模型缺失從而導致位置信息暴露給參數服務器.

7.2 投毒攻擊防御擴展

我們在Intel i5 2.3 GHz，CPU 內存8.00 GB 的計算機上對Re-Shuffle 進行了實驗仿真,計算機平臺為ubuntu18.0.4.為方便比較，本節采用了MNIST[37]數據集以及3 層卷積神經網絡模型，設置學習率 α=0.05，訓練輪數T=1000.我們在Re-Shuffle 協議的基礎上拓展使用了2 種毒化攻擊檢測方案BTGD[19]和BRDL[21]，并通過仿真實驗測試Re-Shuffle 與基線算法在惡意參與者設置下的模型準確度.毒化攻擊設置為：將MNIST 數據集進行標簽翻轉處理.20%參與者作為惡意參與者在本地訓練翻轉后的毒化數據集，80%參與者持有正常MNIST 數據集.本文采用沒有毒化攻擊檢測的聯邦學習方法作為基線方法，使用的算法為FedAvg[8].

首先，我們給出了Re-Shuffle 與基線方法在沒有參與者進行毒化攻擊下的模型在測試集合上的準確率，如圖5 所示.由實驗可知，Re-Shuffle 在模型收斂性上與基線方法基本一致，即Re-Shuffle 在誠實參與者設置下能夠得到較好的訓練結果.

Fig.5 Global model accuracy with honest participants setting圖5 誠實參與者設置下的全局模型準確率

隨后，我們給出了20%的參與者進行毒化攻擊下的模型在測試集上的準確率的對比，如圖6 所示.由實驗結果可知，Re-Shuffle 能夠有效支持毒化攻擊檢測方案的拓展，其檢出效果依賴于其使用的檢測方案.綜上，Re-Shuffle 能夠在保證模型匿名性的前提下支持現有的毒化攻擊檢測方案.

Fig.6 Global model accuracy with 20% malicious participants setting圖6 20%惡意參與者設置下的全局模型準確率

7.3 計算開銷

本節給出了Re-Shuffle 的計算開銷，并將其與7.1 節中給出的相關工作進行比較，此外我們對部分工作進行了實驗仿真，評估了Re-Shuffle 在實際環境下的運行時間.

首先在數據位置生成階段中，第1 輪中，每個參與者之間進行一輪的交互以獲取自己的請求列表，該過程采用與PPDC[20]中相同的加解密方式.第2 輪中，每個參與者根據請求列表與參數服務器進行2輪交互，獲取數據上傳位置，該過程采用OT 協議、Token 及驗證信息h的生成過程計算復雜度隨后服務器返回位置列表的密文，計算復雜度為

本文給出的對比方案的計算開銷見表3.由表3可知，Re-Shuffle 的計算開銷在對比方案中相對較高.盡管如此，Re-Shuffle 采用模型掩碼的方式替代加密整個模型，相較于PPDL 及EPFDL 的實際計算耗時更小；Re-Shuffle 對于掉線用戶的支持度較高，且計算復雜度隨掉線用戶數量的增加而下降.因此在產生大量用戶掉線的場景下，Re-Shuffle 的實際運行時間會低于不支持用戶掉線方案PPDC.Re-Shuffle 以及PPML 均是采用Shamir 秘密分享的方式為參與者模型添加掩碼，因此計算復雜度相同.但是相較于PPML 采用雙掩碼，Re-Shuffle 在掩碼添加的過程中利用秘密分享的同態性，避免了第2 個掩碼的秘密分享計算消耗，因此實際耗時相對更短.

Table 3 Comparison of Computation Cost表3 計算開銷對比

在密碼學方面，我們采用了Lai 等人[35]提出的nout-of-k不經意傳輸協議實現了Re-Shuffle 的模型位置生成并利用Shamir 秘密分享協議實現了Re-Shuffle的模型上傳.具體采用Python 庫Charm-crypto[38]實現了上述協議，其中加解密的參數采用橢圓曲線SS1024[39]，達到了112 b 的安全等級.在參與者及服務器方面，設置參與者數量Np∈[0,500]，掉線參與者數量Ndrop=100，參數服務器數量設置為1.設置Shamir 秘密分享閾值t=300.

我們分析了基線方案FedAvg、Re-Shuffle 以及其他對比方案之間在存在參與者掉線及參與者不掉線情況下參數服務器及每個參與者的計算時間開銷.其中圖7 為不掉線情況下服務器計算開銷對比，圖8為不掉線情況下參與者計算時間開銷對比，圖9 為參與者掉線20%情況下服務器計算時間開銷對比，圖10 為參與者掉線20%情況下服務器計算時間開銷對比.

Fig.7 Comparison of server computing time cost when no participant is offline圖7 參與者不掉線情況下服務器計算時間開銷對比

Fig.8 Comparison of participant computing time cost when no participant is offline圖8 不掉線情況下參與者計算時間開銷對比

Fig.9 Comparison of server computing time cost when 20%participants are offline圖9 參與者掉線20%情況下服務器計算時間開銷對比

Fig.10 Comparison of participant computing time cost when 20% participants are offline圖10 參與者掉線20%情況下參與者計算時間開銷對比

由實驗可知，在參與者不掉線時FedAvg 的時間消耗最低，且時間消耗隨參與者數量呈線性增長.Re-Shuffle 的服務器時間消耗高于PPDC，而參與者時間消耗要更低.這是由于PPDC 的計算復雜度較低，在列表聚合階段并未采用秘密分享來對掉線參與者的掩碼進行恢復，而直接聚合模型列表的復雜度較低.但是在本地執行匿名列表生成階段的時間消耗主要來自于哈希函數的計算以及對模型參數的異或運算，由于Re-Shuffle 直接采用模型掩碼，因此參與者的時間開銷更小.相較于PPML,Re-Shuffle 效率更高，原因在于Re-Shuffle 在構建秘密分享協議時采用了單掩碼，因此在秘密恢復階段的時間開銷要小于基于雙掩碼的PPML.EPFDL 與PPDL 在常規情況下的參與者計算開銷最高，原因在于同態加密會產生大量的時間消耗，但是服務器的運行時間基本不受影響，而Re-Shuffle 由于不需要對模型進行編碼以及同態加密，其時間消耗更低.

當存在參與者掉線時，PPDC 中通過參與者密鑰加密的列表位置不能進行解密，剩余參與者之間需要重新商議并加密生成位置列表，且在再次執行的過程中同樣無法避免參與者的掉線.由于難以計算參與者掉線時PPDC 的計算開銷，我們在參與者掉線的實驗仿真中對其不予考慮.圖9 和圖10 分別給出了參與者掉線20%情況下服務器和參與者的計算時間開銷.

當參與者掉線情況產生時，FedAvg 的服務器運行時間基本不變.而PPML 相較于沒有掉線參與者情況服務器的時間開銷上升，原因在于秘密恢復階段參數服務器需要重新對掉線參與者的第一掩碼執行秘密恢復.但是參與者掉線不會對其他在線參與者執行時間產生影響.EPFDL 與PPDL 由于實際參與者數量的下降，服務器的時間消耗反而因此下降.Re-Shuffle 在實際的執行過程中，由于參與者無論是否掉線，參數服務器均需要對其唯一掩碼執行秘密恢復算法，從而恢復秘密列表.因此，Re-Shuffle 在參與者掉線情況下參與者的實際執行時間基本不受影響.而參與者本地的執行時間同樣受掉線參與者的影響，且與總參與者的數量線性相關.

綜上所述，Re-Shuffle 能夠在可接受的時間開銷范圍內完成參與者匿名列表上傳，此外，當存在參與者掉線時，Re-Shuffle 能夠保證系統的正常執行，且執行的時間開銷基本不受影響.故相較于對比方案，Re-Shuffle 能夠提供更高的協議執行效率，且更適用于可能出現的大量用戶掉線的聯邦學習大量情景.

8 總結與展望

本文提出了一種物聯網環境下新的支持掉線恢復的聯邦學習洗牌協議Re-Shuffle.由于物聯網終端用戶即參與者對數據分享的安全和隱私需求，該協議分別通過n-out-of-k不經意傳輸協議及Shamir 秘密分享協議實現了隨機的模型位置生成以及匿名的原始模型上傳與原始梯度收集.與最近的隱私保護聯邦學習工作相比，Re-Shuffle 可以在上傳原始模型的前提下保護參與者的隱私，因此可以支持目前的大部分毒化攻擊檢測方案.此外，Re-Shuffle 保證少量參與者的掉線不會影響其正常執行，其更適合真實的物聯網環境.我們在分析部分給出了詳細的安全性證明，并在 MNIST 數據集中對比驗證了Re-Shuffle以及其他隱私保護方案的開銷.結果表明，Re-Shuffle能夠在可接受的計算及開銷下保護參與者的隱私.未來會對如何提高方案效率以及毒化攻擊檢測性能作進一步研究.

作者貢獻聲明：陳景雪提出算法思路和實驗方案；高克寒負責完成實驗并撰寫論文；周爾強、秦臻協助高克寒完成實驗并修改論文.