联邦学习安全聚合：基于安全多方计算的经典方案

基于密码学技术的安全聚合可以分为三条技术路线：基于成对加性掩码、基于同态加密和基于秘密分享。其中，以秘密分享为基础的安全聚合可以在服务器端调用安全多方计算协议，理论上可以支持任意聚合方案的安全实现。本文将进一步深入分析该技术路线下的关键工作。

0

系统模型概览

在介绍具体的方案构造之前，本文首先介绍该技术路线遵循的系统模型。具体来说，该方案遵循客户端-服务器架构，其中客户端有个，服务器数量（具体数目 根据安全多方计算协议设置）。在每一轮聚合的工作流程如下：

• 每一个客户端首先调用秘密分享将自己的私有输入分享为多份 ，每一份 发送给对应的服务器 ；
• 服务器 在接收到秘密份额之后，调用安全多方计算协议计算 ；
• 服务器 返回 给每一个客户端，客户端恢复聚合结果。

常见的聚合函数 有很多，例如联邦学习中的加法聚合等。
1

相关论文介绍

1. Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (USENIX NSDI'17)

Henry Corrigan-Gibbs等人首先提出了Prio方案，实现安全、鲁棒且可扩展的聚合统计。

论文如下：

https://www.usenix.org/system/files/conference/nsdi17/nsdi17-corrigan-gibbs.pdf

开源代码如下：

https://github.com/henrycg/prio

Prio系统架构如上图所示，主要贡献包括三个方面：

• 提出了秘密分享下的非交互式证明（secret-shared non-interactive proofs, SNIPs），该证明是针对客户端-服务器架构的专用优化信息论零知识证明； 

• 提出了仿射聚合编码（affine-aggregatable encodings），该技术利用之前的编码方案优化安全聚合下的效率； 

• 最后，Prio将仿射聚合编码和SNIPs结合，同时支持安全聚合下的鲁棒和隐私两种特性。

1.1 Secret-shared Non-Interactive Proofs

接下来首先介绍SNIPs协议的构造。大致来说，SNIPs协议包含一个客户端（证明者，prover）和多个服务器（验证者，verifiers）。客户端的目标是令服务器确认验证电路 ，同时不泄露给服务器任何其他的信息。为了达到这个目标，客户端需要发送给服务器证明串（proof strings），服务器之间利用证明串、调用安全计算协议验证。该验证需要满足零知识证明的三条属性：Correctness, Soundness, Zero knowledge。

1.1.1 SNIPs构造

Set-up. 

令表示在认证电路中的乘法门个数，本文工作的底层编码域记作，其中。

Step 1: Client evaluation. 

对于客户端来说，其知道验证电路 的构造和自身私有输入，因此，其可以计算得到 每条输入输出线上的中间值。按照电路的拓扑结构，不失一般性，记第 个乘法门的输入为 和 。进一步，客户端利用拉格朗日插值算法计算得到多项式 和 ，使得对于 均有 且 。进一步，定义 。如此，和 的次数 ，的次数 。最后，客户端将 进行秘密分享（即将 的系数进行秘密分享），并把份额发送给第个服务器。

Step 2: Consistency chencking at the servers. 

第 个服务器在接收到客户端上传的 和 之后，各个服务器可以在本地计算得到 和 。具体来说，服务器 可以进行如下操作：

• 其本身具有输入的份额 ；

• 其拥有每一个乘法门的输出值秘密分享份额，例如对于第个乘法门，其具有；

• 因此，服务器可以在本地根据仿射操作得到所有其余电路线对应的秘密份额。

有了上述秘密份额，每一个服务器可以在本地利用多项式插值计算得到和 。如果客户端和服务器均诚实执行上述协议，那么有 。否则，一个恶意的客户端可能会发送 的份额给服务器，其中 使得 不是验证电路 中第 个乘法门的输出值。那么必然会有得到的 和 满足 。理由如下：如果存在 满足 ，那么对于 有 且 。由于

则有 ，因此 

Step 3a: Polynomial identity test. 

为了验证，本文使用了Schwartz-Zippel随机多项式测试算法。该算法的大致思想如下：如果，那么是一个次数最多为的非零多项式，该多项式最多在中有个根。因此，服务器可以随机选取然后计算，那么服务器验证得到的概率为。

Step 3b: Multiplication of shares. 

对于3a中的计算，关键在于计算。传统的MPC方案是利用Beaver乘法三元组实现，但是实现该方法需要在预计算调用同态加密或者不经意传输生成三元组，该生成开销较大。在方案Prio中，由于服务器是诚实的且不和客户端合谋，那么可以令客户端在本地生成三元组，然后将发送给第个服务器。即便客户端时恶意的，3a中检测失败的概率也仅有。

Step 4: Output verification.

最后，所有的服务器公开电路输出线的秘密分享，然后验证结果。

1.1.2 安全性和效率

SNIPs失败的概率为，取，上述概率可以做到可忽略。进一步，Prio比较了SNIP和之前零知识证明方案NIZK和SNARK的性能，具体如下表：

1.2 其他内容

除了上述SNIPs，Prio还提出了仿射可聚合编码（Affine-aggregatable encodings，AFEs），从而将一些非线性聚合通过编码转化为编码空间内的线性聚合，提升整体性能。Prio中支持的聚合函数包括：求和与平均、方差、布尔或与、最大最小、频数统计、集合运算和机器学习中的最小平方拟合。有些运算为了提升性能需要有一定的信息泄露，Prio中对相关泄露进行了详细刻画。相关部分的具体实现和实验请参考原文。

2. Prio+：Privacy Preserving Aggregate Statistics via Boolean Shares （SCN'22）

在Prio的基础上，Prio+为了进一步限制恶意客户端的作恶能力，强制令客户端通过布尔分享而不是算术分享上传输入。客户端在接收到布尔分享之后，则通过布尔->算术安全转化协议将布尔分享转化为算术分享，进而实现算术分享下的一些聚合计算，从而避免使用Prio中的零知识证明。该方案的核心在于布尔->算术转化，Prio+基于安全两方计算，利用daBits等技术实现了高效的在线转化。

论文如下：

https://link.springer.com/chapter/10.1007/978-3-031-14791-3_23

开源代码如下：

https://github.com/KuraTheDog/Prio-plus

3. ELSA：Secure Aggregation for Federated Learning with Malicious Actors (IEEE S&P'23)

在S&P'23上，Rathee等人面向联邦学习中的恶意客户端，提出了ELSA兼顾鲁棒性和数据隐私保护。该方案使用基于L2范数的鲁棒性检测算法，并部署两台服务器实现安全聚合。系统架构图如下所示：

ELSA方案的设计思路比较简洁：根据L2范数的鲁棒性检测算法，ELSA需要如下安全两方计算基础模块：算术分享与布尔分享、OT协议和Beaver乘法三元组。利用Beaver乘法三元组用于L2范数计算中的安全求平方运算。

3.1 直观的方案

最直观的方法则是利用两方算术秘密分享把客户端梯度直接秘密分享给两个服务器，两个服务器调用上述安全计算模块实现安全鲁棒性检测、聚合。然而，安全两方计算的离线计算的开销太大，会影响系统的整体性能。

3.2 ELSA的优化

为了减少离线开销，ELSA的优化策略和Prio中优化Beaver乘法三元组的策略很类似：让客户端去生成预计算关联随机数。然而，客户端是不可靠的：在Prio中，客户端生成的随机数即使不正确，在计算验证电路的时候也会被以绝对概率检测出来；但是在ELSA中，关联随机数要用来计算实际任务电路，没有Prio中类似的性质，所以需要保证随机数的正确性。需要验证的关联随机数包括：

• 基础OT生成的随机数；

• 平方关联随机数；

本文用的验证策略大致是令两个服务器对关联随机数进行随机线性组合+Cut&Choose策略，然后验证。该验证比简单的令两方生成关联随机数要高效很多。

3.3 其他内容

ELSA进一步还实现了恶意模型下的隐私性、减少证明串长度、客户端每轮聚合只上传一次数据等优化，相关内容可以参考原文，链接如下：

https://www.computer.org/csdl/proceedings-article/sp/2023/933600b573/1Js0E8t9uFi

开源代码如下：

https://github.com/ucbsky/elsa

2

其他类似工作

除了上述工作之外，我们课题组的EaSTFLy和FLOD系列工作、国外的FLGUARD和HyFL等工作也采取了类似的安全聚合技术路线。

[1]https://www.sciencedirect.com/science/article/pii/S0167404820300985

[2]https://link.springer.com/chapter/10.1007/978-3-030-88418-5_24

[3]https://www.semanticscholar.org/paper/FLGUARD%3A-Secure-and-Private-Federated-Learning-Nguyen-Rieger/f2a215696b4cabe723399e0bb1f9d2ed3665a7ca

[4]https://arxiv.org/abs/2302.09904

作者简介：董业，本科毕业于山东大学计算机科学与技术专业，目前在中国科学院信息工程研究所攻读博士学位。主要研究兴趣包括隐私保护、安全多方计算、同态加密和机器学习。知乎：酸菜鱼。

END

​

往期推荐

1.基于密码的数据安全防护体系研究
2.学术交流 | InForSec 2023年网络空间安全国际学术研究成果分享及青年学者论坛3.椭圆曲线密码在多方安全计算中的应用4.隐私求交| Simple, Fast Malicious Multiparty Private Set Intersection