Skip to content

Chapter 7 通过 Beaver 三元组实现 MPC

1 效率瓶颈与离线-在线思想

背景：计算开销不对称

  • 线性门（加法 / 常数乘）：本地计算即可，开销极低。
  • 非线性门（乘法）：需要交互，是 MPC 的主要性能瓶颈。

Beaver 的核心思想是将与输入无关的重活提前到离线阶段（Offline）完成，在在线阶段（Online）只做少量线性计算与公开操作。

离线-在线范式

  • 离线阶段：生成与真实输入无关的相关随机数（Correlated Randomness），例如 Beaver 三元组。
  • 在线阶段：输入到达后，用这些随机相关性掩盖真实导线值，把昂贵乘法化成公开掩码值和本地线性组合。
  • 安全边界：离线数据必须正确且一次性使用；同一个三元组重复用于不同乘法会泄露输入关系。

2 Beaver 三元组

  • 定义：满足 \(c = a\cdot b\) 的随机共享三元组 \(([a], [b], [c])\)，其中 \(a,b \xleftarrow{}_{\$} \mathbb{F}\) 均匀随机，\([\cdot]\) 表示加法秘密分享。

在线乘法公式

给定输入份额 \([x],[y]\)，以及一个三元组 \(([a],[b],[c])\)

  1. 本地掩码

    \[ [d]=[x]-[a],\qquad [e]=[y]-[b] \]

  2. 公开掩码差值

    \[ d = Open([d]),\qquad e = Open([e]) \]

  3. 本地恢复结果

    \[ xy = (d+a)(e+b)=de+db+ae+ab \]
    \[ \Rightarrow [xy]=de + d[b] + e[a] + [c]. \]
为什么公开 \(d,e\) 不泄露？

因为 \(a,b\) 是均匀随机的，故

\[ d=x-a,\qquad e=y-b \]

在敌手看来也是均匀随机掩码，只是一种一次性掩盖后的差值。

3 基于 Beaver 三元组的 MPC 协议

假设参与方已经预先持有 \(m\) 个 Beaver 三元组 \(([a_k],[b_k],[c_k])_{k=1}^{m}\)

  1. 输入分享阶段：每个参与方把输入 \(x_{i,k}\) 做加法秘密分享，将相应份额分发给其他参与方，形成 \([x_{i,k}]\)

  2. 计算阶段（逐门计算）

    • 加法门 / 常数乘法门：本地线性运算 \([x+y]=[x]+[y]\)

    • 乘法门：消耗一个 Beaver 三元组

      1. 公开

        \[ d = Open([x]-[a]),\qquad e = Open([y]-[b]) \]

      2. 本地计算

        \[ [z] = de + d[b] + e[a] + [c] \]

  3. 输出重建阶段：对每条输出导线 \([y_i]\)，各方把份额发送给指定接收者，接收者恢复最终输出

4 UC 框架下的安全性

理想功能 \(F_{triple}\)

随机取 \(a,b \xleftarrow{}_{\$}\mathbb{F}\)，计算 \(c=ab\)，随机生成加法份额，满足加法分享性质，把 \((a_i,b_i,c_i)\) 分发给 \(P_i\)

模拟器 \(S\) 的做法

  • 被攻陷方输入：用真实输入模拟
  • 诚实方输入：全部置为 \(0\) 后模拟输入分享
  • 计算阶段：模拟诚实方与被攻陷方按协议执行，乘法门中公开的 \(d,e\) 可按均匀随机值模拟
  • 输出阶段：向 \(F_{sfe}\) 请求输出，再均匀补出与该输出一致的诚实方份额

理想/真实世界不可区分

  1. 加法分享隐私性：诚实方的输入份额本就与真实输入无关
  2. 乘法阶段公开的 \(d,e\)：由于三元组中的 \(a,b\) 均匀随机，故 \(d,e\) 对敌手看起来也是均匀随机
  3. 输出重建阶段：模拟器补出的诚实方份额与真实份额分布相同

5 Beaver 三元组的生成

5. 1 方法一：可信第三方（TTP）

实现最简单，但依赖一个半诚实且不串通的额外参与方，通常只适合特定部署环境。

  1. TTP 随机选取 \(a,b \xleftarrow{}_{\$}\mathbb{F}\)，计算 \(c=ab\)

  2. 随机选取份额 \((a_1,\dots,a_n)\)、\((b_1,\dots,b_n)\)、\((c_1,\dots,c_n)\)，满足

    \[ a=\sum_i a_i,\qquad b=\sum_i b_i,\qquad c=\sum_i c_i \]

  3. 把 \((a_i,b_i,c_i)\) 发给 \(P_i\)

5.2 方法二：分布式生成（MPC）

  1. 各方本地随机选取 \(a_i,b_i\)，令

    \[ a=\sum_i a_i,\qquad b=\sum_i b_i \]

  2. 用一个底层 MPC 协议计算 \([c]=[ab]\)，从而得到三元组 \(([a],[b],[c])\)

1. 为什么 Beaver 三元组对效率提升这么大？

因为它把“真正困难的乘法相关性”预先生成好了，在线时只需用随机掩码把真实输入贴到这个相关性上。

2. 恶意安全时还够吗？

还不够。
恶意模型下必须进一步验证三元组真的满足 \(c=ab\)，否则错误三元组会直接破坏正确性。

3. 除了三元组，还有类似的离线原语吗？

有。只要某类交互能被抽象成“与真实输入无关的相关随机数”，通常就能尝试做成预处理原语。