理解 Beaver Triples：实现秘密共享中的安全乘法

在安全多方计算 (MPC) 领域，秘密共享允许一组参与者在保持输入私密性的同时，共同计算一个函数。由于秘密共享具有线性性质，加法操作非常直接，但乘法却是一个重大的技术障碍。如果你只是简单地将两个秘密共享的多项式相乘，结果多项式的次数会增加，这反过来又会增加重构秘密所需的参与者数量。

为了解决这个问题，密码学家使用了一种被称为 Beaver Triples 的技术。这种方法允许各方在不增加多项式次数且不泄露底层秘密的情况下，对秘密共享的值进行乘法运算。本文将通过一个保护隐私的群体决策过程的实际案例，来探讨 Beaver Triples 的机制。

问题所在：乘法瓶颈

想象四位朋友正在尝试决定去哪家餐厅。为了保持私密性，每位朋友为每家餐厅提供两个评分：一个经济适用度评分 ($a$) 和一个偏好度评分 ($f$)。目标是计算一个“朋友级别评分” ($s = a imes f$)，然后将这些评分求和以得到“群体级别评分” ($S = \sum s$)。

使用秘密共享方案（如 Shamir's），每个输入都会被转换为份额 (shares)。例如，Alice 的经济适用度评分变为 $[a]$，她的偏好度评分变为 $[f]$。虽然将这些份额相加很容易，但将它们相乘却很难。

如果我们把份额表示为多项式 $p(x) = a + px$ 和 $q(x) = f + qx$，将它们相乘会得到一个二次多项式：$pqx^2 + (fp + aq)x + af$。这增加了重构阈值；如果原始秘密需要 2 个人才能解锁，那么乘积现在需要 3 个人。在大规模系统中，这种“次数膨胀”会迅速变得难以维持。

Beaver Triples 的几何直觉

为了在不增加多项式次数的情况下乘两个秘密值 $x$ 和 $y$，我们可以使用一个几何恒等式。考虑一个边长为 $x$ 和 $y$ 的矩形。如果我们在这个矩形内选取一个任意点 $(a, b)$，我们可以将 $x$ 和 $y$ 表示为：

$x = a + d$
$y = b + e$

其中 $d = x - a$ 且 $e = y - b$。

大矩形的面积 ($xy$) 随后可以分解为四个较小的面积：

$xy = (a + d)(b + e) = ab + ae + bd + de$

通过代入 $c = ab$，我们得到了 Beaver Triples 中使用的核心恒等式：

$xy = c + ae + bd + de$

实现协议

为了以保护隐私的方式实现这一点，值 $a, b,$ 和 $c$（其中 $c = ab$）必须在实际输入 $x$ 和 $y$ 知道 之前，随机生成并秘密共享给参与者。这些就是 Beaver Triples $[a], [b], [c]$。

分步过程

  1. 预计算： 一个可信的发布者 (dealer) 或一个安全协议会生成三元组 $[a], [b], [c]$，使得 $c = ab$。每个参与者都会收到这些值的份额。
  2. 掩码 (Masking)： 为了乘 $[x]$ 和 $[y]$，参与者计算差值的份额：
    • $[d] = [x] - [a]$
    • $[e] = [y] - [b]$
  3. 公开 (Opening)： 参与者公开 (open) $d$ 和 $e$ 的值。因为 $a$ and $b$ 是随机掩码，所以 $d$ and $e$ 揭示了关于原始秘密 $x$ and $y$ 的任何信息。
  4. 最终计算： 现在 $d$ and $e$ 是公开的常数，参与者可以利用秘密共享的线性性质计算乘积的份额 $[xy]$： $[xy] = [c] + e[a] + d[b] + de$

因为该操作仅涉及加法和与公开常数的乘法，所以多项式的次数不会增加。

一个具体的例子

让我们将其应用于 Ben 的餐厅评分。Ben 的经济适用度为 8，偏好度为 8 ($x=8, y=8$)。群体拥有份额 $[8]$ 和 $[8]$。

假设预计算的 Beaver Triple 是 $a=5, b=6, c=30$。

  1. 计算差值： $[d] = [8] - [5] = [3]$ 和 $[e] = [8] - [6] = [2]$。
  2. 公开差值： 群体公开 $d=3$ 和 $e=2$。
  3. 计算乘积： $[64] = [30] + 2[5] + 3[6] + (3 imes 2) = [30] + [10] + [18] + 6 = [64]$。

关键安全约束

为了使该系统保持安全，两条规则是绝对的：

  1. 随机性： $a$ and $b$ 必须是真正的随机数。如果 $a$ 是一个已知的常数，那么公开 $d = x - a$ 就会立即揭示 $x$。
  2. 一次性使用： 每个三元组必须恰好使用一次。如果同一个三元组 $[a, b, c]$ 被用于两个不同的乘法 $(x, y)$ and $(x', y')$，观察者就可以计算 $d' - d = x' - x$，从而揭示两个秘密输入之间的关系。

总结

Beaver Triples 将复杂的非线性乘法问题转化为一系列线性操作和公开揭示。通过将繁重的工作转移到预计算阶段，MPC 协议可以高效地计算复杂函数——例如群体对晚餐地点的共识——同时确保个人数据保持严格保密。

Sources