基于并行同态加密和STC的高效安全联邦学习*

肖林声，钱慎一

（郑州轻工业大学，河南 郑州 450007）

0 引言

联邦学习（Federated Learning）[1-3]最早由HB McMahan团队提出。联邦学习在一定程度上保证了隐私的安全，但还存在许多不足，如攻击者可以使用共享的梯度来逆向推演，从而得到用户的隐私数据和敏感信息；如果仅适用现有简单的隐私保护技术如同态加密技术（Homomorphic Encryption，HE）、安全多方计算（Secure Multi-Party Computation，MPC）等会产生大量的额外开销，给设备带来巨大的负担。

为了解决以上问题，本文基于稀疏三元压缩（Sparse Ternary Compression，STC）技术和并行同态加密算法提出了一种新方法，不仅可以保护用户隐私，还可极大地减少通信和计算开销。

本文的主要贡献在于两个方面。一方面，将STC和并行同态加密应用到联邦学习方案。与不加密的明文相比，准确性没有降低；与现有的加密工作相比，通信开销极大降低，且显著提升了计算效率。另一方面，本文使用了一种验证聚合结果有效性的方案，有效避免了服务器恶意篡改训练结果的情况。

1 理论基础

下面主要介绍本文使用的联邦学习算法、STC算法、同态加密算法以及消息验证码。

1.1 联邦学习

联邦学习的结构如图1所示。

图1 联邦学习系统结构

模型训练过程如下：

（1）基于私有数据集，用户Ci在本地训练θ，得到梯度向量gi：

（2）服务器S接收从用户上传的梯度向量gi；

（3）在服务器S中，将所有获得的梯度向量聚合：

（4）计算完成后得到聚合梯度向量gS，并将其返回给所有m，然后用户使用聚合梯度更新本地模型：

式中，α是学习率。

在一轮训练完成后，用户需要检测本地模型的准确率是否满足要求。如果满足要求，则停止训练并输出训练好的模型；如果没有满足要求，则继续迭代进行下一轮训练，直到满足要求为止。

1.2 STC算法

联邦学习中，用户在每次训练完成后均需要将训练得到的梯度全部传输给服务器。在需要的梯度参数较多的系统中，这将会占用大量的通信资源，成为系统性能提升的瓶颈。本文主要参考Aij[4]等人提出的Top-K梯度选择方案和Felix Sattler等人[5]提出的Top-K梯度选择方案的扩展——STC稀疏三元算法。

具体来说，每次用户C计算得到梯度g后，首先将梯度向量中的元素g[j]的绝对值进行排序，取出排序完成的梯度绝对值最大的K个梯度，后将这选出的K个梯度值量化为三元张量上传到服务器S。

图2中TK代表用Top-K方案取出的绝对值最大的K个梯度值，而tmp中存储的是梯度的索引和梯度的绝对值。将梯度的索引和梯度的绝对值排序，选出绝对值最大的K个梯度值，在稀疏化的同时对稀疏化后的目标向量。在STC算法的作用下，TK∈Rn最终会生成三元张量TK*∈{-μ,0,μ}n。

文献[5]先使用Top-K算法取出相应的梯度绝对值最大的K个梯度，然后将其梯度值量化为包含{-μ,0,μ}的三元向量。作者用实验证明，三元化不影响收敛速度，甚至会提高训练的模型精度，表明对数据稀疏化和量化的结合相比于单纯使用Top-K算法稀疏化数据更好地利用了通信资源，且效率更高。作者不仅将STC用在用户将梯度上传到服务器的情况，也将STC用到了用户从服务器下载的情况，进一步减小了通信开销。

1.3 并行同态加密算法

关于同态加密的研究，先是Rivest等[6]提出RSA加密算法，后又在文献[7]中提出了同态加密的概念。2009年，Gentry[8]第一次提出了全同态加密方案，并在文献[9]中对该方案进行了详细介绍，并已经由Gentry实现[10-11]。2010年，DGHV方案被提出，是一种基于整数的同态加密方案，只满足加法和乘法的同态加密方案。本文基于胡持等[12]提出的基于DGHV同态加密方案，通过MapReduce框架实现并行加密，在保护个人隐私的同时，通过MapReduce的并行化处理提高数据的加密效率。由于密钥持有问题，同态加密算法不能直接用于联邦学习算法，因此采取多密钥同态加密算法[13]来解决密钥的持有问题。

图2 稀疏三元压缩算法

1.4 消息验证码

消息验证码（Message Authentication Code，MAC）是确认信息完整性并认证的技术[14]，是一种与密钥相关联的单向Hash函数，如文献[15]中提出的HMAC。(G,Sign,Verify)这3个元素组成了验证码，其中生成密钥的算法为G，密钥sk←G(1κ)由G生成其中的κ为安全参数，且安全参数是给定的；Sign(sk,x)则使用sk和信息x生成验证码MAC=Sign(sk,x)；Verify是将sk、x和MAC集合起来，判断Verify(sk,x,MAC)=Accept是不是成立。

算法Sign和Verify需要满足：

本文参考文献[16]中使用消息验证码的思想和梯度选择的索引信息，验证聚合结果的有效性。

2 方案设计

本文基于并行同态加密和STC算法，针对联邦学习算法中的隐私安全和通信开销问题，提出了安全且高效的训练协议。一方面提出协议πHEFL，使得诚实用户的梯度信息受到加密算法的保护，而攻击者无法获得。另一方面，提出了可以在保护用户梯度隐私的前提下抵抗恶意篡改攻击的协议，以保证聚合结果的可用性。

假设用户的数目m≥3且服务器被半诚实攻击者腐化，而所有的用户中有被半诚实攻击者腐化的用户存在。

2.1 协议πHEFL

协议πHEFL是在半诚实的攻击者威胁下保护单个用户梯度的隐私性。该协议流程如图3所示。

首先，每个用户按照式（1）训练模型θ，从而得到梯度向量g。其次，用户调用STC稀疏三元压缩算法，选出绝对值最大的K个梯度并将其量化为包含{-μ,0,μ}的三元向量。最后，用户通过并行同态加密算法将选择并量化的梯度向量加密生成密文向量C，并将加密完成的梯度向量上传到服务器。注意，梯度的索引信息也要上传。

服务器在收到用户上传的密文后，根据索引的信息，使用全同态加密中的Eval(evk,C,c1,…,cn)密文运算算法，将梯度在加密状态下进行聚合得到聚合结果gS，后将gS和索引信息的并集返回IND给用户。

协议的形式如下。

输入：隐私数据集Di、待训练模型θ

输出：训练完成的模型θ

①用户均和服务器建立安全的连接；

②每个用户在本地生成随机数；

③用户使用私有数据训练模型；

④用户使用STC稀疏三元压缩算法，选择并量化梯度元素；

⑤用户对选出的并已经量化的梯度调用并行同态加密算法生成密文C；

⑥用户将加密好的梯度密文和索引信息的集合传输到服务器；

⑦服务器根据索引信息，使用密文运算算法Eval(evk,C,c1,…,cn)对各个用户上传的梯度进行聚合；

⑧用户下载服务器中聚合结果的密文，并用私密密钥sk将其还原；

⑨用户使用还原的结果更新本地模型；

⑩若未达到要求，则跳转③进行下一轮训练，或者达到要求停止训练。

协议πHEFL可以很好地保护诚实用户的梯度和隐私信息。

图3 协议πHEFL的流程

2.2 协议

协议πHEFL能够保护用户的梯度信息，但是不能阻止攻击者在不直接泄露用户隐私的情况下腐化服务器并对结果进行修改。

假设攻击者腐化服务器S，记S使用Eval(evk,C,c1,…,cn)聚合生成gS，但是攻击者可能会生成任意的噪声向量r，之后攻击者便可以将噪声和密文一起计算：

从而使得最终聚合的结果受到噪声r的干扰。

利用梯度的索引和量化的梯度值来构造验证码MAC来抵抗恶意攻击者的攻击。

这里要修改安全性假设：需要两个服务器，且这两个服务器不可同时被恶意攻击者腐化，其中一个服务器S1负责聚合梯度，另一个服务器S2负责计算和存储验证码MAC。

和协议πHEFL一样，用户首先在本地训练θ并使用STC算法得到量化梯度，记为：

这里的g[ind]是量化完成后的值，后利用索引信息和梯度的量化值g[ind]计算验证码MAC：

利用同态加密算法将MAC加密，并上传MAC的密文M到所有的服务器。服务器收到用户上传的MAC密文后，使用密文运算算法Eval(evk,C,c1,…,cn)将所有的MAC求和得到MACS：

对于梯度值，使用密文运算算法Eval(evk,C,c1,…,cn)，并使用式（2）来聚合梯度。

聚合完成后，服务器将聚合结果的密文、对应的索引信息INDS以及各个服务器中的MACS返回用户。

用户在本地解密聚合梯度的真实值gS，并在本地进行验证：

（1）两个服务器的MACS都相等；

（2）用户计算：

并检验MAC´S=MACS。

如果以上验证都通过，那么用户接受gS并更新模型；否则，广播错误并终止协议。图4为协议的工作流程。

图4 协议的工作流程

输入：数据集Di和模型θ；

输出：训练完成的模型θ；

①用户均和服务器建立安全的连接；

②每个用户在本地生成随机数；

③用户在本地训练模型，计算梯度；

④用户调用STC稀疏三元压缩法，选择Top-K梯度并将其量化为三元向量；

⑤用户使用式（7）计算验证码MAC；

⑥调用并行同态加密算法分别加密梯度和验证码；

⑦将梯度的密文C上传到服务器S1，将验证码MAC分别发给服务器S1和S2；

⑧服务器S1聚合梯度，且和服务器S2一起按照式（9）求和得到MACS；

⑨用户下载并恢复梯度，同时下载所有服务器的MACS；

⑩如果通过所有的验证，则用户更新本地模型；否则，广播错误并终止训练进行下一轮训练，达到要求的情况下停止训练并输出模型。

下面分析过程的正确性。

（1）如果服务器没有进行任何恶意篡改，那么两个服务器所接收的MAC相同，那么得到的MACS也相同。

（2）这里假设只有两个用户（为了方便，此处先不考虑隐私保护P1、P2，且记P1、P2选择且量化的梯度向量为g1和g2，对应的索引集为IND1和IND2。根据协议，INDS=IND1∪IND2。

对于索引ind来说，∀ind∈INDS，有以下3种情况：

由式（8）可得MACS=MAC1+MAC2，MACS=因此协议在一定程度上抵御了结果不被服务器恶意篡改。

3 实验和结果

选择的数据集中有37万条数据，是2012—2018年的投诉信息，分为78个大类信息和249个小类信息。每一个信息包含78个属性。每次训练迭代中用户需要和服务器交互计算1次，以此完成梯度的安全聚合。直接使用线性支持向量机训练所得到的准确率为79%。

本文使用预测准确率、通信开销大小以及单次训练所消耗的时间来评判协议的有效性。

3.1 模型的准确率

为了证明协议的可用性，需要计算准确率。若准确率达到了明文条件下的水平或者没有较大的下降，说明提出的协议对训练模型的预测性能没有太大影响。因为验证训练结果的过程对模型的准确性并没有影响，所以这一部分只考虑明文和πHEFL协议两种情况。

探索不同梯度选择比率对训练模型的影响。在不同的梯度选择比率下，迭代100次，选择1%、5%和10%和明文下100%上传的方式比较。在表1中可以看到，上传的梯度的增加对准确度的提升没有太大影响。

表1 模型最终准确率

3.2 通信开销

为了提升通信性能，并在有效减少通信开销的同时保证隐私安全，在STC稀疏三元压缩的基础上，结合并行同态加密提出了相对高效的解决方案。实验中将STC中的梯度选择的比率控制在1%、5%和10%，且在明文、协议πHEFL和协议下测量了在训练完成的情况下通信的开销，结果如表2所示。

表2 一次迭代训练中上传和下载的通信开销

从实验结果可以看出，采用STC稀疏三元压缩法可以很好地解决通信开销问题。将STC选择的选择梯度的比率从10%到1%，通信性能有了明显优化，上传的开销相比于明文优化了约50倍，而下载的开销则优化了约4.9倍。由第3.1章节和文献[5]可知，STC稀疏三元压缩选择的比率不会对模型的性能造成太大影响，且相比于Top-K梯度选择算法，STC在减小通信开销的同时可以提高训练精度。此外，增加验证信息并没有增加额外的通信开销。可见，STC算法在联邦学习领域拥有巨大的发展潜力。

3.3 时间开销

在训练过程中，测量了协议πHEFL和各个阶段的时间开销。需要说明，这里的PWH直接使用同态加密而没有并行化处理。在协议的用户端和服务器端中分别加入了处理验证码的时间开销。在STC下选择梯度的比率为1%、5%和10%进行实验，并与明文状态和未使用并行化而直接使用同态加密的PWH方案进行对比，结果如表3和表4所示。

表3 一次迭代训练中的训练和传输时间开销

表4 一次迭代训练中的服务器端，预处理和总体的时间开销

结果表明，和明文训练相比，加入的并行化同态加密安全协议在训练时引入了一定的时间开销，但是和直接使用同态加密相比，引入的时间开销小了很多。随着梯度选择的比率上升，同态加密算法所消耗的时间也在快速上升。可以发现，用户端的计算时间、服务器端的计算时间以及明文的计算时间增加的幅度很小，且这种增幅在实际应用中是可以接受的。除了同态加密所花费的时间开销以外，主要的时间开销来自于传输梯度的时间开销，这是目前限制安全联邦学习应用的主要原因。

4 结语

联邦学习中隐私安全、时间开销和通信开销是其重要的瓶颈，而这些问题在安全联邦学习中的影响正在变得更加严重。本文使用STC稀疏三元压缩算法和并行同态加密算法结合起来，一定程度上在时间开销、通信开销和隐私保护之间取得了平衡。此外，参考文献[16]构造了验证码，但随着系统的增大，安全联邦学习效率低下依旧是重要的研究课题。未来的工作重点将着重研究进一步提升安全联邦学习的效率。