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

Efficient Grouping Secure Aggregation Method Based on Binary Tree

安全聚合是联邦学习安全共享过程中确保本地模型聚合安全性和隐私性的关键环节。然而,现有方法存在计算开销大、公平机制差、隐私泄露、无法抗量子攻击等问题。为此,该文提出一种基于二叉树的高效分组安全聚合方法(Tree-Aggregate)。首先,基于二叉树构建用户分组安全通信协议将计算开销从O(Nlg^(2)lg Nlglglg N)降到O(lg Nlg N)量级,并通过均匀分摊机制保证了用户计算开销的公平性;然后,提出一种分组不均衡场景下的随机填充算法,解决单一用户引起的隐私泄露问题。最后,该文通过融入格密钥交换协议,为Tree-Aggregate方法增加了抗量子攻击的能力。通过理论分析,Tree-Aggregate将计算开销的增长速率由线性级别变为对数级别,并通过实验对比分析表明,当用户数量N≥300时计算开销相较于现有方法减小了近15倍。

Secure aggregation is a key step to ensure the security and privacy of local model aggregation in federated learning security sharing.However,the existing methods have many problems,such as high computational 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 in this paper.Firstly,the binary tree based user group security communication protocol can reduce the computation cost from O(Nlg^(2)lg Nlglglg N)to O(lg Nlg N)magnitude and ensure the fairness of the computation cost through the uniform allocation mechanism.Then,a random padding algorithm is proposed to solve 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,and through experimental comparative analysis,when the number of users N≥300,computation cost is reduced by nearly 15 times compared with existing methods.