物联网环境下鲁棒的源匿名联邦学习洗牌协议

陈景雪 高克寒 周尔强 秦 臻

（电子科技大学信息与软件工程学院 成都 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能够在可接受的计算及开销下保护参与者的隐私.未来会对如何提高方案效率以及毒化攻击检测性能作进一步研究.

作者贡献声明：陈景雪提出算法思路和实验方案；高克寒负责完成实验并撰写论文；周尔强、秦臻协助高克寒完成实验并修改论文.