安全多方计算 (SMC) 聚合协议

安全多方计算 (SMC) 采用加密方法实现隐私，与通过添加噪声实现隐私的差分隐私等方法形成对比。SMC 在联邦学习中的主要目标是允许中心服务器计算客户端更新的聚合值（通常是求和或加权平均），而无需获知任何单个客户端的更新。设想有多个参与方，每个方持有一个私密输入（其模型更新 $u_i$），它们希望计算一个联合函数（例如总和 $\sum u_i$），同时又不向彼此或聚合服务器公开其输入。

核心原理：基于秘密共享进行计算

许多用于安全聚合的实用SMC协议都依赖于秘密共享的想法。大致思路是将每个客户端的私密更新向量 $u_i$ 分割成多个片段，称为份额。这些份额的分配方式如下：

1. 单个份额几乎不透露原始更新 $u_i$ 的任何信息。
2. 特定函数（如求和）可以直接在份额上计算。
3. 在份额上计算得到的函数结果与应用于原始秘密值的函数结果一致。
4. 除非结合了足够数量的份额（通常是所有份额，或预设阈值），否则无法重建原始秘密值 $u_i$，而协议设计会阻止这种情况发生。

用于聚合的加性秘密共享

一种常见且相对高效的安全求和技术是加性秘密共享。下面我们介绍一个简化的协议，它涉及 $N$ 个客户端和一个服务器，旨在计算 $S = \sum_{i=1}^{N} u_i$，同时服务器不获知任何 $u_i$。

1. 成对掩码生成： 在发送更新之前，每对客户端 $(i, j)$（其中 $i < j$）需要协商确定一个大的随机数（或向量）$m_{ij}$。此掩码必须仅客户端 $i$ 和 $j$ 知晓。这可以通过使用诸如迪菲-赫尔曼密钥交换等技术来实现，以建立成对的对称密钥，然后这些密钥为两个客户端的伪随机数生成器（PRNG）提供种子，从而独立生成相同的 $m_{ij}$。

2. 客户端侧掩码： 每个客户端 $i$ 使用其与其他客户端共享的成对掩码来掩盖其更新向量 $u_i$。它计算一个掩码更新 $u'_i$：

   $$u'_i = u_i + \sum_{j > i} m_{ij} - \sum_{j < i} m_{ji} \pmod{M}$$

   此处，$M$ 是一个大整数，定义了进行计算的有限域或环。对于向量，加法和减法通常是按元素进行的。本质上，客户端 $i$ 添加它与具有较高索引的客户端生成的掩码，并减去与具有较低索引的客户端生成的掩码。

3. 发送到服务器： 每个客户端 $i$ 只将其掩码更新 $u'_i$ 发送给服务器。

4. 服务器侧聚合： 服务器简单地对其接收到的掩码更新进行求和：

   $$S' = \sum_{i=1}^{N} u'_i \pmod{M}$$

5. 掩码抵消： 让我们分析总和 $S'$。当服务器对 $u'_i$ 求和时，每个掩码 $m_{ij}$（其中 $i < j$）恰好出现两次：一次在 $u'_i$ 中为正（来自项 $+\sum_{k > i} m_{ik}$），一次在 $u'_j$ 中为负（来自项 $-\sum_{k < j} m_{jk}$）。因此，所有掩码在最终总和中相互抵消：

   $$S' = \sum_{i=1}^{N} \left( u_i + \sum_{j > i} m_{ij} - \sum_{j < i} m_{ji} \right) = \sum_{i=1}^{N} u_i + \sum_{i=1}^{N} \sum_{j > i} m_{ij} - \sum_{i=1}^{N} \sum_{j < i} m_{ji} \pmod{M}$$

   由于每个 $m_{ij}$ 都出现一次正数和一次负数，总和简化为：

   $$S' = \sum_{i=1}^{N} u_i = S \pmod{M}$$

   服务器获得了准确的总和 $S$，而无需查看任何单个的 $u_i$。

使用加性秘密共享实现安全聚合的交互流程。客户端建立成对秘密（虚线），在本地掩盖其更新，并将掩码更新（蓝色箭头）发送到服务器。服务器对这些更新求和，掩码相互抵消，仅公开聚合总和（黄色箭头）。

安全假设与考量

这种加性共享方案针对诚实但好奇的服务器提供安全性。服务器正确遵循协议，但可能会尝试从其接收到的消息（即 $u'_i$）中推断信息。由于 $u'_i$ 实际上是 $u_i$ 加上服务器未知的随机值之和/差（因为每个 $m_{ij}$ 都涉及客户端 $j \neq i$），因此假设掩码是密码学安全的随机数， $u'_i$ 不会向服务器公开任何有关 $u_i$ 的信息。

然而，这种基本方案存在局限性：

• 串谋： 如果服务器与一个或多个客户端串谋，它们可能能够重建非串谋客户端的更新。例如，如果服务器与客户端 1 串谋，它知道 $u'_1$。它还知道所有涉及客户端 1 的掩码 $m_{1j}$。这会损害其他客户端的隐私。
• 客户端掉线： 如果客户端计算了其掩码份额 $u'_i$ 但在发送到服务器之前掉线，服务器将计算出一个不正确的总和，因为涉及掉线客户端的掩码将无法完全抵消。聚合协议需要处理掉线的机制，这通常涉及阈值密码学（如沙米尔秘密共享）或更复杂的交互协议。
• 计算和通信开销：
  • 设置： 建立成对秘密会产生通信和计算开销（例如，交换）。
  • 掩码： 客户端执行额外的加法/减法运算。对于高维模型，这通常可以处理。
  • 通信： 发送的更新 ($u'_i$) 的大小与原始更新 ($u_i$) 相同。然而，设置阶段会增加通信轮次。更多协议通常需要客户端之间或客户端与服务器之间进行多轮交互。

沙米尔秘密共享与阈值密码学

沙米尔秘密共享 (SSS) 是另一种适用于 SMC 的基础技术。在 $(t, n)$-SSS 中，一个秘密被分割成 $n$ 个份额，其中任意 $t$ 个份额可以重建秘密，但 $t-1$ 个份额不透露任何信息。这可以通过让客户端使用 SSS 共享其更新来用于聚合。聚合可以在份额上执行（由于 SSS 中使用的多项式插值的同态性质）。SSS 提供了针对多达 $n-t$ 个掉线的固有稳定性（如果 $t$ 个客户端成功提交份额），以及针对多达 $t-1$ 个参与方串谋的安全性。然而，与简单的加性共享相比，SSS 通常涉及更复杂的操作（多项式求值/插值）。

与差分隐私（DP）和同态加密（HE）的比较

• SMC 与 DP： SMC 旨在阻止服务器获知关于个体更新的任何信息，从而针对服务器提供强大的输入隐私保护。DP 允许服务器查看（带噪声的）更新，但提供了关于即使从最终模型中，关于任何贡献该更新的个体数据可以推断出什么的正式保障。它们应对不同的隐私方面。SMC 不直接防御针对最终聚合模型的推断攻击。
• SMC 与 HE： SMC 和 HE 都允许在不公开原始输入给服务器的情况下进行计算（聚合）。HE 涉及客户端加密更新、服务器在密文上进行计算以及解密（通常需要中心化或多方解密）。HE 有时会比特定的 SMC 协议产生更高的计算开销，特别是对于复杂计算，但可能比某些 SMC 方案需要更少的客户端间交互。选择通常取决于具体的性能要求、安全假设和系统架构。

"设计基于SMC的实用联邦学习系统，需要仔细权衡安全保障与计算和通信成本，并处理客户端掉线等实际问题。"