随着物联网(Internet of things, IoT)、大数据及机器学习的发展，基于深度学习的技术为我们带来很多便利[1-2]：IoT可以通过传感器设备快速收集环境中的数据，同时具有计算能力的IoT设备可以随时随地参与移动计算[3]；5G可以加快数据的传输速度[4]；移动计算能提供大量的数据处理单元处理数据[5].然而在这些技术发展的背后，大规模的隐私敏感数据正在被泄露.当客户端将数据传输至服务器进行处理时，数据所有权与控制权分离将导致客户端数据有泄露的风险.为了弥补集中式学习带来的隐私泄露问题并充分利用IoT设备收集到的数据，Google于2016年提出了联邦学习(federated learning, FL)[6].客户端在本地训练好数据模型后，只需要将模型参数传递给服务器进行聚合即可，原始数据不离开本地，从而保证了客户端数据的隐私与安全.

然而，近些年的研究发现联邦学习框架中传输的梯度仍然会泄露隐私信息，甚至泄露原始数据[7-8].鉴于此，出现了许多梯度安全聚合的技术，主要包括采用差分隐私(differential privacy, DP)、同态加密(homomorphic encryption, HE)及安全多方计算(secure multi-party computation, MPC)等.但是它们仍然存在各种各样的问题，比如：差分隐私中如何平衡模型准确率及隐私保护是个巨大的挑战；同态加密的计算及通信代价比较高；虽然安全多方计算被广泛用于联邦学习，但标准的安全多方计算算法会存在较大的通信消耗.特别地，McMahan等人[9]指出联邦学习的最大瓶颈是梯度传输过程中产生的大量通信，而基于安全多方计算提供的隐私保护又需要额外的通信代价.在实际应用中，特别是资源受限的设备，难以承受如此巨大的通信负担，故通信时梯度的压缩需要被考虑.因此，深入研究能适用于资源受限环境的、通信高效、有隐私保护且有较好模型性能的算法非常有必要.

为了解决联邦学习中隐私泄露存在的问题，本文完成了2方面的工作：

1) 本文结合压缩感知、1比特压缩感知及安全多方计算中的加法秘密共享技术的优点，提出了2个通信高效的联邦学习算法，使用Top-K稀疏及压缩感知技术同时减少了联邦学习框架中上传和下放数据的通信开销，再利用加法秘密共享技术进一步增强重要梯度参数的隐私性.与现有工作相比，本文算法在降低通信开销的同时保证了数据传输及聚合时的安全.

2) 在常用数据集上进行的图像分类实验结果表明，与近期最新的相关算法[10]CS_FL和CS_FL_1bit以及基线算法FedAvg[9]和SignSGD[11]相比，本文的算法实现了通信开销、隐私保护及模型效率三者的有效平衡.

1 相关工作

本节主要介绍有关联邦学习隐私保护及梯度压缩的现有方案.

1.1 联邦学习隐私保护

为了保证联邦学习框架中模型梯度在传输和聚合时的安全性，现有的方案主要基于3种技术：1)差分隐私；2)同态加密；3)多方安全计算.

差分隐私技术是一种基于噪声机制的数据失真隐私保护技术，在联邦学习训练过程中，通过对需要保护的参数进行噪声扰动，使攻击者无法获取真实参数[12-14].一般情况下，添加的噪声主要是拉普拉斯分布或者高斯分布的噪声.例如，用f(d′)f(d)+来定义拉普拉斯机制，其中用具有拉普拉斯分布的噪声去实现ε差分隐私.但是在基于差分隐私的联邦学习中，隐私预算ε越低，添加的噪声越大，隐私保护程度越强，然而却降低了数据的可用性.如何去平衡隐私与可用性是差分隐私需要考虑的问题.此外，与同态加密及安全多方计算相比，差分隐私无法保证参数在传输过程中的隐私性[15].

同态加密是一种能在密文状态下也可进行复杂计算的加密方法[16-17].Aono等人[18]在逻辑回归的训练过程中使用同态加密保护数据，通过存储及计算复杂度，表明该方法可应用于大规模联邦学习.Hayashi等人[19]提出了一种加同态加密方法，在该方法中，只有拥有解密密钥的参与者才可对更新后的全局模型解密，但其计算代价比较高.Chai等人[20]基于Paillier同态加密实现了安全联邦矩阵分解，但该方法要求客户端必须诚实.虽然同态加密能达到很好的隐私保护效果，但其效率的局限性导致其难以应用于资源受限的环境中.

安全多方计算允许在无可信第三方的情况下设计一个函数，使互不信任的各方在不泄露其原始数据的情况下得到安全输出[21-23]，因此非常适合联邦学习框架中梯度安全聚合的场景.安全多方计算的方式有多种，但考虑到设备资源受限的问题，无法承担混淆电路等方法带来的计算及通信压力，于是本文使用安全多方计算中的加法秘密共享来对数据保密.相比于差分隐私及同态加密，基于安全多方计算的分布式学习[24-26]有较多优势：与基于差分隐私的分布式学习相比，基于安全多方计算的方式不会影响模型聚合精度，也不需要考虑可用性与隐私的平衡；与基于同态加密的分布式学习相比，使用基于加法秘密共享的安全多方计算需要所有客户端联合或一定数量客户端联合[27]才可重构数据，但基于同态加密的方式安全多方计算一般需要假设计算方诚实.

1.2 联邦学习梯度压缩

如引言所述，联邦学习中最大的瓶颈是梯度传输过程中产生的大量通信负载，且随着参数数量的上升，通信开销越来越大.若要用于资源受限的环境，梯度压缩是必要的.针对联邦学习通信开销大的问题，研究者们提出了许多梯度压缩机制，目前主要有3种方式：1)稀疏；2)量化；3)压缩感知.

基于稀疏的梯度压缩方式有多种，Yin等人[28]提出只传输大于某阈值的梯度给服务器，以此减少通信量.Heafield等人[29]提出另一种方式，将梯度进行排序后仅传输前P%的梯度给服务器，其他的存入残差向量.但这些梯度稀疏的压缩只考虑到减少客户端上传局部模型梯度的通信量，未考虑到服务器下发全局模型梯度的通信量.

基于量化的梯度压缩可以压缩联邦学习框架中上传及下发的通信量.最经典的方式是Bernstein 等人[30]提出的1比特量化，客户端只需要上传局部模型梯度的符号给服务器，从而让通信消耗减少了32倍.但Sattler等人[31]指出在非独立同分布(non-independent identically distributed, non-IID)数据集上性能显著下降的问题，并提出稀疏三元化压缩，在梯度传输前通过稀疏、三元化及编码方式对梯度压缩.但是这些量化方式都较为粗糙，导致信息大量丢失，且在non-IID上性能降低较为明显.

相比于传统压缩，压缩感知(compressed sensing, CS)可通过远低于经典的Nyquist采样定理要求的采样频率恢复信号.其大致思想是用满足一定条件的测量矩阵将稀疏或可压缩的高维信号投影到低维空间，然后通过求解一个优化问题高概率恢复信号[32].由于压缩感知的这些优点，其广泛用于信号处理领域，但几乎没有用于联邦学习中.Li等人[10]将压缩感知应用于联邦学习中，并在通信效率及模型准确性上表现出较好的性能.然而文献[10]中的算法每一轮训练均包含2个阶段，且2个阶段都需要客户端与服务器交互，从而造成额外的通信负担.此外，文献[10]将压缩测量值直接传递给服务器，虽然经过压缩感知后的测量值具有一定的安全性[33-34]，但Chen等人[35]指出通过测量值依然会泄露隐私信息.基于上文所述联邦学习存在的瓶颈问题及文献[10]存在的问题，本文提出2个通信高效的适用于资源受限环境的联邦学习，并基于加法秘密共享对传输的重要梯度测量值加密以进一步保证隐私性.

2 基础知识

2.1 联邦学习

联邦学习本质上是一种分布式机器学习框架，可在保障数据隐私安全及合法合规的基础上实现数据共享，共同建模[6].基本框架表述为：假设联邦学习中参与方有n个客户端和1个参数聚合服务器，每个客户端Ci拥有本地的数据集Xi，i=1,2,…,n.在模型训练的每一轮k∈{1,2,…,T}开始时，服务器发送前一轮的全局模型参数Gk-1给随机选择的m个客户端.每个客户端Ci利用本地的数据集Xi通过最小化损失函数得到局部模型参数随后客户端Ci计算局部模型变化值并发送给服务器.当服务器接收到客户端传来的模型变化值后，服务器计算得到新一轮的全局模型，其中wt为学习率，服务器再将新一轮的全局模型参数Gt+1分发给随机选择的m个客户端.一直迭代该训练过程，直到模型收敛.

2.2 压缩感知

压缩感知是一个将采样与压缩过程融合成单一感知过程的新颖的框架.在该框架中，若原始信号是稀疏或者可压缩的，则可以仅仅通过少量测量值恢复出原始信号[32].

假设x∈N是一个N×1维信号向量，则压缩感知的采样过程可描述为

y=Φx,

(1)

其中y∈M是通过将信号x左乘一个测量矩阵Φ∈M×N得到的测量值向量.若原始信号不是稀疏的，则需要利用稀疏基对原始信号x进行稀疏表示，即x=Ψs，其中Ψ为一个N×N的稀疏基矩阵，且Ψ与Φ不相关.因此，若感知矩阵ΦΨ满足约束等距性，则稀疏信号s可通过解决如下的1最小化问题来重构.

(2)

其中‖·‖1表示1范式.得到稀疏信号后，可通过得到原始信号.

2.3 安全多方计算

安全多方计算是一种不需要可信第三方参与的协议.假设在协议中有n个拥有私有数据D1,D2,…,Dn的参与者P1,P2,…,Pn，参与者可以合作计算公开函数P(D1,D2,…,Dn)，且在满足计算正确性的同时保证私有数据的保密性.安全多方计算的概念最早由Yao[36]于1982年提出.

秘密共享技术是安全多方计算领域中常用的技术之一，由Shamir[37]提出了(t,n)门限秘密共享方案.秘密共享将秘密分成n份然后将份额保存在第i个持有者Pi处，若需

要重构秘密则需要不少于t个份额.该方案满足：

1)少于t个份额时参与者无法得知有关秘密的任何信息；2)任意不少于t个份额就能恢复出秘密出于对安全和性能的综合考虑，本文采用Cramer等人[38]提出的(n,n)门限的高效秘密共享——加法秘密共享.其基本流程具体介绍如下：

秘密共享SecShr: 输入秘密份额数目n、输出n个秘密份额.

1) 随机选择n-1个随机数：

(3)

2) 计算第n个秘密份额：

(4)

秘密恢复SecRec:输入n个秘密份额输出秘密

(5)

因此，只要少于n个秘密份额则不能得到任何关于秘密的信息，任意得到n个秘密份额的用户可以根据式(5)恢复出秘密

3 算法设计

在本节中，基于压缩感知及安全多方计算，针对联邦学习中存在的通信开销大、隐私泄露及设备资源有限等问题，提出了2个基于压缩感知及安全多方计算的安全高效联邦学习算法——ICFM算法和ICFM_1bit算法.下面，首先介绍2个算法的整体框架，接着给出框架内的2个算法的详细步骤.

3.1 算法框架

整体算法框架如图1所示，其中包含本文提出的2个算法ICFM算法和ICFM_1bit算法.两者不同之处主要在于，ICFM算法客户端上传的是被部分加密后的压缩测量值，ICFM_1bit算法上传的是压缩测量值量化后再部分加密的结果.框架中，C1,C2…,Cn代表n个客户端，PS代表参数聚合服务器.由于无线通信环境的服务器带宽有限，只允许少量客户端同时上传数据，因此我们在算法每次迭代前从n个客户端中任意选择m个客户端参与本次迭代计算.在第t轮迭代中，所有客户端最初用相同的模型框架和模型参数Gt初始化，被选择的每个客户端Ci根据本地数据训练出本地模型参数并计算得到模型梯度变化值为了降低梯度传输的通信量，我们采用了稀疏及压缩感知技术得到压缩测量值若进一步减少通信量，我们可以对测量值进一步量化，但通过进一步量化后最终全局模型训练精度会有所下降.另外，为了保证传递的测量值隐私性且尽量减少传输通信负载，我们用加法秘密共享方式对重要的梯度参数(易被攻击的参数)加密后传递给PS.PS对传递过来的参数进行聚合后，将全局参数下发给所有客户端，客户端重构出全局更新参数后，计算得到更新后的模型梯度Gt+1.

3.2 ICFM算法

ICFM算法的伪代码如算法1所示.

算法1. ICFM算法.

输入：初始化的模型参数G0;

输出：优化后的模型参数GT+1.

初始化：假设所有的客户端拥有统一的初始化模型参数G0，残差向量

① for t=0,1,…,T do

② 随机选择集合M⊆C,|M|=m;

③ for 1≤i≤m in parallel do

④

⑤

⑥

⑦

⑧

⑨

⑩

将发送给其他客户端;

Cj接收到后计算

将及发送给服务器;

end for

The server does:

将发送给每

个客户端;

for i∈{1,2,…,I} in parallel do

end for

end for

return GT+1.

每个参与的客户端Ci基于本地的数据集Xi以及当前梯度Gt执行k次梯度下降法得到更新后的局部模型，表达式为

(6)

其中M是在第t轮迭代开始前从n个客户端的集合C中任选m个客户端组成的子集.训练好的局部模型再加上由上一轮稀疏得到的残差得到:

(7)

从而弥补稀疏处理导致的模型精度误差下降问题.基于式(7)计算局部模型变化值

(8)

得到变化值后，若直接将数据传递给PS会造成通信量大的情况，本算法采用先稀疏后压缩的方法降低通信量，稀疏过程采用Top-K算法，将变化值从大到小排序，然后取前K大的数据保存下来，其他的值均置为0，对的稀疏可简单表达为

(9)

其中N.为了防止稀疏化对模型准确率造成负面影响，我们将在稀疏化过程中被置为零的项存入残差向量，并在下一轮的迭代中用于弥补稀疏带来的误差，残差计算公式为

(10)

使用随机测量矩阵ψt∈M×N对稀疏化后的梯度变化值压缩成测量值，此过程表达式为

(11)

为了防止压缩测量值在直接传递给PS的过程中泄露隐私信息，又考虑到基于加法秘密共享的安全多方计算的算法会导致较多的额外通信开销，权衡安全与效率后，本文选择仅加密第一隐藏层的梯度测量值.我们将测量值分成2部分，分别为A类测量值(模型第一隐藏层的梯度测量值)以及B类测量值(模型非第一隐藏层的梯度测量值)：

(12)

客户端Ci将A类测量值分成m个秘密份额：

(13)

基于式(13)生成的秘密份额，客户端Ci将其中的m-1个秘密份额发送给其他m-1个客户端，则此时客户端Cj接收到的秘密份额为将本地秘密份额与接收到的的秘密份额相加得到并用来更新原来的A类测量值公式化表达为

(14)

(15)

基于式(12)～(15)，客户端Ci将更新后的A类测量值及未更新的B类测量值发送给服务器，服务器根据式(16)聚合收到的测量值：

(16)

其中m=|M|.此后，服务器将下发给所有客户端，每个客户端基于及测量矩阵ψt使用IHT算法[39]重构得到

(17)

基于重构的每个客户端更新得到全局模型：

(18)

其中wt为学习率.

3.3 ICFM_1bit算法

ICFM_1bit算法与ICFM算法较为相似，伪代码如算法2所示.被选中的客户端Ci基于本地的数据集Xi以及当前梯度Gt执行k次梯度下降法得到

更新后的局部模型如式(6)所示，接着再加上由上一轮稀疏造成的残差得到式(7)，再计算如式(8)的局部模型梯度变化值随后，基于Top-K算法稀疏得到如式(9)的稀疏值其中再将稀疏过程中置零项的数值存入残差向量如式(10)所示.接着使用随机测量矩阵ψt∈M×N将稀疏化后的梯度变化值压缩为测量值如式(11)所示.然后通过只保留测量值符号位的方法将测量值量化成1 bit的数据，即

(19)

其中sgn(·)为符号函数.与ICFM算法类似，我们将量化后的测量值分为A类量化测量值以及B类量化测量值

(20)

另外，客户端Ci将A类量化测量值分成m个秘密份额：

(21)

基于式(21)生成的秘密份额，客户端Ci将其中的m-1个秘密份额发送给其他m-1个客户端，则此时客户端Cj将本地的份额与接收到的份额相加，得到并用来更新原来的A类量化测量值公式化表达为

(22)

(23)

基于式(19)～(23)的操作，客户端Ci将更新后的A类量化测量值及未更新的B类量化测量值发送给PS，PS通过多数投票的方式对客户端传来的量化测量值进行聚合：

(24)

其中m=|M|.聚合后，服务器将聚合值下发给所有客户端，每个客户端基于及测量矩阵ψt使用BIHT算法[40]重构得到

(25)

基于式(25)，每个客户端更新全局模型：

(26)

其中ut为学习率.

算法2. ICFM_1bit算法.

输入：初始化的模型参数G0;

输出：优化后的模型参数GT+1.

初始化：假设所有的客户端拥有统一的初始化模型参数G0，残差向量

① for t=0,1,…,T do

② 随机选择集合M⊆C,|M|=m;

③ for 1≤i≤m in parallel do

④

⑤

⑥

⑦

⑧

⑨

⑩

将发送给其他客户端;

Cj接收到后计算

将及发送给服务器;

end for

The server does:

将发送

给每个客户端;

for i∈{1,2,…,I} in parallel do

end for

end for

return GT+1.

4 算法分析

本节对本文所提出的算法进行正确性及安全性分析.

4.1 正确性分析

本节中主要对PS是否能够正确得到选择的客户端传来的梯度更新值进行分析.算法2是在梯度测量值量化后做秘密共享，而算法1直接针对梯度测量值做秘密共享，但这2个算法的不同不影响本文使用的秘密共享方法的正确性分析，因此本文使用算法1为例.首先，假设在t轮训练时，每个客户端将A类梯度测量值分为m个秘密份额，则有客户端1将分为客户端2将分为客户端i将分为客户端m将分为若直接将这些数据传输给PS，则PS接收到每个客户端的原始梯度的秘密共享值，可以在PS端根据秘密共享份额恢复出每个客户端真实的更新梯度，即可得到所有客户端A类更新梯度的总和而本算法中，客户端i∈M将发送给其他m-1个客户端，则客户端1拥有客户端2拥有客户端i拥有客户端m拥有客户端将拥有的所有秘密份额的和代替自己的原始A类梯度传递至PS，此时PS将依然得到所有客户端A类更新梯度的总和与客户端传递A类原始梯度得到的更新梯度总和一样.而剩下的B类更新梯度直接传递原始值，故最后服务器可以得到正确的客户端传递的所有梯度测量更新值之和.

4.2 安全性分析

本节主要讨论本文所提算法是否能保证梯度传输及聚合的安全性.如引言所述，压缩感知本身具有安全性[33-34]，但经过压缩感知后的梯度测量值仍然可能由于能量的泄露导致隐私信息泄露.另外，Sotthiwat等人[41]指出，相比CNN中其他层，第一隐藏层中的参数包含更多原始数据信息，更容易泄露隐私信息.因此，为了权衡通信效率与安全，本文只对A类梯度(第一隐藏层梯度)测量值加密.我们不直接传递A类压缩梯度参数，而是将其分成m份秘密份额并将其他m-1份分发给其他m-1个客户端，此时每个客户端仅拥有自己的A类梯度测量值的一份秘密份额，以及m-1份来自其他m-1个客户端的秘密份额.客户端将自己拥有的秘密份额组合起来代替自己原有的A类梯度测量值，并将更新后的A类梯度测量值传递给PS.

首先我们分析仅加密训练网络的第一隐藏层的参数是否可以保证安全性.由于第一隐藏层参数最接近原始图像，且Sotthiwat等人[41]经过实验证明，相比于其他层，第一隐藏层能触发最大的图像均方误差(mean squared error, MSE)，因此其中包含更多的原始图像信息且更为敏感.另外，在对MNIST数据集图片进行训练时，实验证明仅加密网络第一隐藏层参数足以保护图片隐私安全.因此，本文在对已具有压缩感知自身安全性的梯度测量值上，再对易泄露隐私的A类梯度测量值加密，进一步保证了传输梯度测量值的安全性.

其次，我们在半诚实外部敌手攻击情况下或者在算法参与方为半诚实敌手情况下，形式化分析本文所提算法是否能保证A类梯度测量值的安全性.由于所提算法1与算法2中的A类梯度测量值的安全性均基于加法秘密共享，因此我们仅以算法1为例对安全性进行分析.

定理1. 在不超过m-2个客户端及服务器被外部半诚实敌手腐化的前提下，本文所提算法能够保证敌手无法获得关于诚实客户端真实A类梯度测量值的任何信息.

证明. 我们考虑半诚实外部敌手攻击情况.假设在第t轮迭代中，敌手腐化了m-2个客户端及参数服务器的情况.这种情况下，敌手可从服务器得到A类梯度更新测量值的聚合值以及m个客户端传来的A类梯度更新测量值除此之外，敌手还可以知道所有被腐化客户端的真实A类梯度测量值.则敌手计算诚实用户的真实梯度之和，即

(27)

其中honest代表未被腐化的诚实客户端的集合，而corrupted代表被腐化的客户端集合.至少有2个诚实客户端的梯度之和无法得到具体的某个诚实客户端的真实A类梯度测量值.

另外，即使敌手在被腐化客户端中知晓诚实客户端发往腐化客户端的秘密份额，假设诚实客户端q秘密份额组成为此时敌手仅知道其中m-2个秘密份额，其他份额在诚实客户端手中，故亦无法推断出某个诚实客户端q秘密份额真实A类梯度测量值.

证毕.

定理2. 在不超过m-1个客户端合谋的前提下，任意客户端i无法知晓其他客户端的真实A类梯度测量值，服务器无法得到某个具体客户端真实A类梯度测量值.

证明. 我们考虑内部攻击的情况，即参与迭代的客户端与服务器都可能是半诚实敌手.首先考虑半诚实敌手为某个客户端i，在半诚实情况下无法获得诚实客户端j的真实A类梯度测量值，由于客户端i仅知道客户端j测量值的第i份值，即使与其他m-2个客户端合谋，得到其他m-2份客户端j测量值的份额，此时合谋的客户端i拥有

(28)

根据加法秘密共享的性质，由于无法得到客户端j处的第j份秘密份额，则无法获得关于客户端j的真实梯度测量值的信息.

其次，我们考虑服务器为半诚实敌手的情况.服务器从客户端i处得到更新后的A类梯度测量值为

(29)

而客户端i真实的A类梯度测量值为

(30)

因此服务器得到的并不是客户端i真实的A类梯度测量值，而是每个客户端第i份秘密份额之和，故服务器只能最后得到所选m个客户端A类梯度测量值之和，无法得到某个具体客户端真实的A类梯度更新测量值.

证毕.

5 实验与结果

在本节中，我们对本文所提的ICFM算法及ICFM_1bit算法性能进行了分析，主要包括在经典的MNIST数据集[42]与Fashion-MNIST数据集[43]上对图像分类任务准确率的测量，以及在训练时对通信开销的评估，并对比了近期最新的相关算法(CS_FL和CS_FL_1bit)[10]及基线算法(FedAvg和SignSGD)[9,11].实验结果表明，本文所提算法更具优越性.其中ICFM，CS_FL与FedAvg传给服务器的数据均为梯度测量值或者原始梯度值，而ICFM_1bit, CS_FL_1bit与SignSGD传给服务器的数据均为梯度测量值或者原始梯度值的1比特量化数据.为了公平，以下性能分析主要将非1比特与1比特这2类算法分开比较.

我们在Apple M1 CPU with 3.20 GHz 16 GB RAM 平台上进行实验，采用Pytorch作为机器学习训练库,并利用Python3实现安全多方计算、Top-K稀疏以及压缩感知算法.本文采用的CNN模型是一个6层的网络模型，包含2层卷积层、2层池化层及2层全连接层，卷积核的大小均为5×5.数据集MNIST是包含60 000个训练图像及10 000个测试图像的0～9的手写数字，而Fashion-MNIST数据集是包含60 000个训练图像及10 000个测试图像的共10个类别的图像，类别包含T恤、牛仔裤、外套、裙子等.实验中，我们假设一共有100个客户端，通过frac的值调节参与迭代计算的客户端的数量，客户端对图像进行训练时采用动量为0.5的SGD优化器.

5.1 模型准确率

为了比较本文所提算法与现有算法的准确率，我们考虑了在MNIST及Fashion-MNIST数据集上独立同分布(IID)与非独立同分布(non-IID)数据的算法性能.在本文提出的算法上，我们设置稀疏等级l=0.05，压缩率samplerate=0.1，多次测试不同学习率下的算法性能，并选择最优学习率进行实验.

首先，我们在MNIST数据集上客户端参与率Cp=0.3时测试了不同算法的分类准确率.在IID情况下，如图2(a)所示，我们观察到由于FedAvg传输的梯度原始数据未对其数据进行压缩量化，故其分类准确率无疑最高，大概收敛在99%.而SignSGD准确率最低，大概在96.96%，可能由于其未对数据预处理而粗暴量化造成.CS_FL算法与ICFM算法的分类准确率与收敛速度比较接近，CS_FL_1bit算法与ICFM_1bit算法的分类准确率与收敛速度较为接近，但图2(a)左图放大为图2(a)右图，可以发现本文所提的ICFM算法的收敛速度稍快于CS_FL算法，且最后收敛准确率比CS_FL算法高0.2%.同时，本文所提的ICFM_1bit算法比CS_FL_1bit算法的收敛速度稍快且准确率高0.12%左右，但ICFM_1bit算法与CS_FL_1bit算法性能均高于SignSGD的性能.在non-IID情况下，如图2(b)所示，FedAvg准确率最高且收敛速度最快，ICFM算法比CS_FL算法收敛速度稍快且准确率高0.12%.而ICFM_1bit算法性能远好于CS_FL_1bit算法，本文所提ICFM_1bit算法收敛速度明显快于CS_FL_1bit算法且准确率比CS_FL_1bit算法的最高准确率高1.2%，另外CS_FL_1bit算法震荡较大，比基线SignSGD最高准确率高2.7%.另外，我们发现在non-IID情况下，本文提出的ICFM_1bit算法在前期收敛速度略低于ICFM算法，但最后准确率收敛值几乎相同且准确率收敛值非常接近基线FedAvg，表明本文所提的ICFM_1bit算法在MNIST数据集non-IID情况下能在通信代价更低的情况下保证分类准确率与ICFM算法及FedAvg相差不多.

接着，我们在Fashion-MNIST数据集上客户端参与率Cp=0.3时测试了分类准确率.在IID情况下，如图3(a)所示，FedAvg准确率及收敛速度依然最快，但本文提出的ICFM算法收敛速度仅次于FedAvg且最后准确率仅差0.8%，ICFM算法相比于CS_FL算法收敛速度更快且最终收敛准确率高1.8%.与此同时，ICFM_1bit算法相较于CS_FL_1bit算法，收敛速度略快且准确率高1.2%左右，而SignSGD算法依然是所比较算法中收敛速度最慢且准确率最低的一个算法.在non-IID情况下，为了更加清楚地展示实验结果，我们将传递梯度测量值或者原始梯度值的算法ICFM,CS_FL与FedAvg展示在图3(b)中，而将传递梯度测量值或者原始梯度值的1比特量化数据的算法ICFM_1bit,CS_FL_1bit与SignSGD展示在图3(c)中.从图3(b)中我们观察到，ICFM,CS_FL与FedAvg分类准确率曲线走向比较相近，但本文提出的ICFM算法在前期收敛速度略快于CS_FL算法，且准确率高1.3%左右.从图3(c)中我们发现，3个算法振幅都比较大，但本文所提ICFM_1bit算法优于CS_FL_1bit算法及基线SignSGD算法.

图4展示了在MNIST数据集上不同参与率情况下的分类准确率.图4(a)表示在IID情况下不同算法在不同参与率情况下测试准确率.我们发现，当参与率由0.1上升为0.3时，除了SignSGD外，其他算法的准确率均有不同程度的上升，特别是CS_FL_1bit算法上升幅度达到4.7%，表明参与率的值对算法CS_FL_1bit影响最大.图4(b)表示基于non-IID的情况，从中我们发现参与率由0.1变到0.3时，ICFM,CS_FL与FedAvg算法准确率有不同程度的增加，但是ICFM_1bit,CS_FL_1bit与SignSGD算法准确率却有不同程度的下降，这表明在non-IID情况下，相比于参与率为0.3，参与率为0.1更适合于1 bit类型的算法.

5.2 通信效率

由于联邦学习中通信的消耗主要受参与通信的客户端数量、模型参数的个数以及执行算法本身的影响，故本节分别基于5.1节用到的6层CNN网络以及更复杂的VGG16网络[44]测试了在不同算法下的通信消耗.

如图5所示，在6层CNN网络上，由于模型参数较少，总体的通信消耗在参与者个数为64时也少于6 MB，图5左图中FedAvg由于传输的原始梯度没有经过压缩量化等，故通信消耗几乎成指数性增长.本文提出的ICFM算法及ICFM_1bit算法虽然经过秘密共享技术保证重要梯度测量值的安全，然而却带来了额外的通信代价，但由于并没有对所有梯度参数加密，故带来的通信代价可接受，另外，在参与者个数较少时，ICFM算法与CS_FL算法的通信代价几乎相同.并且，未用秘密共享的ICFM算法——ICFM_NMPC在参与者个数为32时比ICFM算法减少了0.1 MB，同时比CS_FL减少了0.01 MB.因此，本文所提ICFM算法未加安全性时比CS_FL高效，增加安全性后通信消耗也可接受.与此同时，我们发现所提出的ICFM_1bit算法随着参与者个数的增加，通信消耗比CS_FL_1bit算法通信消耗更少、通信效率更高.由于本文算法在每轮训练只需要与服务器交互一次，但CS_FL_1bit需要交互2次，故本文所提ICFM算法及ICFM_1bit算法用较少的额外通信消耗收获了更强的安全性，在6层CNN网络上，本文所提算法相比其他算法有较好的性能.

图6为在更为复杂的VGG16网络上针对不同的算法的通信消耗分析.如图6左图所示，本文所提的ICFM算法在较为复杂网络中通信消耗几乎与CS_FL一致，这是由于本文只对第一隐藏层网络进行加密，当网络层数越多，对第一层隐藏网络加密带来的额外通信在总通信的影响会越多.从被放大的图6右图我们发现，本文所提ICFM_1bit算法几乎与未用加密的ICFM_1bit_NMPC算法消耗相近，且ICFM_1bit算法通信消耗随着客户端个数的增加比CS_FL_1bit通信消耗更少，且在客户端个数为64时，比CS_FL_1bit降低大约112.4 MB.

根据图5、图6可以发现本文所提算法在较为复杂的VGG16网络上与其他算法相比，通信效率更高.在稍简单的6层CNN网络上，本文的ICFM_1bit算法通信效率也比其他算法更高，ICFM算法中安全性保证带来的额外通信消耗也可以接受.综上所述，从性能和安全性2方面综合考虑，本文所提2种算法相比其他算法无疑是最优的.

6 总 结

联邦学习中梯度传输造成的高通信代价成为其重要瓶颈之一，特别在资源受限的环境影响更为严重.同时，保障梯度的安全传输与聚合也成为联邦学习中的重大挑战.本文算法结合Top-K稀疏、压缩感知及多方安全计算的优势，在保证梯度传输及聚合安全的情况下大幅度提升了通信效率.但本文工作也有不足之处，由于本文应用于资源受限的环境，出于对安全和性能的综合考虑，本文采用高效的(n,n)加法秘密共享，需要假设被选择的m个客户端能够成功将自己更新后的梯度测量值传递给服务器，暂时未考虑某些客户端出现掉线、损坏等情况，算法鲁棒性不够强.可能的解决方式有：1)寻找较为高效的(t,n)阈值秘密共享代替加法秘密共享，只要服务器接收到不少于t个梯度测量值份额，则可以恢复计算得到A类梯度测量值；2)采用其他密码学方式对A类梯度测量值进行保护，由于在服务器端只能得到所参与客户端A类梯度测量值之和，而不能得到具体某个客户端A类梯度.在未来工作中，我们将进一步考虑算法鲁棒性问题.

作者贡献声明：陈律君设计研究方案，负责实验，撰写初稿；肖迪参与方案讨论、论文修改及最后定稿讨论；余柱阳采集数据、参与实验研究及结果分析；黄会负责采集、分析数据；李敏负责数据分析及调查.

参考文献

[1]Hao Fei, Min Geyong, Chen Jinjun, et al. An optimized computational model for multi-community-cloud social collaboration[J]. IEEE Transactions on Services Computing, 2014, 7(3): 346-358

[2]Qian Wenjun, Sheng Qingni, Wu Pengfei, et al. Research progress on privacy-preserving techniques in big data computing environment[J]. Chinese Journal of Computers, 2022, 45(4): 669-701 (in Chinese)(钱文君, 沈晴霓, 吴鹏飞, 等. 大数据计算环境下的隐私保护技术研究进展[J]. 计算机学报, 2022, 45(4): 669-701)

[3]Savazzi S, Nicoli M, Rampa V. Federated learning with cooperating devices: A consensus approach for massive IoT networks[J]. IEEE Internet of Things Journal, 2020, 7(5): 4641-4654

[4]Loghin D, Cai Shaofeng, Chen Gang, et al. The disruptions of 5G on data-driven technologies and applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2020, 32(6): 1179-1198

[5]Wang Shiqiang, Tuor T, Salonidis T, et al. Adaptive federated learning in resource constrained edge computing systems[J]. IEEE Journal on Selected Areas in Communications, 2019, 37(6): 1205-1221

[6]McMahan B, Ramage D. Federated learning: Collaborative machine learning without centralized training data[EB/OL]. Google Research Blog, 2017 [2022-03-25]. https://ai.googleblog.com/2017/04/federated learning-collaborative.html

[7]Zhu Ligeng, Liu Zhijian, Han Song. Deep leakage from gradients[J]. Advances in Neural Information Processing Systems, 2019, 32 [2022-05-18]. https://proceedings.neurips.cc/paper/2019/file/60a6c4002cc7b29142def8871531281a-Paper.pdf

[8]Zhao Bo, Mopuri K, Bilen H. iDLG: Improved deep leakage from gradients[J]. arXiv preprint, arXiv:2001.02610, 2020

[9]McMahan B, Moore E, Ramage D, et al. Communication-efficient learning of deep networks from decentralized data[C] //Proc of Artificial Intelligence and Statistics. Fort Lauderdale, MA: JMLR, 2017: 1273-1282

[10]Li Chengxi, Li Gang, Varshney P. Communication-efficient federated learning based on compressed sensing[J]. IEEE Internet of Things Journal, 2021, 8(20): 15531-15541

[11]Bernstein J, Zhao Jiawei, Azizzadenesheli K, et al.SignSGD with majority vote is communication efficient and fault tolerant[J]. arXiv preprint, arXiv:1810.05291, 2018

[12]Liu Ruixuan, Cao Yang, Yoshikawa M, et al. Fedsel: Federated SGD under local differential privacy with top-k dimension selection[C] //Proc of Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2020: 485-501

[13]Wu Nan, Farokhi F, Smith D, et al. The value of collaboration in convex machine learning with differential privacy[C] //Proc of 2020 IEEE Symp on Security and Privacy (SP). Piscataway, NJ: IEEE, 2020: 304-317

[14]Wang Tian, Mei Yaxin, Jia Weijia, et al. Edge-based differential privacy computing for sensor-cloud systems[J]. Journal of Parallel and Distributed Computing, 2020, 136(10): 75-85

[15]Liu Junxu, Meng Xiaofeng. Survey on privacy-preserving machine learning[J]. Journal of Computer Research and Development, 2020, 57(2): 346-362 (in Chinese)(刘俊旭, 孟小峰. 机器学习的隐私保护研究综述[J]. 计算机研究与发展, 2020, 57(2): 346-362)

[16]Brakerski Z. Fully homomorphic encryption without modulus switching from classical GapSVP[C] //Proc of Annual Cryptology Conf. Berlin: Springer, 2012: 868-886

[17]Min Zhaoe, Yang Geng, Sangaiah A, et al. A privacy protection-oriented parallel fully homomorphic encryption algorithm in cyber physical systems[J]. EURASIP Journal on Wireless Communications and Networking, 2019, 2019(1): 1-14

[18]Aono Y, Hayashi T, Trieu Phong L, et al. Scalable and secure logistic regression via homomorphic encryption[C] //Proc of the 6th ACM Conf on Data and Application Security and Privacy. New York: ACM, 2016: 142-144

[19]Aono Y, Hayashi T, Wang Lihua, et al. Privacy-preserving deep learning via additively homomorphic encryption[J]. IEEE Transactions on Information Forensics and Security, 2017, 13(5): 1333-1345

[20]Chai Di, Wang Leye, Chen Kai, et al. Secure federated matrix factorization[J]. IEEE Intelligent Systems, 2020, 36(5): 11-20

[21]Jiang Han, Xu Qiuliang. Advances in key techniques of practical secure multi-party computation[J]. Journal of Computer Research and Development, 2015, 52(10): 2247-2257 (in Chinese)(蒋瀚, 徐秋亮. 实用安全多方计算协议关键技术研究进展[J]. 计算机研究与发展, 2015, 52(10): 2247-2257)

[22]Zhao Chuan, Zhao Shengnan, Zhao Minghao, et al. Secure multi-party computation: Theory, practice and applications[J]. Information Sciences, 2019, 476(20): 357-372

[23]Jiang Han, Xu Qiuliang. Secure multiparty computation in cloud computing[J]. Journal of Computer Research and Development, 2016, 53(10): 2152-2162 (in Chinese)(蒋瀚, 徐秋亮. 基于云计算服务的安全多方计算[J]. 计算机研究与发展, 2016, 53(10): 2152-2162)

[24]Canetti R, Feige U, Goldreich O, et al. Adaptively secure multi-party computation[C] //Proc of the 28th Annual ACM Symp on Theory of Computing. New York: ACM, 1996: 639-648

[25]Goldreich O. Secure multi-party computation[J]. Manuscript Preliminary Version, 1998, 78: 110-122

[26]Damgård I, Pastro V, Smart N, et al. Multiparty computation from somewhat homomorphic encryption[C] //Proc of Annual Cryptology Conf. Berlin: Springer, 2012: 643-662

[27]Goldwasser S. Multi party computations: Past and present[C] //Proc of the 16th Annual ACM Symp on Principles of Distributed Computing. New York: ACM, 1997: 1-6

[28]Yin Lihua, Feng Jiyuan, Xun Hao, et al. A privacy-preserving federated learning for multiparty data sharing in social IoTs[J]. IEEE Transactions on Network Science and Engineering, 2021, 8(3): 2706-2718

[29]Aji A, Heafield K. Sparse communication for distributed gradient descent[J]. arXiv preprint, arXiv:1704.05021, 2017

[30]Bernstein J, Wang Yuxiang, Azizzadenesheli K, et al. SignSGD: Compressed optimisation for non-convex problems[C] //Proc of Int Conf on Machine Learning. Stockholmsmässan, MA: PMLR, 2018: 560-569

[31]Sattler F, Wiedemann S, Müller K, et al. Robust and communication-efficient federated learning from non-IID data[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019, 31(9): 3400-3413

[32]Donoho D. Compressed sensing[J]. IEEE Transactions on Information Theory, 2006, 52(4): 1289-1306

[33]Bianchi T, Bioglio V, Magli E. Analysis of one-time random projections for privacy preserving compressed sensing[J]. IEEE Transactions on Information Forensics and Security, 2016, 11(2): 313-327

[34]Yu N Y. Indistinguishability and energy sensitivity of Gaussian and Bernoulli compressed encryption[J]. IEEE Transactions on Information Forensics and Security, 2018, 13(7): 1722-1735

[35]Chen Tingsheng, Hou Kaini, Beh W, et al. Low-complexity compressed-sensing-based watermark cryptosystem and circuits implementation for wireless sensor networks[J]. IEEE Transactions on Very Large Scale Integration Systems, 2019, 27(11): 2485-2497

[36]Yao A C. Protocols for secure computations[C] //Proc of the 23rd Annual Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 1982: 160-164

[37]Shamir A. How to share a secret[J]. Communications of the ACM, 1979, 22(11): 612-613

[38]Cramer R, Damgård I, Maurer U. General secure multi-party computation from any linear secret-sharing scheme[C] //Proc of Int Conf on the Theory and Applications of Cryptographic Techniques. Berlin: Springer, 2000: 316-334

[39]Blumensath T, Davies M E. Iterative hard thresholding for compressed sensing[J]. Applied and Computational Harmonic Analysis, 2009, 27(3): 265-274

[40]Jacques L, Laska J, Boufounos P, et al. Robust 1-bit compressive sensing via binary stable embeddings of sparse vectors[J]. IEEE Transactions on Information Theory, 2013, 59(4): 2082-2102

[41]Sotthiwat E, Zhen Liangli, Li Zengxiang, et al. Partially encrypted multi-party computation for federated learning[C] //Proc of 2021 IEEE/ACM 21st Int Symp on Cluster, Cloud and Internet Computing (CCGrid). Piscataway, NJ: IEEE, 2021: 828-835

[42]LeCun Y. The MNIST database of handwritten digits[J/OL]. 1998 [2021-06-15]. http://yann.lecun.com/exdb/mnist/

[43]Xiao Han, Rasul K, Vollgraf R. Fashion-MNIST: A novel image dataset for benchmarking machine learning algorithms[J]. arXiv preprint, arXiv:1708.07747, 2017

[44]Simonyan K, Zisserman A. Very deep convolutional networks for large-scale image recognition[J]. arXiv preprint, arXiv:1409.1556, 2014

Communication-Efficient Federated Learning Based on Secret Sharing and Compressed Sensing

Chen Lüjun, Xiao Di, Yu Zhuyang, Huang Hui, and Li Min

(College of Computer Science, Chongqing University, Chongqing 400044) (Key Laboratory of Dependable Service Computing in Cyber Physical Society(Chongqing University), Ministry of Education, Chongqing 400044)

Abstract The rapid development of deep learning technology has brought us great convenience, but it also results in the disclosure of a large number of private data. Federated learning (FL) allows clients to jointly train models only by sharing gradients, which seems to solve the privacy information leakage problem, but some research show that gradients transmitted in FL frameworks can still result in privacy information leakage. Moreover, the high communication cost of FL is difficult to apply to resource-constrained environments. Therefore, we put forward two communication-efficient and secure FL algorithms, which use Top-K sparse and compressed sensing to reduce communication overhead caused by the gradient transmission, and further use additive secret sharing in secure multi-party computation (MPC) to encrypt the important gradient parameter measurements in order to simultaneously realize communication overhead reduction and security enhancement. The main difference between the two algorithms is that the client and server communicate with each other by transmitting the gradient measurement value and the quantization result of the gradient measurement value, respectively. Experiments on MNIST and Fashion-MNIST data show that, compared with other algorithms, the proposed algorithms can further increase the security at a lower communication cost and have better performance in model accuracy.

Key words compressed sensing; security multi-party computation; federated learning; communication-efficient; resource-constrained

收稿日期：2022-06-11； 修回日期：2022-08-12

基金项目：国家自然科学基金项目(62072063)；国家重点研发计划项目(2020YFB1805400)；重庆市研究生科研创新项目(CYB21062)

This work was supported by the National Natural Science Foundation of China (62072063), the National Key Research and Development Program of China (2020YFB1805400), and the Graduate Student Research and Innovation Foundation of Chongqing (CYB21062).

通信作者：肖迪(dixiao@cqu.edu.cn)

中图法分类号 TP391; TP181

(clj@cqu.edu.cn)

Chen Lüjun, born in 1995. PhD candidate. Her main research interests include privacy preserving, secure multi-party computation and federated learning.

陈律君，1995年生.博士研究生.主要研究方向为隐私保护、安全多方计算和联邦学习.

Xiao Di, born in 1975. PhD, professor and PhD supervisor. Senior member of CCF. His main research interests include privacy preserving and data security.

肖 迪，1975年生.博士，教授、博士生导师.CCF高级会员.主要研究方向为隐私保护和数据安全.

Yu Zhuyang, born in 1999. Master candidate. His main research interests include secure multi-party computation and machine learning.

余柱阳，1999年生.硕士研究生.主要研究方向为安全多方计算和机器学习.

Huang Hui, born in 1992. PhD candidate. Her main research interests include multimedia security, compressed sensing security and federated learning security.

黄 会，1992年生.博士研究生.主要研究方向为多媒体安全、压缩感知安全和联邦学习安全.

Li Min, born in 1995. PhD candidate. Her main research interests include federated learning, privacy preserving, compressed sensing and differential privacy.

李 敏，1995年生.博士研究生.主要研究方向为联邦学习、隐私保护、压缩感知和差分隐私.