第 3 章一个安全多方计算协议的例子

学习目标

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

本章将介绍一个具有完美隐私性的通用安全多方计算协议：假设有任意数量的 $n$ 个参与方，当不超过 $t < n / 2$ 个参与方一起汇集他们的信息时，他们无法获得除了协议输出以外的任何额外信息。我们将在第6章严格证明：即使参与方的计算能力是无限的，他们也无法获得任何额外信息。

与第1章相同，我们仍然需要假设所有参与者都遵守协议，这种安全性被称为半诚实安全(semi-honest security)或被动安全(passive security)。我们假设任意两个参与方都可以使用安全信道通信。（注：本章参考了书 [CDN, 2015]，Chapter 3. Reproduced with permission of the Licensor through PLSclear.）

Shamir秘密分享

本章介绍的安全多方计算协议基于Shamir秘密分享方案 [Shamir, 1979]。Shamir秘密分享是一种基于有限域 $\mathbb{F}$ 上的多项式的秘密分享，要求 $|\mathbb{F}|>n$. 我们假设 $\mathbb{F}=\mathbb{Z}_p$，其中 $p$ 是一个大素数且 $n < p$.

首先，参与方选定 $n$ 个各不相同且均不为0的值 $(\alpha_1, …, \alpha_n)$. 要分享某个值 $s \in \mathbb{F}$，算法选择阶数最多为 $t$ 的随机多项式 $q_s(x) \in \mathbb{F}[x]$ ，使得 $q_s(0) = s$，然后私下向参与方 $P_j$ 发送秘密份额 $s_j = q_s(\alpha_j)$. 根据拉格朗日插值法可以证明，这种方法产生的秘密份额满足两个基本性质：(1) 任何 $t+1$ 组或更多的秘密份额可以重建秘密 $s$；(2) 任何 $t$ 组或更少的秘密份额不包含关于 $s$ 的信息. 下面，我们进行详细说明。

拉格朗日插值法

拉格朗日插值法 · 公式

直观地说，我们可以通过 $\ell + 1$ 个横坐标不同的点确定一个唯一的至多 $\ell$ 次的多项式，而拉格朗日插值法给出了该多项式的构造方式。设 $q(x)$ 是 $\mathbb{F}$ 上至多 $\ell$ 次的多项式，$(\alpha_1, …, \alpha_{\ell+1})$ 对所有 $i \neq j$ 满足 $\alpha_i \neq \alpha_j$，则:

q(x) = \sum_{i=1}^{\ell+1} q(\alpha_i) \delta_i(x)

拉格朗日插值法 · 公式

其中，$\delta_i(x)$ 是 $\ell$ 次多项式，满足 $\delta_i(\alpha_i) = 1$ 且 $\delta_i(\alpha_j) = 0, \forall j \neq i$. 换言之，$\delta_i(x)$ 的定义如下

\delta_i(x) = \prod_{1 \leq j \leq \ell+1, j \neq i} \frac{x - \alpha_j}{\alpha_i - \alpha_j}

我们来看一下这个公式为什么成立。首先，每个 $\delta_i(x)$ 是 $\ell$ 个单项式的乘积，是 $\ell$ 次多项式，所以 $q(x) = \sum_{i=1}^{\ell+1} q(\alpha_i) \delta_i(x)$ 是 $\ell$ 次的多项式相加，它最多为 $\ell$ 次。其次，注意到 $\delta_i(x)$ 满足 $\delta_i(\alpha_i) = 1$ 且 $\delta_i(\alpha_j) = 0, \forall j \neq i$，故 $q(x)$ 在 $\alpha_i$ 处的值为 $q(\alpha_i)$. 最后，我们还需要说明 $q(x)$ 是唯一的。这是因为当 $x = \alpha_i, \; 1 \leq i \leq \ell + 1$ 时， $q(x) - \sum_{i=1}^{\ell+1} q(\alpha_i) \delta_i(x)$的值为0，只有零多项式满足值为0的位置比它的次数更多，因此 $q(x) - \sum_{i=1}^{\ell+1} q(\alpha_i) \delta_i(x)$ 一定是零多项式，即 $q(x) = \sum_{i=1}^{\ell+1} q(\alpha_i) \delta_i(x)$.

拉格朗日插值法 · 公式

至此我们证明了Shamir秘密分享的第一条性质：任何 $t+1$ 组或更多的秘密份额可以重建秘密 $s$. 因为参与方可以通过拉格朗日插值法计算 $q_s(x)$ 并得到 $q_s(0) = s$. 对于拉格朗日插值法构造出的多项式 $q(x)$，令 $x = 0$，我们有

q(0) = \sum_{i=1}^{\ell+1} q(\alpha_i) \cdot \delta_i(0)

拉格朗日插值法 · 公式

对于所有阶数至多为 $\ell$ 的多项式 $q(x)$ 成立. 令 $r_i = \delta_i(0)$，我们得到了一组向量 $\boldsymbol{r} = (r_1, …, r_{\ell+1})$，可以将所有阶数至多为 $\ell$ 的多项式 $q(x)$ 在0处的取值表示为 $q(\alpha_i)$ 的线性组合：

q(0) = \sum_{i=1}^{\ell+1} q(\alpha_i) \cdot r_i

$\boldsymbol{r} = (r_1, …, r_{\ell+1})$ 被称为重组向量（recombination vector）。需要注意的是，$\delta_i(x)$ 不依赖于 $q(x)$，所以 $\delta_i(0)$ 也不依赖于 $q(x)$. 重组向量 $\boldsymbol{r}$ 适用于所有多项式 $q(x)$，是每个参与方都可以计算的公共信息。

下面，我们证明Shamir秘密分享的第二个性质：任意 $t$ 个或更少的秘密份额不包含关于 $s$ 的信息。我们证明如下命题：对于任意秘密 $s \in \mathbb{F}$ 和一组 $\boldsymbol{\alpha}$ 的值 $(\alpha_1, …, \alpha_t)$（$\alpha_i$ 各不相同且均不为0），均匀随机采样一个阶数 $\leq t$ 且满足 $q(0) = s$ 的函数 $q(x)$，Shamir秘密分享的 $t$ 个秘密份额 $(q(\alpha_i))_{i \in [t]}$ 服从 $\mathbb{F}^t$ 上的均匀分布。由于 $\mathbb{F}^t$ 上的均匀分布显然与 $s$ 无关，这也就直接证明了这些秘密份额不包含关于 $s$ 的信息。

我们的证明方法是构造一个从 $\mathbb{F}^t$ 到 $\mathbb{F}^t$ 的可逆映射，因为从 $\mathbb{F}^t$ 到 $\mathbb{F}^t$ 的任何可逆映射都将 $\mathbb{F}^t$ 上的均匀分布映射到 $\mathbb{F}^t$ 上的均匀分布。首先，Shamir秘密分享需要采样随机多项式 $q(x)$ 满足 $q(0) = s$，这等价于从 $\mathbb{F}^t$ 中均匀随机采样 $\boldsymbol{b} = (b_1, …, b_t)$，并令 $q_b(x) = s + \sum_{j=1}^t b_j x^t$. 对于固定的 $s$ 和 $\boldsymbol{\alpha} = (\alpha_1, …, \alpha_t)$，定义如下的映射，它将 $\boldsymbol{b} = (b_1, …, b_t)$ 映射到 $(q_b(\alpha_i))_{i \in [t]}$. 显然这是一个 $\mathbb{F}^t$ 到 $\mathbb{F}^t$ 的映射。接下来我们说明它是可逆的。给定一组 $(y_i)_{i \in [t]} \in \mathbb{F}^t$ 满足 $q_b(\alpha_i)=y_i$，由于我们还知道 $q_b(0) = s$，所以我们知道了 $q_b(x)$ 上 $t + 1$ 个点的坐标，可以通过拉格朗日插值法来计算 $q_b(x)$ 和 $\boldsymbol{b} \in \mathbb{F}^t$. 因此，该映射是可逆的。由此可知，$t$ 个秘密份额 $(q(\alpha_i))_{i \in [t]}$ 服从 $\mathbb{F}^t$ 上的均匀分布。

计算示例

计算示例 · 公式

我们再用一个具体的示例来展示Shamir秘密分享的计算过程。假设有5个参与方 $P_1, \ldots, P_5$，敌手控制了 $t = 2$ 个被攻陷参与方。参与方在 $\mathbb{F}=\mathbb{Z}_{11}$ 中计算，且被分享的秘密是 $s = 6$. 令 $\boldsymbol{\alpha} = (\alpha_1, \ldots, \alpha_5) = (1, 2, 3, 4, 5)$. 算法均匀随机地选取 $b_1, b_2 \leftarrow_{\$} \mathbb{F}$，假设选取到了 $b_1 = 7$ 和 $b_2 = 1$，然后我们定义

\[h(x) = s + b_1 x + b_2 x^2 = 6 + 7 x + x^2\]

计算示例 · 公式

并计算 $s_1 = h(1) = 6 + 7 + 1 \bmod 11 = 3, \; s_2 = h(2) = 24 \bmod 11 = 2, \; s_3 = h(3) = 3, \; s_4 = h(4) = 6, \; s_5 = h(5) = 0$. 因此，秘密份额为

\[(3, 2, 3, 6, 0)\]

计算示例 · 公式

然后，$s_i$ 被安全地发送给 $P_i$. 现在假设参与方得到了秘密份额 $s_3$、$s_4$、$s_5$. 由于 $3>2$，这些参与方可以使用拉格朗日插值法来重建秘密。

首先计算

\delta_3(x)=\prod_{j=4,5} \frac{x-\alpha_j}{\alpha_3-\alpha_j}=\frac{(x-4)(x-5)}{(3-4)(3-5)}=\left(x^2-9 x+20\right)((3-4)(3-5))^{-1} (\bmod 11)

计算示例 · 公式

由于 $(3-4)(3-5)=2$ 且 $2 \cdot 6 \bmod 11=1$，因此 $((3-4)(3-5))^{-1} \bmod 11=6$. 因此，

\delta_3(x)=\left(x^2-9 x+20\right) \cdot 6=\left(x^2+2 x+9\right) 6=6 x^2+12 x+54=6 x^2+x+10 (\bmod 11)

计算示例 · 公式

同理，计算

\begin{aligned} \delta_4(x) & = 10 x^2+8 x+7 \\ \delta_5(x) & = 6 x^2+2 x+6 \end{aligned}

计算示例 · 公式

现在，对于任何的 $s_3, s_4, s_5$，如果我们令

h(x)=s_3 \cdot \delta_3(x)+s_4 \cdot \delta_4(x)+s_5 \cdot \delta_5(x)

计算示例 · 公式

那么有$h(3)=s_3 \cdot 1+s_4 \cdot 0+s_5 \cdot 0=s_3, \; h(4)=s_3 \cdot 0+s_4 \cdot 1+s_5 \cdot 0=s_4, \; h(5)=s_3 \cdot 0+$ $s_4 \cdot 0+s_5 \cdot 1=s_5$. 这说明 $h(x)$ 就是我们希望重建的多项式。

将 $\delta_3(x), \delta_4(x), \delta_5(x)$ 代入，得到

\begin{aligned} h(x) & =s_3 \delta_3(x)+s_4 \delta_4(x)+s_5 \delta_5(x) \\ & =\left(6 s_3+10 s_4+6 s_5\right) x^2+\left(s_3+8 s_4+2 s_5\right) x+\left(10 s_3+7 s_4+6 s_5\right) \end{aligned}

计算示例 · 公式

假设 $h(x)$ 的形式为 $h(x)=s+b_1 x+b_2 x^2$，有

\begin{aligned} s & =10 s_3+7 s_4+6 s_5 \bmod 11 \\ b_1 & =s_3+8 s_4+2 s_5 \bmod 11 \\ b_2 & =6 s_3+10 s_4+6 s_5 \bmod 11 \end{aligned}

计算示例 · 公式

这就是从秘密份额 $s_3=h(3), s_4=$ $h(4)$ 和 $s_5=h(5)$ 计算 $h(x)$ 的通式。

最后，我们将 $s_3=3, s_4=6$ 和 $s_5=0$ 代入上述公式，得到

\begin{aligned} s & =10 \cdot 3+7 \cdot 6+6 \cdot 0 \bmod 11=72 \bmod 11=6 \\ b_1 & =3+8 \cdot 6+2 \cdot 0 \bmod 11=51 \bmod 11=7 \\ b_2 & =6 \cdot 3+10 \cdot 6+6 \cdot 0 \bmod 11=78 \bmod 11=1 \end{aligned}

计算结果与秘密分享时选择的多项式（式 3.1）一致。

如果我们只想要得到秘密值 $s$ 而不是整个多项式，那么只需计算 $s=10 s_3+7 s_4+6 s_5 \bmod 11$. 这里的向量 $\boldsymbol{r}=(10,7,6)$ 就是当 $h(x)$ 阶数最大为 2 时，从 $h(3)$、$h(4)$ 和 $h(5)$ 计算 $h(0)$ 的重组向量。

半诚实安全的电路计算协议

现在，我们基于Shamir秘密分享来构造安全多方计算协议。

算术电路

我们用算术电路来表示有限域 $\mathbb{F}$ 上的任何函数。假设每个参与方恰好有一个属于有限域 $\mathbb{F}$ 的输入和输出。也就是说，函数 $f: \mathbb{F}^n \rightarrow \mathbb{F}^n,\left(x_1, …, x_n\right) \rightarrow$ $\left(y_1, …, y_n\right)$，即 $\left(y_1, …, y_n\right)=f\left(x_1, …, x_n\right)$.

形式化地说，这样的电路是一个有向无环图，其中的节点称为门(gate)，边称为导线(wire)，每个门最多有两个输入导线。首先，每个参与方 $P_i$ 有一个记为 $i$ 的输入门，$P_i$ 为该门提供输入值 $x_i$. 电路共有 $n$ 个输入门，它们没有输入导线但可以有任意数量的输出导线，输入值被复制到它的所有输出导线上。电路有一些内部的加法门和乘法门，它们有两个输入导线和任意数量的输出导线；这些门将它们的两个输入相加或相乘后放到输出导线上。还有一种常数乘法门，它们有一个输入导线和任意数量的输出导线，这类门带有 $\mathbb{F}$ 中的一个常数 $c$，表示执行乘以 $c$ 的运算。最后，对于每个 $P_i$，有一个记为 $i$ 的输出门，它有一个输入导线但没有输出导线。最终分配给这个门的输入导线的值将会是 $y_i$.

电路的计算过程如下：假设输入值已经被确定（也就是将 $x_i$ 输入标记为 $i$ 的输入门）。假设门已经以某种（任意的）方式编号。我们取第一个所有输入导线的值都已经确定的门，计算其输出值，并将该值放在该门的输出导线上。重复此过程，直到所有导线都被赋了值。当这个过程结束时，输出值也就确定了。我们将这个过程中遍历门的顺序称为计算顺序。

注意，考虑算术电路是没有一般性损失的：任何可计算的函数都可以用“与”门和“非”门表示为多项式大小的布尔电路。

它们可以通过 $\mathbb{F}$ 中的操作来模拟：布尔值“真”和“假”的编码是1和0，比特 $b$ 的“非”运算是 $1-b$，比特 $b$ 和 $b^{\prime}$ 的“与”运算是 $b \cdot b^{\prime}$.

协议描述

我们把某个参与方的子集记作 $C$，它的大小最多为 $t$，这些参与方将在协议结束后聚在一起，尽可能地从他们所见的数据中推导额外信息。我们把 $C$ 中的参与方称为被攻陷的(corrupted)，把不在 $C$ 中的参与方称为诚实的(honest)。由于我们要计算的函数是在 $\mathbb{F}$ 上的算术电路，因此，协议需要对输入值（以及中间结果）进行 $\mathbb{F}$ 中的一系列加法和乘法运算，并且不泄漏除了最终结果以外的任何信息。

为了协议描述的简洁性，我们定义一些方便的符号。

定义

给定 $\boldsymbol{\alpha} = (\alpha_1, \ldots, \alpha_n)$. 设 $a \in \mathbb{F}$ 且 $f$ 是一个阶数最多为 $t$ 的多项式，满足 $f(0)=a$. 我们定义 $[a ; f]_t$ 如下：

[a ; f]_t = (f(\alpha_1), \ldots, f(\alpha_n))

即，它表示由 $f$ 计算出来的秘密 $a$ 的秘密份额集。根据上下文，我们有时会省略阶数或多项式，写作 $[a ; f]$ 或 $[a]$.

协议描述 · 公式

注意，符号 $[a ; f]$ 一方面描述了一个对象，即秘密份额集 $(f(1), …, f(n))$. 另一方面，它也是一个声明：它声明了 $f(0) = a$. 符号 $[a ; f]_t$ 描述了同一个对象 $(f(1), …, f(n))$，但进一步地声明了 $\operatorname{deg}(f) \leq t$.

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

\begin{aligned} {[a ; f]_t+[b ; g]_t } & = (f(\alpha_1) + g(\alpha_1), \ldots, f(\alpha_n) + g(\alpha_n)) \\ c[a ; f]_t & =(c f(\alpha_1), \ldots, c f(\alpha_n)) \\ {[a ; f]_t *[b ; g]_t } & = (f(\alpha_1) g(\alpha_1), \ldots, f(\alpha_n) g(\alpha_n)) \end{aligned}

容易观察到：$f(\alpha_i)+g(\alpha_i)=(f+g)(\alpha_i)$ 和 $f(\alpha_i) g(\alpha_i)=(f g)(\alpha_i)$. 因此，我们有如下的引理：

引理

对于任意 $a, b, \alpha \in \mathbb{F}$ 和任意在 $\mathbb{F}$ 上阶数最多为 $t$ 的多项式 $f, g$，满足 $f(0)=a$ 和 $g(0)=b$，以下等式成立：

引理（续 2）

\begin{aligned} {[a ; f]_t+[b ; g]_t } & =[a+b ; f+g]_t \\ c[a ; f]_t & =[c a ; c f]_t \\ {[a ; f]_t *[b ; g]_t } & =[a b ; f g]_{2 t} \end{aligned}

注意，我们这里定义的符号不仅描述了秘密份额集，还声明了多项式的阶数。例如，等式 $[a ; f]_t *[b ; g]_t=[a b ; f g]_{2 t}$ 表明对象 $(f(1), …, f(n)) * (g(1), …, g(n))$ 与 $((f g)(1), …,(f g)(n))$ 相同，它还表明 $(f g)(0)=a b$ 且 $\operatorname{deg}(f g) \leq 2 t$.

该引理说明了一个重要的结论：通过对份额进行计算，我们可以隐式地对秘密进行相应的计算。例如，第一个等式表明，如果秘密 $a, b$ 已被分享，每个参与方在本地将他的 $a$ 和 $b$ 的份额相加，那么就获得了秘密 $a+b$ 的秘密份额。下面，我们再定义一些参与方的行为：

定义

给定 $\boldsymbol{\alpha} = (\alpha_1, …, \alpha_n)$. 参与方 $P_i$ 分发 $\left[a ; f_a\right]_t$，指的是他选择了一个阶数 $\leq t$ 的均匀随机多项式 $f_a(x)$，且满足 $f_a(0)=a$，然后对于 $j=1, …, n$ 将秘密份额 $f_a(\alpha_j)$ 发送给 $P_j$. 每当参与方基于多项式 $f_a$ 获得了值 $a$ 的份额时，我们说参与方持有 $\left[a ; f_a\right]_t$.

假设参与方持有 $\left[a ; f_a\right]_t,\left[b ; f_b\right]_t$. 那么，当我们说参与方计算 $\left[a ; f_a\right]_t+\left[b ; f_b\right]_t$ 时，这指的是每个参与方 $P_i$计算$f_a(\alpha_i)+f_b(\alpha_i)$，根据引理 3.1，这意味着现在参与方持有 $\left[a+b ; f_a+f_b\right]_t$. 我们以类似的方式定义参与方计算 $c [a ; f]_t$ 和 $[a ; f]_t *[b ; g]_t$.

基于上述定义的工具和术语，我们可以给出一个安全地计算算术电路的协议，我们称之为“半诚实安全的电路计算协议”，如图 3.1所示。

半诚实安全的电路计算协议

协议分为三个阶段：输入分享阶段、计算阶段和输出重建阶段。

输入分享阶段。给定 $\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)$.

安全性分析

我们来分析一下协议的安全性。我们要说明协议满足以下两个性质：

完美的正确性：参与方接收到正确输出的概率为1.
完美的隐私性：任意大小最多为 $t < n / 2$ 的被攻陷方子集 $C$，无论他们的计算能力如何，执行协议后不会得到除 $\left\{x_j, y_j\right\}_{P_j \in C}$ 之外的任何信息。

为了精确地描述隐私性，我们再次使用第1章中提到的“基于模拟的证明范式”：要证明某个参与方只得到了信息$X$，我们将证明他看到的一切信息都可以在仅知道 $X$ 的情况下高效地模拟。

定义视图 $\text{view}_{j}$ 为 $P_j$ 在协议执行过程中看到的所有值。更准确地说，视图 $\text{view}_{j}$ 是一个向量，它的第一个元素是 $x_j$，然后每当 $P_j$ 做出随机选择时，我们将其添加到视图 $\text{view}_{j}$ 中，每当 $P_j$ 收到一条消息时，我们也将这条消息添加到 $\text{view}_{j}$ 中。注意，视图 $\text{view}_{j}$ 是一个随机变量，因为它依赖于 $P_j$ 和其他参与方做出的随机选择。

安全性分析 · 公式

协议满足隐私性意味着，存在一个高效的算法——模拟器 $\mathcal{S}$，它以 $\left\{x_j, y_j\right\}_{P_j \in C}$ 作为输入，生成一个输出，其分布与 $C$ 在协议期间看到的所有信息完全相同；也就是说，我们希望

\mathcal{S}\left(\left\{x_j, y_j\right\}_{P_j \in C}\right) \stackrel{\text{perf}}{=} \left\{\text{view}_{j}\right\}_{P_j \in C}

由于我们要证明协议具有完美的隐私性，所以要求这两个分布完全相同。

请读者注意，尽管第4章给出的通用可组合安全模型也是基于模拟的范式，但它与这里的定义有很大不同。因为如果被攻陷方可以违背协议，那么仅有正确性和隐私性是不足以保证协议的安全的。

下面我们依次证明正确性和隐私性。

正确性。 根据引理 3.1的前两个公式可知，当加法门和常数乘法门被处理过后，参与方持有 $\left[y ; f_y\right]_t$，其中 $y$ 是输出导线的正确值。根据引理 3.1的第三个公式和重组向量的定义可知，当乘法门被处理过后，参与方也持有 $\left[y ; f_y\right]_t$，$y$ 是输出导线的正确值。最后，根据拉格朗日插值法的正确性可知，输出重建阶段恢复的是正确的 $y_i, i \in [n]$.

类型1：在输入分享阶段和乘法门中，他们接收诚实方计算的秘密份额集 $\left[x_i ; f_{x_i}\right]_t$ 和 $\left[h(\alpha_i) ; f_i\right]_t$ 中自己的份额。
类型2：在输出重建阶段中，对于每个被攻陷方的输出 $y$，他们接收 $\left[y ; f_y\right]_t$ 中的所有份额。

我们要说明这两类消息不会泄漏额外信息，直观上来说，这是因为它们具有以下两个特性：

特性1：诚实方在进行输入分享和计算乘法门时发送给被攻陷方的所有值，都是使用随机多项式 $f_{x_i}$ 和 $f_i$ 分享的，它们的阶数最多为 $t$. 因为最多有 $t$ 个被攻陷方，所以被攻陷方集合最多接收 $t$ 个份额。在「拉格朗日插值法」一节我们论证过，阶数最多为 $t$ 的随机多项式的 $t$ 个份额只是均匀随机值。
特性2：诚实方在输出重建阶段中发送给被攻陷方的值，给定被攻陷方已知的值和输出 $y$，他们自己就能计算出来。这是因为在输出重建阶段之前，他们已经知道每个被攻陷方 $P_i$ 自己的份额 $f_y(\alpha_i)$. 这给了他们 $f_y(x)$ 上的 $t$ 个点。如果又得到了结果 $y$，他们额外知道了 $f_y(0)=y$，就可以使用拉格朗日插值法计算 $f_y(x)$. 由 $f_y(x)$ 他们可以计算出所有诚实方 $P_j$ 的 $f_y(\alpha_j)$，而 $f_y(\alpha_j)$ 正是 $P_j$ 在输出重建阶段中发送的 $y$ 的份额。

细心的读者会注意到，这种直观上的分析实际上也接近于一个形式化的证明。回想一下，我们的目标是构建一个模拟器 $\mathcal{S}$，给定被攻陷方的输入和输出，输出一个与协议中被攻陷方视图具有相同分布的值。从上面的直观分析中可以看出 $\mathcal{S}$ 应该如何工作：

首先，它已知被攻陷方的输入，它遵循协议执行，就好像自己是被攻陷方那样。
在输入分享阶段和计算乘法门时，它通过采样均匀随机值来模拟诚实方发送给被攻陷方的份额。根据特性1，这样产生的分布是正确的。
在输出重建阶段，每个输出 $y$ 会被发给被攻陷方，$\mathcal{S}$ 用它“反过来”计算诚实方在 $\left[y ; f_y\right]$ 中的份额，使其与被攻陷方的 $t$ 个模拟份额以及 $f_y(0)=y$ 相一致，然后用它们来模拟诚实方发送给被攻陷方的用来重建输出的份额。根据特性2，这样产生的分布是正确的。

至此，我们通过一个通用安全多方计算协议的例子展示了“基于模拟的证明范式”。之后，本书的第4章将进一步讨论安全模型的形式化定义，在第6章给出上述协议的形式化安全证明。

计算示例

本章的最后，我们通过计算示例来更直观地展示：在输出重建阶段，将一个输出的所有份额发给被攻陷方不会影响安全性。这意味着秘密份额不包含“结果是如何计算出来”的信息：例如，$c = a + b$ 被重建且结果为8，那么 $c$ 的 $n$ 个秘密份额将能够同时与 $a=4, b=4$ 和 $a=3, b=5$ 这两种情况都保持一致，否则，协议就泄漏了额外信息。接下来我们通过例子详细说明。

假设在协议执行过程中，变量 $a$ 和 $b$ 已被计算，下一步需要计算变量 $c = a + b$ 并输出给 $P_1$. 令 $\boldsymbol{\alpha} = (\alpha_1, \alpha_2, \alpha_3) = (1, 2, 3)$. 假设 $n=3$ 且 $t=1$. 即，有三个参与方 $P_1, P_2, P_3$，其中一个可以是被攻陷的。不失一般性地，假设 $P_1$ 是被攻陷的. 因为 $t=1$，我们使用的多项式形式为 $f(x)=b_0+b_1 x$，是一条直线。

我们假设 $a=4$ 通过多项式 $a(x)=4+ x$ 进行秘密分享，$b=4$ 通过多项式 $b(x)=4+2x$ 进行秘密分享。那么计算过程如下表所示：

$b$

4

$\mathbf{6}$

8

10

根据多项式 $a(x)=4+ x$ 得 $a(1)=5, \; a(2)=6, \; a(3)=7$，根据 $b(x)=4+2x$ 得 $b(1)=6, \; b(2)=8, \; b(3)=10$. 当各方计算变量 $c=a+b$ 时，他们通过本地相加计算出份额11、14 和 17。在表格中，所有 $P_1$ 看到的秘密份额都加粗显示。

$P_1$ 应该只能知道 $c=8$，而不知道关于 $a$ 和 $b$ 的任何信息（除了 $a+b=8$ 以外）。这确实是成立的，因为我们可以把另一个假设 $a=3, b=5$ 填入表中。如果 $a=3, b=5$，$P_1$ 将有以下视图（$P_1$ 不知道 $P_2$ 和 $P_3$ 的份额）：

$b$

5

$\mathbf{6}$

$?$

如果 $a(0)=3$ 且 $a(1)=5$，那么就有 $a(x)=3+2 x$，从而 $a(2)=7$ 和 $a(3)=9$. 同理，如果 $b(0)=5$ 且 $b(1)=6$，那么就有 $b(x)=5+ x$，从而 $b(2)=7, b(3)=8$. $P_1$ 将这些值填入表格得到：

$b$

5

$\mathbf{6}$

7

8

这个假设与 $P_1$ 所看到的内容是一致的，因为 $7+7=14$ 且 $9+8=17$. 因此，$a=3, b=5$ 与 $a=4, b=4$ 同样可能。

我们再研究一个相乘的例子。假设 $a = 2, b = 4$，用于分享它们的多项式是 $a(x)=2+x$和$b(x)=4-x$. 此时，计算过程如下：

$b$	4	$\mathbf{3}$	2	1
$d_2$	8	$\mathbf{8}$	8	8
$d_3$	5	$\mathbf{6}$	7	8

我们先看表格的上半部分，注意到 $d = a b = 8$ 的份额不在一条直线上，因为 $d(x)=a(x) b(x)$ 不是一条线，而是一个二次多项式。实际上，$d(x)=(2+x)(4-x)=8+2x-x^2$，这与 $d(1)=9, d(2)=8, d(3)=5$ 相一致。

当参与方计算了本地乘积 $d_i$ 之后，协议的下一步是让每个参与方分发 $d_i$. 在表格的下半部分，$P_1$ 使用了多项式 $d_1(x)=9-2 x$，$P_2$ 使用了多项式 $d_2(x)=8+0 x$，$P_3$ 使用了多项式 $d_3(x)=5+ x$. 然后，各方通过重组向量 $(3,-3,1)$ 在本地合并它们的份额，得到表格中的份额：例如，$P_1$ 计算出 $3=3 \cdot 7+(-3) \cdot 8+1 \cdot 6$. 最后，参与方再基于 $3, -2, -7$ 重建出最终的结果 $c = 8$.

与加法时类似，可以假设另一种情况 $a = 1, b = 8$，然后填出一张一致的表格，如下表所示：

$b$	8	$\mathbf{3}$	-2	-7
$d_2$	-10	$\mathbf{8}$	26	44
$d_3$	-49	$\mathbf{6}$	61	116

由这两个例子我们可以更直观地了解到，输出重建阶段只重建了最终的结果，而没有泄漏关于“结果是如何计算出来的”信息。

本章思考题

Shamir秘密分享中，为什么要求多项式的最高次数 $t$ 必须满足 $t < n/2$？如果 $t \geq n/2$，会对协议造成什么影响？
本章节中所介绍的安全多方计算协议是设计在域上使用的，能否直接迁移至环上？注意：环里面的一些元素有逆元。
如果不使用“基于模拟的证明范式”，能否其他方式来定义协议的隐私性？

学习笔记

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

本章笔记

\(b\)	4	\(\mathbf{3}\)	2	1
\(d_2\)	8	\(\mathbf{8}\)	8	8
\(d_3\)	5	\(\mathbf{6}\)	7	8

第 3 章 一个安全多方计算协议的例子

目录

第 3 章 一个安全多方计算协议的例子

Shamir秘密分享

拉格朗日插值法

计算示例

半诚实安全的电路计算协议

算术电路

协议描述

安全性分析

计算示例

本章思考题

学习笔记

第 3 章一个安全多方计算协议的例子

第 3 章一个安全多方计算协议的例子