名称	SAMK: Secure aggregation for federated learning under multiple keys with low communication rounds
期刊	IEEE Transactions on Dependable and Secure Computing
作者	Cheng Guo, Ling Li, Ximeng Liu, Kim-Kwang Raymond Choo*, Yining Liu
DOI	10.1109/TDSC.2025.3602908

TLDR

本文提出了一中适用于 多密钥 环境的安全聚合联邦学习方案 SAMK，通过利用 BFV 密文的多项式结构并结合 Paillier 同态求和，实现了 单轮、无交互、 多密钥独立解密 且 可容忍任意客户端掉线 的聚合方案。SAMK 允许每个客户端在不参与协同解密、且无法获取他人更新的前提下独立恢复聚合结果，从而兼顾隐私性与可用性。SAMK虽然每轮只需一次交互，但是是以通信开销为代价。

背景

• 基于同态加密的安全聚合虽然可以保护隐私，但是所有客户端使用相同的密钥，在这种情况下，可能会发生内部攻击，半诚实的客户端 可能通过使用共享密钥解密其他客户端的密文来获取其模型更新；
• 当客户端使用不同密钥时，现有方案需要额外的交互，导致通信轮次的增加；
  • 当客户端掉线时，现有方案通过额外的实体间交互来协同消除掉线客户端密钥的影响，从而确保聚合过程安全且正确地完成。

预备知识

作者主要使用了多密钥 BFV 和 Paillier 同态加密，下面主要介绍一下 BFV 加密系统，Paillier 加密系统和多项式插值进行少许介绍。

BFV 加密系统

Brakerski-Fan-Vercauteren（BFV）密码系统是一种基于环上带误差学习（RLWE）的方案，支持加法和乘法同态运算。

对于 BFV，可阅读某乎文章：全同态加密方案之BFV

在BFV 中，密文空间是多项式商环 ${\mathcal{R}}_q={\mathbb{Z}}_q[x]/(X^N+1)$，其中 $N$ 是 2 的幂，$q$ 是密文模数。明文空间是多项式商环 ${\mathcal{R}}_t={\mathbb{Z}}_t[x]/(X^N+1)$，其中 $t$ 是明文模数，且 $t<q$。

单密钥 BFV 由五个算法组成：

1. $BFV.Setup(1^{\lambda })\to pp$：输入安全参数 $\lambda$，设置 RLWE 维度 $N$、密文模数 $q$、明文模数 $t$、密钥分布 $\phi$ 和 RLWE 误差分布 $\chi$。输出公共参数 $pp$： p p = { N , q , t , φ , χ } pp=\{N,q,t,\varphi,\chi\} pp={N,q,t,φ,χ}
2. $BFV.SecKeyGen(\mathrm{pp})\to sk$：输入安全参数 $\lambda$，采样 $s\leftarrow {\mathcal{R}}_3$。输出秘钥 $sk$：$$sk=s$$
3. $BFV.PubKeyGen(\mathrm{pp},\mathrm{sk})\to pk$：采样 $a\in {\mathcal{R}}_q$ 和 $e\leftarrow \chi$。输出公钥 $pk$：$$pk=(p_0,p_1)=([-(s\cdot a+e){]}_q,a)$$
4. $BFV.Encrypt(\mathrm{pp},\mathrm{pk},\mathrm{m})\to ct$：输入明文 $m$，采样 $u\leftarrow {\mathcal{R}}_3$ 和 $e_0$、$e_1\leftarrow \chi$。计算 $\Delta =q/t$。输出密文 $ct$：$$ct=(c_0,c_1)=([\Delta [m{]}_t+u{p}_0+e_0{]}_q,[u{p}_1+e_1{]}_q)\in {\mathcal{R}}_q^2$$
5. $BFV.Decrypt(\mathrm{pp},\mathrm{sk},\mathrm{ct})\to m$：解密密文 $ct$ 得到明文 $m$：$$m={\left[\lfloor \frac{t\cdot [c_0+c_{1}s{]}_q}{q}\rceil \right]}_t$$
   为了改进单密钥BFV的缺陷，多密钥BFV（MK-BFV）被提出，持在不同密钥下加密的密文。

假设有 $k$ 个参与方，每个参与方都有一个索引 $i$（$1\le i\le k$）及其公钥和私钥。多密钥BVF由以下算法组成：

1. $\mathrm{MK}\text{-}BFV.Setup(1^{\lambda })\to pp$：运行 $BFV.Setup(1^{\lambda })$ 并输出公共参数 $pp$。
2. M K - B F V . K e y G e n ( p p ) → { s k i , p k i } \mathrm{MK\text{-}BFV. KeyGen(pp)}→\{sk_i, pk_i\} MK-BFV.KeyGen(pp)→{ski​,pki​}：每个参与方 $i$ 分别通过 $s{k}_i\leftarrow BFV.SecKeyGen(\mathrm{pp})$ 和 $p{k}_i\leftarrow BFV.PubKeyGen(\mathrm{pp},\mathrm{sk})$ 生成其私钥和公钥。
3. $\mathrm{MK}\text{-}BFV.Encrypt(\mathrm{pp},\mathrm{p}{\mathrm{k}}_{\mathrm{i}},{\mathrm{m}}_{\mathrm{i}})\to {\overline{ct}}_i$：每个参与方 $i$ 生成 BFV 密文，表示为 $c{t}_i=(c_{i,0},c_{i,1})\leftarrow BFV.Encrypt(\mathrm{pp},\mathrm{p}{\mathrm{k}}_{\mathrm{i}},{\mathrm{m}}_{\mathrm{i}})$。然后将 $c{t}_i$ 转换为密文 ${\overline{ct}}_i$：$${\overline{ct}}_i=(c_{i,0},{\bar{c}}_{i,1},\dots ,{\bar{c}}_{i,k})\in {\mathcal{R}}_q^{k+1}$$其中$${\bar{c}}_{i,j}=\{\begin{array}{llc}{c}_{i,1}& \mathrm{if}j=i,& \\ 0& \text{otherwise.}& \end{array}$$

${\overline{ct}}_i$ 是这样构建的：客户端 $i$ 首先把 $c_{i,0}$ 放置在 ${\overline{ct}}_i$ 的 0 索引位置，然后把 $c_{i,1}$ 放置在 ${\overline{ct}}_i$ 的 $i$ 号索引位置，其他位置置为0。

4. $\mathrm{MK}\text{-}BFV.Decrypt(\mathrm{pp},{\overline{\mathrm{ct}}}_{\mathrm{i}},\mathrm{s}{\mathrm{k}}_1,\dots ,\mathrm{s}{\mathrm{k}}_{\mathrm{k}})\to m_i$：输入密文 ${\overline{ct}}_i$，输出明文 $m_i$：$$m_i={[\lfloor \frac{t\cdot {\left[c_{i,0}+{\sum }_{j=1}^k{\bar{c}}_{i,j}\cdots k_j\right]}_q}{q}\rceil \rfloor }_t$$
5. $\mathrm{MK}\text{-}BFV.Add(\mathrm{pp},{\overline{\mathrm{ct}}}_0,{\overline{\mathrm{ct}}}_1)\to c{t}_{add}$：给定两个密文：${\overline{ct}}_1=(c_{1,0},c_{1,1},0,\dots ,0)\in {\mathcal{R}}_q^{k+1}$ 和 ${\overline{ct}}_2=(c_{2,0},0,c_{2,1},0,\dots ,0)\in {\mathcal{R}}_q^{k+1}$，输出密文 $c{t}_{add}$：$$c{t}_{add}=([c_{1,0}+c_{2,0}{]}_q,c_{1,1},c_{2,1},0,\dots ,0)\in {\mathcal{R}}_q^{k+1}$$

Paillier 加密系统

Paillier密码系统是一种基于 复合剩余类 问题的半同态加密算法，支持加法同态运算。主要由密钥生成、加密、解密和同态加四个算法组成。

多项式插值

多项式插值是一种利用区间内若干 已知点 处的函数值，通过多项式来近似函数 $f(x)$ 的方法。假设有 $z+1$ 个不同的点对：$\{(x_i,f(x_i)){\}}_{i=1}^z$，可以构造出一个阶为 $z$ 的多项式：$$P(x)=a_k{x}^k+a_{k-1}{x}^{k-1}+\cdots +a_0$$
其中满足 $f(x_i)=P(x_i)$。

常用的插值方法有拉格朗日插值和牛顿插值。本文使用的是牛顿插值法。

实体和威胁模型

SAMK 的系统模型如下图所示：

SAMK 包含一个服务器和 $n$ 个客户端 $U_{i\in [0,n-1]}$。

• 每个客户端 $U_i$ 生成其自身的公钥和私钥（步骤 1）。$U_i$ 使用公钥对模型更新 $m_i$ 进行加密（步骤 ©2），并在从服务器下载聚合密文 $C{T}_{agg}$ 后，使用私钥对其进行解密以获得聚合结果 $m_{agg}$（步骤 4）。
• 服务器初始化系统参数，聚合客户端的密文（步骤 3）。
• 此外，客户端可能在上传密文之前或之后掉线，本文的解决方案是服务器只聚合收集到的密文，然后发回在线客户端。

威胁模型

• 服务器和客户端都是诚实但好奇的，这意味着他们会诚实地执行协议，但会尝试推断和分析接收到的消息或公开可用的密文；
• 客户端可能会尝试通过推断其他客户端的模型更新来获取其敏感信息；
• 本文假设客户端与服务器之间不存在共谋，但客户端之间可能会共谋，以共同推断非共谋客户端的敏感信息；
• 此外，客户端与服务器之间的所有通信渠道都是不安全的，任何实体（服务器、客户端和外部人员）都可以拦截传输的信息。

SAMK

如何实现多密钥下的客户端单独解密

在多密钥BFV加密系统下，每个客户端 $U_i$ 拥有自己的公私钥 $(p{k}_i,s{k}_i)$，并且利用公钥 $p{k}_i$ 加密模型更新 $m_i$ 得到密文：$$ct=(c_{i,0},c_{i,1})=([\Delta [m_i{]}_t+u_i{p}_{i,0}+e_{i,0}{]}_q,[u_i{p}_{i,1}+e_{i,1}{]}_q)$$
作者察觉到，如果想用每个客户端的私钥都能解密聚合密文 $C{T}_{agg}$，可以通过构造多项式，基于 RLWE 的密码系统的密文正是多项式形式，只要每个客户端都能构造出这个多项式，便能实现单独解密。

作者首先构造一个 $f_i(x)=s{k}_i\cdot c_{i,1}=s_i[u_i{p}_{i,1}+e_{i,1}{]}_q$，这样解密 $m_i$ 就转换为了：$$m_i={\left[\lfloor \frac{t\cdot {\left[c_{i,0}+f_i(x)\right]}_q}{q}\rceil \right]}_t$$
同样地，解密聚合密文就转化为了：$$m_{agg}={\left[\lfloor \frac{t\cdot {\left[C{T}_{agg}+F(x)\right]}_q}{q}\rceil \right]}_t$$
其中 $m_{agg}=[{\sum }_{i=0}^{n-1}{m}_i{]}_t$， $C{T}_{agg}=[{\sum }_{i=0}^{n-1}{c}_{i,0}{]}_q$， $F(x)={\sum }_{i=0}^{n-1}{f}_i(x)$。

作者利用 $N$ 个点来构造多项式：$$\text{Poly.Inter}((x_0,F(x_0)),(x_1,F(x_1)),\dots ,(x_{N-1},F(x_{N-1})))\to F(x)$$

SAMK 框架主要有五个阶段：setup ，keygen ，encrypt ，aggregate 和 decrypt。

SAMK 的加解密和聚合的细节图如下所示：

建立阶段

在建立阶段，服务器初始化 BFV 和 Paillier 加密系统的安全参数，并生成自变量集合 $X=x_0,x_1,\dots ,x_{N-1}$ 和公共参数 $PP$。具体细节如算法 1 所示。

其中 Paillier 的安全参数 $\kappa$ 是密钥的位长度，为了确保 Paillier 加密不越界，应该保证 $\frac{(q-1)\cdot (x_{\max }^N-1)}{x_{\max }-1}<2^{2\kappa }$，其中 $x_{max}$ 是 $X$ 中的最大元素，比较符左侧表示 $f_i(x)$ 中的最大多项式值。

密钥生成

客户端 $U_i$ 独立生成自己的 BFV 密钥对 $(p{k}_i,s{k}_i)$ 和 Paillier 密钥对 $(p{k}_i^{\prime },s{k}_i^{\prime })$。服务器独立生成自己的 Paillier 密钥对 $(p{k}_S^{\prime },s{k}_S^{\prime })$ 。

在所有实体生成其密钥后，它们会广播用于加密的 Paillier 公钥。BFV 公钥主要用于加密模型更新，而 Paillier 公钥主要用于加密 BFV 密文的多项式值。

加密

在加密过程中，每个客户端 $U_i$ 使用 BFV 对 $m_i$ 进行加密，并使用 Paillier 对 BFV 密文的 $N$ 个多项式值进行加密。其中，$N-1$ 个值使用服务器的 Paillier 公钥加密，剩余的一个值使用 所有客户端 的 Paillier 公钥加密。作者使用 $[[\cdot ]]$ 和 $[[\cdot ]{]}^{\prime }$ 分别表示模型更新和多项式值的密文。

加密可以分为四个步骤进行：

1. 客户端 $U_i$ 使用其自身的 BFV 公钥 $p{k}_i$ 对其模型更新 $m_i$ 进行加密，得到密文 $[[m_i]]$。
2. $U_i$ 使用 $s{k}_i$ 和 $c_i$ 计算多项式 $f_i(x)=s{k}_i\cdot c_{i,1}$。
3. 使用 $X$ 中的 $N$ 个值作为自变量，计算 $f_i(x)$ 的 $N$ 个不同值：$f_i(x_0)$、 $f_i(x_1)$ 、… 、$f_i(x_{N-1})$。
4. 对于前 $N-1$ 个值，$U_i$ 使用服务器的 Paillier 公钥 $p{k}_S^{\prime }$ 对它们进行加密，得到密文：$[[f_i(x_0)]{]}_S^{\prime }$ 、$[[f_i(x_1)]{]}_S^{\prime }$ 、…、$[[f_i(x_{N-2})]{]}_S^{\prime }$。对于 $f_i(x_{N-1})$，$U_i$ 使用每个客户端 $U_v\in U$ 的 Paillier 公钥 $p{k}_v^{\prime }$ 对其进行加密，得到密文：$[[f_i(x_{N-1})]{]}_0^{\prime }$ 、$[[f_i(x_{N-1})]{]}_1^{\prime }$ 、…、$[[f_i(x_{N-1})]{]}_{n-1}^{\prime }$。

加密完成后，每个客户端将所有密文发送给服务器进行聚合，客户端存在掉线，服务器会收到来自 $n_1$ 个客户端的信息，将这些客户端集合记为 $H,|H|=n_1$。

优化计算开销

我们知道，模型更新可以展开为一个 $l$ 维向量 m i = { m i , 0 , m i , 1 , … , m i , l − 1 } m_i=\{m_{i,0},m_{i,1},\dots,m_{i,l-1}\} mi​={mi,0​,mi,1​,…,mi,l−1​}，其中每个数都是小bits数值，而 BFV 的明文空间容量是很大的，所以我们可以使用打包技术，将多个参数打包进一个明文中，从而减少密文数量。

假设一个 BFV 明文多项式最多可以容纳 $M$ 个数据；将 $M$ 个模型参数编码到一个明文中可以一次性加密它们。每个客户端的 BFV 密文可以被简化为 $l/M$。

而在 Paillier 加密系统中，明文空间 $N_S$ 可以容纳 $k$ 条信息，其中 $k$ 满足：${\sum }_{t=0}^{k-1}|f_i(x_t)|\le |N_S|$，其中 $|N_S|$ 和 $|f_i(x_t)|$ 分别表示对应的位长度。因此每个客户端可以将 $k$ 个明文打包成一个明文以提高效率。

但是我们知道，数值的相加会产生进位，为了防止越界，需要为每个明文分配足够的空间，本文为每个明文 $f_i(x_t)$ 分配 $|F_{max}^t|$ 的位空间，其中 $F_{max}^t$ 是 $n$ 个客户端的 $f_i(x_t)$ 的最大可能聚合结果。

聚合

在聚合过程中，服务器对模型更新的密文 $\{[[m_j]]{\}}_{j=0}^{n_1-1}$ 和多项式值的密文 { { [ [ f j ( x t ) ] ] S ′ } t = 0 N − 2 , { [ [ f j ( x N − 1 ) ] ] i ′ } i = 0 n − 1 } j = 0 n 1 − 1 \{\{[[f_j (x_t )]]_S^′ \}_{t=0}^{N−2} , \{[[f_j (x_{N−1})]]_i^′\}_{i=0}^{n−1}\}_{j=0}^{n_1−1} {{[[fj​(xt​)]]S′​}t=0N−2​,{[[fj​(xN−1​)]]i′​}i=0n−1​}j=0n1​−1​ 执行同态加法运算。然后，它解密下标为 $S$ 的聚合后的密文以获得 $N-1$ 个多项式值 { F ( x t ) } t = 0 N − 2 \{F (x_t)\}_{t=0}^{N−2} {F(xt​)}t=0N−2​。

如算法4所示，聚合阶段主要包括3个步骤。

1. 服务器聚合所有客户端的 $[[m_j]]$ 以获得聚合密文 $C{T}_{agg}$。
2. 服务器分别聚合所有客户端的密文 $[[f_j(x_0)]{]}_S^{\prime }$ ，$[[f_j(x_1)]{]}_S^{\prime }$ ，…，$[[f_j(x_{N-2})]{]}_S^{\prime }$，以获得聚合密文 $[[F(x_0)]{]}_S^{\prime }$ ，$[[F(x_1)]{]}_S^{\prime }$ ，…，$[[F(x_{N-2})]{]}_S^{\prime }$：

$$\begin{array}{rl}[[F(x_0)]{]}_S^{\prime }& =[[f_0(x_0)]{]}_S^{\prime }\cdot \dots \cdot [[f_{n_1-1}(x_0)]{]}_S^{\prime }\mathrm{mod}{N_S}^2\\ [[F(x_1)]{]}_S^{\prime }& =[[f_0(x_1)]{]}_S^{\prime }\cdot \dots \cdot [[f_{n_1-1}(x_1)]{]}_S^{\prime }\mathrm{mod}{N_S}^2\\ [[F(x_{N-2})]{]}_S^{\prime }& =[[f_0(x_{N-2})]{]}_S^{\prime }\cdot \dots \cdot [[f_{n_1-1}(x_{N-2})]{]}_S^{\prime }\mathrm{mod}{N_S}^2\end{array}$$

然后服务器将所有客户端的密文 $[[f_j(x_{N-1})]{]}_0^{\prime }$, $[[f_j(x_{N-1})]{]}_1^{\prime }$, …, $[[f_j(x_{N-1})]{]}_{n_1-1}^{\prime }$ 分别聚合，以获得聚合密文 $[[F(x_{N-1})]{]}_0^{\prime }$, $[[F(x_{N-1})]{]}_1^{\prime }$, …, $[[F(x_{N-1})]{]}_{n_1-1}^{\prime }$：
$$\begin{array}{rl}[F(x_{N-1})]{]}_0^{\prime }& =[[f_0(x_{N-1})]{]}_0^{\prime }\cdot \dots \cdot [[f_{n_1-1}(x_{N-1})]{]}_0^{\prime }\mathrm{mod}{N_0}^2\\ [[F(x_{N-1})]{]}_1^{\prime }& =[[f_0(x_{N-1})]{]}_1^{\prime }\cdot \dots \cdot [[f_{n_1-1}(x_{N-1})]{]}_1^{\prime }\mathrm{mod}{N_1}^2\\ [[F(x_{N-1})]{]}_{n_1-1}^{\prime }& =[[f_0(x_{N-1})]{]}_{n_1-1}^{\prime }\cdot \dots \cdot [[f_{n_1-1}(x_{N-1})]{]}_{n_1-1}^{\prime }\mathrm{mod}{N_{n_1-1}}^2\end{array}$$

3. 最后，服务器使用其 Paillier 密钥 $s{k}_S$ 解密密文 $[[F(x_0)]{]}_S^{\prime }$、$[[F(x_1)]{]}_S^{\prime }$、…、$[[F(x_{N-2})]{]}_S^{\prime }$，以获得 $F(x_0)$、$F(x_1)$、…、$F(x_{N-2})$。如果在加密中使用了打包技术，则在服务器解密多项式值的密文后，需要对明文进行解包。

然后服务器将聚合值发送给在线客户端，详细内容可见算法4：

解密

在解密过程中，每个客户端 $U_j\in H$ 都从服务器接收到消息 { C T a g g , F ( x 0 ) , F ( x 1 ) , … , F ( x N − 2 ) , [ [ F ( x N − 1 ) ] ] j ′ } \{CT_{agg}, F(x_0), F(x_1), \dots, F(x_{N−2}), [[F(x_{N−1})]]_j^′\} {CTagg​,F(x0​),F(x1​),…,F(xN−2​),[[F(xN−1​)]]j′​}。$U_j$ 能够独立解密 $[[F(x_{N-1})]{]}_j^{\prime }$，然后结合 $F(x_{N-1})$ 与 $F(x_0)$、$F(x_1)$、…、$F(x_{N-2})$，$U_j$ 可以独立解密 $C{T}_{agg}$ 以获得聚合结果 $m_{agg}$。

如算法5所示，解密阶段分为三个步骤。

1. 客户端 $U_j$ 使用其Paillier密钥 $s{k}_j^{\prime }$ 解密密文 $[[F(x_{N-1})]{]}_j^{\prime }$，以获得$F(x_{N-1})$。
2. 在获得 $F(x_{N-1})$ 后，结合接收到的 $N-1$ 个点 { F ( x t ) } t = 0 N − 2 \{F(x_t)\}_{t=0}^{N−2} {F(xt​)}t=0N−2​，客户端 $U_j$ 总共拥有 $N$ 个 $F(x)$ 的点。客户端利用这 $N$ 个点进行多项式插值以获得 $F(x)$。
3. 最后，客户端 $U_j$ 使用 $F(x)$ 和 $C{T}_{agg}$ 获得聚合结果 $m_{agg}$ 。如果在BFV加密中使用了批量编码，在解密聚合密文 $C{T}_{agg}$ 后，需要对明文 $m_{agg}$ 进行解码以恢复所有模型参数。
   

总结

优点

• 做到多密钥环境下的“单轮、无交互聚合”；
• 支持任意数量的客户端掉线；
• 安全性强：服务器与客户端均无法恢复其他实体的更新；
• 精确加解密；
• 无需可信第三方、无需多服务器架构；

缺点

• 单轮通信量巨大，本文为了减少交互，却是以通信量为代价；
• 每轮客户端不仅要计算 BFV ，还要计算 Paillier ，计算开销也不低；
• 多项式插值的计算开销也不小。