第 7 章通过 Beaver 三元组实现 MPC

学习目标

掌握本章核心定义、协议步骤与安全结论。
能复述协议输入/输出与理想功能，并指出图中关键步骤。
理解半诚实/恶意设定下的证明思路（模拟器与归约）。

无论是BGW协议、GMW协议，还是第1章所介绍的协议，可以发现：线性门（加法门、常数乘法门、常数加法门、异或门、非门）的开销很小，参与方仅需在本地进行计算即可；而非线性门（乘法门、与门）的开销很大，参与方需要两两进行交互，并调用较为复杂的子协议（例如OT、OLE）。

为了降低非线性门的计算开销，Beaver三元组(Beaver triple) [Beaver et al.]是一种被广泛采用的实用技术。它的基本思想是：将MPC协议分为在线阶段和离线阶段（预处理阶段），离线阶段生成与输入无关的相关随机数（指具有特定关系的随机值，即Beaver三元组），在线阶段通过消耗这些相关随机数来加速乘法门的计算。这样的设计模式可以将大部分开销转移到离线阶段，从而大大提升在线阶段的效率。

下面，本章的介绍采用模块化的方法：首先，将Beaver三元组的生成抽象为理想功能 $\mathcal{F}_{\mathsf{triple}}$，在 $\mathcal{F}_{\mathsf{triple}}$-混合模型下构造高效的协议并进行安全性证明。然后，我们讨论如何生成Beaver三元组，即如何实现 $\mathcal{F}_{\mathsf{triple}}$.

基于Beaver三元组的MPC协议

Beaver三元组

Beaver三元组由Beaver提出 [Beaver et al.]，它指的是秘密份额集三元组 $([a], [b], [c])$，其中 $a, b$ 为有限域 $\mathbb{F}$ 上均匀随机选取的元素，满足 $c = ab$.

为了叙述的简洁，我们先定义一些方便的符号来表示加法秘密分享的计算。我们用 $[x]$ 表示秘密 $x \in \mathbb{F}$ 的秘密份额集，即 $[x] = (x_1,…,x_n)$，满足 $x = x_1 + … x_n$. 我们采用与BGW协议类似的术语：参与方 $P_i$ 分发 $x$，指的是 $P_i$ 均匀随机选择 $x_1, …, x_n$ 满足 $x = x_1 + … x_n$，然后将 $x_\ell$ 发送给 $P_\ell$. 当参与方获得了 $x$ 的份额时，我们说参与方持有 $[x]$.

对于常数 $\alpha \in \mathbb{F}$，我们定义如下的逐项加法、常数乘法和常数加法：

Beaver三元组 · 公式

\begin{aligned} [x] + [y] & = (x_1 + y_1, \ldots, x_n + y_n) \\ \alpha[x] & = (\alpha x_1, \ldots, \alpha x_n) \\ [x] + \alpha & = (x_1 + \alpha, x_2, \ldots, x_n) \end{aligned}

Beaver三元组 · 公式

很容易发现，加法秘密分享满足如下的性质：

\begin{aligned} [x] + [y] & = [x + y] \\ \alpha [x] & = [\alpha x] \\ [x] + \alpha & = [x + \alpha] \end{aligned}

让我们看看Beaver三元组是如何实现乘法门的计算的。假设乘法门的输入 $x, y$ 已经被秘密分享在 $n$ 个参与方之中，每个参与方还持有Beaver三元组 $([a], [b], [c])$ 中自己对应的份额，即参与方持有 $([x], [y], [a], [b], [c])$，其中 $x, y$ 是乘法门的输入，$([a], [b], [c])$ 是Beaver三元组。

乘法门的计算分为如下三个步骤：

参与方本地计算 $[x] - [a] = [x - a], [y] - [b] = [y - b]$.
对上一步计算的份额进行秘密重建，所有参与方获得 $d = x - a, \; e = y - b$.
参与方本地计算 $d[b] + e[a] + [c] + de$，作为输出导线的份额。

首先，这样计算获得的结果是正确的。根据加法秘密分享的性质，我们有 $[xy] = [(d + a)(e + b)] = [de + db + ea + ab] = d[b] + e[a] + [c] + de$. 因此，$d[b] + e[a] + [c] + de$ 就是 $xy$ 的秘密份额集。关于隐私性，协议的第1和第3步都是本地计算，而在第2步中，参与方进行了秘密重建得到了 $d = x - a, \; e = y - b$. 我们需要确保 $x, y$ 不被泄露，协议确实满足了这一点，因为 $a, b$ 都是均匀随机值，因此 $d, e$ 也是均匀随机值，不会泄露任何信息。

与同样采用加法秘密分享的GMW协议相比，通过Beaver三元组实现的乘法门计算只需对两个值进行秘密重建，在半诚实模型下可以让所有参与方将秘密份额发给 $P_1$，$P_1$ 再将重建结果发给每个参与方，只需 $O(n)$ 的通信量。而GMW协议中乘法门的计算需要参与方两两执行OLE，共 $O(n^2)$ 个OLE. 由此可见，Beaver三元组显著降低了乘法门所需的通信量和计算量。

协议描述

根据以上计算乘法门的方法，我们很容易构造基于Beaver三元组的MPC协议，其加法门、常数乘法门以及输出重建的过程与GMW协议完全相同。完整的协议如图 7.1所示。

基于Beaver三元组的MPC协议

协议分为三个阶段：输入分享阶段、计算阶段和输出重建阶段。参与方 $P_1, …, P_n$ 想要计算函数 $f: \mathbb{F}^{M_\mathsf{in}^1} \times \cdots \times \mathbb{F}^{M_\mathsf{in}^n} \rightarrow \mathbb{F}^{M_\mathsf{out}^1} \times \cdots \times \mathbb{F}^{M_\mathsf{out}^n}$ 并已经将其转化成了包含加法门、常数乘法门、常数加法门、乘法门的算术电路。参与方已经生成并持有了 $m$ 个Beaver三元组 $([a^k], [b^k], [c^k]), k \in [1,m]$. 设电路的乘法门数量不超过 $m$.

输入分享阶段。对于 $P_i$ 的每个输入 $x_{i, k} \in \mathbb{F}, \; k \in [M_\mathsf{in}^i]$，$P_i$ 分发 $x_{i, k}$.

计算阶段。重复以下步骤，直到所有门都被计算。根据门的类型，执行以下操作之一：

加法门。假设参与方持有 $[w_i], [w_j]$. 参与方计算 $[w_i] + [w_j] = [w_i + w_j]$.
常数乘法门。假设对应的常数为 $\alpha$，参与方持有 $[w_i]$. 参与方计算 $\alpha [w_i] = [\alpha w_i]$.
常数加法门。假设对应的常数为 $\alpha$，参与方持有 $[w_i]$. 参与方计算 $[w_i] + \alpha = [w_i + \alpha]$.
乘法门。假设参与方持有 $[w_i], [w_j]$ 以及Beaver三元组 $([a], [b], [c])$. 参与方执行以下操作：
1. 参与方本地计算 $[w_i] - [a] = [w_i - a], [w_j] - [b] = [w_j - b]$.
2. 对上一步计算的份额进行秘密重建，所有参与方获得 $d = w_i - a, \; e = w_j - b$.
3. 参与方本地计算 $d[b] + e[a] + [c] + de = [w_i w_j]$.

输出重建阶段。对于 $P_i$ 的每个输出 $y_{i, k} \in \mathbb{F}$，其他参与方将自己的份额 $s_{i, k}^\ell, \; \ell \neq i$ 发给 $P_i$，$P_i$ 计算 $y_{i, k} = s_{i, k}^1 + … + s_{i, k}^n$.

安全性证明

我们在 $\mathcal{F}_{\mathsf{triple}}$-混合模型下证明，上述协议对于静态半诚实敌手UC-安全实现了安全函数计算的理想功能 $\mathcal{F}_{\mathsf{sfe}}$. 也就是说，我们假设参与方在协议的离线阶段通过请求 $\mathcal{F}_{\mathsf{triple}}$ 获得了Beaver三元组。$\mathcal{F}_{\mathsf{triple}}$ 的定义如图 7.2所示。

Beaver三元组生成的理想功能 $\mathcal{F}_{\mathsf{triple}}$

理想功能 $\mathcal{F}_{\mathsf{triple}}$ 与参与方 $P_1, …, P_n$ 交互。

输入： 参与方没有输入。

理想功能 $\mathcal{F}_{\mathsf{triple}}$ 执行如下操作：

随机选取 $a, b \leftarrow_{\$} \mathbb{F}$，计算 $c = ab$.
随机选取 $a_1, b_1, c_1, …, a_n, b_n, c_n$，满足 $a = a_1 + … + a_n, \; b = b_1 + … + b_n, \; c = c_1 + … +c_n$.
对所有 $i \in [n]$，将 $a_i, b_i, c_i$ 发送给 $P_i$.

Beaver三元组生成的理想功能 $\mathcal{F}_{\mathsf{triple}}$

定理

假设被攻陷方数量不超过 $n - 1$，图 7.1中的协议 $\Pi$ 在 $\mathcal{F}_{\mathsf{triple}}$-混合模型下对于静态半诚实敌手UC-安全实现了理想功能 $\mathcal{F}_{\mathsf{sfe}}$（图 6.2）。

安全性证明

要证明该定理，我们需要构造模拟器 $\mathcal{S}$，使得对所有PPT的环境 $\mathcal{Z}$，都有

\operatorname{exec}_{\Pi, \mathcal{A}, \mathcal{Z}}^{\mathcal{F}_{\mathsf{triple}}} \approx \operatorname{exec}_{\mathcal{F}_{\mathsf{sfe}}, \mathcal{S}, \mathcal{Z}}

其中 $\mathcal{A}$ 是平凡敌手。

模拟器 $\mathcal{S}$. 模拟器 $\mathcal{S}$ 在内部运行 $\mathcal{A}$，转发 $\mathcal{Z}$ 与 $\mathcal{A}$ 之间的消息。此外，$\mathcal{S}$ 模拟 $\mathcal{F}_{\mathsf{triple}}$ 诚实地生成Beaver三元组。令 $C$ 为被攻陷方的集合。$\mathcal{S}$ 的工作方式如下。

当从 $\mathcal{F}_{\mathsf{sfe}}$ 收到 $(\operatorname{Input}, \mathsf{sid}, P_i)$ 时，如果 $P_i \in C$，那么 $P_i$ 是被攻陷的，$\mathcal{S}$ 可以得到 $P_i$ 的输入 $(x_{i, 1}, …, x_{i, M_\mathsf{in}^i})$. $\mathcal{S}$ 以 $(x_{i, 1}, …, x_{i, M_\mathsf{in}^i})$ 为输入模拟 $P_i$ 遵循协议执行输入分享。
当从 $\mathcal{F}_{\mathsf{sfe}}$ 收到 $(\operatorname{Input}, \mathsf{sid}, P_j)$ 时，如果 $P_j \notin C$，那么 $P_j$ 是诚实的。$\mathcal{S}$ 设置 $P_j$ 的输入为 $(x_{j, 1}, …, x_{j, M_\mathsf{in}^j}) = (0, …, 0)$，然后模拟 $P_j$ 遵循协议执行输入分享，将秘密份额发给被攻陷方。
计算阶段，$\mathcal{S}$ 模拟诚实方和被攻陷方遵循协议执行。（也就是说，$\mathcal{S}$ 模拟诚实方以 $(0, …, 0)$ 为输入执行协议）
输出重建阶段，重建 $P_i$ 的输出时，$\mathcal{S}$ 发送 $(\operatorname{Output}, \mathsf{sid}, P_i)$ 给 $\mathcal{F}_{\mathsf{sfe}}$. 如果 $P_i$ 是被攻陷的，$\mathcal{S}$ 将得到 $P_i$ 的输出 $(y_{i, 1}, …, y_{i, M_\mathsf{out}^i})$. 对于每个输出值 $y_{i, k}$，$\mathcal{S}$ 均匀随机地选择诚实方的份额 $s_{i, k}^\ell, \; P_\ell \notin C$，使得 $s_{i, k}^1 + … + s_{i, k}^n = y_{i, k}$. 然后将诚实方的份额发送给 $P_i$.

不可区分性。真实世界和理想世界的不同在于：(1) 理想世界的诚实方输入为 $(0, …, 0)$；(2) 输出重建阶段，理想世界的诚实方份额是 $\mathcal{S}$ 模拟的。这对于环境 $\mathcal{Z}$ 是不可区分的，因为：加法秘密分享的隐私性确保了秘密份额与诚实方的输入无关；计算乘法门时，因为Beaver三元组分享的秘密是均匀随机的，所以秘密重建得到的 $d = w_i - a, \; e = w_j - b$ 是均匀随机值；最后，输出重建阶段 $\mathcal{S}$ 模拟的份额与真实世界中诚实方的份额也具有相同的分布。因此，真实世界和理想世界是不可区分的。

Beaver三元组的生成

本节，我们讨论一下Beaver三元组的生成方式。

基于可信第三方的方式

Beaver三元组 $([a], [b], [c])$ 本质上是一种满足 $c = ab$ 的相关随机数(Correlated Randomness)，它与协议的输入是无关的。因此，在有可信第三方的场景下，可以由可信第三方执行理想功能 $\mathcal{F}_{\mathsf{triple}}$ 的操作，将Beaver三元组分发给参与方。这是一种非常高效的Beaver三元组生成方式。具体而言，第三方执行以下操作：

随机选取 $a, b \leftarrow_{\$} \mathbb{F}$，计算 $c = ab$.
随机选取 $a_1, b_1, c_1, …, a_n, b_n, c_n$，满足 $a = a_1 + … + a_n, \; b = b_1 + … + b_n, \; c = c_1 + … +c_n$.
对所有 $i \in [n]$，将 $a_i, b_i, c_i$ 发送给 $P_i$.

注意，这里的可信第三方需要满足：(1) 他是半诚实的；(2) 他不会与参与方串通。假设1保证了生成的Beaver三元组是正确的；而如果第三方与参与方互相串通，由于第三方知道 $a, b, c$，计算乘法门时需要重建 $d = x - a, \; e = y - b$，那么乘法门的输入 $x, y$ 显然会被泄露。如果上述两个假设成立，那么协议是安全的，且可信第三方无法得到参与方的输入，因此这与“参与方直接将输入交给可信第三方”是不同的。

分布式生成方式

在某些场景下，如果找不到可信的第三方，那么就需要各个参与方分布式地生成Beaver三元组。在Beaver三元组 $([a], [b], [c])$ 中，$a, b$ 是均匀随机选取的，也就是说，参与方需要通过某种方式秘密分享一个均匀随机值，使得没有人知道被分享的随机值是什么。这与之前的情况不同，之前的秘密分享过程中，都存在一个秘密的持有者，它知道秘密并完成秘密份额的计算和分发。

这个问题的解决方法非常简单：只需让每个参与方 $P_i$ 在本地均匀随机选择 $a_i \leftarrow_{\$} \mathbb{F}$ 作为秘密份额，然后定义 $a = a_1 + … + a_n$. 首先，只需有一个诚实方，那么 $a$ 就是均匀随机的；其次，根据 $a$ 的定义，秘密份额集 $\{a_i\}$ 构成了 $a$ 的正确的加法秘密分享。可以看出，参与方通过随机选择自己的份额隐式地定义了随机值 $a$，而没有参与方可以知道 $a$ 的值。同样地，参与方 $P_i$ 均匀随机选择 $b_i \leftarrow_{\$} \mathbb{F}$ 作为秘密份额，并且定义 $b = b_1 + … + b_n$.

接下来，参与方还需要计算 $c = ab$ 的秘密份额。这实质上就是一个乘法门的计算，参与方可以通过调用GMW协议的乘法门计算协议，在 $\mathcal{F}_{\mathsf{OLE}}$-混合模型下实现。注意到，每个乘法门需要消耗一个Beaver三元组，而分布式地计算一个Beaver三元组实质上就是计算了一个乘法门，显然，这样的方法无法降低协议的总开销。但是请读者注意，Beaver三元组是与协议输入无关的，因此参与方可以提前生成大量的Beaver三元组，将绝大部分开销转移到离线阶段，从而大大提升在线阶段的效率。

更具体而言，生成Beaver三元组的方式包括：基于OT的方式 [Gilboa, 1999; Dem et al., 2015]，基于同态加密的方式 [Pullonen, 2012]等，它们本质上是高效地实现了底层的OLE协议。相关随机数的高效生成仍是一个广受关注的研究方向，我们将其作为读者的拓展阅读内容，这里不再展开。

本章思考题

思考一下Beaver三元组是否还有其他生成方法，这些方法的效率如何？同时，它们将引入什么额外的安全假设？
请思考在恶意安全模型中，如何快速高效地批量验证Beaver三元组的正确性？
除了Beaver三元组，是否还有其他安全多方计算原语可以使用类似的方法在离线阶段先进行预计算，从而大大减少在线阶段的开销？这些原语需要满足什么性质才可以将大部分开销转移到离线阶段？

学习笔记

记录协议细节、模拟器构造与图中记号对照。

本章笔记

第 7 章 通过 Beaver 三元组实现 MPC

目录

第 7 章 通过 Beaver 三元组实现 MPC

基于Beaver三元组的MPC协议

Beaver三元组

协议描述

安全性证明

Beaver三元组的生成

基于可信第三方的方式

分布式生成方式

本章思考题

学习笔记

第 7 章通过 Beaver 三元组实现 MPC

第 7 章通过 Beaver 三元组实现 MPC