第 6 章基于线性秘密分享的协议

学习目标

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

从本章起，我们开始介绍经典的MPC协议。我们从半诚实安全的协议开始，第6章介绍基于线性秘密分享的MPC协议，第7章介绍通过Beaver三元组实现的MPC协议；第8章介绍基于混淆电路的MPC协议；最后，在第9章，我们介绍恶意安全的MPC协议。

BGW协议（半诚实安全）

协议描述

让我们回到第3章所介绍的协议，它就是Ben-Or，Goldwasser，Wigderson [Ben et al., 1988](BGW)所提出的著名协议的半诚实安全版本。我们再次展示整个协议，如图 6.1所示。其中，$t < n/2$.

BGW协议 $\Pi_\mathsf{BGW}$

协议分为三个阶段：输入分享阶段、计算阶段和输出重建阶段。参数 $t, n$ 满足 $t < n/2$. 参与方已经把要计算的函数转化成了算术电路。协议描述采用第3章定义的术语和符号。

输入分享阶段。给定 $\boldsymbol{\alpha} = (\alpha_1, …, \alpha_n)$. 每个持有输入 $x_i \in \mathbb{F}$ 的参与方 $P_i$ 分发 $\left[x_i ; f_{x_i}\right]_t$. 然后，按照先前定义的计算顺序逐个处理电路中的门。在输入分享阶段结束后，需要确保所有输入门已被处理过。

计算阶段。重复以下步骤，直到所有门都被处理（然后进入下一个阶段）。考虑计算顺序中尚未处理的第一个门。根据门的类型，执行以下操作之一：

加法门。参与方持有 $\left[a ; f_a\right]_t,\left[b ; f_b\right]_t$ 作为门的两个输入 $a, b$. 参与方计算 $\left[a ; f_a\right]_t+\left[b ; f_b\right]_t=\left[a+b ; f_a+f_b\right]_t$.
带有常数 $c$ 的常数乘法门。参与方持有 $\left[a ; f_a\right]_t$ 作为门的输入 $a$. 参与方计算 $c \left[a ; f_a\right]_t=\left[c a ; c f_a\right]_t$.
乘法门。参与方持有 $\left[a ; f_a\right]_t,\left[b ; f_b\right]_t$ 作为门的两个输入 $a, b$.
1. 参与方计算 $\left[a ; f_a\right]_t *\left[b ; f_b\right]_t=\left[a b ; f_a f_b\right]_{2 t}$.
2. 定义 $h \stackrel{\text { def }}{=} f_a f_b$. 那么 $h(0)=f_a(0) f_b(0)=a b$，并且各方持有 $[a b ; h]_{2 t}$；即，$P_i$ 持有 $h(\alpha_i)$. 每个 $P_i$ 分发 $\left[h(\alpha_i) ; f_i\right]_t$.
3. 注意到 $\operatorname{deg}(h)=2 t \leq n-1$. 设 $\boldsymbol{r}$ 为「Shamir秘密分享」一节定义的重组向量，即向量 $\boldsymbol{r}=\left(r_1, …, r_n\right)$ 对于任何阶数 $\leq n-1$ 的多项式 $h$，都有 $h(0)=\sum_{i=1}^n r_i h(\alpha_i)$. 参与方计算

\begin{aligned} \sum_{i=1}^n r_i\left[h(\alpha_i) ; f_i\right]_t & =\left[\sum_{i=1}^n r_i h(\alpha_i) ; \sum_{i=1}^n r_i f_i\right]_t \\ & =\left[h(0) ; \sum_{i=1}^n r_i f_i\right]_t=\left[a b ; \sum_{i=1}^n r_i f_i\right]_t \end{aligned}

输出重建阶段。此时，包括输出门在内的所有门都已处理。对于每个标记为 $i$ 的输出门，执行以下操作：参与方持有 $\left[y_i ; f_{y_i}\right]_t$，其中 $y_i$ 是分配给输出门的值。每个 $P_j$ 安全地将 $f_{y_i}(\alpha_j)$ 发送给 $P_i$，后者使用拉格朗日插值法从 $f_{y_i}(\alpha_1), …, f_{y_i}(\alpha_{t+1})$ 或任何其他 $t+1$ 个点计算出 $y_i=f_{y_i}(0)$.

安全性证明

在第3章中，我们已经做了一个很接近于形式化证明的安全性分析。假设被攻陷方的数量为 $t$. 安全性分析基于两个观察：(1) 在输入分享阶段和计算乘法门时，被攻陷方收到的 $t$ 个份额只是均匀随机值。(2) 在输出重建阶段，被攻陷方收到的诚实方份额可以根据已有的份额和输出值计算出来。现在，我们给出通用可组合模型下的形式化证明。

我们采用「安全函数计算的理想功能」一节所定义的安全函数计算理想功能 $\mathcal{F}_{\mathsf{sfe}}$，如图 6.2所示。

理想功能 $\mathcal{F}_{\mathsf{sfe}}$

该理想功能 $\mathcal{F}_{\mathsf{sfe}}$ 与参与方 $P_1, …, P_n$ 以及敌手 $\mathcal{S}$ 交互。它的参数是函数 $f$ 满足 $(y_1, …, y_n) = f(x_1, …, x_n)$.

当收到来自 $P_i$ 的消息 $(\operatorname{Input}, \mathsf{sid}, x_i)$ 时，该理想功能 $\mathcal{F}_{\mathsf{sfe}}$ 做如下操作：
- 记录 $(\operatorname{Input}, \mathsf{sid}, x_i)$，并发送 $(\operatorname{Input}, \mathsf{sid}, P_i)$ 给敌手 $\mathcal{S}$.
当收到来自 $\mathcal{S}$ 的 $(\operatorname{Output}, \mathsf{sid}, P_i)$ 时，如果所有参与方均已提供输入，该理想功能 $\mathcal{F}_{\mathsf{sfe}}$ 做如下操作：
- 发送 $(\operatorname{Output}, \mathsf{sid}, y_i)$ 给接收方 $P_i$.

安全函数计算理想功能 $\mathcal{F}_{\mathsf{sfe}}$

为了使证明更加简洁，我们假设电路在每个输出之前都紧跟着一个乘法门。如果电路对于输出 $y_i$ 不满足这样的结构，我们可以增加一个新的乘法门计算 $y_i x'_i$ 并输出，其中 $x'_i = 1$. 这样的修改最多增加常数个乘法门。

注意，即使没有这个假设，协议仍然是安全的，但会让证明更加复杂。我们将在后面讨论这一点。

定理

假设参与方之间存在点对点安全信道。假设被攻陷方数量不超过 $t, \; t < n/2$. 图 6.1中的协议 $\Pi_\mathsf{BGW}$ 对于静态半诚实敌手UC-安全实现了理想功能 $\mathcal{F}_{\mathsf{sfe}}$（图 6.2）。

安全性证明

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

\operatorname{exec}_{\Pi_\mathsf{BGW}, \mathcal{A}, \mathcal{Z}} \approx \operatorname{exec}_{\mathcal{F}_{\mathsf{sfe}}, \mathcal{S}, \mathcal{Z}}

其中 $\mathcal{A}$ 是平凡敌手。因为BGW协议是信息论安全的，所以这里不需要限制环境 $\mathcal{Z}$ 是PPT的。

模拟器 $\mathcal{S}$. 模拟器 $\mathcal{S}$ 在内部运行 $\mathcal{A}$，转发 $\mathcal{Z}$ 与 $\mathcal{A}$ 之间的消息。令 $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$. $\mathcal{S}$ 以 $x_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 = 0$，然后模拟 $P_j$ 遵循协议执行输入分享，将秘密份额发送给被攻陷方。
对于加法门和常数乘法门，$\mathcal{S}$ 模拟被攻陷方遵循协议执行。
对于每个乘法门，$\mathcal{S}$ 模拟被攻陷方遵循协议执行；对于每个诚实方，$\mathcal{S}$ 模拟其分发 $[0]_t$ 给被攻陷方。
在输出重建阶段重建 $P_i$ 的输出时，$\mathcal{S}$ 发送 $(\operatorname{Output}, \mathsf{sid}, P_i)$ 给 $\mathcal{F}_{\mathsf{sfe}}$. 如果 $P_i$ 是被攻陷的，$\mathcal{S}$ 将得到 $P_i$ 的输出 $y_i$. $\mathcal{S}$ 构造 $t$ 阶多项式 $f_{y_i}$，满足 $f_{y_i}(0) = y_i$ 且与 $P_i$ 已知的 $|C|$ 个秘密份额相一致。具体而言，如果 $|C| = t$，$\mathcal{S}$ 通过拉格朗日插值构造 $f_{y_i}$；如果 $|C| < t$，$\mathcal{S}$ 均匀随机选取 $t - |C|$ 个诚实方的份额，然后进行拉格朗日插值构造 $f_{y_i}$. 最后，对于 $P_j \notin C$，$\mathcal{S}$ 将 $f_{y_i}(\alpha_j)$ 作为 $P_j$ 的份额发送给 $P_i$.

不可区分性。我们通过两个引理来证明环境 $\mathcal{Z}$ 在真实世界和理想世界的视图是不可区分的。

对于第一个引理，我们定义一个函数 $\mathsf{Strip}$. $\mathsf{Strip}(\text{view}_{i})$ 以被攻陷方 $P_i \in C$ 的视图作为输入，移除输出重建阶段来自诚实方的份额后直接输出。即 $\mathsf{Strip}(\text{view}_{i})$ 包括 $P_i$ 的输入 $x_i$，$P_i$ 做的随机选择，$P_i$ 在输入分享阶段和计算乘法门时收到的所有份额，以及 $P_i$ 在输出重建阶段收到的来自被攻陷方的份额。

\{ \mathsf{Strip}(view_i^{(0)}) \}_{P_i \in C} \stackrel{perf}{=} \{ \mathsf{Strip}(view_i^{(1)}) \}_{P_i \in C}

安全性证明

对于 $b = 0$ 或 $1$，我们分析协议的每个阶段所产生的分布是否相同。

输入分享阶段。对于 $P_i \in C$，有 $x_i^{(0)} = x_i^{(1)}$，显然会产生相同的分布。对于 $P_j \notin C$，有可能 $x_j^{(0)} \neq x_j^{(1)}$，但是在「Shamir秘密分享」一节论证过 $t$ 个或更少的份额只是均匀随机值，与 $x_j^{(b)}$ 无关。因此，无论 $b = 0$ 或 $1$，产生的分布均相同。
加法门和常数乘法门。加法门和常数乘法门无需交互，对 $\text{view}_{j}^{(b)}$ 的分布没有影响。
乘法门。由输入分享阶段的分析可知，对于被攻陷方，他们乘法门的输入是均匀随机值，在计算乘法门时收到的不超过 $t$ 个份额也是均匀随机值。因此，被攻陷方计算并发送的值对于 $b = 0$ 或 $1$ 有相同的分布。
输出重建阶段。由于 $\mathsf{Strip}$ 移除了输出重建阶段来自诚实方的份额，因此输出重建阶段对 $\mathsf{Strip}(view_i^{(b)})$ 的分布没有影响。

引理得证。

安全性证明

对于第二个引理，我们定义一个函数 $\mathsf{Dress}$. 给定向量 $\boldsymbol{y}_{C} = \{y_i\}_{P_i \in C}$，$\mathsf{Dress}_{\boldsymbol{y}_{C}}$ 的输入是 $\{ \mathsf{Strip}(\text{view}_{i}) \}_{P_i \in C}$，然后为其填补上被 $\mathsf{Strip}$ 移除的输出重建阶段来自诚实方的份额。具体而言，$\mathsf{Dress}$ 的做法就如模拟器 $\mathcal{S}$ 那样：对于每个 $P_i \in C$，构造 $t$ 阶多项式 $f_{y_i}$，满足 $f_{y_i}(0) = y_i$ 且与 $P_i$ 已知的 $|C|$ 个秘密份额相一致。如果 $|C| = t$，通过拉格朗日插值构造 $f_{y_i}$；如果 $|C| < t$，均匀随机选取 $t - |C|$ 个诚实方的份额，然后进行拉格朗日插值构造 $f_{y_i}$. 最后，将 $f_{y_i}(\alpha_j)$ 作为诚实方 $P_j \notin C$ 的份额填补上.

\mathsf{Dress}_{\boldsymbol{y}_{C}} (\{ \mathsf{Strip}(view_i) \}_{P_i \in C}) \stackrel{perf}{=} \{ view_i \}_{P_i \in C}

安全性证明

设 $\text{view}_{i}$ 中的输出值为 $y'_i$. 根据BGW协议的正确性可知，$y'_i = y_i$，其中 $(y_1, …, y_n) = f(\boldsymbol{x})$. 因此，$\text{view}_{i}$ 的输出重建阶段得到了 $y_i$ 的 $n$ 个秘密份额 $[y_i ; f_{y_i}]_t$. 如果 $|C| = t$，根据拉格朗日插值的正确性，$\mathsf{Dress}_{\boldsymbol{y}_{C}}$ 恰恰正确恢复了被 $\mathsf{Strip}$ 移除的份额。如果 $|C| < t$，$\mathsf{Dress}_{\boldsymbol{y}_{C}}$ 首先均匀随机选取了 $t - |C|$ 个诚实方的份额：这 $t - |C|$ 个份额与真实运行得到的份额都是均匀随机值，有相同的分布。然后，因为 $f_{y_i}(0) = y_i$，由拉格朗日插值唯一确定了剩余的诚实方份额。综上可知，$\mathsf{Dress}_{\boldsymbol{y}_{C}} (\{ \mathsf{Strip}(view_i) \}_{P_i \in C}) \stackrel{perf}{=} \{ view_i \}_{P_i \in C} $.

安全性证明

有了这两个引理，我们可以论证 $\mathcal{Z}$ 在真实世界和理想世界的视图是完美不可区分的。令 $\boldsymbol{x} = (x_1, \ldots, x_n)$ 为输入向量，令 $\boldsymbol{x}^{(0)} = (x_1^{(0)}, \ldots, x_n^{(0)})$ 对 $P_i \in C$ 有 $x_i^{(0)} = x_i$，对 $P_j \notin C$ 有 $x_j^{(0)} = 0$. 那么，根据 $\mathcal{S}$ 的构造，理想世界的视图为

\mathsf{Dress}_{\boldsymbol{y}_{C}} (\{ \mathsf{Strip}(\mathrm{view}_{i}^{(0)}) \}_{P_i \in C})

令真实世界的视图为 $\{ \mathrm{view}_{i} \}_{P_i \in C}$，根据引理 1可知

\{ \mathsf{Strip}(\mathrm{view}_{i}^{(0)}) \}_{P_i \in C} \stackrel{\mathrm{perf}}{=} \{ \mathsf{Strip}(\mathrm{view}_{i}) \}_{P_i \in C}

因为算法不能增加两个随机变量的统计距离（注：即 $\delta(\mathcal{A}(X_1), \mathcal{A}(X_2) ) \leq \delta(X_1, X_2)$，其中 $X_1, X_2$ 是随机变量，$\delta$ 表示统计距离，$\mathcal{A}$ 是任何算法。它的证明留作读者的练习。），我们有

\mathsf{Dress}_{\boldsymbol{y}_{C}} (\{ \mathsf{Strip}(\mathrm{view}_{i}^{(0)}) \}_{P_i \in C}) \stackrel{\mathrm{perf}}{=} \mathsf{Dress}_{\boldsymbol{y}_{C}} (\{ \mathsf{Strip}(\mathrm{view}_{i}) \}_{P_i \in C})

根据引理 2

\mathsf{Dress}_{\boldsymbol{y}_{C}} (\{ \mathsf{Strip}(\mathrm{view}_{i}) \}_{P_i \in C}) \stackrel{\mathrm{perf}}{=} \{ \mathrm{view}_{i} \}_{P_i \in C}

故

\mathsf{Dress}_{\boldsymbol{y}_{C}} (\{ \mathsf{Strip}(\mathrm{view}_{i}^{(0)}) \}_{P_i \in C}) \stackrel{\mathrm{perf}}{=} \{ \mathrm{view}_{i} \}_{P_i \in C}

即真实世界和理想世界的视图有完全相同的分布。证毕。

为什么假设输出门之前都有乘法门？以上的证明假设了输出门之前都有乘法门，如果没有这样的假设，协议仍然是安全的，但是在证明时有一些微妙的差别需要注意。例如，当 $|C| < t$ 时，如果协议运行过程中计算了 $[a; f_a]_t, [b; f_b]_t$ 和 $[a+b; f_{a+b}]_t$，而在输出重建阶段，被攻陷方又得到了这些值，那么敌手就可以通过检查 $f_a + f_b \stackrel{?}{=} f_{a+b}$ 来试图区分真实世界和理想世界。因此 $\mathcal{S}$ 的构造需要更加小心，它做的随机选择必须满足这样的一致性要求。但是，如果我们假设输出门之前都有乘法门，由于乘法门的计算过程加入了新的随机性，因此输出重建阶段的多项式就总是均匀随机的了。

GMW协议

上一节介绍的BGW协议是基于Shamir秘密分享的，第1章的协议是基于复制秘密分享的。本节，我们介绍GMW协议 [Gol et al., 1987]。它由Goldreich，Micali，和Wigderson所提出，是一个基于加法秘密分享的通用MPC协议，它允许最多 $n - 1$ 个被攻陷方（$n$ 为参与方的数量），且适用于布尔电路和算术电路。我们首先考虑两方布尔电路，然后将其拓展到多方布尔电路；最后，我们介绍多方算术电路的GMW协议。

两方布尔电路GMW协议

我们首先介绍两方的布尔版本GMW协议。假设参与方 $P_1$ 和 $P_2$ 的输入分别为 $x_1$ 和 $x_2$，他们想要计算 $(y_1, y_2) = f(x_1, x_2)$，并且已经将 $f$ 转化为了布尔电路 $\mathcal{C}$. 协议流程如下。

加法秘密分享。对于输入 $x_1$ 的每个比特 $x_{1, k} \in \{ 0 , 1 \}$，$P_1$ 选择随机比特 $r_{1, k}^1, r_{1, k}^2$，满足 $r_{1, k}^1 \oplus r_{1, k}^2 = x_{1, k}$. 具体而言，$P_1$ 选择均匀随机比特 $r_{1, k}^1$ 并令 $r_{1, k}^2 = r_{1, k}^1 \oplus x_{1, k}$. 然后将 $r_{1, k}^2$ 发给 $P_2$. 类似地，$P_2$ 的输入 $x_2$ 的每一个比特也以同样的方式秘密分享。

逐门计算。完成输入分享后，$P_1$ 和 $P_2$ 对电路 $\mathcal{C}$ 进行逐门计算。考虑输入导线为 $w_i, w_j$，输出导线为 $w_k$ 的门 $G$，每一根输入导线$w_x\ (x \in \{i,j\})$的值都被秘密分享为 $s^1_x$ 和 $s^2_x$，满足 $s^1_x \oplus s^2_x = w_x$. $P_1$ 持有 $w_i$ 和 $w_j$上的 $s^1_i$ 和 $s^1_j$ ，$P_2 $持有 $s^2_i$ 和$s^2_j $，协议需要使得门 $G$ 计算完成后，$P_1$ 和 $P_2$ 分别持有 $w_k$ 的秘密份额 $s^1_k$ 和 $s^2_k$ 满足 $s^1_k \oplus s^2_k = w_k$. 不失一般性地，我们假设 $\mathcal{C}$ 由非门、异或门、与门组成（注：在离散数学中，非门、异或门、与门是完备的。）。下面我们依次介绍各个门的计算方式。

两方布尔电路GMW协议 · 公式

非门(NOT)。非门只有一个输入 $w_i$，输出 $w_k$ 为 $w_i$ 的翻转。假设 $P_1$ 持有 $s_i^1$，$P_2$ 持有 $s_i^2$，满足 $w_i = s^1_i \oplus s^2_i $，那么，

w_k = \overline{w_i} = \overline{s^1_i \oplus s^2_i} = s^1_i \oplus s^2_i \oplus 1 = (s^1_i \oplus 1) \oplus s^2_i

我们可以让 $P_1$ 设置 $s^1_k = s^1_i \oplus 1$，$P_2$ 设置 $s^2_k = s^2_i$，即 $P_1$ 将自己的输入导线的秘密份额翻转，而$P_2$ 直接将输入导线的秘密份额作为输出导线的份额。这样，参与方就获得了 $w_k$ 的秘密份额。

异或门(XOR)。异或门的计算也不需要双方交互。假设异或门的输入为 $w_i, w_j$，输出为 $w_k = w_i \oplus w_j$. $P_1$ 持有秘密份额 $s_i^1, s_j^1$，$P_2$ 持有 $s_i^2, s_j^2$，满足 $w_i = s^1_i \oplus s^2_i, \; w_j = s^1_j \oplus s^2_j$. 我们有

两方布尔电路GMW协议 · 公式

w_k = w_i \oplus w_j = (s^1_i \oplus s^2_i ) \oplus (s^1_j \oplus s^2_j ) = (s^1_i \oplus s^1_j ) \oplus (s^2_i \oplus s^2_j )

我们可以让 $P_1$ 设置 $s^1_k = s^1_i \oplus s^1_j$，$P_2$ 设置 $s^2_k = s^2_i \oplus s^2_j$，也就是双方分别将自己的秘密份额在本地计算异或，即可获得 $w_k$ 的秘密份额。

与门(AND)。与门的计算需要交互，$P_1$ 和 $P_2$ 需要调用1-out-of-4 OT. 让我们看一下与门的情况。同样，假设与门的输入为 $w_i, w_j$，输出为 $w_k = w_i \wedge w_j$. $P_1$ 持有秘密份额 $s_i^1, s_j^1$，$P_2$ 持有 $s_i^2, s_j^2$，满足 $w_i = s^1_i \oplus s^2_i, \; w_j = s^1_j \oplus s^2_j$. 那么，

两方布尔电路GMW协议 · 公式

w_k = w_i \wedge w_j = (s^1_i \oplus s^2_i ) \wedge (s^1_j \oplus s^2_j )

从 $P_1$ 的角度来看，其持有的 $s^1_i$、$s^1_j$ 是已知的，而$P_2$ 持有的两个份额 $s^2_i$、$s^2_j$ 是未知的，共有四种可能的情况。 $P_1$ 不能直接获得 $P_2$ 的秘密份额，因为那样会违背隐私性，但是 $P_1$ 可以为 $P_2$ 持有份额的每种可能情况准备相应的 $w_k$ 的秘密份额，并和 $P_2$ 运行 1-out-of-4 OT 协议，让 $P_2$ 根据其持有的份额来选择对应的 $w_k$ 的份额。

具体来说，令 $S(\alpha, \beta) = (s^1_i \oplus \alpha) \wedge (s^1_j \oplus \beta)$ 是与门的输出，其中 $\alpha, \beta \in \{0,1\}$ 代表 $P_2$ 持有的秘密份额 $s^2_i, s^2_j$，$P_1$ 均匀随机选择掩码 $r \leftarrow_{\$} \{ 0 , 1 \}$，并计算一张包含四个OT输入的表：

两方布尔电路GMW协议 · 公式

T = ( \begin{matrix} r \oplus S(0,0) \\ r \oplus S(0,1) \\ r \oplus S(1,0) \\ r \oplus S(1,1) \end{matrix} )

之后 $P_1$ 和 $P_2$ 运行1-out-of-4 OT协议，其中 $P_1$ 作为发送方以表 $T$ 作为输入，$P_2$ 作为接收方以 $s^2_i, s^2_j$ 作为选择比特，得到 $r \oplus S(s^2_i, s^2_j)$. 然后，$P_1$ 和 $P_2$ 分别将 $r$ 和 $r \oplus S(s^2_i, s^2_j)$ 作为与门输出导线的秘密份额。根据OT协议的隐私性，$P_1$ 不知道 $P_2$ 的选择比特，$P_2$ 也不知道 $P_1$ 的其余三个输入，因此与门的输入不会被泄露。

输出重建。输出重建的过程非常简单。设 $P_1$ 的输出为 $y_1$，对于 $y_1$ 的每个比特 $y_{1, k} \in \{0, 1\}$，$P_2$ 将自己的秘密份额 $s_{1, k}^2$ 发给 $P_1$，然后 $P_1$ 计算 $y_{1, k} = s_{1, k}^1 \oplus s_{1, k}^2$. 对于 $P_2$ 的每个输出比特，也执行同样的操作即可。

多方布尔电路GMW协议

协议描述

上述针对两方布尔电路的协议很容易拓展到多方的场景。假设 $n$个参与方 $P_1, P_2, …, P_n$ 想要计算 $(y_1, …, y_n) = f(x_1, …, x_n)$，并将函数 $f$ 转换为了布尔电路 $\mathcal{C}$. 协议的流程仍然包括加法秘密分享、逐门计算和输出重建。

加法秘密分享。对于输入 $x_i$ 的每个比特 $x_{i, k} \in \{0, 1\}$，$P_i$ 选择随机比特 $r_{i, k}^1, …, r_{i, k}^n$ 满足 $\bigoplus\limits_{\ell=1}^n r_{i, k}^\ell = x_{i, k}$，然后将 $r_{i, k}^\ell$ 发给 $P_\ell$ 作为秘密份额。每个参与方都以这样的方式对自己的输入进行秘密分享。可以看出，这样的方式使得任意 $n - 1$ 个参与方无法获得关于秘密的任何信息，根据「门限秘密分享」一节的定义，它是 $(n-1, n)$-门限秘密分享。

逐门计算。考虑具有输入导线 $w_i, w_j$ 以及输出导线 $w_k$ 的门 $G$，每一根输入导线 $w_x (x \in \{i,j\})$ 的值都被秘密分享为 $s_x^1, …, s_x^n$，满足 $s^1_x \oplus … \oplus s^n_x = w_x$. $P_\ell$ 持有 $w_i$ 和 $w_j $上的 $s^\ell_i$ 和 $s^\ell_j$，协议需要使得门 $G$ 计算完成后，$P_\ell$持有 $w_k$ 的秘密份额 $s^\ell_k$. 不失一般性地，我们仍假设 $\mathcal{C}$ 由非门、异或门、与门组成。

非门(NOT)。非门只有一个输入 $w_i$，输出 $w_k$ 为 $w_i$ 的翻转。假设 $P_\ell$ 持有 $s_i^\ell$，满足 $w_i = s^1_i \oplus … \oplus s^n_i $，那么，

协议描述 · 公式

w_k = \overline{w_i} = \overline{s^1_i \oplus \dots \oplus s^n_i} = s^1_i \oplus \dots \oplus s^n_i \oplus 1 = (s^1_i \oplus 1) \oplus s^2_i \dots \oplus s^n_i

我们可以让 $P_1$ 设置 $s^1_k = s^1_i \oplus 1$，其他参与方 $P_\ell, \; \ell \neq 1$ 设置 $s^\ell_k = s^\ell_i$，即 $P_1$ 将自己的输入导线的秘密份额翻转，而其他参与方将输入导线的秘密份额作为输出导线的份额。

异或门(XOR)。假设异或门的输入为 $w_i, w_j$，输出为 $w_k = w_i \oplus w_j$. $P_\ell$ 持有 $s_i^\ell, s_j^\ell$，满足 $w_i = s^1_i \oplus … \oplus s^n_i, \; w_j = s^1_j \oplus … \oplus s^n_j$. 我们有

协议描述 · 公式

w_k = w_i \oplus w_j = (s^1_i \oplus \dots \oplus s^n_i ) \oplus (s^1_j \oplus \dots \oplus s^n_j ) = (s^1_i \oplus s^1_j ) \oplus \dots \oplus (s^n_i \oplus s^n_j )

我们可以让 $P_\ell$ 设置 $s_k^\ell = s_i^\ell \oplus s_j^\ell$，也就是参与方将自己的秘密份额在本地计算异或，即可获得 $w_k$ 的秘密份额。

与门(AND)。与门的计算最为复杂。同样，假设与门的输入为 $w_i, w_j$，输出为 $w_k = w_i \wedge w_j$. $P_\ell$ 持有 $s_i^\ell, s_j^\ell$，满足 $w_i = s^1_i \oplus … \oplus s^n_i, \; w_j = s^1_j \oplus … \oplus s^n_j$. 那么，因为与运算对异或运算满足分配律（注：这可以通过真值表来验证。），我们有

协议描述 · 公式

w_k = w_i \wedge w_j = (s^1_i \oplus \dots \oplus s^n_i ) \wedge (s^1_j \oplus \dots \oplus s^n_j) \\ = \left( \bigoplus\limits^{n}\limits_{\ell=1} s^\ell_i \wedge s^\ell_j \right) \oplus \left( \bigoplus\limits_{\ell_1 \neq \ell_2} s^{\ell_1}_i \wedge s^{\ell_2}_j \right)

观察上式，项 $s^\ell_i \wedge s^\ell_j$ 可以由 $P_\ell$ 在本地计算。对于 $s^{\ell_1}_i \wedge s^{\ell_2}_j$，它的计算需要 $P_{\ell_1}$ 和 $P_{\ell_2}$ 的交互，显然，$P_{\ell_1}$ 和 $P_{\ell_2}$ 可以通过调用两方GMW协议来计算。或者，他们采用两方GMW协议中的方法，调用1-out-of-4 OT来计算 $(s^{\ell_1}_i \wedge s^{\ell_2}_j) \oplus (s^{\ell_1}_j \wedge s^{\ell_2}_i)$. 具体而言，令 $S(\alpha, \beta) = (s^{\ell_1}_i \wedge \alpha) \oplus (s^{\ell_1}_j \wedge \beta)$，其中$\alpha, \beta \in \{0,1\}$ 代表 $P_{\ell_2}$ 所持有的秘密份额 $s^{\ell_2}_j, s^{\ell_2}_i$，$P_{\ell_1}$ 均匀随机选择掩码 $r \leftarrow_{\$} \{0,1\}$ 并计算一张包含四个OT输入的表：

协议描述 · 公式

T = ( \begin{matrix} r \oplus S(0,0) \\ r \oplus S(0,1) \\ r \oplus S(1,0) \\ r \oplus S(1,1) \end{matrix} )

之后 $P_{\ell_1}$ 和 $P_{\ell_2}$ 运行 1-out-of-4 OT，$P_{\ell_1}$ 以表 $T$ 为输入作为发送方，$P_{\ell_2}$ 作为接收方以 $s^{\ell_2}_j, s^{\ell_2}_i$ 作为选择比特，得到 $r \oplus S(s^{\ell_2}_j, s^{\ell_2}_i)$. 然后，$P_{\ell_1}$ 设置 $r_{\ell_1, \ell_2} = r$，$P_{\ell_2}$ 设置 $r_{\ell_2, \ell_1} = r \oplus S(s^{\ell_2}_j, s^{\ell_2}_i)$. 最后，每个参与方 $P_\ell$ 将 $s^\ell_i \wedge s^\ell_j$ 与OT过程中所得到的值全部计算异或，得到 $w_k$ 的份额 $s_k^\ell = (s^\ell_i \wedge s^\ell_j) \oplus (\bigoplus\limits_{\ell' \neq \ell} r_{\ell, \ell'})$. 由式（式 6.3）可知，这样得到的秘密份额满足 $w_k = s_k^1 \oplus … \oplus s_k^n$.

输出重建。输出重建的过程与两方的情形完全类似。设 $P_i$ 的输出为 $y_i$，对于 $y_i$ 的每个比特 $y_{i, k} \in \{0, 1\}$，其他参与方将自己的份额 $s_{i, k}^\ell, \; \ell \neq i$ 发给 $P_i$，然后 $P_i$ 计算 $y_{i, k} = s_{i, k}^1 \oplus … \oplus s_{i, k}^n$. 每个参与方都通过这样的方式重建输出。

最后，完整的布尔电路GMW协议如图 6.3所示。

布尔电路GMW协议 $\Pi_\mathsf{GMW}^\mathsf{bool}$

协议分为三个阶段：输入分享阶段、计算阶段和输出重建阶段。参与方已经把要计算的函数转化成了包含非门、异或门和与门的布尔电路。

输入分享阶段。设 $P_i$ 的输入为 $x_i$. 对于 $x_i$ 的每个比特 $x_{i, k} \in \{0, 1\}$，$P_i$ 选择随机比特 $r_{i, k}^1, …, r_{i, k}^n$ 满足 $\bigoplus\limits_{\ell=1}^n r_{i, k}^\ell = x_{i, k}$，然后将 $r_{i, k}^\ell$ 发给 $P_\ell$ 作为秘密份额。

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

非门(NOT)。假设输入导线上的值为 $w_i$，输出导线上的值为 $w_k$. 参与方 $P_\ell$ 持有的秘密份额为 $s_i^\ell$. $P_1$ 设置 $s_k^1 = s_i^1 \oplus 1$ 为输出导线上的份额，其他参与方 $P_\ell, \; \ell \neq 1$ 设置 $s_k^\ell = s_i^\ell$ 为输出导线上的份额。
异或门(XOR)。假设输入导线上的值为 $w_i, w_j$，输出导线上的值为 $w_k$. 参与方 $P_\ell$ 持有的秘密份额为 $s_i^\ell, s_j^\ell$. $P_\ell$ 设置 $s_k^\ell = s_i^\ell \oplus s_j^\ell$ 为输出导线上的份额。
与门(AND)。假设输入导线上的值为 $w_i, w_j$，输出导线上的值为 $w_k$. 参与方 $P_\ell$ 持有的秘密份额为 $s_i^\ell, s_j^\ell$. 参与方执行如下操作。
1. 对于任意的 $\ell_1 \neq \ell_2$，$P_{\ell_1}$ 与 $P_{\ell_2}$ 执行如下操作：令 $S(\alpha, \beta) = (s^{\ell_1}_i \wedge \alpha) \oplus (s^{\ell_1}_j \wedge \beta)$，$P_{\ell_1}$ 均匀随机选择 $r \leftarrow_{\$} \{0, 1\}$ 并计算表
  $T = ( \begin{matrix} r \oplus S(0,0) \\ r \oplus S(0,1) \\ r \oplus S(1,0) \\ r \oplus S(1,1) \end{matrix} )$ $P_{\ell_1}$ 以表 $T$ 为输入作为发送方，$P_{\ell_2}$ 作为接收方以 $s^{\ell_2}_j, s^{\ell_2}_i$ 作为选择比特运行1-out-of-4 OT，$P_{\ell_2}$ 得到 $r \oplus S(s^{\ell_2}_j, s^{\ell_2}_i)$. $P_{\ell_1}$ 设置 $r_{\ell_1, \ell_2} = r$，$P_{\ell_2}$ 设置 $r_{\ell_2, \ell_1} = r \oplus S(s^{\ell_2}_j, s^{\ell_2}_i)$.
2. $P_\ell$ 设置 $s_k^\ell = (s^\ell_i \wedge s^\ell_j) \oplus (\bigoplus\limits_{\ell' \neq \ell} r_{\ell, \ell'})$ 为输出导线上的份额。

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

安全性证明

这里，我们不考虑1-out-of-4 OT的具体实现，而是将其抽象成理想功能 $\mathcal{F}_{\mathsf{OT}^1_4}$（如图 6.4所示）。也就是说，当参与方需要运行1-out-of-4 OT时，他们调用理想功能 $\mathcal{F}_{\mathsf{OT}^1_4}$. 下面我们证明，当 $t \leq n-1$ 时，布尔电路GMW协议 $\Pi_\mathsf{GMW}^\mathsf{bool}$ 在 $\mathcal{F}_{\mathsf{OT}^1_4}$-混合模型下对于静态半诚实敌手UC-安全实现了安全函数计算理想功能 $\mathcal{F}_{\mathsf{sfe}}$（图 6.2）。

1-out-of-4 OT 的理想功能 $\mathcal{F}_{\mathsf{OT}^1_4}$

输入： $P_s$ 的输入是4条消息 $(x_{0, 0}, x_{0, 1}, x_{1, 0}, x_{1, 1})$. $P_r$ 的输入是选择比特 $b_0, b_1$.

输出： $P_r$ 输出 $x_{b_0, b_1}$. $P_s$ 没有输出。

1-out-of-4 OT 的理想功能 $\mathcal{F}_{\mathsf{OT}^1_4}$

这里的证明思路与BGW协议非常类似。首先，由布尔电路GMW协议的构造可知，参与方计算完每个门之后都得到了正确的秘密份额，协议满足正确性。对于隐私性，在输入分享阶段，协议采用的加法秘密分享使得任意不超过 $n - 1$ 个参与方得到的份额都是均匀随机值。在计算阶段，非门、异或门的计算可以在本地进行，不会泄露信息；与门的计算中1-out-of-4 OT需要参与方的交互，由于加入了随机掩码 $r$，$P_{\ell_2}$ 得到的也只是均匀随机值。最后的输出重建阶段，诚实方的份额可以根据被攻陷方已知的份额和协议输出来高效地模拟。

注意，与BGW协议不同，GMW协议不是信息论安全的，因为底层的OT协议不可能做到信息论安全（见定理 5.1）。

定理

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

安全性证明

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

\operatorname{exec}_{\Pi_\mathsf{GMW}^\mathsf{bool}, \mathcal{A}, \mathcal{Z}}^{\mathcal{F}_{\mathsf{OT}^1_4}} \approx \operatorname{exec}_{\mathcal{F}_{\mathsf{sfe}}, \mathcal{S}, \mathcal{Z}}

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

模拟器 $\mathcal{S}$. 模拟器 $\mathcal{S}$ 在内部运行 $\mathcal{A}$，转发 $\mathcal{Z}$ 与 $\mathcal{A}$ 之间的消息。因为是 $\mathcal{F}_{\mathsf{OT}^1_4}$-混合模型，$\mathcal{S}$ 还需要模拟 $\mathcal{F}_{\mathsf{OT}^1_4}$. 令 $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$. $\mathcal{S}$ 以 $x_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 = 0$，然后模拟 $P_j$ 遵循协议执行输入分享，将秘密份额发送给被攻陷方。
对于与门的1-out-of-4 OT，$\mathcal{S}$ 模拟被攻陷方遵循协议执行。如果被攻陷方是1-out-of-4 OT的接收方，$\mathcal{S}$ 模拟 $\mathcal{F}_{\mathsf{OT}^1_4}$ 输出一个随机比特给被攻陷方。（如果被攻陷方是1-out-of-4 OT的发送方，那么他在1-out-of-4 OT中没有得到输出，因此 $\mathcal{S}$ 什么都不用做。）
在输出重建阶段重建 $P_i$ 的输出时，$\mathcal{S}$ 发送 $(\operatorname{Output}, \mathsf{sid}, P_i)$ 给 $\mathcal{F}_{\mathsf{sfe}}$. 如果 $P_i$ 是被攻陷的，$\mathcal{S}$ 将得到 $P_i$ 的输出 $y_i$. 对于 $y_i$ 的每个比特 $y_{i, k}$，$\mathcal{S}$ 随机选择诚实方的份额 $s_{i, k}^\ell, \; P_\ell \notin C$，使得 $s_{i, k}^1 \oplus … \oplus s_{i, k}^n = y_{i, k}$. 然后将诚实方的份额发送给 $P_i$.

不可区分性。根据前面的分析，很容易看出 $\mathcal{Z}$ 在真实世界和理想世界的视图是不可区分的。首先，协议的构造满足正确性，故理想世界与真实世界中诚实方的输出相同。然后，不论在真实世界还是理想世界，输入分享阶段和执行1-out-of-4 OT时，被攻陷方得到的都是均匀随机值。在输出重建阶段，被攻陷方收到的诚实方份额也具有相同的分布。因此，真实世界和理想世界是不可区分的。

多方算术电路GMW协议

协议描述

在布尔电路中，每一根导线上的值是一个比特；在算术电路中，每一根导线上的值是一个有限域 $\mathbb{F}$ 上的元素。与布尔电路GMW协议的思路相同，我们可以使用类似的方法将协议拓展到算术电路的场景。不同之处在于，计算乘法门时，我们使用OLE（Oblivious Linear Evaluation，茫然线性计算）协议 [Dot et al., 2012]来替换OT协议。在某个有限域 $\mathbb{F}$ 上的OLE协议中，发送方 $P_s$ 的输入是 $\alpha, \beta \in \mathbb{F}$，接收方 $P_r$ 的输入是 $x \in \mathbb{F}$，协议运行结束后，$P_r$ 获得 $\gamma = \alpha x + \beta$，$P_s$ 不获取任何输出。也就是说，发送方和接收方以 $\alpha, \beta, x$ 为输入做了线性计算 $\gamma = \alpha x + \beta$，但是发送方不知道接收方的输入 $x$，接收方也不知道发送方的输入 $\alpha, \beta$. OLE的理想功能 $\mathcal{F}_{\mathsf{OLE}}$ 如图 6.5所示。

OLE的理想功能 $\mathcal{F}_{\mathsf{OLE}}$

输入： $P_s$ 的输入是 $\alpha, \beta \in \mathbb{F}$. $P_r$ 的输入是 $x \in \mathbb{F}$.

输出： $P_r$ 输出 $\gamma = \alpha x + \beta$. $P_s$ 没有输出。

OLE的理想功能 $\mathcal{F}_{\mathsf{OLE}}$

OLE的实现。读者可能会好奇OLE是如何实现的。实现OLE的朴素的方法包括：(1) 使用通用MPC协议（例如「姚氏混淆电路协议」一节将要介绍的姚氏混淆电路协议）；(2) 使用（加法）同态加密。（加法）同态加密是一种公钥加密方案，并且满足加法同态性，即 $\mathsf{Enc}_{\mathsf{pk}}(x) + \mathsf{Enc}_{\mathsf{pk}}(y) = \mathsf{Enc}_{\mathsf{pk}}(x + y)$. 基于这个工具，$P_r$ 可以生成 $(\mathsf{pk}, \mathsf{sk})$，然后计算 $\mathsf{Enc}_{\mathsf{pk}}(x)$ 并发送给 $P_s$，$P_s$ 通过加法同态性计算 $\alpha \cdot \mathsf{Enc}_{\mathsf{pk}}(x) + \mathsf{Enc}_{\mathsf{pk}}(\beta) = \mathsf{Enc}_{\mathsf{pk}}(\alpha x + \beta)$ 并发送给 $P_r$，最后 $P_r$ 将其解密得到 $\alpha x + \beta$. 关于更高效的OLE构造现在仍是密码学的研究课题之一，这里我们不过多关注OLE的具体实现，而是把它抽象为理想功能 $\mathcal{F}_{\mathsf{OLE}}$，然后在 $\mathcal{F}_{\mathsf{OLE}}$-混合模型下构造协议。

现在，我们介绍算术电路GMW协议。假设有 $n$个参与方 $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}$，其中 $P_i$ 有 $M_\mathsf{in}^i$ 个输入和 $M_\mathsf{out}^i$ 个输出。$\mathcal{C}$ 是函数 $f$ 对应的算术电路。协议的流程如下。

加法秘密分享。对于 $P_i$ 的每个输入 $x_{i, k} \in \mathbb{F}, \; k \in [M_\mathsf{in}^i]$，$P_i$ 选择 $n$ 个域上的随机元素 $r^1_{i,k}, …, r^n_{i,k}$ 满足 $\sum\limits_{\ell=1}^n r^\ell_{i,k} = x_{i, k}$，然后将 $r^\ell_{i, k}$ 发送给 $P_\ell$ 作为秘密份额。每个参与方都以这样的方式进行秘密分享。可以看出，这样的加法秘密分享是 $(n-1, n)$-门限秘密分享（见「门限秘密分享」一节的定义）。

逐门计算。考虑具有输入导线 $w_i, w_j$ 以及输出导线 $w_k$ 的门 $G$，每一根输入导线 $w_x\ (x \in \{i,j\})$ 的值都被秘密分享为 $s^1_x, …, s^n_x$，满足 $s_x^1 + … + s_x^n = w_x$. $P_\ell$ 持有 $w_i$ 和 $w_j $上的 $s^\ell_i$ 和 $s^\ell_j$，协议需要使得门 $G$ 计算完成后，$P_\ell$ 持有 $w_k$ 的秘密份额 $s^\ell_k$. 不失一般性地，假设 $\mathcal{C}$ 由加法门、常数乘法门、常数加法门、乘法门组成。

加法门。对于加法门，我们有

协议描述 · 公式

w_i + w_j = (s^1_i + \dots + s^n_i ) + (s^1_j + \dots + s^n_j ) = (s^1_i + s^1_j ) + \dots + (s^n_i + s^n_j )

协议描述 · 公式

也就是说，参与方只需要将自己的秘密份额在本地相加，即 $P_\ell$ 设置 $s^\ell_k = s^\ell_i + s^\ell_j$.

常数乘法门。设常数乘法门对应的常数为 $\alpha$. 常数乘法门只有一个输入 $w_i$，输出为 $w_k = c \cdot w_i$. 我们有

\alpha \cdot w_i = \alpha \cdot (s^1_i + \dots + s^n_i) = \alpha \cdot s^1_i + \dots + \alpha \cdot s^n_i

协议描述 · 公式

也就是说，参与方只需要将自己的秘密份额在本地乘以常数 $\alpha$，即 $P_\ell$ 设置 $s^\ell_k = \alpha \cdot s^\ell_i$.

常数加法门。设常数加法门对应的常数为 $\alpha$. 常数加法门只有一个输入 $w_i$，输出为 $w_k = w_i + \alpha$. 我们有

w_i + \alpha = (s^1_i + \dots + s^n_i) + \alpha = (s^1_i + \alpha) + s^2_i + \dots + s^n_i

协议描述 · 公式

也就是说，参与方 $P_1$ 将自己的秘密份额设置为 $s^1_k = s^1_i + \alpha$，其他参与方 $P_\ell, \; \ell \neq 1$ 设置 $s^\ell_k = s^\ell_i$.

乘法门。乘法门的计算需要参与方的交互。对于乘法门，我们有

w_k = w_i w_j = (s^1_i + \dots + s^n_i ) (s^1_j + \dots + s^n_j) \\ = \left( \sum\limits^{n}\limits_{\ell=1} s^\ell_i s^\ell_j \right) + \left( \sum\limits_{\ell_1 \neq \ell_2} s^{\ell_1}_i s^{\ell_2}_j \right)

这里的想法与计算布尔电路与门非常相似。首先，$P_\ell$ 可以本地计算 $s^\ell_i s^\ell_j$. 对于 $s^{\ell_1}_i s^{\ell_2}_j$，需要 $P_{\ell_1}$ 和 $P_{\ell_2}$ 的交互。具体来说，$P_{\ell_1}$ 选择均匀随机数 $r_{\ell_1, \ell_2} \leftarrow_{\$} \mathbb{F}$，然后 $P_{\ell_1}$ 和 $P_{\ell_2}$ 运行OLE协议，$P_{\ell_1}$ 作为发送方以 $s^{\ell_1}_i$ 和 $-r_{\ell_1, \ell_2}$ 作为输入，$P_{\ell_2}$ 作为接收方以 $s^{\ell_2}_j$ 作为输入，OLE运行结束后，$P_{\ell_2}$ 得到 $\gamma_{\ell_1, \ell_2} = s^{\ell_1}_i s^{\ell_2}_j - r_{\ell_1, \ell_2}$. 此时 $\gamma_{\ell_1, \ell_2}$ 和 $r_{\ell_1, \ell_2}$ 就构成了 $s^{\ell_1}_i s^{\ell_2}_j$ 的加法秘密分享。最后，$P_\ell$ 设置 $s_k^\ell = s^\ell_i s^\ell_j + \sum\limits_{\ell' \neq \ell} (r_{\ell, \ell'} + \gamma_{\ell', \ell})$ 为 $w_k$ 的秘密份额。由计算过程可知，这样得到的秘密份额满足 $w_k = s_k^1 + … + s_k^\ell$.

输出重建。对于 $P_i$ 的每一个输出 $y_{i, k}$，其他参与方将自己的份额 $s_{i, k}^\ell, \; \ell \neq i$ 发给 $P_i$，然后 $P_i$ 计算 $y_{i, k} = s_{i, k}^1 + … + s_{i, k}^n$. 每一个输出都以这样的方式重建。

最后，完整的算术电路GMW协议如图 6.6所示。

算术电路GMW协议 $\Pi_\mathsf{GMW}^\mathsf{arith}$

协议分为三个阶段：输入分享阶段、计算阶段和输出重建阶段。参与方 $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}$ 并已经将其转化成了包含加法门、常数乘法门、乘法门的算术电路。

输入分享阶段。对于 $P_i$ 的每个输入 $x_{i, k} \in \mathbb{F}, \; k \in [M_\mathsf{in}^i]$，$P_i$ 选择域上的随机元素 $r_{i, k}^1, …, r_{i, k}^n$ 满足 $\sum\limits_{\ell=1}^n r_{i, k}^\ell = x_{i, k}$，然后将 $r_{i, k}^\ell$ 发给 $P_j$ 作为秘密份额。

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

加法门。假设输入导线上的值为 $w_i, w_j$，输出导线上的值为 $w_k$. 参与方 $P_\ell$ 持有的秘密份额为 $w_i^\ell, w_j^\ell$. $P_\ell$ 设置 $s_k^\ell = s_i^\ell + s_j^\ell$ 为输出导线上的份额。
常数乘法门。假设对应的常数为 $\alpha$，输入导线上的值为 $w_i$，输出导线上的值为 $w_k$. 参与方 $P_\ell$ 持有的秘密份额为 $w_i^\ell$. $P_\ell$ 设置 $s_k^\ell = \alpha \cdot s_i^\ell$ 为输出导线上的份额。
常数加法门。假设对应的常数为 $\alpha$，输入导线上的值为 $w_i$，输出导线上的值为 $w_k$. 参与方 $P_\ell$ 持有的秘密份额为 $w_i^\ell$. $P_1$ 设置输出导线上的份额为 $s_k^1 = s_i^1 + \alpha$，其他参与方 $P_\ell, \; \ell \neq 1$ 设置输出导线上的份额为 $s_k^\ell = s_i^\ell$.
乘法门。假设输入导线上的值为 $w_i, w_j$，输出导线上的值为 $w_k$. 参与方 $P_\ell$ 持有的秘密份额为 $w_i^\ell, w_j^\ell$. 参与方执行以下操作：
1. 对于所有的 $\ell_1 \in [n], \; \ell_2 \in [n] \backslash \{\ell_1\}$，$P_{\ell_1}$ 与 $P_{\ell_2}$ 执行如下操作：$P_{\ell_1}$ 均匀随机选择 $r_{\ell_1, \ell_2} \leftarrow_{\$} \mathbb{F}$. $P_{\ell_1}$ 和 $P_{\ell_2}$ 运行OLE协议，其中 $P_{\ell_1}$ 作为发送方以 $s^{\ell_1}_i , -r_{\ell_1, \ell_2}$ 作为输入，$P_{\ell_2}$ 作为接收方以 $s^{\ell_2}_j$ 作为输入，$P_{\ell_2}$ 得到 $\gamma_{\ell_1, \ell_2} = s^{\ell_1}_i s^{\ell_2}_j - r_{\ell_1, \ell_2}$.
2. $P_\ell$ 设置 $s_k^\ell = s^\ell_i s^\ell_j + \sum\limits_{\ell' \neq \ell} (r_{\ell, \ell'} + \gamma_{\ell', \ell})$ 为输出导线上的份额。

输出重建阶段。对于 $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$.

安全性证明

不难发现，假设 $t \leq n -1$，在 $\mathcal{F}_{\mathsf{OLE}}$ 混合模型下，算术电路GMW协议 $\Pi_\mathsf{GMW}^\mathsf{arith}$ 对于静态半诚实敌手UC-安全实现了安全函数计算的理想功能 $\mathcal{F}_{\mathsf{sfe}}$. 分析思路与布尔电路相同：首先，协议构造满足正确性。对于隐私性，在秘密分享和计算乘法门时，被攻陷方看到的是均匀随机值；在输出重建时，根据协议输出和被攻陷方的份额可以模拟诚实方的份额，其分布与真实协议中完全相同。

定理

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

此定理的证明与定理 6.2完全类似，不再赘述。

本章思考题

为什么安全多方计算的函数 $f$ 要以算术电路或者布尔电路的方式来表达？安全多方计算能否支持一般性的随机存取机器（Random Access Machine, RAM）模型计算任务，例如C语言代码？如何安全地处理RAM模型中的条件分支和跳转指令？
本章节所介绍的BGW协议和GMW协议都假设参与方之间存在点对点安全信道，在现实中我们应该如何实现这些安全信道，相对应的，会引入哪些安全假设？
GMW协议中与门是通过使用OT协议来实现的，如果使用其他密码学原语（例如，同态加密）替代OT，协议会如何变化？请思考这种替代对安全性和效率的影响。

学习笔记

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

本章笔记

第 6 章 基于线性秘密分享的协议

目录

第 6 章 基于线性秘密分享的协议

BGW协议（半诚实安全）

协议描述

安全性证明

GMW协议

两方布尔电路GMW协议

多方布尔电路GMW协议

协议描述

安全性证明

多方算术电路GMW协议

协议描述

安全性证明

本章思考题

学习笔记

第 6 章基于线性秘密分享的协议

第 6 章基于线性秘密分享的协议