用预处理乘法三元组实现 MPC

思想

将 MPC 协议划分为预处理阶段（参与方输入未知）和在线阶段（参与方选择好输入）是一种很受欢迎的 MPC 协议构造范式。预处理阶段为各个参与方生成一些相互之间具有一定关联性的随机量。参与方于在线阶段可以“消耗”这些随机量。
我们以 BGW 协议为例，在BGW 协议中唯一的实际开销为乘法门求值时的通信开销，然而由于这一步骤是在对秘密份额进行操作，而参与方只能于在线阶段得到秘密份额（秘密份额取值依赖于电路输入），因此将这部分操作转移到预处理阶段好像不是那么简单。Beaver 提出了一种非常聪明的方法，可以将大部分通信量都转移到预处理阶段。
Beaver 三元组（也称乘法三元组）指的是秘密份额三元组 $ [a] $，$ [b] $，$ [c] $，其中 $ a $ 和 $ b $ 是从某个适当的域中选择出的随机数，而 $ c = ab $。在线阶段中，每对一个乘法门求值都需要“消耗”一个 Beaver 三元组。
考虑一个输入导线为 $ \alpha $，$ \beta $ 的乘法门，各参与方持有秘密份额 $ [\nu_\alpha] $ 和 $ [\nu_\beta] $。为应用 Beaver 三元组 $ [a] $，$ [b] $ 和 $ [c] $ 计算 $ [\nu_\alpha \cdot \nu_\beta] $，参与方执行以下步骤：

各参与方在本地计算 $ [\nu_\alpha - a] $，并打开 $ d = \nu_\alpha - a $（所有参与方向其他参与方告知自己持有的秘密份额 $ [d] $）。虽然 $ d $ 取值依赖于秘密值 $ \nu_\alpha $，但由于其被随机值 $ a $ 覆盖，所以并不会泄露任何相关信息。
各个参与方在本地计算 $ [\nu_\beta - b] $，并打开 $ e = \nu_\beta - b $
有下列等式：
$$
\begin{array}{lll}
\nu_\alpha \nu_\beta & = & (\nu_\alpha - a + a)(\nu_\beta - b + b) \\
& = & (d + a)(e + b) \\
& = & de + db + ae + ab \\
& = & de + db + ae + c
\end{array}
$$
由于 $ d $ 和 $ e $ 已经被打开，各方都持有秘密份额 $ [a] $，$ [b] $，$ [c] $，因此各参与方可通过下述公式计算秘密份额 $ [\nu_\alpha \nu_\beta] $：$ [\nu_\alpha \nu_\beta] = de + d[b] + e[a] + [c] $

应用这一技术，只需要公开两个参数即可通过本地计算完成乘法门的求值，而在普通 BGW 协议中每次求值需要发送 $ n $ 个域元素。不过用这种方式来比较性能开销实际上忽略了 Beaver 三元组生成时引入的计算和通信开销。但是可以通过一些方法批量生成 Beaver 三元组，使得生成每个三元组的平均开销仅为每个参与方发送常数个域元素。

抽象

只要“抽象秘密分享方案”的秘密份额 $ [\nu] $ 满足一下性质就可以使用 Beaver 三元组方法：

加同态性：给定 $ [x] $、$ [y] $ 和公开值 $ z $，参与方不需要交互即可计算得到 $ [x + y] $、$ [x + z] $ 以及 $ [xz] $
可打开性：给定 $ [x] $，参与方可以选择向所有其他参与方披露 $ x $
隐私性：攻击者（无论何种攻击者）都无法从 $ [x] $ 中得到与 $ x $ 相关的任何信息
Beaver 三元组：各个参与方可以为每一个乘法门构造满足 $ c = ab $ 的随即三元组 $ [a] $，$ [b] $，$ [c] $
随机输入工具：对于属于参与方 $ P_i $ 的输入导线，各个参与方可以得到一个随机的秘密份额 $ [r] $，秘密份额 $ [r] $ 对除 $ P_i $ 以外的所有参与方来说都是随机的，只有 $ P_i $ 已知 $ r $。在协议执行过程中，当 $ P_i $ 为此条输入导线选择好输入值 $ x $ 后，$ P_i $ 可以向所有其他参与方公开 $ \delta = x - r $（不会泄露关于 $ x $ 的任何信息），参与方可以利用加同态性在本地计算得到 $ [x] = [r] + \delta $
只要抽象秘密分享方案满足上述所有性质，Beaver 三元组的方法就是安全的。更进一步，只要抽象秘密分享方案在恶意攻击者的攻击下仍然满足可打开性和隐私性，则 Beaver 三元组方法也可以抵御恶意攻击者的攻击

参考文献

实用安全多方计算导论 /（美）戴维・埃文斯（David Evans），（美）弗拉基米尔・科列斯尼科夫（Vladimir Kolesnikov），（美）迈克・罗苏莱克（Mike Rosulek）著；刘巍然，丁晟超译。北京：机械工业出版社，2021.5