基于同态加密与RingAllreduce的去中心化联邦学习

张斯杰

摘要：联邦学习为解决数据的使用权与所有权分离问题提供了一种可能的解决方案，但其依赖一台中央服务器来编排训练过程，并接收全部客户端的贡献，对网络带宽要求高，并易造成单点故障或隐私泄露。该文通过引入RingAllreduce算法构建联邦学习框架，提出了一套去中心化联邦学习网络，同时引入了STC三元稀疏算法和同态加密，在多数据节点场景下实现了隐私数据保护与联邦学习模型更新，有效提升了通信性能与联邦学习系统的安全性。

关键词：同态加密;去中心化;联邦学习;分布式;RingAllreduce

中图分类号：TP311      文献标识码：A

文章编号：1009-3044（2021）34-0025-03

由于云计算和云服务的便利性和灵活性，越来越多的用户选择将他们的本地数据迁移到基于云的服务器，以此来节省本地数据管理费用和系统维护费用。由于数据存储在用户物理控制之外的云中，云服务器管理员和非法用户（如没有访问权限的黑客）可能会试图访问数据，试图获取其中的信息，这可能导致数据信息和用户隐私的泄露。因此，在数据所有权和使用权分离的情况下，研究满足当地法律且合规的数据共享与使用方案，在当前隐私与数据保护日益受到各个国家重视的背景下具有重要意义。联邦学习[1]在当前场景下提出了一种可能的解决方案。

同态加密[2]是在机器学习与外包计算中最广泛使用的数据保护技术，因为它支持代数运算，包括对密码文的加法和乘法。如果一种加密方法支持加法或乘法运算，则称为部分同态加密，如果它支持无限多的加法和乘法运算，则称为完全同态加密。

本方案基于联邦学习与同态加密，针对云计算环境下的数据共享与数据使用构建方案。本方案研究结果有助于解决复杂分布式场景中云计算应用端云环境下的数据所有权与使用权分离造成的隐私保护问题，有效利用了网络带宽并解决了单点故障问题，对安全性进行了证明，对进一步推进联邦学习在实际环境下的算法验证与应用落地有研究价值与重要意义。

1 知识基础

1.1 联邦学习

联邦学习算法中，每个客户端均基于其本地数据独立地计算当前模型的更新，并将此更新传达给中央服务器，在中央服务器上，客户端的梯度更新被汇总以计算出一个新的全局模型。在这种情况下，移动通信设备，如手机是典型的客户端，它可以提高通信效率，同时确保用户的隐私和安全[3]。Bonawitz K[4]在TensorFlow的基础上实现了针对移动设备的联邦学习框架并部署成功了可拓展的生产系统。Konečný[5]提出对模型量化压缩以实现联邦学习。Yang[6]提出了更全面的联邦学习框架，包括横向联邦学习、纵向联邦学习和联邦迁移学习。Liu[7]在联邦学习与XGBoost上设计了一系列协议与方案，并证明具有一定安全性和高效性。

模型训练过程如图1所示：

1）客户端Ci本地存儲有私有数据集Di，通过全局参数[θ]与Di训练模型获取梯度向量 [gi]：

[gi=Trainθ， Di]                             （1）

2）中央服务器接收各个梯度向量 [gi]

3）将中央服务器每个获得的梯度向量聚合：

[gs=i=1ngi]                                            （2）

4）获得更新全局模型所需要的聚合梯度向量[gs]，将其广播给Ci，然后用户使用[gs]更新本地模型。

[θ←θ− αmgs]                                             （3）

其中（3）式中，α是学习率。

经过一个周期的训练，客户端验证本地模型是否满足准确性要求。如果满足要求，则终止流程，并输出本地训练后的模型;如果不满足要求，则继续迭代训练下一轮，直到满足要求。

1.2 同态加密

同态加密（Homomorphic encryption）是一种允许直接对密文进行操作的可计算加密技术。云服务中计算方根据密文完成计算后，数据拥有方解密该密文计算结果，即可获得对应明文的运算结果。如果一种同态加密方法支持计算方对加法或乘法运算，则称为部分同态加密，如果它支持无限多次的加法和乘法运算，则称为全同态加密。在不损失安全性和正确性的前提下，同态加密满足了多方分别使用公钥和秘钥对信息进行加密和解密。

同态加密的概念最初提出用于解决云计算等外包计算中的数据机密性保护问题，防止云计算服务提供商获取敏感明文数据，实现“先计算后解密”等价于传统的“先解密后计算”。随着区块链、隐私计算等新兴领域的发展及其对隐私保护的更高要求，同态加密的应用边界拓展到了更为丰富的领域[8]。

1.3 RingAllreduce

RingAllreduce[9]是一种针对分布式场景下多client场景进行数据交换与梯度融合的算法，常被用于gpu集群，在有限带宽场景下有力地解决了网络瓶颈的问题。

如图2所示，client以环状组成去中心化网络，每个 client 在Scatter Reduce 阶段，接收 N-1 次数据，N 是client 数量;每个client在allgather 阶段，接收 N-1 次 数据;每个 GPU 每次发送 K/N 大小数据块，K 是总数据大小;所以，Data Transferred=2（N−1）*K/N ，随着 client数量 N 增加，总传输量恒定。也就是理论上，随着client数量的增加，Ring Allreduce有线性加速能力。

2 安全去中心化联邦学习系统

2.1 数据传输

本文所面对的场景中各个节点与信道都存在攻击可能，因此整个数据传输与梯度聚合过程中需要通过同态加密进行隐私保护。但同态加密会导致所需要传输的带宽压力增加，并且在联邦学习训练过程中，如果將全部梯度参数都进行同步，在梯度参数多的场景下，将占用大量的通信资源，成为系统性能的瓶颈。因此我们在数据传输中引入了稀疏三元压缩（STC）[10]算法，STC扩展了现有的top-k梯度稀疏化的压缩技术，用一种新的机制来实现对数据传输中数据的压缩，更好地利用了通信资源，并一定程度上解决了同态加密所需传输带宽较高的问题。具体来说，每个本地模型计算出梯度g之后，首先将梯度向量中的元素的绝对值应用top-k算法，获取绝对值最大的k个梯度，之后将这选出的 k 个梯度值量化为包含[−μ，0，μ]的三元张量。

在当前应用场景中，本方案设计了改进后的基于Paillier与STC的同态加密算法，实现了密钥生成、加密算法、解密算法与密文运算，在去中心化联邦学习场景下保护隐私数据不被恶意用户或服务端泄露。

a） 密钥生成：

随机独立选择两个大素数p，q，满足公式（4）

[gcdpq，p−1q−1=1]                  （4）

[计算n=pq， λ=lcm（p−1，q−1）]

[取g∈Z∗n2]

[计算μ=（Lgλ mod n2）−1 mod n]

最终得到公钥[pk = n，g， 私钥sk=（λ， μ）]

b）加密：

假设要加密的张量三元组为[m]，随机独立选择一个整数[r]

计算出密文[c= gm∙rn mod n2]

c） 解密：

需要解密的密文为c

明文公式为[m=Lcλ mod n2∙μ mod n]

d）密文运算

[DEm1， r1∙Em2， r2 mod n2=m1+m2  mod n]（5）

本方案将随机数[g]取值为[n+1]，根据二项式定理，将加密运算中的模指数运算简化为了一次模乘，加速了加密过程。

2.2方案设计

在本文所涉及场景中，我们希望基于一致性哈希环状组网方式，实现联邦学习网络中数据节点以地位对等的环状扁平化拓扑结构互相连通与交互，每个节点均承担联邦学习中服务器端所需的网络路由与梯度更新职责，最终摆脱联邦学习里中心服务器对系统的束缚，避免中心服务器带宽瓶颈、单点故障与隐私泄露，实现基于RingAllreduce的去中心化联邦学习系统。

整体架构如图3所示，首先所有客户端广播自己位置与IP，通过对IP进行一致性哈希进行环状组网。之后选举一个承担解密工作的client，生成加密公钥与私钥，并将私钥广播给所有客户端。用户在本地读取私有数据，并训练模型。在基于RingAllreduce梯度更新与聚合场景中，利用基于STC向量化的同态加密算法，对各个客户端私有数据进行加密，防止好奇客户端窃取其他客户端数据，并保证了数据的准确性与模型的有效性。最终由解密client将解密后梯度广播给所有client，完成一轮训练。详细训练过程如下：

输入：各个模型私有数据[dn]，待训练模型[θ]

输出：训练完毕的模型[θ]

①各个client依靠对IP一致性哈希进行环形组网;

②基于raft执行选主，最终选出leader client [c0]作为解密client;

③[c0]生成同态加密公钥私钥，将公钥广播给网络内所有client;

④[cn]获取本地数据[dn]，结合当前待训练模型[θ]进行训练;

⑤使用STC稀疏三元算法压缩选择并量化梯度元素，利用公钥将量化后梯度数据加密;

⑥运行RingAllreduce算法将加密后梯度元素数据进行汇总并求和;

⑦[c0]运行解密算法获取最终梯度[gs]，广播给网络里所有client;

⑧client使用[gs]更新本地模型

⑨若未达到要求，由②进行下一轮训练，或者达到模型要求，停止训练

3 实验

本文选用数据集为美国国家标准与技术研究院收集整理的大型手写数字数据库（Mixed National Institute of Standards and Technology database，简称MNIST），该数据集包含60，000个用于培训的示例和10，000个用于测试的示例。 这些数字已经标准化，并以固定大小的图像（28x28像素）为中心，其值为0到1。为简单起见，每个图像都被展平并转换为784个特征（28 * 28）的一维 numpy数组）。

本文使用预测准确率（Acc）、传输数据量开销（Vol）以及训练总时间（Time）评判模型的有效性。

结果表明，与传统的有中心联邦学习方案相比，基于RingAllreduce的去中心化联邦学习模型在执行速度和模型准确度有微小损失的前提下，大大降低了中心服务器的带宽开销，同时一定程度上加快了训练速度。在引入STC三元稀疏梯度算法后，我们对梯度向量进行同态加密并引入了加密解密步骤，在引入一定时间与传输数据量的基础上实现了对用户隐私数据的保护。

4 结束语

联邦学习作为解决数据安全与隐私保护下的端云场景应用起到了重要的作用，但其在工业场景中经常由于中心服务器带宽瓶颈影响训练效率与横向拓展，以及在梯度数据泄露时用户隐私数据也会受到威胁。本文提出了基于同态加密与RingAllreduce的去中心化联邦学习模型，利用STC稀疏压缩算法在不影响模型准确性的前提下提升了同态加密效率与数据传输效率，通过使用RingAllreduce实现了去中心化架构，在摆脱单点依赖的同时，有效提升了通信性能与联邦学习系统的安全性。未来的工作重点应当着重研究进一步提升同态加密与联邦学习的效率。

参考文献：

[1] Yang Q，Liu Y，Cheng Y，et al.Federated learning[J].Synthesis Lectures on Artificial Intelligence and Machine Learning，2019，13（3）：1-207.

[2] Gentry C.Fully homomorphic encryption using ideal lattices[C]//Proceedings of the 41st annual ACM symposium on Symposium on theory of computing - STOC '09.May 31-June2，2009.Bethesda，MD，USA.New York：ACMPress，2009：169-178.

[3] Li T，Sahu A K，Talwalkar A，et al.Federated learning：challenges，methods，and future directions[J].IEEE Signal Processing Magazine，2020，37（3）：50-60.

[4] Bonawitz K，Eichner H，Grieskamp W，et al.Towards federated learning at scale：system design[EB/OL].2019

[5] Konečný J，McMahan H B，Yu F X，et al.Federated learning：strategies for improving communication efficiency[EB/OL].2016：arXiv：1610.05492[cs.LG].https：//arxiv.org/abs/1610.05492

[6] Yang Q，Liu Y，Chen T J，et al.Federated machine learning[J].ACM Transactions on Intelligent Systems and Technology，2019，10（2）：1-19.

[7] Liu Y，Ma Z，Liu X M，et al.Boosting privately：privacy-preserving federated extreme boosting for mobile crowdsensing[EB/OL].2019

[8] 李顺东，窦家维，王道顺.同態加密算法及其在云安全中的应用[J].计算机研究与发展，2015，52（6）：1378-1388.

[9] Sergeev A，Balso M D.Horovod：fast and easy distributed deep learning in TensorFlow[EB/OL].2018

[10] Sattler F，Wiedemann S，Müller K R，et al.Robust and communication-efficient federated learning from non-i.i.d.data[J].IEEE Transactions on Neural Networks and Learning Systems，2019，31（9）：3400-3413.

【通联编辑：光文玲】