基于二叉树的高效分组安全聚合方法.pdf

基于二叉树的高效分组安全聚合方法孙 奕 周传鑫*汪德刚 杨 帆 高 琦(信息工程大学密码工程学院 郑州 450001)ONlg2lgNlglglgNO(lgNlgN)摘 要：安全聚合是联邦学习安全共享过程中确保本地模型聚合安全性和隐私性的关键环节。然而，现有方法存在计算开销大、公平机制差、隐私泄露、无法抗量子攻击等问题。为此，该文提出一种基于二叉树的高效分组安全聚合方法(Tree-Aggregate)。首先，基于二叉树构建用户分组安全通信协议将计算开销从降到量级，并通过均匀分摊机制保证了用户计算开销的公平性；然后，提出一种分组不均衡场景下的随机填充算法，解决单一用户引起的隐私泄露问题。最后，该文通过融入格密钥交换协议，为Tree-Aggregate方法增加了抗量子攻击的能力。通过理论分析，Tree-Aggregate将计算开销的增长速率由线性级别变为对数级别，并通过实验对比分析表明，当用户数量N 300时计算开销相较于现有方法减小了近15倍。关键词：联邦学习；安全聚合；分组拓扑；公平性中图分类号：TN919.1文献标识码：A文章编号：1009-5896(2023)07-2546-08DOI:10.11999/JEIT220745Efficient Grouping Secure Aggregation Method Based on Binary TreeSUN Yi ZHOU Chuanxin WANG Degang YANG Fan GAO Qi(Department of Cryptogram Engineering,Information Engineering University,Zhengzhou 450001,China)O(Nlg2lgNlglglgN)O(lgNlgN)Abstract:Secure aggregation is a key step to ensure the security and privacy of local model aggregation infederated learning security sharing.However,the existing methods have many problems,such as highcomputational overhead,poor fairness mechanism,privacy disclosure,and inability to resist quantum attack.Therefore,Tree-Aggregate,an efficient grouping secure aggregation method based on binary tree is proposed inthis paper.Firstly,the binary tree based user group security communication protocol can reduce thecomputation cost from to magnitude and ensure the fairness of thecomputation cost through the uniform allocation mechanism.Then,a random padding algorithm is proposed tosolve the privacy leakage problem caused by a single user.Finally,the anti-quantum attack capability of tree-aggregate method is improved by incorporating lattice-key exchange protocol.Through theoretical analysis,tree-aggregate can change the growth rate of computation cost from linear level to logarithmic level,andthrough experimental comparative analysis,when the number of users N 300,computation cost is reduced bynearly 15 times compared with existing methods.Key words:Federated learning;Security aggregation;Grouping topology;Fairness 1 引言联邦学习作为无需数据聚合即可实现跨域数据协同分析的新兴技术，能够有效降低传统数据安全交换领域的隐私泄露风险1。安全聚合是一种解决联邦学习中数据安全与隐私保护问题的关键技术，它通过密码技术、差分隐私技术保护用户的本地模型，使得半诚实的服务器无法获知真实的用户模型，同时恶意用户也无法通过与服务器共谋的方式窃取联邦学习中其他用户的隐私信息。O(N2)但是，安全聚合方法需要用户之间维持着大量的开销负担，这对于资源受限的用户来说是无法忍受的。特别是在百万量级的移动设备中2，设备开销随着用户数量N的增加呈指数级增长，过高的开销成为联邦学习发展的瓶颈之一。目前有3种降低开销的方式3：(1)算法优化：针对数据类型优化模型训练算法；(2)压缩：压缩模型数据大小；(3)结构优化：分层、分级、分组调整联邦学习系统架构。它们分别从不同的维度去解决联邦学习中的开销难题，其中结构优化作为解决大规模联邦学习开销问题的有效方法受到了大量研究者的关注。另外，在安全聚合协议中系统整体开销和用户 收稿日期：2022-06-07；改回日期：2022-09-04；网络出版：2022-09-07*通信作者：周传鑫zhou_第45卷第7期电 子 与 信 息 学 报Vol.45No.72023年7月Journal of Electronics&Information TechnologyJul.2023公平性之间往往难以取得有效的平衡。因此，保证用户之间开销的公平性也是联邦学习安全聚合的重点关注问题之一。同时随着量子时代的到来，基于大数分解困难问题的密钥交换算法已经无法满足新的安全需求，联邦学习系统迫切需要一种能够抗量子攻击的密钥交换算法作为安全聚合方法的基础。O(N2)O(Nlg2lgN lglglgN)L 1logLSo等人4提出一种逐层累加的链式拓扑结构(Turbo-Aggregate)，通过分层分组的安全通信协议将用户的计算开销从降到量级，在保护用户隐私安全的前提下减少了用户的计算负担。为了进一步提升时间效率，So等人4还提出了增强版的并行运算协议Turbo-Aggregate+，使得位于同一层的用户组能够并行通信，将安全聚合协议的执行步骤从降到量级，减少了协议的运行时间。但是，Turbo-Aggregate+协议的计算开销随着层级的增加而增加，这样的开销分配对高层级用户是不公平的，而没有公平的开销机制也就无法吸引更多拥有优质数据的用户参与联邦学习。另外，So等人并没有考虑用户分组不均衡场景下的隐私安全问题，这可能会导致单一用户组的本地模型泄露。对此，本文提出一种基于二叉树的高效分组安全聚合方法(Tree-Aggregate)，基于二叉树构建用户分组安全通信协议有效降低了用户计算开销，保证协议内部用户开销的公平性，同时还提出了一种分组不均衡场景下的随机填充算法，解决单一用户引起的隐私泄露问题。另外本文还在用户与服务器中间融入了格密钥交换协议，为联邦学习系统增加了抗量子攻击的能力。本文主要的研究工作如下：O(Nlg2lgNlglglgN)O(lgNlgN)(1)设计了一个基于二叉树的高效分组安全聚合方法Tree-Aggregate，基于二叉树构建用户分组安全通信协议将用户的计算开销从降到量级，并通过均匀分摊机制保证了用户计算开销的公平性。(2)设计了一种分组不均衡场景下的随机填充算法，通过随机筛选填充用户传递聚合模型，无需消耗计算资源解决单一用户引起的隐私泄露问题。(3)融入了格密钥交换协议，为联邦学习系统提供了抗量子攻击的能力。(4)通过理论分析，Tree-Aggregate将计算开销的增长速率由线性级别变为对数级别，并通过实验对比分析表明，当用户数量N 300时计算开销相较于现有方法减小了近15倍。2 方案设计本节详细介绍了基于二叉树的高效分组安全聚合方法Tree-Aggregate，其主要由4个部分组成。(1)Tree-Aggregate能够保证联邦学习安全共享过程中本地模型的安全性和隐私性，图1展示了方法在联邦学习中的整体应用。(2)展示了基于二叉树建立的分组安全通信协议从用户层到服务器层的数学推导过程，证明了方法的安全性。(3)针对用户分组不均衡的场景，提出一种随机填充算法在组内增加若干虚拟用户，解决单一用户引起的隐私泄露问题。(4)Tree-Aggregate融入了格密钥交换协议为联邦学习增加抗量子攻击的能力。2.1 系统结构Tree-Aggregate利用一个基于二叉树的聚合策 图 1 系统结构(N用户被划分到H层L组二叉树拓扑中)第7期孙 奕等：基于二叉树的高效分组安全聚合方法2547 l LNllLNl=Nxi l L略计算所有用户的本地模型，其使用到的主要参数在表1中给出了说明。给定一个N用户的联邦学习网络，然后将所有的用户划分为H层L组中，如图1所示，其中在组中有个用户，且。在用户组的划分中，采用了一种抗偏见的公共随机生成协议，保证每个用户都被随机分配到一个可用组中5。使用表示组中用户i的本地模型。因此Y=lLiNlxi(1)xiFq其中，和Y都来自阶为q的有限域，由于聚合操作都是在有限域内实现的，为方便运算省去了模q操作。图1中系统结构一共分为9个步骤，依次为：(1)本地训练；(2)格密钥交换服务器掩码；(3)协商独立掩码；(4)上传掩码模型；(5)单用户组随机填充；(6)交互聚合模型；(7)挑选最终组；(8)上传服务器解密；(9)下一轮更新。Tree-Aggregate作为安全聚合方法，能够帮助联邦学习更好地保护用户隐私安全，降低计算开销，保证公平性，防止隐私泄露，提升系统抗量子攻击能力。Tree-Aggregate规定所有的用户在聚合阶段都按顺序执行，位于二叉树叶子节点用户将自己的训练模型加上掩码后逐层上传至根节点用户组中。在这里，Tree-Aggregate能够在掉线用户不超过N/2的情况下利用拉格朗日编码添加冗余恢复掉线用户数据，细节内容请参见文献4的.C节。为保护根节点用户的隐私安全，最终用户组的训练模型并不能直接上传给服务器，Tree-Aggregate在最后增加了虚拟步骤。当聚合阶段完成后，从所有的用户中随机选择一组用户作为最终组，其聚合与秘密分享逻辑和用户组保持一致。Tree-Aggregate保证任何一方(用户或服务器)都不能学习单个模型或模型子集的部分聚合。除了所有用户的最终聚合模型外，服务器什么也学不到，这是通过秘密共享掩盖单个模型实现的，本文将在下面描述这一点。2.2 基于二叉树的分组安全通信协议uiuiri,jri,jTree-Aggregate使用秘密分享掩盖单个用户模型，以保护其隐私，防止联邦学习各方之间潜在的共谋。这需要两个步骤来完成。在第1步中，服务器与每个用户协商出一个随机密钥作为掩码，表示用户i的掩码值。仅由服务器和相关用户知道，因此只要服务器是诚实的，它就可以保护用户的隐私安全，防止其余用户通过共谋攻击联邦学习的聚合模型。但是，如果服务器与恶意用户共谋，泄露特定用户的随机掩码则可能破坏联邦学习的安全性。为了保护用户隐私不受此类场景的影响，在第2步中，用户还需要在单个模型上附加独立掩码，以防止服务器和用户之间潜在的共谋，表示用户i发送给上级根节点组中的用户j。综上，用户i的本地模型为 x(h)i,j=x(h)i+u(h)i+r(h)i,j(2)x(h)i x(h)i,jr(h)i,ji IjJr(h)i,j=0r(h)i,j其中，代表层h中用户i的明文本地模型，代表层h中被两层掩码保护的本地模型，为了在根节点的聚合中抵消所有的独立掩码，在所有的中。不仅能够保证用户的隐私安全，同时也能够保证聚合的准确性，使独立掩码抵消后与原始数据聚合相等。s(h)i此外，每个用户持有一个局部聚合模型对应的变量，其表示用户i在层h中的变量。在Tree-Aggregate的每个阶段，用户更新这些变量并将它们传播到下一个组。因此，用户i在层h(h 1)中的变量为 s(h)i=1NmmM s(h1)m+mM x(h1)m,i+1NnnN s(h1)n+nN x(h1)n,i(3)s(1)is(l)i其中，h表示根节点层，h1表示叶子节点层，M和N表示叶子节点的特定组，而m和n表示叶子节点特定组中的用户，另外设定初始聚合时=0。而h层中用户i将式(2)和式(3)中的两个值同时发给上级根节点组中的用户。这里，设定另一个局部聚合模型对应的变量s(h)i=1NmmM s(h1)m+1NnnN s(h1)n(4)mM x(h1)m,inN x(h1)n,i其中，不包含h1层中的本地模型和。因此，在根节点h+1层中的用户聚合变量值为表 1 主要参数说明参数定义N用户总数量L用户分组H用户分层Nl位于l 组中的用户数量u服务器掩码r独立掩码s局部聚合模型2548电 子 与 信 息 学 报第 45 卷s(h+1)k=1NiiI s(h)i+1NjjJ s(h)j=1NmmM s(h1)m+mMx(h1)m+mMu(h1)m+1NnnN s(h1)n+nNx(h1)n+nNu(h1)n+1NppP s(h1)p+pPx(h1)p+pPu(h1)p+1NqqQ s(h1)q+qQx(h1)q+qQu(h1)q=s(h)i+s(h)j+m,n,p,qM,N,P,Qx(h1)m,n,p,q+m,n,p,qM,N,P,Qu(h1)m,n,p,q(5)r(h1)i,mr(h1)i,nr(h1)i,pr(h1)i,qmMr(h1)i,m=0nNr(h1)i,n=0pPr(h1)j,p=0qQr(h1)j,q=0s(2)=1NiiI s1i=0i1=0s(h+1)k其中，式(5)中还包含独立掩码,。而根据对独立掩码的定义，,，如图2所示。另外，在初始聚合中，因此逐层递推下去，等于所有叶子节点的本地模型与服务器掩码之和s(h+1)k=m,.,qM,.,Qxm,.,q+m,.,qM,.,Qum,.,q(6)xsm,.,qM,.,Qum,.,q综上所述，在图2中，用户组M和用户组N中的每个用户分别与用户组I中的每个用户进行密钥协商，并交互本地掩码模型 和局部聚合模型，用户组P,Q中的每个用户与用户组J中的每个用户进行同样的操作。等到M,N,P,Q层的通信完成后，用户组I,J中的每个用户再与用户组K中的每个用户通信。在最后阶段，服务器从式(8)中获得最终的聚合值，并删除服务器掩码。如果在协议执行期间没有用户退出，那么这种方法可以很好地工作。另外，如果有任何用户掉线，随机掩码的存在导致聚合无法得到准确的结果，推荐使用拉格朗日编码算法4解决掉线问题。2.3 不平衡分组场景下的随机填充算法Nl 2Nl1Nl 2Nl=1 si xi,jri,jri,j在一些联邦学习场景下，用户数量无法按照预定的方式分组，例如当用户数量恰好是质数时，无论以哪种分组方式都无法保证用户被公平地划分到用户组中，如图3所示。同时，为了考虑联邦学习公平性与正向激励，服务器不能剔除部分用户以满足分组要求。在本方法中，这种分组结果导致二叉树是非平衡的。本文考虑两种场景，一种是所有组内的用户数量，一种是部分组内用户数量。当时，Tree-Aggregate能够按照3.2节中约定的方式完成联邦学习，同时保证用户隐私的安全性。但是当时，该组叶子节点的两个用户组在逐层上传,时，本该防止服务器与恶意用户共谋的独立掩码失去作用。由于根节点组中只有1个用户，独立掩码无法通过秘密分享的方式分别传递给多个用户，从而无法保护叶子节点组用户的隐私安全。Nl=1 s(h)x(h)r(h)为了解决这类问题，本文提出一种添加虚拟用户的方法增强二叉树的平衡性。为此，任意选择一些用户作为虚拟用户填充的用户组，使其再次参与到联邦学习的安全聚合中。不过这些虚拟用户仅仅负责接收和上传聚合变量，并不会再次传输用户的本地模型。因此，虚拟用户不需要再与上层根节点组用户交互独立掩码。s(h)i为了更简便阐述非平衡二叉树方法的安全性和正确性，将二叉树的聚合简化为链式聚合。在h层中，聚合变量的值为 s(h)i=1NjjJ s(h1)j+jJx(h1)j,i+jJu(h1)j,i+jJr(h1)j,i(7)图 2 基于二叉树的高效分组安全聚合实例第7期孙 奕等：基于二叉树的高效分组安全聚合方法2549 s(h)ir(h1)j,is(h+1)k显然，由于中包含独立掩码，用户i无法联合服务器窃取h1层用户的隐私信息。而h+1层用户的聚合变量值为s(h+1)k=1NiiI s(h)i=1NjjJ s(h1)j+jJx(h1)j,i+jJu(h1)j,i(8)r(h1)j,iNl=1从式(8)中得，h1层独立掩码在h+1层被抵消且并不会泄露任何用户的隐私信息。综上，通过添加虚拟用户增强二叉树平衡性的方式能够有效解决时叶子节点用户组隐私泄露问题。2.4 格密钥交换迪菲-赫尔曼(DiffieHellman,DH)密钥交换方案是由Diffie等人6于1976年提出的公钥密码方案，其被广泛应用于联邦学习的安全聚合方案中4,7,8。但是在Monz等人9提出了Shor量子算法后，量子计算机的出现使得基于大整数分解、离散对数等传统困难问题的方案可以在多项式时间内解决，这同样也威胁了以DH密钥交换方案为基础的安全聚合的安全性。因此，本文基于环上容错学习(Ring-Learning With Errors,R-LWE)问题设计的密钥交换算法(NewHope)10为Tree-Aggregate提供了抗量子攻击的能力。a Rqks,eseks,e,eseeb=a s+ebb a u=at+NTT(e)v=NTT1(bt)+e+v用户和服务器通信双方会提前商定一个多项式作为系统参数。接着用户从中心二项式分布中采样得到多项式，其中 为私钥，为噪声输入。同时，服务器也从中采样得到多项式，为服务器的私钥，与为噪声信号。此时用户通过计算得到公钥，并将公钥以及公钥种子进行多项式的编码后发送给服务器。服务器接收到用户发送的公钥后，首先对公钥进行解码操作得到多项式 以及公钥种子，由公钥种子生成公参多项式；其次服务器计算,，然后服务器 uv uvv vv NTT1(u s)(K)将多项式 以及经压缩产生的字节数组h进行编码得到密文c，最后将密文c传送给用户。用户收到密文后，首先对密文进行解码操作得到,h；其次后对字节数组h解压缩操作得到，有；然后计算进行解编码操作，最后得到最终的共享密钥。3 性能分析 3.1 效率分析Tree-Aggregate的聚合开销主要由两个部分组成：计算开销和通信开销。而计算开销中最占用时间的步骤是通过秘密分享掩蔽模型。用户通过秘密分享掩蔽模型的计算开销是O(logN)。而在每个执行阶段，用户的计算过程都是并行处理的，因此每个阶段的计算开销与单个用户计算开销相同，为O(logN)。Nl=1clogNc D(0.5|T/N)D(a|b)Nl=1clgNNlN/Nl=2LL=lgcNlgNO(lgNlgN)另外，Tree-Aggregate采用与文献4相同的分组方式，当时，Tree-Aggregate能够达到相同的隐私保护强度。其中，T是共谋恶意用户的数量，是参数a和b的伯努利分布之间的相对熵(Kullback-Leibler,KL)距离11。显然，在一个N用户的联邦学习系统中可以分为组用户。而在完全二叉树的分组结构下，分组数量与执行步骤L的关系为，因此执行步骤。综上Tree-Aggregate计算开销为。l LNlO(lg2N)2L+1 2L=lgcNlgNO(NlgN)通信开销是通过测量整个网络上的通信总量来评估的，与集中式通信架构相同，Tree-Aggre-gate的通信架构中也包含一个中央服务器。在执行步骤中，组用户发送一个信息给上层组中用户的通信开销为。同时联邦学习结构通信轮数随着二叉树层数的增加呈等比数列的形式增加 为，又 由 上 述 内 容 得 执 行 步 骤，综上Tree-Aggregate通信开销为。C=O(NlgN)O(Nlg2lgNlglglgN)O(logNlogN)综上所述，安全聚合协议的总开销由通信开销和计算开销组成，所以Tree-Aggregate的总开销为。而本文的贡献主要是将安全聚合协 议 的 计 算 开 销 从降 到量级，而通信开销保持不变。表2显示了本文所提Tree-Aggregate协议与现有联邦学习安全聚合工作的计算开销比较，其中m表示模型更新的大小。3.2 公平性分析So等人4同样意识到Turbo-Aggregate的链式 图 3 不均衡分组条件下的随机填充算法2550电 子 与 信 息 学 报第 45 卷lgLO(Nlg2lgNlglglgNO(lgNlgN)结构对于联邦学习系统效率的严重浪费，因此提出了Turbo-Aggregate+方法将联邦学习的执行步骤从L1降到了，如图4(b)所示。图4表明在N=24用户，L=8组的联邦学习系统中，Turbo-Aggregate+只需要3步，而Turbo-Aggregate需要7步才能完成同样的安全聚合操作。而4.1节证明了Tree-Aggregate利用二叉树的拓扑结构将联邦学 习 的 计 算 效 率 从)降 到 了，它的计算开销比Turbo-Aggregate和Turbo-Aggregate+都低。同时，Turbo-Aggregate+计算开销的降低是以部分组用户通信开销的增加为代价的。这种现象在大量用户组的场景下更为明显，位于联邦学习系统高层的用户组会面临多次的秘密分享操作，不同用户在相同的激励下维持着不同的通信开销显然是不公平的。而本文Tree-Aggregate保证了联邦学习系统中的用户组至多只需要与两组用户保持秘密分享操作，它将二叉树拓扑结构增加的通信开销均匀地分布到每组用户中，保证了系统中用户的公平性。3.3 隐私安全分析Ehh 1Bhh h 1h 1h h+1s(h)h 1PEh=PBh Nl/2PEhBh(N,T,Nl)假设事件表示服务器与用户之间为了窃取层中诚实用户的本地模型而发起的共谋，表示层组h中共谋用户的数量。Tree-Aggregate方法中的聚合信息是由低层组向高层组流动，因此位于层中的共谋用户无法窃取层中的任何信息，而位于层中的共谋用户最多只能获得局部聚合模型。根据文献4，当层h中的共谋用户数量超过层h中总用户数的1/2时，共谋用户就能拥有足够的能力窃取层用户的模型隐私，即。为了计算，设定在N个用户中共有不超过T个共谋用户，而事件遵循参数为的超几何分布，其尾概率(tail probability)被限定为PBhNl2 exp(cTNl)(9)cT=D(0.5 T/N)T (0.5 )N其中，15。当且 图 4 不同方案间的拓扑结构表 2 计算开销对比方法计算开销文献4O(mNlog2logNlogloglogN)文献 8O(mN2)文献12O(mNlogN+Nlog2N)文献13O(mNlogN)文献14O(mN)本文O(mlogNlogN)第7期孙 奕等：基于二叉树的高效分组安全聚合方法2551 0cT时，始终是一个正常数。因此，本地模型隐私泄露的可能性为Pprivacy leakage=PlN/NlEh lN/NlPEhNNlexp(cTNl)=Bprivacy(10)N/NlBprivacyBprivacy其中，表示总的分组数，表示隐私泄露的风险。而上界的渐近性为limNBprivacy=exp limNlgBprivacy=exp limN(lgN lgNl cTNl)=exp()=0(11)N 0T=(0.5 )NlimNBprivacy=0综上所述，当且时，Tree-Ag-gregate方法能够抵抗个共谋用户的攻击，此时的隐私泄露风险。4 实验对比分析 4.1 实验环境本文使用分布式框架FedML库16实现了Tree-Aggregate，并与最新的Turbo-Aggregate计算时间做了对比。在用户之间的通信上，采用的是基于Python的MPI4Py17消息传递接口。实验挑选了300个虚拟云主机作为模拟的联邦学习用户，其中最大带宽统一设置为1 Gbit/s，云主机之间程序独立运行，且互相能够通信。需要说明的是本文只考虑联邦学习的聚合阶段，本地用户上使用的是模拟矩阵向量来测算安全聚合方法的单轮传输，这是因为这些向量可以被真实世界联合学习中任何训练过的本地模型替换。本文实现了下面3个结构：O(Nlg2lgN lglglgN)(1)基准：将Turbo-Aggregate作为基准方法4，如图4(a)所示。它是一种通过链式分组结构降低计算开销的安全聚合方法，计算开销为。lgLO(lg2Nlg2lgN lglglgN)(2)Turbo-Aggregate+：为了进一步降低联邦学习计算开销，So等人4还通过并行加速的方式将执行阶段的数量从L1降到了，如图4(b)所示，计算开销为。O(lgNlgN)(3)Tree-Aggregate：类似于Turbo-Aggreg-ate+方法，Tree-Aggregate同样是借鉴了并行加速的思想，但是本文的聚合协议与上述两种比较协议是完全不同的。上述两种比较协议本质上是两组用户之间的相互通信，而在3.2节中详细阐述了Tree-Aggregate是一种基于二叉树的拓扑结构，它是两组用户作为叶子节点与另一组根节点用户之间的通信，如图4(c)所示，计算开销为。4.2 实验结果分析实验比较的是每个协议单轮安全聚合的总运行时间，同时逐渐增加联邦学习中用户N的数量。其中为了更精准地对比分析，总运行时间中不包含用户本地训练模型的时间。由于整个联邦学习过程的其他步骤都保持不变，因此整个联邦学习阶段与单轮安全聚合花费的时间应该保持正比，实验结果如图5所示。可以看出，Turbo-Aggregate和TurboAggreg-ate+的总运行时间几乎与用户数量呈线性关系，而Tree-Aggregate在用户数量较大时计算开销明显小于上述两种安全聚合方法，总运行时间与用户数量呈对数关系。实验表明计算开销随着用户数量N的增加计算开销的增加趋势明显降低，当N=300时Tree-Aggregate将安全聚合的总运行时间提升了近15倍，比同为并行运算的TurboAggregate+快近1.7倍。随着用户数量的增加，计算速度的提升预计将进一步增强。5 结束语O(Nlg2lgNlglglgN)O(lgNlgN)本文提出一个基于二叉树的高效分组安全聚合方法Tree-Aggregate，可以将安全聚合的计算开销从降到量级，其为用户提供的公平性能够激励更多用户参与到联邦学习数据共享过程中。实验对比分析表明，计算开销的增长速率随用户数量N的增加明显降低，当N300时，Tree-Aggregate的总运行时间相较于之前的Turbo-Aggregate方法有近15倍的加速，相较于Turbo-Aggregate+方法有近1.7倍的加速。另外，本文还针对分组不均衡场景，提出了一个随机填充算法解决单一用户导致的隐私泄露问题。最后，Tree-Aggregate还融入了格密钥交换算法为联邦学习提供了抗量子攻击的能力。同样的，Tree-Aggregate也拥有与Turbo-Ag-gregate相同的去中心化能力和用户退出安全保证。这不是本文的重点，但Tree-Aggregate仍然可以通 图 5 运行时间对比分析2552电 子 与 信 息 学 报第 45 卷过拉格朗日编码算法恢复出掉线用户的数据，不过这会一定程度上增加联邦学习的通信开销。下一步，本文会从两个方面展开研究。第一，为Tree-Aggregate安全聚合方法添加差分隐私噪声保护全局模型的安全性。将安全多方计算和差分隐私结合形成混合安全聚合方法能够更好地保护本地模型和全局模型，抵抗恶意用户与服务器之间的共谋攻击。第二，本文认为根据实际的网络拓扑结构，适应性地改变联邦学习的聚合方式，而不局限于二叉树或者链式拓扑结构也是未来值得研究的方向之一。参 考 文 献MCMAHAN B,MOORE E,RAMAGE D,et al.Communication-efficient learning of deep networks fromdecentralized dataC.The 20th International Conference onArtificial Intelligence and Statistics(AISTATS),FortLauderdale,USA,2017:12731282.1IMTEAJ A,THAKKER U,WANG Shiqiang,et al.Asurvey on federated learning for resource-constrained IoTdevicesJ.IEEE Internet of Things Journal,2022,9(1):124.doi:10.1109/jiot.2021.3095077.2周传鑫,孙奕,汪德刚,等.联邦学习研究综述J.网络与信息安全学报,2021,7(5):7792.doi:10.11959/j.issn.2096-109x.2021056.ZHOU Chuanxin,SUN Yi,WANG Degang,et al.Survey offederated learning researchJ.Chinese Journal of Networkand Information Security,2021,7(5):7792.doi:10.11959/j.issn.2096-109x.2021056.3SO J,GLER B,and AVESTIMEHR A S.Turbo-aggregate:Breaking the quadratic aggregation barrier insecure federated learningJ.IEEE Journal on SelectedAreas in Information Theory,2021,2(1):479489.doi:10.1109/jsait.2021.3054610.4SYTA E,JOVANOVIC P,KOGIAS E K,et al.Scalablebias-resistant distributed randomnessC.The 38th IEEESymposium on Security and Privacy(SP),San Jose,USA,2017:444460.doi:10.1109/sp.2017.45.5DIFFIE W and HELLMAN M.New directions incryptographyJ.IEEE Transactions on InformationTheory,1976,22(6):644654.doi:10.1109/tit.1976.1055638.6BONAWITZ K,IVANOV V,KREUTER B,et al.Practicalsecure aggregation for federated learning on user-helddataC.The 30th Annual Conference on NeuralInformation Processing Systems(NIPS 2016),Barcelona,Spain,2016:15.7BONAWITZ K,IVANOV V,KREUTER B,et al.Practical8secure aggregation for privacy-preserving machinelearningC.The 2017 ACM SIGSAC Conference onComputer and Communications Security,Dallas,USA,2017:11751191.doi:10.1145/3133956.3133982.MONZ T,NIGG D,MARTINEZ E A,et al.Realization ofa scalable Shor algorithmJ.Science,2016,351(6277):10681070.doi:10.1126/science.aad9480.9ALKIM E,DUCAS L,PPPELMANN T,et al.Post-quantum key exchange:A new hopeC.The 25th USENIXConference on Security Symposium,Austin,USA,2016:327343.10FRANCESCHETTI M and MINERO P.Elements ofinformation theory for networked control systemsM.COMO G,BERNHARDSSON B,and RANTZER A.Information and Control in Networks.Cham:Springer,2014:337.doi:10.1007/978-3-319-02150-8_1.11BELL J H,BONAWITZ K A,GASCN A,et al.Securesingle-server aggregation with (poly)logarithmicoverheadC.The 2020 ACM SIGSAC Conference onComputer and Communications Security,New York,USA,2020:12531269.doi:10.1145/3372297.3417885.12CHOI B,SOHN J,HAN Dongjun,et al.Communication-computation efficient secure aggregation for federatedlearningJ.arXiv:2012.05433,2020.13FEREIDOONI H,MARCHAL S,MIETTINEN M,et al.SAFELearn:Secure aggregation for private federatedlearningC.2021 IEEE Security and Privacy Workshops(SPW),San Francisco,USA,2021:5662.doi:10.1109/spw53761.2021.00017.14HE Chaoyang,ANNAVARAM M,and AVESTIMEHR S.Group knowledge transfer:Collaborative training of largeCNNs on the edgeJ.arXiv:2007.14513,2020.15HE Chaoyang,LI Songze,SO J,et al.FedML:A researchlibrary and benchmark for federated machine learningJ.arXiv:2007.13518,2020.16DALCN L,PAZ R,and STORTI M.MPI for pythonJ.Journal of Parallel and Distributed Computing,2005,65(9):11081115