基于二叉树的高效分组安全聚合方法.pdf
《基于二叉树的高效分组安全聚合方法.pdf》由会员分享,可在线阅读,更多相关《基于二叉树的高效分组安全聚合方法.pdf(8页珍藏版)》请在咨信网上搜索。
1、基于二叉树的高效分组安全聚合方法孙 奕 周传鑫*汪德刚 杨 帆 高 琦(信息工程大学密码工程学院 郑州 450001)ONlg2lgNlglglgNO(lgNlgN)摘 要:安全聚合是联邦学习安全共享过程中确保本地模型聚合安全性和隐私性的关键环节。然而,现有方法存在计算开销大、公平机制差、隐私泄露、无法抗量子攻击等问题。为此,该文提出一种基于二叉树的高效分组安全聚合方法(Tree-Aggregate)。首先,基于二叉树构建用户分组安全通信协议将计算开销从降到量级,并通过均匀分摊机制保证了用户计算开销的公平性;然后,提出一种分组不均衡场景下的随机填充算法,解决单一用户引起的隐私泄露问题。最后,该
2、文通过融入格密钥交换协议,为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 C
3、huanxin 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.H
4、owever,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 binar
5、y 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.Fin
6、ally,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,w
7、hen 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。安全聚合是一种解决联邦学习中数据安全与隐私保护问题的关键技术,它通过密码技术、差分隐私技术保护用户的本地模型,使得
8、半诚实的服务器无法获知真实的用户模型,同时恶意用户也无法通过与服务器共谋的方式窃取联邦学习中其他用户的隐私信息。O(N2)但是,安全聚合方法需要用户之间维持着大量的开销负担,这对于资源受限的用户来说是无法忍受的。特别是在百万量级的移动设备中2,设备开销随着用户数量N的增加呈指数级增长,过高的开销成为联邦学习发展的瓶颈之一。目前有3种降低开销的方式3:(1)算法优化:针对数据类型优化模型训练算法;(2)压缩:压缩模型数据大小;(3)结构优化:分层、分级、分组调整联邦学习系统架构。它们分别从不同的维度去解决联邦学习中的开销难题,其中结构优化作为解决大规模联邦学习开销问题的有效方法受到了大量研究者的
9、关注。另外,在安全聚合协议中系统整体开销和用户 收稿日期:2022-06-07;改回日期:2022-09-04;网络出版:2022-09-07*通信作者:周传鑫zhou_第45卷第7期电 子 与 信 息 学 报Vol.45No.72023年7月Journal of Electronics&Information TechnologyJul.2023公平性之间往往难以取得有效的平衡。因此,保证用户之间开销的公平性也是联邦学习安全聚合的重点关注问题之一。同时随着量子时代的到来,基于大数分解困难问题的密钥交换算法已经无法满足新的安全需求,联邦学习系统迫切需要一种能够抗量子攻击的密钥交换算法作为安全聚
10、合方法的基础。O(N2)O(Nlg2lgN lglglgN)L 1logLSo等人4提出一种逐层累加的链式拓扑结构(Turbo-Aggregate),通过分层分组的安全通信协议将用户的计算开销从降到量级,在保护用户隐私安全的前提下减少了用户的计算负担。为了进一步提升时间效率,So等人4还提出了增强版的并行运算协议Turbo-Aggregate+,使得位于同一层的用户组能够并行通信,将安全聚合协议的执行步骤从降到量级,减少了协议的运行时间。但是,Turbo-Aggregate+协议的计算开销随着层级的增加而增加,这样的开销分配对高层级用户是不公平的,而没有公平的开销机制也就无法吸引更多拥有优质数
11、据的用户参与联邦学习。另外,So等人并没有考虑用户分组不均衡场景下的隐私安全问题,这可能会导致单一用户组的本地模型泄露。对此,本文提出一种基于二叉树的高效分组安全聚合方法(Tree-Aggregate),基于二叉树构建用户分组安全通信协议有效降低了用户计算开销,保证协议内部用户开销的公平性,同时还提出了一种分组不均衡场景下的随机填充算法,解决单一用户引起的隐私泄露问题。另外本文还在用户与服务器中间融入了格密钥交换协议,为联邦学习系统增加了抗量子攻击的能力。本文主要的研究工作如下:O(Nlg2lgNlglglgN)O(lgNlgN)(1)设计了一个基于二叉树的高效分组安全聚合方法Tree-Agg
12、regate,基于二叉树构建用户分组安全通信协议将用户的计算开销从降到量级,并通过均匀分摊机制保证了用户计算开销的公平性。(2)设计了一种分组不均衡场景下的随机填充算法,通过随机筛选填充用户传递聚合模型,无需消耗计算资源解决单一用户引起的隐私泄露问题。(3)融入了格密钥交换协议,为联邦学习系统提供了抗量子攻击的能力。(4)通过理论分析,Tree-Aggregate将计算开销的增长速率由线性级别变为对数级别,并通过实验对比分析表明,当用户数量N 300时计算开销相较于现有方法减小了近15倍。2 方案设计本节详细介绍了基于二叉树的高效分组安全聚合方法Tree-Aggregate,其主要由4个部分组
13、成。(1)Tree-Aggregate能够保证联邦学习安全共享过程中本地模型的安全性和隐私性,图1展示了方法在联邦学习中的整体应用。(2)展示了基于二叉树建立的分组安全通信协议从用户层到服务器层的数学推导过程,证明了方法的安全性。(3)针对用户分组不均衡的场景,提出一种随机填充算法在组内增加若干虚拟用户,解决单一用户引起的隐私泄露问题。(4)Tree-Aggregate融入了格密钥交换协议为联邦学习增加抗量子攻击的能力。2.1 系统结构Tree-Aggregate利用一个基于二叉树的聚合策 图 1 系统结构(N用户被划分到H层L组二叉树拓扑中)第7期孙 奕等:基于二叉树的高效分组安全聚合方法2
14、547 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)单用户组随
15、机填充;(6)交互聚合模型;(7)挑选最终组;(8)上传服务器解密;(9)下一轮更新。Tree-Aggregate作为安全聚合方法,能够帮助联邦学习更好地保护用户隐私安全,降低计算开销,保证公平性,防止隐私泄露,提升系统抗量子攻击能力。Tree-Aggregate规定所有的用户在聚合阶段都按顺序执行,位于二叉树叶子节点用户将自己的训练模型加上掩码后逐层上传至根节点用户组中。在这里,Tree-Aggregate能够在掉线用户不超过N/2的情况下利用拉格朗日编码添加冗余恢复掉线用户数据,细节内容请参见文献4的.C节。为保护根节点用户的隐私安全,最终用户组的训练模型并不能直接上传给服务器,Tree-
16、Aggregate在最后增加了虚拟步骤。当聚合阶段完成后,从所有的用户中随机选择一组用户作为最终组,其聚合与秘密分享逻辑和用户组保持一致。Tree-Aggregate保证任何一方(用户或服务器)都不能学习单个模型或模型子集的部分聚合。除了所有用户的最终聚合模型外,服务器什么也学不到,这是通过秘密共享掩盖单个模型实现的,本文将在下面描述这一点。2.2 基于二叉树的分组安全通信协议uiuiri,jri,jTree-Aggregate使用秘密分享掩盖单个用户模型,以保护其隐私,防止联邦学习各方之间潜在的共谋。这需要两个步骤来完成。在第1步中,服务器与每个用户协商出一个随机密钥作为掩码,表示用户i的掩
17、码值。仅由服务器和相关用户知道,因此只要服务器是诚实的,它就可以保护用户的隐私安全,防止其余用户通过共谋攻击联邦学习的聚合模型。但是,如果服务器与恶意用户共谋,泄露特定用户的随机掩码则可能破坏联邦学习的安全性。为了保护用户隐私不受此类场景的影响,在第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中被两层掩码保护的
18、本地模型,为了在根节点的聚合中抵消所有的独立掩码,在所有的中。不仅能够保证用户的隐私安全,同时也能够保证聚合的准确性,使独立掩码抵消后与原始数据聚合相等。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表示叶子节点特定组中的用户
19、,另外设定初始聚合时=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
20、+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)中还包含独立掩码,。而根据对独
21、立掩码的定义,,,如图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)中获得最终的聚合值,并删除服务器掩码。如果在协议执行期间没有用
22、户退出,那么这种方法可以很好地工作。另外,如果有任何用户掉线,随机掩码的存在导致聚合无法得到准确的结果,推荐使用拉格朗日编码算法4解决掉线问题。2.3 不平衡分组场景下的随机填充算法Nl 2Nl1Nl 2Nl=1 si xi,jri,jri,j在一些联邦学习场景下,用户数量无法按照预定的方式分组,例如当用户数量恰好是质数时,无论以哪种分组方式都无法保证用户被公平地划分到用户组中,如图3所示。同时,为了考虑联邦学习公平性与正向激励,服务器不能剔除部分用户以满足分组要求。在本方法中,这种分组结果导致二叉树是非平衡的。本文考虑两种场景,一种是所有组内的用户数量,一种是部分组内用户数量。当时,Tree
23、-Aggregate能够按照3.2节中约定的方式完成联邦学习,同时保证用户隐私的安全性。但是当时,该组叶子节点的两个用户组在逐层上传,时,本该防止服务器与恶意用户共谋的独立掩码失去作用。由于根节点组中只有1个用户,独立掩码无法通过秘密分享的方式分别传递给多个用户,从而无法保护叶子节点组用户的隐私安全。Nl=1 s(h)x(h)r(h)为了解决这类问题,本文提出一种添加虚拟用户的方法增强二叉树的平衡性。为此,任意选择一些用户作为虚拟用户填充的用户组,使其再次参与到联邦学习的安全聚合中。不过这些虚拟用户仅仅负责接收和上传聚合变量,并不会再次传输用户的本地模型。因此,虚拟用户不需要再与上层根节点组用
24、户交互独立掩码。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)
25、j,iNl=1从式(8)中得,h1层独立掩码在h+1层被抵消且并不会泄露任何用户的隐私信息。综上,通过添加虚拟用户增强二叉树平衡性的方式能够有效解决时叶子节点用户组隐私泄露问题。2.4 格密钥交换迪菲-赫尔曼(DiffieHellman,DH)密钥交换方案是由Diffie等人6于1976年提出的公钥密码方案,其被广泛应用于联邦学习的安全聚合方案中4,7,8。但是在Monz等人9提出了Shor量子算法后,量子计算机的出现使得基于大整数分解、离散对数等传统困难问题的方案可以在多项式时间内解决,这同样也威胁了以DH密钥交换方案为基础的安全聚合的安全性。因此,本文基于环上容错学习(Ring-Learn
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 二叉 高效 分组 安全 聚合 方法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。