物联网的研究工作是目前信息技术中的一个重要领域^[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]提出了一种隐私增强型联邦学习（privacy-enhanced 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种算法组成，分别是秘密分享算法${{{{SS}}.Share}}(s,t,{x_i}) \to {y_i}$，以及秘密重构算法${{ SS.Recon}}(\{ {x_1},{y_1}\} ,…,\{ {x_i},{y_i}\} ),i \geqslant t$. 其中${x_i}$是公开数值，${y_i}$是对应的秘密分享值，$t$是阈值.

1） ${{SS.Share}}$的算法

随机选择$t$个数${a_0},{a_1},…,{a_{t - 1}}$，在有限素数域下生成一个秘密分享多项式$f(x)$：

对给定的公开数值${x_i}$, 秘密所有者计算对应的秘密分享值${y_i} = f({x_i})$，并发送给对应的接收者.

2） ${{SS.Recon}}$的算法

对于$t$个秘密分享值${y_1},{y_2}, … ,{y_t}$, 秘密分享多项式可以利用拉格朗日插值法进行重构：

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

基于相同公开数值${x_i}$及阈值$t$生成的不同秘密分享多项式满足加法同态性，给出一个加法同态的例子：

对于相同的秘密分享多项式及公开参数${x_i},i \in [{1},t]$，分别对秘密${s_0},{s_1}$生成对应的$t$个秘密分享值：

由式（1）可知：

由此得，

因此，${s_0} + {s_1}$可以通过不小于$t$个秘密分享值之和${y_i} + {g_i}$恢复出来，即秘密分享具有加法同态性.

2.2   不经意传输协议

n-out-of-k不经意传输常用于安全多方计算的场景中. 在OT协议中存在2个实体：消息发送者$S$拥有一个秘密集合$M = \{ {m_1},{m_2},…,{m_n}\}$，消息接收者$R$拥有一个选择集合$l = \{ {a_1},{a_2},…,{a_k}\}$. 消息请求者根据自己的选择集合向消息发送者S请求数据${M_{\rm{r}}} = \{ {m_{{a_1}}},{m_{{a_2}}},…,{m_{{a_k}}}\}$.

本文采用了Lai等人^[35]提出的n-out-of-k 不经意传输协议，$S P$为系统参数，$R$的选择集合为$l,|\;l\;| = k$，私钥为$s{k_{\rm{r}}}$. $S$的秘密集合为$M,|M| = n$. 具体的算法为：

1） 令牌生成算法${{ OT.Token}}(SP,s{k_{\rm{r}}},l) \to \{ P(l),h\}$. 其中$P(l)$为包含接收者选择信息的令牌，$h$为选择数的验证信息.

2） 信息加密算法${{ OT.Enc}}(M,P(l),h,k) \to \{ {{{C}}_0},{{{C}}_1},…, {{{C}}_n}\}$. 其中$M$=$\{ {C_0},{C_1},…,{C_n}\}$为经过选择令牌及验证信息加密后的秘密列表.

3） 信息解密算法${{OT.Dec}}(\{ {{C}_0}, {{C}_1}, …, {{C}_n}\} , l, s{k_{\rm{r}}}, S P) \to {M_{\rm{r}}}$.

上述算法满足安全需求：

1）发送者不能知晓接收者选择了哪些秘密，即不能获取$l$.

2）接收者能够正确地获取并解密自己的请求数据${M_{\rm{r}}}$.

3）接收者不能获取请求列表数据以外的其他秘密，即不能获取$M - {M_{\rm{r}}}$.

3.   系统实体及威胁模型

本节主要讨论系统实体和威胁模型. 符号定义见表1.

表  1  符号定义

Table  1.  Notations Definition

符号	定义
$PS$	参数服务器
$CA$	证书认证机构
${P_i}$	第$i$个参与者
$U$	在线参与者列表
${N_P}$	参与者的数量
${N_{{\rm{drop}}} }$	掉线参与者数量
$W_i^T$	参与者Pi在T轮的本地训练模型
$W_{\rm{g}}^T$	在T轮的全局模型
$G_i^T$	参与者Pi在T轮的梯度数据
$\text{α}$	学习率
$k$	用户可选位置个数
$s$	模型位置
${L_W}$	模型列表
$L$	请求列表
$t$	秘密分享阈值
${r_i}$	参与者${P_i}$的模型掩码
${y_{i,j}}$	${P_i}$发送给${P_j}$的${r_i}$秘密分享份额
$(p{k_{\rm{p}}},s{k_{\rm{p}}})$	参数服务器的公私钥
$(p{k_{{i} } },s{k_{i } })$	参与者${P_i}$的公私钥

下载: 导出CSV 

| 显示表格

3.1   系统实体

本文协议Re-Shuffle共涉及3类实体，即证书颁发机构$CA$、训练参与者${P_i},i \in [1,{N_P}]$及参数服务器$PS$. 本文系统确保每个${P_i}$的训练模型都可以在没有第三方可信机构的情况下匿名上传到参数服务器.

1） 证书颁发机构$CA$.$CA$负责生成初始化参数以保证公钥的真实性，具体任务包括将公钥与${P_i}$绑定，并为实体颁发公钥证书.

2） 参与者${P_i}$. 每个参与者${P_i}$会在本地进行模型训练. 为了保证隐私性，${P_i}$在训练结束后需要将她/他的本地模型生成加密列表并匿名发送到$PS$以进行后续的模型毒化攻击检测. 在Re-Shuffle中，${P_i}$会与参数服务器$PS$以及其他参与者进行通信.

3） 参数服务器$PS$.$PS$需要为每个参与者准备数据上传位置，并通过与参与者之间的交互实现数据位置的随机化分配. 之后，在参与者匿名化的加密模型上上传结束后，$PS$需要对模型解密以恢复参与者原始梯度数据.

3.2   威胁模型

$PS$被认为是诚实且好奇的，它遵守协议，不主动发起攻击，但可能会试图通过收到的信息，如参与者上传的匿名模型列表、协议中间参数等来推断参与者的模型位置. 系统中的参与者被分为诚实参与者和恶意参与者. 诚实参与者和恶意参与者都会遵守协议，但是恶意参与者会出于某种目的对本地梯度数据或本地模型投毒来降低全局模型的准确性. 另外，恶意参与者可能与恶意参与者或参数服务器共谋以推测诚实参与者的上传位置. 威胁模型如图1所示.

图  1  威胁模型

Figure  1.  Threat model

下载: 全尺寸图片 幻灯片

4.   设计目标

本文的设计目标是提供一个隐私保护的联邦学习安全聚合协议. 该协议允许参与者匿名上传加密的模型到参数服务器，为参与者的本地模型提供匿名化隐私保护. 与此同时，由于参数服务器最终可以通过解密收集到原始梯度数据，所以在保证梯度数据匿名性的同时保证了梯度数据的原始性. 因为可以收集到原始的梯度，进而可以对本地梯度数据进行毒化攻击检测，解决现阶段难以同时实现隐私保护以及毒化攻击检测的问题. 具体而言我们的目标有3个.

1）原始性. $PS$能够获取到参与者的原始训练梯度. 相较于其他隐私保护联邦学习协议，$PS$仅能获取聚合模型或加密模型. Re-Shuffle协议能够保证$PS$获取原始梯度数据，因此能够轻易地被应用到现有的毒化攻击检测方案中，具有更好的可扩展性.

2）不可链接性（匿名性）. 保证已上传的模型无法与其数据源进行链接，即：系统中的任何实体都不能够推测出参与者上传的模型是哪一个，同时最终收集到的梯度也无法链接到具体参与者，这保证了参与者的隐私.

3）参与者掉线容错. 在训练的任何阶段，少量参与者的掉线不会影响到Re-Shuffle协议的正常执行，这更适用于真实的物联网环境，保证了协议的容错性，增加了协议的鲁棒性.

5.   方案构造

为了实现第4节中提到的目标，本文设计了一种支持掉线恢复的数据源匿名联邦学习洗牌协议 Re-Shuffle. 该协议在不引入第三方可信机构的前提下实现了参与者模型的随机上传. 具体来说，Re-Shuffle包括3个部分：初始化、数据位置的生成以及数据匿名收集，每个实体之间的交互流程见图2.

图  2  Re-Shuffle协议流程

Figure  2.  Protocol process of Re-Shuffle

下载: 全尺寸图片 幻灯片

初始化阶段的系统实体之间生成必要参数，包括密码学相关参数以及联邦学习初始模型等. 数据位置生成阶段会为${P_i}$生成若干个可选择的模型上传位置. 具体地，${P_i}$之间通过随机通信以确定互不冲突的位置请求参数.

随后任意${P_i}$都能根据其请求参数利用n-out-of-k 不经意传输协议向$PS$请求互不冲突的数据上传位置. OT保证${P_i}$能够在$PS$无法得知其请求的前提下获取互不冲突的数据到相应上传位置，防止恶意参与者与参数服务器之间的合谋攻击造成的隐私泄露，进一步保护参与者隐私. 在数据匿名收集阶段，${P_i}$生成一个上传列表，将训练模型插入获取的数据上传到相应位置中. 随后通过随机掩码对整个上传列表加密，并将随机掩码的秘密分享份额发送给在线参与者. 当参数服务器将所有参与者上传列表聚合后，通过不小于$t$个在线参与者的秘密分享份额之和减去聚合列表中的掩码之和，从而计算得到原始梯度列表. 由于在执行上传列表聚合之前参数服务器无法消去列表掩码，而当列表聚合之后参数服务器无法获取每个参与者模型的位置信息，因此Re-Shuffle实现了模型的匿名化上传. Re-Shuffle的具体方案为：

1）初始化阶段. 本阶段生成密码学相关的必要参数，以及联邦学习训练所需的模型参数和超参数. $PS$初始化全局模型$W_{\rm{g}}^0$和学习率$\text{α}$.$PS$将$W_{\rm{g}}^0$和$\text{α}$发送给所有参与者. 此外，$PS$发布$param = \{ {G},g,h,p,a\}$作为系统参数，其中$g,h \in {G}；p,a \in \mathbb{Z}_p^*$. 参与者${P_i},i \in [1,{N_P}]$，生成自己的私钥$s{k_i} = {x_i}, {x_i} \in \mathbb{Z}_p^*$, 公钥$p{k_i} = {g^{{x_i}}}$.${P_i}$将$p{k_i}$发送给其他所有参与者${P_j}$.$PS$随机生成$k \cdot {N_P}$个数据位置 ${s_1},{s_2},…,{s_{k \cdot {N_P}}}$，其中$k$为每个参与者可选择的位置个数，并生成自己的私钥$s{k_p} \in \mathbb{Z}_{\rm{p}}^*$, 公钥$p{k_p} = {g^{s{k_{\rm{p}}}}}$. $PS$将$p{k_p}$发送给每个参与者.

2）数据位置生成阶段. 为降低计算开销，采用Lai等人^[35]的高效OT协议 ，具体流程为：

①第1轮（请求参数选择）：

$PS$：

ⅰ）可以参与本轮工作的参与者通知参数服务器,参数服务器将本轮参与者列表${U_1}$发送给所有的参与者${P_i},i \in {U_1}$.

ⅱ）随机选择一个参与者${P_i},i \in {U_1}$作为初始发送方，然后将位置数量$k \cdot {N_P}$发送给${P_i}$. 本轮${N_P}{\text{ = |}}{U_1}|$.

${P_i}$：

ⅰ）生成请求集合${L_{{\rm{ch}}}} = \{ 1,2,…,k \cdot {N_P}\}$.

ⅱ）随机从${L_{{\rm{ch}}}}$中取出$D$个请求参数${L_i} = \{ {l_1},{l_2},…, {l_D}\} ,D \in [1,k]$. 随后${P_i}$随机选择$b \in \mathbb{Z}$，并生成时间戳$Timestep = {g^{b \cdot \sum\limits_{j \in {U_{1,}}j \ne i} {{u_j}} }}$. 其中，${g^{{u_j}}}$为用户${P_j}$的公开参数.

ⅲ）随机选择${P_j},j \in {U_1}$，生成密文${\{ {L_{{\rm{ch}}}} - {L_i}\} _{p{k_j}}}$，并将$\{ {\{ {L_{{\rm{ch}}}} - {L_i}\} _{p{k_j}}},Timestep,{g^b}\}$发送给${P_j}$.

${P_j}$：

ⅰ）接受到来自其他参与者的密文. 如果已经进行过参数选择，则通知发送方重新选择.

ⅱ）如果第一次进行参数选择，使用自己的私钥解密获得选择列表${L_{{\rm{ch}}}} - {L_i}$，并选择请求参数${L_j} = \{ {l_1},{l_2},…, {l_D}\} ,D \in [1,k]$.

ⅲ）在本地，对时间戳的生命周期减1：$Timestep = Timestep/{({g^b})^{{u_j}}}$.

ⅳ）判断$Timestep$是否等于1. 如果不相等，则执行初始参与者${P_i}$相同的操作；如果相等，则通知所有参与者进行位置选择.

经过请求参数选择后，每个参与者都可以得到互不冲突的1~$k$个请求参数，为了便于理解，图3给出了请求参数选择的一个例子，其中，$k = 3,{N_p} = 4$.

图  3  参数选择

Figure  3.  Parameter selection

下载: 全尺寸图片 幻灯片

②第2轮（位置选择）：

${P_i}$收到开始信号后，每个参与者利用令牌生成算法计算选择令牌及验证信息$\{ T o{k_i},{h_i}\} \leftarrow$${{ OT.Token}} (param,s{k_{{i}}},{L_{{i}}})$，其具体计算过程见公式：

将选择消息$\{ To{k_i},{h_i},D\} ,D = |{L_i}|$发送给$PS$. $PS$收到来自${P_i}$的选择消息并判断如下公式是否成立：

如果不成立，那么协议终止；否则计算秘密列表. 生成随机掩码$r \in \mathbb{Z}_p^*$利用信息加密算法计算秘密列表

$\left\{ {C_0},\;{C_1},\;…,\;{C_n},\;…,\;{C_{k \cdot {N_p}}}\right\} \leftarrow {{OT.Enc}}(\{ {s_1},\;{s_2}\;,…,\;$ ${{s_n}\;,…,\;s_{k \cdot {N_P}}}\} ,T o{k_i},\;{h_i},\;D,\;r\;)\;$计算过程为：

将秘密列表$\{ {C_0},{C_1},…,{C_{k \cdot {N_p}}}\}$发送给所有参与者${P_i}$. ${P_i}$收到来自$PS$的秘密列表$\{ {C_0},{C_1},…,{C_{k \cdot {N_p}}}\}$，每个参与者利用解密算法计算位置列表${s_n} \in {S_i} = \{ {s_{{l_1}}}, {s_{{l_2}}},…, {s_{{l_D}}}\} \leftarrow{{ OT.Dec}}(\{ {C_0},{C_1},…,{C_{k \cdot {N_p}}}\} ,{l_d},s{k_i},param)$具体计算过程为：

图4 给出了数据位置获取的一个例子.

图  4  数据位置生成

Figure  4.  Data location generation

下载: 全尺寸图片 幻灯片

3）数据匿名收集阶段. 本阶段${P_i}$向$PS$发送模型上传列表. $PS$聚合所有接收的上传列表，通过秘密分享协议恢复参与者的原始模型，并得到一个无序的参与者训练模型列表. 整个阶段中参与者掉线人数不超过$|{U_1}| - t$则不会影响模型的上传，否则需要重新执行数据位置生成. 本阶段的协议描述为：

①第1轮（秘密分享）

${P_i}$计算自己$T$轮的模型参数$W_i^T \leftarrow W_{\rm{g}}^{T - 1} \pm \text{α} G_i^T$并随机生成一个模型掩码${r_i} \in \mathbb{N}$, 选择一个分配的位置${s_i} \in {S_i}$，生成匿名模型上传列表${L_{{W_i}}}$:

对每个参与者${P_j},j \in {U_1}$生成${r_i}$的分享值${y_{i,j}} \leftarrow$${{SS.Share}}({r_i},t,j)$，此处${y_{i,j}}$包括${P_i}$生成给自己的分享值${y_{i,i}}$. 对每个${y_{i,j}}$，使用对应参与者${P_j}$的公钥加密，生成密文${c_{i,j}} \leftarrow Enc(p{k_j},{y_{i,j}})$. 将${L_{{W_i}}}$及所有的${c_{i,j}}$上传到$PS$. 本轮参与匿名列表上传的参与者集合为${U_2}$，接收${P_i}$上传的${L_{{W_i}}}$及${c_{i,j}}$. 如果$|{U_2}| \lt t$,则协议终止，否则继续执行. 对参与者${P_j},j \in {U_2}$, 发送所有可以被$s{k_j}$解密的密文${c_{i,j}},i \in {U_2}$.

②第2轮（匿名列表恢复）

${P_j}$接收来自$PS$的密文列表${c_{i,j}},i \in {U_2}$，解密获得秘密分享：

将$\displaystyle\sum\limits_{i \in {U_2}} {{y_{i,j}}}$发送给$PS$. 本轮参与$\displaystyle\sum\limits_{i \in {U_2}} {{y_{i,j}}}$上传的参与者集合为${U_3}$. 接受参与者${P_j},j \in {U_3}$的分享值$\displaystyle\sum\limits_{i \in {U_2}} {{y_{i,j}}}$，如果$|{U_3}| \lt t$，则协议终止，否则继续执行. 计算聚合的模型列表${L_W}$为：

其中$L_{{w_j}}^n$表示参与者${P_j}$列表的第$n$个元素, $W_{j,n}^T$表示选择位置${s_j} = n$的参与者模型. 从${P_j},j \in {U_3}$上传的分享$\displaystyle\sum\limits_{i \in {U_2}} {{y_{i,j}}}$中随机选择$t$个，执行秘密分享重构算法获取秘密之和：

计算原始模型梯度列表$L_{\rm{G}}^{}$为：

如果$L_{\rm{G}}^{}$中存在的非空位数等于$|{U_2}|$，则对列表中所有原始梯度或生成的本地模型进行投毒攻击检测，并聚合生成全局模型，否则终止协议. 关于投毒攻击防御的部分，我们在第7节扩展.

6.   安全分析

本节分析了Re-Shuffle协议在第3节所假设的威胁模型下的安全性. 具体而言，所有的实体都诚实地执行协议，但是服务器可以获取协议执行过程中全部接收到的中间数据，并推测收集阶段每个模型所属的参与者. 此外，允许$t - 1$个恶意参与者共谋，以推测诚实参与者的上传模型. 我们证明在存在攻击者的前提下，Re-Shuffle协议可以保证诚实参与者上传模型的原始性、匿名性以及允许参与者掉线的鲁棒性.

6.1   原始性

本节给出协议的正确性证明，以及主要验证Re-Shuffle能够在数据匿名列表恢复阶段聚合得到原始的参与者模型参数.

由Re-Shuffle描述可知，每个参与者${P_i}$模型列表的上传位置为${s_i}$，其具体匿名列表为：

其中，第${s_i}$个位置为自己的本轮训练模型${g^{{r_i} + {s_i}}} \cdot W_i^T$，其余位置填充的构造数据为:

${g^{{r_i} + s}} \cdot W_{\rm{g}}^{T - 1}(s \in [1,k \cdot {N_P}],s \ne {s_i})$.

由于每个参与者${P_i}$将自己的掩码${r_i}$的秘密分享值${y_{i,j}}$发送给在线的其他参与者${P_j},j \in |{U_2}|$，因此${r_i}$可以通过秘密分享恢复算法计算：

其中，${U_t} \subseteq {U_2},|{U_t}| = t$. 然而，由于需要保证列表聚合之前$PS$不能直接通过秘密分享获取掩码${r_i}$的值，因此${U_2}$中的参与者在本地执行秘密分享值的聚合，${P_j}$可以计算聚合值为：

随后在匿名列表恢复阶段$PS$执行列表聚合后${s_n}$位置对应的匿名列表表项为：

其中，想要恢复该项中对应的参与者模型$W_{j,n}^T$，需要计算${U_2}$中所有参与者模型掩码的聚合值$\displaystyle\sum\limits_{j \in {U_2}} {{r_j}}$. 由秘密分享同态性可知：

因此对第$n$个匿名列表表项可以消去掩码，得到原始模型梯度$G_n^T$：

假设第$n$个表项没有参与者选择，那么消去掩码后，该位置参数值为空：

综上所述，我们的方案可以保证最后$PS$能够成功计算匿名列表聚合后每个参与者的梯度信息，且无参与者选择位置的聚合结果为空.

6.2   不可链接性（匿名性）

本文采用了与Bonawitz等人^[13]相同的标准混合论证来证明Re-Shuffle的安全性，实体的视图由内部状态的参数和从其他实体接收到的所有消息组成. 为便于表述，我们首先给出所使用的符号描述，给定${U_4} \subseteq {U_3} \subseteq {U_2} \subseteq {U_1} \subseteq U$表示在每一轮中参与者在线集合，其中$U$为初始参与者集合（$|U| = {N_P}$）. 我们用${U_2}\backslash {U_3}$表示为第2轮中在线的参与者而第3轮中掉线的参与者集合, 用${W_i}$表示参与者${P_i}$的模型$i \in U$，${W_{U'}} = {\{ {W_i}\} _{i \in U'}}$表示参与者集合$U'$包含的模型集合. 为便于表示，我们规定每个实体的输入数据、接收数据以及其在协议运行过程所观察到的所有数据作为该实体的视图. 给定对手集合$C \subseteq P' \cup \{ PS\}$,其中$P'$表示恶意参与者的集合（$|P'| \lt t$）.${{REAL}}_c^{U,t,k}({W_U},{U_1}, {U_2},{U_3},{U_4})$表示在实际执行Re-Shuffle过程中$C$中实体的联合视图. 其中$k$表示由$PS$初始化的安全参数，$t$表示秘密分享要求的阈值. 基于符号定义，给出定理1.

定理1：　存在一个概率多项式时间（PPT）模拟器${{SIM}}_c^{U,t,k}({W_U},{U_1},{U_2},{U_3},{U_4})$，使得${{SIM_c}}^{U,t,k}$输出的视图在与联合视图${{ REAL}}_c^{U,t,k}$在概率多项式时间之下具有不可区分性，即有公式成立：

证明.我们采用了标准混合论据^[31-32]来证明该定理. ${{SIM}}$将对${{ REAL}}_c^{U,t,k}$进行一系列的修改. 修改的内容为Re-Shuffle执行期间的数据和参数. 如果${{SIM}}$的输出与${{ REAL}}_c^{U,t,k}$难以区分，则说明敌手不能获取关于参与者的任何信息，即Re-Shuffle可以保护参与者的模型匿名性. 我们以${{\rm{ Hyb}}_i},i \in [1,7]$，表示每一轮交互过程中${{SIM}}$对系统参数的一次修改.

1） ${{Hyb}_1}$. 在这个混合模式中，${{SIM}}$生成随机列表${L_{{\rm{ch}}}} = \{ {b_1},{b_2},…,{b_i}\} ,i \in [{\textit{1}},{N_P}]$替换所有诚实用户${P_i} \in {U_1}\backslash C$的选择列表${L_{{\rm{ch}}}}$. 其中，任意选择$b \lt {N_P}$，且两两不相等. 随后，模拟器将${L_{{\rm{ch}}}}$及$Timestep$发送至${P_i}$. 由于每个参与者对列表${L_{{\rm{ch}}}}$的选择是随机的，因此${{Hyb}_1}$与${{ REAL}}_c^{U,t,k}$是不可区分的.

2） ${{ Hyb}}{_2}$. 在这个混合模式中，${{SIM}}$生成随机数${{\textit{θ }}_i} \in \mathbb{Z}_p^*$，以替换所有诚实参与者${P_i} \in {U_1}\backslash C$的私钥$s{k_i}$. ${{SIM}}$计算令牌$T ok{'_i}$及验证信息$h{'_i}$为：

由OT安全性假设可知，敌手无法恢复参与者的密钥${\textit{θ }_i}$，此外，敌手执行令牌验证仍可以得到：

因此在这种模式下，${{Hyb}_2}$与${{ REAL}} _c^{U,t,k}$是不可区分的.

3） ${{Hyb}_3}$. 在这种混合模式中，${{SIM}}$生成随机选择列表$L{'_i}(|L{'_i}| \leqslant k)$，以替换所有诚实参与者${P_i} \in {U_1}\backslash C$的选择列表${L_i}$. ${{SIM}}$修改${{Hyb}_2}$计算为：

与${{Hyb}_2}$类似，由于参与者选择列表随机生成，根据OT安全假设^[36]，敌手无法获取参与者的选择列表. 此外敌手执行令牌验证可得到：

因此${{Hyb}_3}$与${{ REAL}} _c^{U,t,k}$是不可区分的.

4） ${{Hyb}_4}$. 在这种混合模式中，${{SIM}}$用$V_i^T$代替了本轮所有诚实参与者${P_i} \in {U_2}\backslash C$的本地模型$W_i^T$，其中$V_i^T$和$W_i^T$具有相同的维度. ${{SIM}}$据此计算${P_i}$的上传模型列表为：

由于模型掩码是随机生成，且参与者选择位置对$PS$是不可见的，因此${{Hyb}_4}$与${{ REAL}}_c^{U,t,k}$是不可区分的.

5） ${{Hyb}_5}$. 在这种混合模式中，${{SIM}}$用随机位置${s_i}' \in {L_i}'$替换所有诚实参与者${P_i} \in {U_2}\backslash C$选择的数据分配位置${s_i}$.${{SIM}}$据此计算${P_i}$的上传模型列表为：

由于参与者的分配位置对$PS$是不可见的，并且梯度在掩码加密下是不可区分的，因此${{Hyb}_5}$与${{ REAL}}_c^{U,t,k}$是不可区分的.

6） ${{Hyb}_6}$. 在这种混合模式中，${{SIM}}$使用随机数替换所有诚实参与者${P_i} \in {U_2}\backslash C$关于掩码${r_i}$的所有秘密分享${y_{i,j}}$. 显然，单个敌手无法获取${r_i}$的原始值. 当$|{U_3}| \lt t$, 由Shamir秘密分享的安全性^[28]可知，敌手无法恢复${r_i}$；当$|{U_3}| \geqslant t$，且$|{U_3}\backslash C| - |{U_3}| \lt t$时，根据诚实参与者与敌手之间的非共谋设置，以及Shamir秘密分享的安全性可知敌手无法获取${r_i}$的原始值. 因此$Hy{b_6}$与${{ REAL}}_c^{U,t,k}$是不可区分的.

7） ${{Hyb}_7}$. 在这种混合模式中，${{SIM}}$使用随机数替换所有诚实参与者${P_i} \in {U_3}\backslash C$关于秘密分享聚合$\displaystyle\sum\limits_{i \in {U_2}} {{y_{i,j}}}$，同理于${{Hyb}_6}$根据诚实参与者与敌手之间的非共谋设置以及Shamir秘密分享的安全性可知，${{Hyb}_7}$与${{ REAL}}_c^{U,t,k}$是不可区分的. 证毕.

综上所述，可以采样出一个模拟器${{SIM}}$，并且${{SIM}}$的输出与实际视图${{ REAL}}_c^{U,t,k}$的输出是不可区分的. 因此，在诚实参与者的上传列表参与聚合消除掩码之前，敌手无法获取关于参与者上传模型列表的任何信息，包括真实的模型数据位置以及模型参数. 当聚合结束后，敌手可以获取聚合列表，汇总所有参与者的原始模型，但是无法获取每个参与者模型在列表中的位置. 即 Re-Shuffle可以保护模型匿名性.

6.3   鲁棒性（容错性）

定理2：　在Re-Shuffle中，如果存在系统的参与者掉线的情况，无需进行数据上传位置的重新选择，且当参与者在线数量$|U|$高于阈值t时，该轮次的匿名模型列表恢复阶段可以正常执行.

证明.我们将对Re-Shuffle协议中每一轮可能的参与者掉线情况作分析，并给出的执行情况，以证明其对用户掉线的鲁棒性.

1）数据位置生成阶段（第2轮）. 在此阶段，在线参与者集合为${U_1}$. 当$|{U_1}| \geqslant t$时，参与者可以与$PS$交互，并利用OT协议获取若干模型上传位置. 当参与者掉线时，由于OT协议执行过程无需与其他参与者交互，剩余参与者向$PS$请求自己的数据上传位置. 因此，该过程参与者掉线不会影响协议的正常执行.

2）匿名模型收集阶段（第1轮）. 在此阶段，在线参与者集合为${U_2}$. 当$|{U_2}| \geqslant t$时,每个参与者${P_i},i \in |{U_2}|$上传自己的匿名模型列表${L_{{W_i}}}$，并将加密的掩码${r_i}$的秘密分享值的密文${c_{i,j}}, {j \in {U_2}}$上传至$PS$.$PS$将所有参与者上传的加密掩码分享发送给对应且仍然在线的参与者${P_j},j \in \{ {U_3}\backslash {U_2}\}$. 由于参与者的匿名模型列表及其加密后的掩码秘密分享在本轮一并发送至$PS$，如果本轮参与者掉线，则该参与者的匿名模型列表不会上传. 因此无需在第2轮恢复列表掩码. 综上，该过程参与者掉线不会影响协议的正常执行.

3）匿名数据收集阶段（第2轮）. 在此阶段，在线参与者集合为${U_3}$. 当$|{U_3}| \geqslant t$时,每个参与者${P_j},j \in |{U_3}|$会根据上一轮在线参与者集合${U_2}$聚合所有接受的秘密分享$\displaystyle\sum\limits_{i \in {U_2}} {{y_{i,j}}}$并上传该聚合分享值至$PS$. 当参与者掉线时，由Shamir秘密分享的同态性可知，$PS$可以通过不小于$t$个聚合值$\displaystyle\sum\limits_{i \in {U_2}} {{y_{i,j}}} ,j \in {U_3}$计算上一轮中掩码的聚合值$\displaystyle\sum\limits_{i \in {U_2}} {{r_i}}$. 因此该过程参与者掉线不会影响协议的正常执行. 综上，当参与者在线数量$|U_3|$高于$t$时，Re-Shuffle的执行不会受参与者掉线影响. 证毕.

6.4   抗合谋攻击

定理3：　在Re-Shuffle中，除了参与者${P_i}$外，只要有1个诚实参与者${P_j}$，即使参数服务器与其他参与者合谋也无法获取参与者${P_i}$的梯度数据的位置.

证明.在Re-Shuffle中，每个参与者${P_i}$可以选择$k$个位置，参与者${P_j}$也可以选择$k$个位置. 随后，在使用了n-out-of-k 不经意传输协议后，所有的位置被随机化. 在这种情况下，即使参数服务器与除${P_j}$外的其他参与者合谋也无法推断出${P_i}$的具体位置. 一般情况下，我们考虑超过一半的参与者为诚实参与者，在这种假设下，即使参数服务器与其他少数恶意参与者一起合谋也无法得到${P_i}$的梯度数据的具体位置. 证毕.

7.   性能评估

本节从功能性、毒化攻击检测，以及计算开销3个方面对Re-Shuffle进行了分析，并与相关隐私保护方案进行了对比：隐私保护数据收集（privacy-preserving data collection, PPDC）^[20]、隐私保护深度学习（privacy-preserving deep learning, PPDL）^[25]、隐私保护机器学习（privacy-preserving machine learning, PPML）^[13]以及高效隐私保护联邦深度学习（efficient and privacy-preserving federated deep learning，EPFDL）^[36].

7.1   功能对比

本节对Re-Shuffle方案以及前述方案进行功能性对比. 其中，分别从梯度隐私性、毒化防御可扩展性、抗共谋、隐私保护方法以及参与者掉线可恢复性这5个方面进行了对比分析. 对比的结果见表2.

表  2  现有工作对比

Table  2.  Comparison of Existing Work

方案	梯度隐私	毒化攻击 防御扩展	抗共谋	隐私保护方法	掉线恢复
PPDC	√	√	√	源匿名	×
PPDL	√	×	×	同态加密
PPML	√	×	√	秘密分享	√
EPFDL	√	×	√	差分隐私/ 同态加密
Re-Shuffle	√	√	√	不经意传输/ 秘密分享	√
注: "√"表示具有特性；"×"表示不具有特性.

下载: 导出CSV 

| 显示表格

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层卷积神经网络模型，设置学习率$\alpha$=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在诚实参与者设置下能够得到较好的训练结果.

图  5  诚实参与者设置下的全局模型准确率

Figure  5.  Global model accuracy with honest participants setting

下载: 全尺寸图片 幻灯片

随后，我们给出了20%的参与者进行毒化攻击下的模型在测试集上的准确率的对比，如图6所示. 由实验结果可知，Re-Shuffle能够有效支持毒化攻击检测方案的拓展，其检出效果依赖于其使用的检测方案. 综上，Re-Shuffle能够在保证模型匿名性的前提下支持现有的毒化攻击检测方案.

图  6  20%恶意参与者设置下的全局模型准确率

Figure  6.  Global model accuracy with 20% malicious participants setting

下载: 全尺寸图片 幻灯片

7.3   计算开销

本节给出了Re-Shuffle的计算开销，并将其与7.1节中给出的相关工作进行比较，此外我们对部分工作进行了实验仿真，评估了Re-Shuffle在实际环境下的运行时间.

首先在数据位置生成阶段中，第1轮中，每个参与者之间进行一轮的交互以获取自己的请求列表，该过程采用与PPDC^[20]中相同的加解密方式. 第2轮中，每个参与者根据请求列表与参数服务器进行2轮交互，获取数据上传位置，该过程采用OT协议、Token及验证信息$h$的生成过程计算复杂度$O\left( {{N_p}} \right)$. 随后服务器返回位置列表的密文，计算复杂度为$O\left( {{N_p}} \right)$.

在匿名模型列表上传的过程中，每个参与者使用随机掩码对模型加密，并生成长度为${\text{3}}{N_p}$的匿名模型列表，该过程参与者的计算复杂度为$O\left( {\delta {N_p}} \right)$，其中$\delta$表示模型的大小. 随后每个参与者在本地对所有在线用户计算随机掩码的秘密分享，该过程参与者的计算复杂度为$O\left( {{N_p} - {N_{\rm{drop}}}} \right)$，最坏情况的计算复杂度为$O\left( {{N_p}} \right)$（即没有参与者掉线）. 服务器将对应秘密分享值发送至每个参与者，参与者在本地执行解密并聚合所有的局部秘密分享值，计算复杂度为$O\left( {{N_p}} \right)$. 最后每个参与者将局部分享上传至参数服务器. 参数服务器在本地聚合所有的匿名列表，该过程复杂度为$O\left( {\delta N_p^2} \right)$并根据参与者上传秘密分享消除聚合后的列表掩码，该过程的计算复杂度为$O\left( {\delta {{\left( {{N_p} - {N_{\rm{drop}} }}\right)}^2}} \right)$, 最坏情况的计算复杂度为$O\left( {\delta N_p^2} \right)$. 综上所述我们得出Re-Shuffle执行过程中参与者的计算复杂度为$O\left( {N_p^2 + \delta {N_p}} \right)$，服务器的计算复杂度为$O\left( {\delta N_p^2} \right)$.

本文给出的对比方案的计算开销见表3. 由表3可知，Re-Shuffle的计算开销在对比方案中相对较高. 尽管如此，Re-Shuffle采用模型掩码的方式替代加密整个模型，相较于PPDL及EPFDL的实际计算耗时更小；Re-Shuffle对于掉线用户的支持度较高，且计算复杂度随掉线用户数量的增加而下降. 因此在产生大量用户掉线的场景下，Re-Shuffle的实际运行时间会低于不支持用户掉线方案PPDC. Re-Shuffle以及PPML均是采用Shamir秘密分享的方式为参与者模型添加掩码，因此计算复杂度相同. 但是相较于PPML采用双掩码，Re-Shuffle在掩码添加的过程中利用秘密分享的同态性，避免了第2个掩码的秘密分享计算消耗，因此实际耗时相对更短.

表  3  计算开销对比

Table  3.  Comparison of Computation Cost

方案	服务器开销	参与者开销
PPDC	$O( {\delta {N_p}\log {N_p}} )$	$O( \delta )$
PPML	$O( {\delta N_p^2} )$	$O( {N_p^2 + \delta {N_p}} )$
PPDL	$O( {\delta {N_p}} )$	$O( \delta )$
EPFDL	$O( {N_p^2 + \delta {N_p}} )$	$O( \delta )$
Re-Shuffle	$O( {\delta N_p^2} )$	$O( {\delta {N_p}} )$

下载: 导出CSV 

| 显示表格

在密码学方面，我们采用了Lai等人^[35]提出的n-out-of-k 不经意传输协议实现了Re-Shuffle的模型位置生成并利用Shamir秘密分享协议实现了Re-Shuffle的模型上传. 具体采用Python库Charm-crypto ^[38]实现了上述协议，其中加解密的参数采用椭圆曲线SS1024 ^[39]，达到了112 b的安全等级. 在参与者及服务器方面，设置参与者数量${N_p} \in \left[ {0,500} \right]$，掉线参与者数量${N_{{\rm{drop}}}}$=100，参数服务器数量设置为1. 设置Shamir秘密分享阈值$t$=300.

我们分析了基线方案FedAvg、Re-Shuffle以及其他对比方案之间在存在参与者掉线及参与者不掉线情况下参数服务器及每个参与者的计算时间开销. 其中图7为不掉线情况下服务器计算开销对比，图8为不掉线情况下参与者计算时间开销对比，图9为参与者掉线20%情况下服务器计算时间开销对比，图10为参与者掉线20%情况下服务器计算时间开销对比.

图  7  参与者不掉线情况下服务器计算时间开销对比

Figure  7.  Comparison of server computing time cost when no participant is offline

下载: 全尺寸图片 幻灯片

图  8  不掉线情况下参与者计算时间开销对比

Figure  8.  Comparison of participant computing time cost when no participant is offline

下载: 全尺寸图片 幻灯片

图  9  参与者掉线20%情况下服务器计算时间开销对比

Figure  9.  Comparison of server computing time cost when 20% participants are offline

下载: 全尺寸图片 幻灯片

图  10  参与者掉线20%情况下参与者计算时间开销对比

Figure  10.  Comparison of participant computing time cost when 20% participants are offline

下载: 全尺寸图片 幻灯片

由实验可知，在参与者不掉线时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能够在可接受的计算及开销下保护参与者的隐私. 未来会对如何提高方案效率以及毒化攻击检测性能作进一步研究.

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