最新论文笔记(+23)：VERSA: Verifiable Secure Aggregation for Cross-Device Federated Learning / TDSC23

VERSA: Verifiable Secure Aggregation for Cross-Device Federated Learning
可译为“VERSA: 面向跨设备联邦学习的可验证安全聚合 ”

最近对模型可验证的文章比较感兴趣，就看了几篇，选一篇最新的文章读了读。这篇VERSA主要的贡献点在于，不需要强安全假设和昂贵的加密操作，即可完成模型的可验证性(后续文章证明是不可以完成验证的，并附上证明），并提出了一种模型恢复攻击（主要针对文章VerifyNet）。下面是边看边记录的一点笔记，也可能有理解错的地方，建议看原文。

• 原文链接：VERSA: Verifiable Secure Aggregation for Cross-Device Federated Learning

文章目录预览

• • 一、背景介绍

  • • 1.1 针对VerifyNet的两个问题
    • 1.2 可验证联邦学习两种场景
    • 1.3 系统模型

  • 二、模型恢复攻击

  • • 2.1 同态哈希
    • 2.2 我们的攻击
    • • 2.2.1 攻击场景

  • 2.2.2 实施步骤

  • 2.2.3 处理浮点型梯度

  • 2.2.4 攻击过程

  • 2.2.5 攻击结果

  • 三、VERSA构造

  • • 3.1 密码学原语
    • • 3.1.1 密钥协商

  • 3.1.2 秘密共享

  • 3.1.3 认证加密

  • 3.1.4 伪随机生成器

    • 3.2 SA技术概况
    • • 3.2.1 用户退出

  • 3.2.2 延迟响应

    • 3.3 提出方案
    • • 3.3.1 Correctness

  • 3.3.2 Soundness

  • 四、性能分析

  • • 4.1 实施步骤
    • 4.2 实验结果

一、背景介绍

摘要 ：在传统cross-device（跨设备）联邦学习中，提交加密的本地模型给不可信的中央服务器聚合以更新全局模型。先前的工作依赖强假设来验证聚合结果的正确性，如不可靠网络中所有用户之间的可信设置。或是遭受昂贵的加密操作，如双线性配对。

本文提出了一种模型恢复攻击 ，证明了大多数本地模型可以在合理时间内泄露。进一步，提出了一种可验证的跨设备联邦学习安全聚合协议VERSA 。VERSA无需在用户之间进行任何可信的验证设置，同时允许中央服务器和用户使用轻量级伪随机生成器来证明和验证模型聚合的正确性，从而最大限度地降低了验证成本。

1.1 针对VerifyNet的两个问题

• 1）先前工作采用的可信设置在保护隐私的跨设备FL环境中安全吗？
• 2）是否可能在不依赖任何可信设置的情况下，为保护隐私的跨设备构建可验证的FL方案？

传统可验证FL用同态哈希，这在计算上很昂贵，它严重依赖双线性配对。当梯度为高维向量时，双线性配对使用是主要瓶颈，因为配对必须在向量中的每个条目中运行。但服务器和用户可以合谋，对受害者提交的哈希值进行暴力攻击，从而在合理时间内恢复输入向量的大多数条目。

目标 ：1）不依赖所有用户之间的任何可信设置下实现可验证性；2）验证过程应该是计算轻量级的。

VERSA通过伪随机生成器（PRG）采用秘密扩展来满足这些要求。具体而言，SA中用户共同为本地模型加密生成一组成对共享秘密。反之，共享密钥用作主密钥，通过PRG派生三个会话密钥。一个会话密钥将本地模型更新编码为模型验证代码。此代码对于验证模型聚合有用，因为单个代码的聚合编码单个本地模型更新的聚合。

主要贡献 ：

• 1）提出了基于VerifyNet的模型恢复攻击，并证明攻击者可以在合理时间内恢复受害者的模型更新；
• 2）提出了一种可验证且隐私保护的模型聚合方案VERSA。通过像PRG这样轻量级原语实现模型聚合的可验证性，最好地支持跨设备FL。
• 3）实验在三个数据集（MNIST、SVHN和CIFA100）证明了模型准确性，表明VERSA在不降低准确性的情况下实现了模型更新的隐私性和可验证性。
• 4）我们进行了性能分析SA和VerifyNet的VERSA。评估结果表明额外的成本运行SA之上的VERSA非常小，比VerifyNet快几个数量级。

1.2 可验证联邦学习两种场景

• 1）服务器扮演证明者的角色，证明它诚实地聚合了本地模型参数，用户为独立的验证者。（我理解的是用户验证全局模型的完整性）
• 2）用户扮演证明者的角色，证明他们没有偏离协议，而服务器是验证者。（我理解的是服务器验证局部模型的可用性）

本文关注第一种场景 ！

1.3 系统模型

• 1）所有n个参与者将本地模型更新发送到服务器；
• 2）服务器聚合本地模型更新；
• 3）将结果返回给每个参与者；
• 4）所有参与者将全局模型更新应用于他们的模型。

与传统FL的区别在于，可验证FL在启用SA的FL之上，其中服务器生成了一个证明其执行正确性的证明，并广播结果。最后，每个参与者验证全局模型更新。

VERSA使每个幸存用户能够验证聚合模型的正确性，并在SA上运行，使用与SA相同的轻量级加密原语实现可验证性。

• 1）发布和共享密钥：这与SA中的发布和共享密钥阶段相同；
• 2）掩蔽：对应于掩蔽相位SA，除了梯度屏蔽之外，用户还派生出一个公共评估密钥和一个私有验证密钥，这两个密钥在后续阶段分别由服务器和用户使用；
• 3）解码并生成模型聚合的证明：对应于SA的解除屏蔽阶段，除了模型聚合之外，服务器还使用评估生成证明，以证明聚合梯度的正确性。服务器广播证明和聚合梯度。
• 4）验证模型聚合：用户使用验证密钥验证模型聚合的正确性，若验证成功，则接受聚合梯度，否则拒绝。

二、模型恢复攻击

描述了基于同态哈希的可验证安全聚合VerifyNet的模型恢复攻击，并证明了攻击的可行性。为了更好理解攻击过程，我们简要解释了使用同态哈希在聚合梯度上实现可验证性的一般方法。

2.1 同态哈希

同态哈希允许对一组哈希值(H(m_1),\cdots,H(m_t))的输入求值一个算术函数F，使得求值算法返回H(f(m_1,\cdots,m_t))，更准确地说，一组单向键控同态哈希H由以下三种算法组成：

• k\leftarrow H.gen：这是一个密钥哈希函数H_k的私钥k生成算法。
• H_k(m)\leftarrow H：这是一个哈希计算算法，对输入m返回H_k(m)。
• H_k(f(m_1,\cdots,m_t))\leftarrow H.eval：这是一个函数求值算法，输入一组哈希值H_k(m_1),\cdots,H_k(m_t)，返回H_k(f(m_1,\cdots ,m_t))。

单向键控哈希函数H的安全性保证了从H_k(m)反转到恢复m实际上是不可行的，应用到SA当中：

• 1）所有用户u共享同态哈希H的秘密密钥k；
• 2）每个用户计算梯度的哈希值H_k(x_u)，并提交一对(SA.mask(x_u), H_k(x_u))给服务器，其中SA.mask(x_u)表示已掩盖的梯度x_u。
• 3）服务器聚合所有的\{SA.mask(x_u)\}_{u\in U}，返回z。服务器计算从用户u接收到的所有哈希值，返回\widehat{z}=H_k(\sum_{u\in U} x_u)，服务器广播一对(z,\widehat{z})。
• 4）在这个阶段，用户在\widehat{z}的协助下验证z=^?\sum_{u\in U} x_u。为此，每个用户计算z的哈希值，然后当且仅当H_k(z)=\widehat{z}时，用户接受z作为正确聚合的模型更新，否则终止。

2.2 我们的攻击

利用观察到的两个特征在VerifyNet上的模型恢复攻击：

• 1）模型参数的分布是高度偏置的 。使得SGD规则生成的梯度项在零附近形成钟形分布。若没有这种观察我们将别无选择，只能在非常大的范围内发动brute-force攻击，比如(-\infty, \infty)在计算上不可行的。
• 2）为了在VerifyNet中对梯度进行编码并验证聚合梯度，所有用户必须共享用于同态哈希的相同秘密参数 。很容易受到恶意用户与服务器勾结发动的暴力攻击，这样编码的梯度可以对受害者同态哈希输出的暴力攻击中恢复。这种用户服务器勾结是包含个人梯度机密性的最重要的安全问题。

2.2.1 攻击场景

在每个用户的本地设备上使用SGD规则在MNIST数据集上运行TensorFlow，并使用同态哈希对梯度进行编码，并将结果发送给服务器。服务器通过与恶意用户串通获取所有同态哈希参数，对受害者提交的同态哈希输出进行暴力攻击。

2.2.2 实施步骤

使用了两种同态哈希算法：DRV哈希和KFM哈希 。前者是VerifyNet中使用，后者是证明本攻击可行性不依赖于编码梯度的任何特定同态哈希。对于DRV哈希，使用MNT224曲线，这是基于配对的加密库中实现的配对的Type-III曲线。由于KFM哈希，使用256、512和1024位质数，每个质数实例化三个独立的KFM哈希，并使用这三种KFM哈希来衡量我们对各种长度质数的攻击的可行性。

2.2.3 处理浮点型梯度

由于DRV哈希和KFM哈希都以整数值为输入，所以训练得到的浮点参数需要在范围内缩放\{-\frac{p-1}{2},\cdots,0,\cdots,\frac{p-1}{2}\}，其中p是用于哈希的大素数。根据浮点数到整数的转换方法，对浮点值v进行量化为整数\lfloor v\cdot \alpha \rfloor，其中\alpha是放缩因子，其中\alpha值越大，量化误差越小。设置\alpha=2^{prec}，其中prec指的是神经网络用来表示梯度值的位精度。

研究表明，16位精度足以不影响模型精度的情况训练神经网络，从而有利于提高能源效率和降低精度表征。因此，我们使用32位精度和16位精度的MNIST训练数据集，以获得两个独立的梯度集。我们对后一组的攻击测量了对基于同态哈希的可验证SA的暴力攻击降低降低的影响。

2.2.4 攻击过程

假设两个梯度集中每个都包含750个梯度，其中每个梯度形成一个包含10个entries的向量（是10维度的意思吗？ ）。由于预计分布将高度偏向于0，因此大多数参数将驻留在一个短对称区间内，如(-x,x)。图2绘制了这些entries的分布，表明它们形成了以零为中心的窄钟形曲线，该图表明，即使我们将x设置为一个小值，例如x=0.2，大多数参数也可以恢复。最后，使用DRV、KFM-256、KFM-512和KFM-1024为每个entries分别获得了四个哈希值。

令h(\lfloor v\cdot \alpha \rfloor)是浮点型梯度项v哈希的对应项。令0是一个浮点型值，使得存在一个整数n满足\lfloor v\cdot \alpha \rfloor=r\cdot n。当穷尽地从0增加（或减少）到i时，我们检查是否h(\lfloor v\cdot \alpha \rfloor)=h(\lfloor r\cdot \alpha \rfloor \cdot i)。这个循环当\lfloor r\cdot \alpha \rfloor \cdot i > \lfloor x \cdot \alpha \rfloor（或\lfloor r\cdot \alpha \rfloor \cdot i < \lfloor -x \cdot \alpha \rfloor）时结束，表明循环超出了给定范围(-x, x)，其中x是一个真实地数字。

选择(r,x)会影响攻击性能。例如，当将r和x分别设置的尽可能小和尽可能大时，恢复的梯度数量将会增加，但代价是完成攻击的时间会增加。尝试了多种(r,x)对，以经验平衡恢复梯度数量和所需时间。在实验中，我们设置r=10^{-7}、10^{-9}分别为16位和32位精度，其中x\in\{0.2,0.3,0.4\}。对于每个哈希梯度集，均匀随机选择100个哈希梯度，并对每个哈希梯度项发起攻击，以测量恢复其对应项（即浮点型梯度项）所需的时间。给定范围内(-x,x)没有找到对应的哈希梯度entries时，我们会终止对每个哈希梯度entries的攻击。

2.2.5 攻击结果

表1总结了三个月内测量的攻击结果，而图3详细展示了我们在给定时间段内恢复梯度entries的速度。对攻击结果的准确性和效率进行了评价。准确度是指恢复的梯度entries数与梯度entries总数之比，效率指是完成攻击所需的时间。

三、VERSA构造

3.1 密码学原语

3.1.1 密钥协商

允许两个不同用户在公共通道上生成共享密钥。（如DH密钥协商）

• 1）pp\leftarrow KA.param(\lambda)：这个算法给定一个安全参数\lambda作为输入，返回一个公共参数pp。
• 2）(pk_u,sk_u)\leftarrow KA.gen(pp)：这个算法给定pp作为输入，返回用户u一个公私钥对(pk_u,sk_u)。
• 3）s_{u,v}\leftarrow KA.agree(sk_u,pk_v)：这个算法给定用户u的sk_u和用户v的pk_v作为输入，返回一个共享密钥s_{u,v}。

3.1.2 秘密共享

利用Shamir (t,n)秘密共享协议，定义就不写了。

3.1.3 认证加密

本文使用对称认证加密，保证了消息的机密性和完整性。（其实就是对称加密的加解密）

3.1.4 伪随机生成器

将输入种子映射到伪随机输出序列，并保证均匀选择的种子上的输出分布在计算上与均匀分布无法区分。本文使用PRG，它将一个输入值展开成一个n维的输出向量，其中R是一个大整数。

3.2 SA技术概况

SA（Secure Aggregation）就是CCS17那篇论文的简写，通过密钥协商允许每两个用户u,v共同生成共享的秘密值，分别为sk_u,sk_v。若由用户u持有，将这个秘密值表示为s_{u,v}，若用户v持有，则表示为s_{v,u}，其中s_{u,v}=s_{v,u}。用户u用s_{u,v}作为PRG的种子，导出随机向量P_{u,v}=PRG(s_{u,v})对梯度进行加密。更准确的说，给定具有逻辑身份的n个用户[1,\cdots,n]集合U，用户u掩盖梯度x_u如下：
y_u=x_u+\sum_{v\in U,uv}PRG(s_{v,u})
考虑到两个掩码梯度y_u和y_v的聚合，然后，分别由u和v生成的两个随机向量PRG(s_{u,v})和PRG(s_{v,u})相互抵消。因此，如果所有用户都成功提交了y_{u\in U}，那么服务器将获得聚合梯度\sum_{u\in U}x_u =\sum_{u\in U}y_u。进一步考虑用户退出问题。

3.2.1 用户退出

考虑用户 u在发送掩码之后梯度之前退出的情况。所有随机向量PRG(s_{v,u})，其中v\in U在\sum_{u\in U}y_u中保持未取消。SA的解决办法是，用户u使用SS将密钥sk_u分成n个共享，这些共享分配给所有用户v\in U，这样用户v只获得一个份额。然后，服务器要求幸存的用户提交退出的用户的秘密密钥sk_u的份额，因此服务器能恢复密钥，计算PRG(s_{u,v})，并从\sum_{u\in U}y_u中删除所有PRG(s_{v,u})。

3.2.2 延迟响应

考虑用户无法及时与服务器通信情况。具体说，用户u可能会延迟传输梯度，因此服务器会收集sk_u的份额。这显然会引发一个安全问题，服务器可以通过派生和删除用于掩盖x_u的所有\{s_{u,v}\}_{v\in U}，从份额中恢复sk_u，并从y_u中恢复泄露x_u，而y_u会较晚到达服务器。SA通过允许u屏蔽x_u两次来解决这个问题：u选择一个随机的种子b_u并计算
y_u=y_u+PRG(b_u)
服务器应该删除PRG(b_u)以获得聚合梯度。为此，每个用户u拆分b_u，并将份额提前发送给所有用户u。然后，在去掩码阶段，服务器必须对每个用户做出明确的选择。对于所有退出用户u\in U，服务器要求幸存的用户提交sk_u的份额。对于幸存的用户u\in U，服务器要求他们提交b_u的份额。因此，服务器可以通过从\sum_{u\in U}y_u中删除所有PRG(s_{v,u})和PRG(b_u)来恢复明文形式的聚合梯度。

3.3 提出方案

如下图所示，为本方案的完整步骤：

为了简单起见，我们忽略用户退出和延迟响应。也就是说，假设所有对(y_u,\bar{y}_u)_{u\in U}及时到达服务器。VERSA利用双重聚合实现了梯度的可验证性。第一次聚合用于计算聚合梯度本身，第二次聚合用于证明第一次聚合的正确性 。在VERSA，每个用户u提交(y_u,\bar{y}_u)。具体来说，\bar{y}_u加密了一个模型验证码F(x_u)=a\circ x_u+b，其中操作\circ是Hadamard product，两个向量(a,b)是隐藏在服务器视图中的秘密向量，所有用户u\in U可以计算相同的向量对(a,b)。下面将解释（i）如何将模型验证码用于可验证计算，以及（ii）如何共享(a,b)无需用户之间的额外通信。

服务器执行两次聚合，以便获得z=\sum_{u\in U}y_u和\bar{z}=\sum_{u\in U}\bar{y}_u，其中\bar{z}=a\circ \sum_{u\in U}x_u+|U|\cdot b。最终，用户通过检查以下条件是否成立来验证
\bar{z}=^?a\circ z+|U|\cdot b.
z的可验证性有以下原因：\bar{z}用两个向量(a,b)封装了z，这些向量对服务器是隐藏的。因此，服务器伪造\sum_{u\in U}x_u的概率（即从z得到聚合结果）被简化为恢复(a,b)的概率，由于PRG的单向性，这是不可行的。而且，只要SA的隐私保证被保留，服务器就无法从\bar{y}_u中恢复F(x_u)。也就是说，我们使用SA的掩蔽方法掩盖F(x_u)。因此，即使(a,b)由于用户与服务器合谋而泄露给服务器，服务器从\bar{y}_u恢复x_u的概率降低到SA被攻破的概率。

这种简化的描述忽略了一个技术障碍。所有幸存的用户必须提前拥有一对向量(a,b)。实现这个假设的一种直接方法是它们之间建立安全通道，并确保它们通过安全通道共享这样一个对。然而，这种方法并不适合用于跨设备FL设置。作为一种替代方法，可以多方计算协议，允许所有用户共同计算对。然而，它要求通信回合与参与实体的数量呈线性关系。但由于繁重的加密算法（如全同态），其计算成本仍然是压倒性的。

可以通过PRG的秘密扩展来解决这个问题 。具体来说，SA中的每个用户u在本地允许密钥协商，使用幸存用户u的所有公钥来计算一组秘密值\{s_{u,v}\}集合来掩盖它的梯度。我们的方法是允许每个幸存的用户通过PRG从\{s_{u,v}\}派生另一个秘密值。首先，用户u计算\alpha \leftarrow \sum_{v\in U}s_{u,v} (mod \ R)。下一步，u将\alpha扩展为两个向量
a=PRG(\alpha||0), b=PRG(\alpha||1)
由于PRG的单向性和伪随机性，服务器既不能从(z,\bar{z})中恢复\alpha，也不能恢复(a,b)。同时，每个幸存用户u都可以从\{s_{u,v}\}_{v\in U}中派生出\alpha和生成(a,b)，从而验证z。

3.3.1 Correctness

在VERSA中求和（即\sum_{u\in U}x_u和\sum_{u\in U}F(x_u))的正确性被简化为SA的正确性，即使在一些用户退出时，这种简化仍有效。假设服务器接收所有对(y_u,\bar{y}_u)_{u\in U}和正确执行SA。在聚合y_u的情况下，以下条件成立。
\sum_{u\in U}y_u=\sum_{u\in U}x_u+\sum_{u\in U}\sum_{v\in U,uv}PRG(s_{u,v})=\sum_{u\in U}x_u (mod \ R),
其中用户u和v生成的所有PRG(s_{u,v})和PRG(s_{v,u})相互抵消。
在聚合\bar{y}_u的情况下，以下条件成立。
\sum_{u\in U}\bar{y}_u=\sum_{u\in U}F(x_u)=\sum_{u\in U}a\circ x_u+\sum_{u\in U}b=a\circ \sum_{u\in U}x_u+|U|\cdot b(mod \ R)

3.3.2 Soundness

当服务器返回正确的聚合梯度时，当且仅当服务器能够convince用户时，VERSA保证了可靠性。服务器无法生成有效的证明（即\bar{z}），而没有正确运行VERSA。

为了正式捕获VERSA的可靠性属性，我们使用基于game的安全模型，其中敌手（试图破坏方案）与挑战者（谁运行这个方案）交互。敌手是服务器，挑战者是代表（幸存）用户的实体。假设PRG是安全的，我们证明了VERSA是安全的。为了做到这点，我们定义了一个可靠性game，在这个game中，敌手会从挑战者哪里获得一个对\{y_u,\bar{y}_u\}_{u\in U}的集合。敌手返回(z,\bar{z})证明聚合正确完成。敌手的目标是诱使挑战者接受一对假的(z^*,\bar{z}^*)。在这个设置中，我们对挑战者设置了一个限制来验证(z^*,\bar{z}^*)，通过运行VERSA的Validating Output阶段，而不是从零开始聚合\{y_u,\bar{y}_u\}_{u\in U} 。这种限制是合理的，因为在跨设备的FL设置中，没有实体访问所有对\{y_u,\bar{y}_u\}_{u\in U}，除了服务器（game中的敌手）。

安全分析就暂时不记录了，后续有时间再添加。

四、性能分析

将VERSA与SA和VerifyNet两种基线方案对比来说明如何提高更高安全的同时提高效率。

4.1 实施步骤

测量了四个阶段的计算时间：共享密钥、屏蔽输入、解除屏蔽输入和返回输出，以及验证输出 。实验在一台配备3.00GHz Intel Core i7-9700处理器和16 GB RAM的台式机上使用JAVA进行的。我们用椭圆曲线DH，Shamir (t,n)秘密共享，AES 128-bit私钥，和SHA-256实施KA、SS、AE，和PRG。为SS设置t=10，用随机生成的10k entry向量，每个entry为64-bit，同时改变用户数量和用户退出率，以获得对这两个不同因素如何影响建议的四个阶段的性能。为了实现VerifyNet，我们使用JAVA编写的基于配对的加密库，实验在两个用户组中进行，分别由500和1000个用户组成。

4.2 实验结果

在掩蔽输入阶段，SA的效率优于VerifyNet和VERSA，因为SA只支持梯度的隐私保护，而其他的则作为补充功能支持聚合梯度的验证。VERSA的成本大约是SA的两倍。与SA相比，VERSA通过PRG执行两次矢量扩展，其中矢量扩展是SA和VERSA的计算主导操作。

相反，VerifyNet产生了比SA和VERSA更多的成本，这是因为VerifyNet中广泛使用了群操作，这些群操作的计算成本超过了通过PRG进行向量展开的计算成本。在解除屏蔽输入和返回输出阶段，VERSA和SA在不发生丢包时显示相似的代价。但当出现丢包时，这些方案表现出明显的成本差异，因为与SA相比，服务器重构这些向量两次。

后续有两篇文章指出了VerSA并不支持可验证性，见

Luo F, Wang H, Yan X. Comments on “VERSA: Verifiable Secure Aggregation for Cross-Device Federated Learning”[J]. IEEE Transactions on Dependable and Secure Computing, 2023.

由于密钥协商 的秘密值由其他用户的公钥计算而来，即\{s_{u,v}\}_{v\in U}和\{s_{v,u}\}_{u\in U}不一定相等，故验证机制不通过。**以下是验证过程：

• 1）假设有三个用户u,v,w，他们分别两两协商密钥有

  • 用户u计算s_{u,v}=KA.agree(sk_u,pk_v), s_{u,w}=KA.agree(sk_u,pk_w)，\alpha_u=s_{u,v}+s_{u,w}。
  • 用户v计算s_{v,u}=KA.agree(sk_v,pk_u), s_{v,w}=KA.agree(sk_v,pk_w)，\alpha_v=s_{v,u}+s_{v,w}。
  • 用户w计算s_{w,u}=KA.agree(sk_w,pk_u), s_{w,v}=KA.agree(sk_w,pk_v)，\alpha_w=s_{w,u}+s_{w,v}。

• 2）已知s_{u,v}=s_{v,u},s_{u,w}=s_{w,u},s_{v,w}=s_{w,v}。要使得\alpha_u=\alpha_v=\alpha_w，则只有s_{u,w}=s_{v,w},s_{v,u}=s_{w,u}。

• 3）由于密钥协商的安全性，这种概率忽略不计，故无法保证上式成立，也就无法完成验证。