Chapter 6 BGW 协议与 GMW 协议¶

1 BGW 协议（基于 Shamir 秘密分享）¶

基本设定

基础：Shamir $(t, n)$-门限秘密分享 (基于多项式插值)
安全门限：$t < n/2$ (诚实多数)
模型：算术电路 (加法门、乘法门)，半诚实敌手
符号：$[a; f_a]_t$ 表示秘密 $a$ 由 $t$ 次多项式 $f_a$ 分享

协议流程

BGW 先将函数 $f$ 表示为算术电路，并在每条导线上维护一个 $t$ 次 Shamir 分享。

输入分享：每个 $P_i$ 对输入 $x_i$ 生成 $[x_i;f_i]_t$，把份额 $f_i(\alpha_j)$ 发给 $P_j$
逐门计算：按电路拓扑顺序处理加法门、常数乘法门和乘法门
输出重构：对输出 $y_i$，各方把输出导线份额发送给接收方 $P_i$，由 $P_i$ 插值恢复输出

线性运算 (本地计算)：
- 加法：$[a + b; f_a + f_b]_t = [a; f_a]_t + [b; f_b]_t$
- 标量乘法：$[c \cdot a; c \cdot f_a]_t = c \cdot [a; f_a]_t$
乘法运算（交互计算）:
- 本地相乘: 各方计算 $v_i = f_a(\alpha_i) \cdot f_b(\alpha_i)$，此时 $v_i$ 是 $2t$ 次多项式 $h(x) = f_a(x)f_b(x)$ 的点
- 降维 (Degree Reduction)：利用重组向量 $r$（满足 $h(0) = \sum r_i h(\alpha_i)$），各方把 $v_i$ 重新做一次 $t$-次 Shamir 分享得到 $[v_i]_t$，计算 $[ab]_t = \sum_{i=1}^n r_i \cdot [v_i]_t$

2 BGW 的安全性¶

理想功能 $F_{sfe}$

设目标函数满足

\[ (y_1,\dots,y_n)=f(x_1,\dots,x_n). \]

当收到 $P_i$ 的 $(\text{Input}, sid, x_i)$ 时，记录输入，并向模拟器泄露 $(\text{Input}, sid, P_i)$
当收到模拟器的 $(\text{Output}, sid, P_i)$ 时，若所有输入都已提交，则计算 $f$ 并把 $(\text{Output}, sid, y_i)$ 发送给 $P_i$
模拟器只能控制输出递送时机，不能修改诚实方输入或函数值

定理（BGW 半诚实安全）

假设参与方之间有点对点安全信道，且被攻陷方数满足 $|C| \le t < n/2$，则 BGW 协议对静态半诚实敌手 UC-安全实现 $F_{sfe}$。

为简化证明，假设每个输出门前紧跟一个乘法门；必要时可增加常数个乘法门，使输出分享在重构前被重新随机化。

模拟器 $S$ 的做法

输入分享阶段：
- 对被攻陷方，用真实输入模拟
- 对诚实方，把输入设成 $0$ 后模拟分享，并把相应份额发给被攻陷方
加法门 / 常数乘法门：直接模拟被攻陷方按协议计算
乘法门：对诚实方重分享的部分，向被攻陷方发送关于 $0$ 的模拟份额
输出重建阶段：向 $F_{sfe}$ 请求对应输出，再补出一组与输出值一致的诚实方份额
- 若 $P_i \in C$，得到 $y_i$，构造 $t$ 次多项式 $f_{y_i}$ 满足 $f_{y_i}(0) = y_i$ 且与已知的 $|C|$ 个份额一致：
  - 若 $|C| = t$，用拉格朗日插值构造 $f_{y_i}$
  - 若 $|C| < t$，先均匀随机选取 $t - |C|$ 个诚实方份额再插值
- 对于 $P_j \notin C$，发送 $f_{y_i}(\alpha_j)$ 作为 $P_j$ 的份额

两条关键引理

Strip 引理：若两个输入向量在被攻陷方输入上相同，则被攻陷方的 stripped view 完美同分布
Dress 引理：给定真实输出 $y_C$，按模拟器方式补回诚实方输出份额后，得到的完整视图与真实视图完美同分布

因此可把诚实方真实输入替换为 $0$，再由 $F_{sfe}$ 给出的输出补回最终视图，真实/理想执行不可区分。

Strip / Dress 的作用

BGW 证明中常把视图拆成两部分：

Strip(view)：删去输出重建阶段来自诚实方的补充份额
Dress(...)：再把这些份额按输出值穿回去

核心思想是：先证明除了输出恢复外，其余视图已与真实分布一致，再证明补回去的输出份额也与真实分布一致。

3 GMW 协议（基于加法秘密分享）¶

基本设定

基础：加法秘密分享（XOR Sharing）

\[ x = x_1 \oplus x_2 \oplus \cdots \oplus x_n \]
安全门限：$t < n$，允许至多 $n-1$ 个被攻陷方
计算模型：布尔电路（XOR, AND, NOT）或算术电路
核心工具：OT / OLE

设每个参与方持有 $a,b$ 的份额 $a_i,b_i$，则利用布尔电路有：

XOR 门（本地）：$c_i = a_i \oplus b_i$
NOT 门（本地）：由 $P_1$ 把自己的份额翻转，$c_1 = a_1 \oplus 1$，其余参与方份额不变
AND 门展开（交互）：$c = (\bigoplus a_i) \land (\bigoplus b_j) = \bigoplus_i (a_i b_i) \oplus \bigoplus_{i < j}(a_i b_j \oplus a_j b_i)$
- $a_i b_i$: 本地计算
- $a_i b_j$: 需要 $P_i$ 和 $P_j$ 交互，利用 1-out-of-4 OT 计算交叉项

用 1-out-of-4 OT 计算交叉项

对于一对参与方 $P_i, P_j$：

$P_i$ 构造四项 OT 表，对应 $P_j$ 的 $4$ 种可能输入

\[ T_{u,v} = (a_i\cdot v)\oplus(u\cdot b_i)\oplus r,\qquad u,v\in\{0,1\} \]
双方执行 1-out-of-4 OT：
- $P_i$ 是发送方，输入整张表
- $P_j$ 是接收方，选择 $(a_j,b_j)$
输出分配：
- $P_i$ 保留份额 $r$
- $P_j$ 得到 $=(a_i b_j \oplus a_j b_i)\oplus r$
- 两者异或起来就是所需交叉项

4 GMW 布尔协议的安全性¶

理想功能 $F_{OT^1_4}$

发送方输入 4 条消息，接收方输入 2 比特选择值 $(b_0,b_1)$，接收方只得到对应一条消息。

定理（GMW 布尔电路）

当被攻陷方数量不超过 $n-1$ 时，GMW 布尔协议在 $F_{OT^1_4}$-混合模型下，对静态半诚实敌手 UC-安全实现 $F_{sfe}$。

这里为什么是计算安全？

因为 OT 本身通常只能在计算假设下实现，所以这一部分证明使用的是计算不可区分而非信息论相等；相应地，环境 $\mathcal{Z}$ 也默认是 PPT。

模拟器 $S$ 的做法

被攻陷方输入按真实值模拟，诚实方输入统一置为 $0$
输入分享阶段发给被攻陷方的份额是均匀随机
若被攻陷方在某个 OT 中是接收方，模拟器直接给它随机 OT 输出
输出阶段再补上与最终输出一致的诚实方份额

不可区分性

输入分享：加法份额对 $|C|\le n-1$ 的敌手仍是均匀随机
AND 门 OT：被攻陷方收到的 OT 输出与随机值计算不可区分
输出阶段：模拟器补出的诚实方份额与真实分布一致

5 算术电路版 GMW¶

对每个输入 $x_{i,k}\in \mathbb{F}$，参与方随机选择

\[ r_{i,k}^{1},\dots,r_{i,k}^{n}\in\mathbb{F},\qquad \sum_{\ell=1}^{n} r_{i,k}^{\ell}=x_{i,k}, \]

并把 $r_{i,k}^{\ell}$ 发给 $P_\ell$，这就是一个 $(n-1,n)-$门限加法秘密分享。

设输入导线为 $w_i, w_j$，输出导线为 $w_k$，$P_\ell$ 持有 $s_i^\ell, s_j^\ell$，则：

加法门：$s_k^\ell = s_i^\ell + s_j^\ell$。
常数乘法门 $(\alpha)$：$s_k^\ell = \alpha \cdot s_i^\ell$
常数加法门 $(\alpha)$：$P_1$ 加上常数，即 $s_k^1 = s_i^1 + \alpha$，其余份额不变，即$s_k^\ell = s_i^\ell$
乘法门：$w_k = \sum_\ell s_i^\ell \sum_\ell s_j^\ell = \sum_{\ell=1}^{n} s_i^\ell s_j^\ell + \sum_{\ell_1\ne \ell_2} s_i^{\ell_1} s_j^{\ell_2}$
- 本地项：每个 $P_\ell$ 自己算 $s_i^\ell s_j^\ell$
- 交叉项：通过 OLE 计算

OLE 理想功能 $F_{OLE}$

发送方输入 $(\alpha,\beta)\in\mathbb{F}^2$
接收方输入 $x\in\mathbb{F}$
接收方得到

\[ \gamma = \alpha x + \beta \]

用 OLE 计算交叉项

对每对 $(\ell_1,\ell_2)$，$P_{\ell_1}$ 取随机 $r_{\ell_1,\ell_2}\xleftarrow{}_{\$}\mathbb{F}$

设发送方输入 $(\alpha,\beta)=\left(s_i^{\ell_1}, -r_{\ell_1,\ell_2}\right)$，接收方输入 $x=s_j^{\ell_2}$，得到：

\[ \gamma_{\ell_1,\ell_2}=s_i^{\ell_1}s_j^{\ell_2}-r_{\ell_1,\ell_2} \]

最终 $P_\ell$ 的输出份额为

\[ s_k^\ell = s_i^\ell s_j^\ell + \sum_{\ell'\ne \ell}\left(r_{\ell,\ell'}+\gamma_{\ell',\ell}\right) \]

输出重建：对输出 $y_{i,k}$，其他参与方把各自份额发给 $P_i$，由其计算

\[ y_{i,k} = \sum_{\ell=1}^{n} s_{i,k}^{\ell}. \]

BGW 与 GMW 的比较

协议	基础分享	安全门限	适合电路	非线性门代价	安全类型
BGW	Shamir 多项式分享	$t < n/2$	算术电路	乘法需要降阶交互	信息论安全
GMW	加法/XOR 分享	$t < n$	布尔/算术电路	AND 需 OT，乘法需 OLE	计算安全

1. 为什么 BGW 要求 $t < n/2$，而 GMW 能做到 $t < n$？

BGW 的乘法会把分享次数从 $t$ 提升到 $2t$，必须还能恢复并降阶；而 GMW 的非线性计算交给 OT / OLE，门限取决于底层原语而不是多项式次数。

2. 什么时候更偏向 BGW？

在诚实多数且希望得到信息论安全时，BGW 很自然。

3. 什么时候更偏向 GMW？

在两方或少数参与方场景，尤其需要利用 OT/OLE、Beaver 预处理等现代优化时，GMW 更灵活。

4. 为什么安全多方计算里的函数总要先写成电路？

因为协议真正会处理的是局部可组合的基本门操作。只要能把函数分解成加法门、乘法门、XOR 门、AND 门等基本门，就能逐门安全求值并复用已有原语。

5. BGW 和 GMW 都假设点对点安全信道，这在现实里怎么满足？

通常做法是先用公钥基础设施、认证密钥交换、TLS 或更底层的安全信道协议把通信层保护好，再在其上运行 MPC。

6. GMW 里如果用同态加密替代 OT / OLE，会怎样？

可以，但协议形态会改变：非线性门不再通过 OT/OLE 完成，而转为同态运算或密文交互。这样可能减少某些轮次，但会带来更重的公钥开销，具体优劣取决于电路类型和实现环境。

协议	基础分享	安全门限	适合电路	非线性门代价	安全类型
BGW	Shamir 多项式分享	\(t < n/2\)	算术电路	乘法需要降阶交互	信息论安全
GMW	加法/XOR 分享	\(t < n\)	布尔/算术电路	AND 需 OT，乘法需 OLE	计算安全