Beaver 三元组简介

# 利用秘密份额进行计算——介绍 Beaver 三元组 来源：https://stoffelmpc.com/stoffel-blog/beaver-triples-tuples 你和朋友们正计划出去吃晚饭。通常情况下，你是那个负责为所有人买单的朋友。但最近市场行情不佳，所以每个人都得开始自己掏腰包了。 然而，并非每位朋友都很有钱，因为市场状况确实不太妙，其中一位还只是学生。但外部环境的压力并不能阻止这个朋友圈聚会并一起享受一顿美餐。为了共同享受这顿饭，需要决定去哪家餐厅。但大家喜欢的菜系不同，且各家餐厅的价格高低不一。考虑到每个人的财务状况和饮食偏好各不相同，你试图设计一种尊重隐私的方法，让群体就选择哪家餐厅达成共识。 作为一名密码学家，你知道可以利用**秘密共享**（[Secret Sharing](https://stoffelmpc.com/stoffel-blog/guide-to-secret-sharing?utm_source=x&utm_medium=social&utm_campaign=mpc-blog-series&utm_content=badcryptobitch)）来解决这个问题。你想出了一条简单的评分规则来决定大家去哪家餐厅：对于餐厅 *j*，成员 *i* 将提交： * $a_{ij}$ = 我能负担得起在该餐厅就餐的程度 * $f_{ij}$ = 我想在该餐厅就餐的程度 每个 $a_{ij}$ 和 $f_{ij}$ 都在 0-10 的范围内评级。个人层面的评分为 $s_{ij} = a_{ij} \times f_{ij}$。餐厅 *j* 的群体总分为 $S_j = \sum s_{ij}$。 最后，至少需要 2 位朋友公开餐厅的得分，然后决定晚餐地点。 我们希望保持每个人的 $a_{ij}$ 和 $f_{ij}$ 得分私密，以维持群组内的和谐。 这个朋友圈共有 4 人，你们正试图在 3 家餐厅中做出选择。你需要至少 2 人合作才能公开群体层面的餐厅得分。 具体化来说，假设这 4 位朋友分别是 Alice、Ben、Chloe 和 Stoffel。群体正在 3 家餐厅之间做决定：餐厅 A、餐厅 B 和餐厅 C。 每位朋友提交一对 $(a, f)$，其中 $a$ 代表 affordability（支付能力/可负担性），$f$ 代表 food preference（饮食偏好）。 私有输入如下： 餐厅 A: Alice (8,5)，Ben (7,6)，Chloe (9,4)，Stoffel (6,5)。 餐厅 B: Alice (6,9)，Ben (8,8)，Chloe (7,7)，Stoffel (5,9)。 餐厅 C: Alice (9,3)，Ben (4,7)，Chloe (6,6)，Stoffel (8,4)。 目标是不向群组中的所有人公开这些数字。目标是利用这些数字私下计算餐厅得分，并仅在最后公开最终的群体层面得分。 使用秘密共享的符号表示，每个私有输入都会被转换为份额（shares）。因此，Alice 不需要公开她对餐厅 A 的可负担性评分，群体获得的是该值的份额。用符号表示，这是 $[a_{ij}]$ 的一个实例。 同样，Alice 不需要公开她对餐厅 A 的饮食偏好评分，群体获得的是该值的份额。用符号表示，这是 $[f_{ij}]$ 的一个实例。 这对每位朋友和每家餐厅都适用。更一般地说，每个私有的可负担性评分变为 $[a_{ij}]$，每个私有的饮食偏好评分变为 $[f_{ij}]$。 我们要计算的是个人层面得分的份额 $[s_{ij}] = [a_{ij}f_{ij}]$，然后计算群体层面餐厅得分的份额 $[S_j] = \sum [s_{ij}]$。 最后，群体公开餐厅 A、餐厅 B 和餐厅 C 的最终得分，但不公开个人的可负担性或饮食偏好得分。 但你意识到这里有一个问题。 你实际上如何计算 $[a_{ij}] [f_{ij}]$？ 我们知道，对于每家餐厅 $j$ 和每位朋友 $i$，我们得到以下份额： $p_{ij}(x) = a_{ij} + p x$, $q_{ij}(x) = f_{ij} + q x$ 其中 $p_{ij}(0) = a_{ij}$ 且 $q_{ij}(0) = f_{ij}$。 如果我们直接计算 $p_{ij}(x)q_{ij}(x)$，我们会得到 $pqx^2 + (f_{ij}p + a_{ij}q)x + a_{ij}f_{ij}$，其中 $p_{ij}q_{ij}(0) = a_{ij}f_{ij}$。这确实能让我们私下获得正确的每家餐厅每位朋友的得分。 问题在于，之前我们只需要至少 2 位朋友就能公开最终得分。但现在，我们需要至少 3 位朋友才能公开最终得分；这几乎是群组里的所有人。 有没有办法仍然得到一个次数为 $t$ 的多项式，且该多项式的截距仍然是 $a_{ij}f_{ij}$？ 事实证明，答案是肯定的。 ## 利用秘密份额进行计算 记得在秘密共享的文章中，秘密共享本身是一个具有以下性质的线性函数： 对于秘密份额 $[x]$ 和 $[y]$，我们有 对于已知数 $a$，我们有 此外，我们还有公开操作（open operation），即使用拉格朗日插值法重构秘密： 我们该如何在不增加重构所需阈值的情况下计算 $[x][y]$？ 对于任意 $x$ 和 $y$，让我们考虑以下图表： 注意，x 轴上 0 到 $x$ 的距离是 $x$，同样，y 轴上 0 到 $y$ 的距离是 $y$。我们可以画一个矩形，得到一个尺寸为 $x$ 乘 $y$、面积为 $xy$ 的矩形。 有没有办法利用 $xy$ 的几何解释来想出计算 $[x][y]$ 的方法？ 在图表中，让我们更仔细地观察矩形的内部。对于任意点 $(a, b)$，我们可以类似地形成一个面积为 $ab$ 的另一个矩形。 注意，我们可以将 $x$ 和 $y$ 用 $a$ 和 $b$ 表示如下：$x = a + (x-a)$, $y = b + (y-b)$。 然后我们可以用 $a$ 和 $b$ 重新计算 $xy$ 的面积。我们得到 每一项都在较大的 $xy$ 矩形内形成较小的矩形。现在，设 $d = x-a$, $e = y-b$ 且 $c = ab$。则 我们现在有了一个关系式，可用于在不增加底层多项式次数的情况下实现共享秘密的乘法！ ## 但且慢。 我们快要到了，但还差一点。 如果我们有份额 $[x][y]$，我们希望重用我们的矩形恒等式来计算 $[xy] = [c] + [bd] + [ae] + [de]$，其中 $d, e$ 和 $c$ 如上定义。但如果 $d$ 和 $e$ 也是秘密共享的，我们该如何处理它们？关键在于实际上公开 $d$ 和 $e$，并将它们作为公开已知的数字使用。 但这会不会泄露 $x$ 和 $y$？不会，因为正如我们将展示的，$a$ 和 $b$ 充当 $x$ 和 $y$ 的随机生成掩码。因此，公开 $d$ 和 $e$ 不会泄露关于 $x$ 和 $y$ 的任何信息。 首先，假设 $a$ 不是随机生成的。那么 $a$ 是某个已知过程的结果，可以被外部观察者推断出来。这意味着利用已知关系 $d=x-a$，外部观察者可以推断出关于 $x$ 的信息。如果外部观察者可以直接计算 $a$，那么他们可以直接通过 $x = d + a$ 得到 $x$。所以，公开 $d$ 会泄露关于 $x$ 的信息。因此，$a$ 需要是随机生成的。$b$ 的情况同理。 其次，假设 $[a]$ 和 $[b]$ 在两次不同的乘法 $(x, y)$ 和 $(x', y')$ 中被重复使用。那么，我们有 $d = x-a, d' = x'-a, e = y-b, e' = y'-b$。我们可以看到 $d'-d = x'-x$ 且 $e'-e = y'-y$，这揭示了秘密值 $x, x', y, y'$ 之间的关系。这些关系与“公开 $d, d', e$ 和 $e'$ 不应泄露关于 $x, x', y$ 和 $y'$ 的任何有意义信息”这一事实相矛盾。因此，$[a], [b]$ 和 $[c]$ 必须且只能使用一次。 例如，如果群组中的任何人能够分辨出 Ben 给某家餐厅的评分比 Chloe 高了 5 分，那么他们就拥有足够的信息来推断 Ben 的私有评分。也许他更喜欢那家餐厅，也许他更负担得起。谁知道呢？总之，不应该有人知道。我们不希望群组中的任何人能够确定此类信息。 现在我们已经证明，$a$ 和 $b$ 需要随机生成且仅使用一次，以便作为 $x$ 和 $y$ 的掩码。这意味着可以安全地公开 $d$ 和 $e$，而不会向外部观察者泄露关于 $x$ 和 $y$ 的信息。 总结来说，由于 $d$ 和 $e$ 可以安全公开，我们现在可以计算 其中 $[a], [b], [c]$ 且 $c=ab$ 被称为 **Beaver 三元组**（Beaver Triples），以原始作者 Don Beaver 的名字命名。 ## 那我们如何使用它们呢？ 你知道有一个服务提供利用卫星熵生成的 Beaver 三元组。使用此服务，群组中的每个人都会获得相同 Beaver 三元组 $[a], [b], [c]$ 的份额。 等等？每个人都获得相同的 Beaver 三元组？ 是的，也不是。每个人都获得相同底层 Beaver 三元组的份额。他们并没有获得原始值 $a, b$ 和 $c$。 Alice 获得 $a$ 的一个份额、$b$ 的一个份额和 $c$ 的一个份额。Ben、Chloe 和 Stoffel 也获得他们各自的份额。在一起，他们的份额代表了相同的底层 Beaver 三元组 $[a], [b], [c]$。但没有个人知道原始的 $a, b$ 和 $c$ 值。 由于有 4 位朋友和 3 家餐厅，我们需要 12 个个人层面的得分。每个个人层面的得分需要一次乘法。因此，群体需要 12 个新的 Beaver 三元组。每个三元组仅使用一次。 现在，让我们通过一个得分来走一遍流程。以 Ben 对餐厅 B 的得分为例。Ben 提交 $a=8$ 和 $f=8$。这里，$a$ 是可负担性，$f$ 是饮食偏好。所以 Ben 对餐厅 B 的个人层面得分应为 $8 \times 8 = 64$。 但 Ben 不会直接公开这些值中的任何一个。群组不需要知道 Ben 能在餐厅 B 花多少钱。群组也不需要知道 Ben 有多想在餐厅 B 吃饭。 所以，Ben 对这两个值进行秘密共享。群组拥有 $[8]$ 和 $[8]$，现在需要计算 $[8 \times 8]$。 对于这次乘法，假设 Beaver 三元组的底层值为 $a=5, b=6$ 且 $c=ab=30$。这里的符号有点重载。这个 $a$ 是 Beaver 三元组掩码。它不是 Ben 的可负担性评分。 同样，没有人看到原始值 5、6 和 30。每个人都只有份额 $[5], [6]$ 和 $[30]$。 群组计算 $[d] = [8] - [5]$ 和 $[e] = [8] - [6]$。然后群组公开 $d=3$ 和 $e=2$。这是安全的，因为 5 和 6 是保持隐藏的随机掩码。 现在每个人都可以计算 $[xy] = [c] + d[b] + e[a] + de$。 代入数字，$[64] = [30] + 3[6] + 2[5] + 3 \times 2 = [30] + [18] + [10] + 6 = [64]$。 所以群组现在拥有了 Ben 对餐厅 B 得分的份额 $[64]$，而无需 Ben 公开他的可负担性评分或饮食偏好评分。 这个过程对每位朋友和每家餐厅都适用。在协议内部，个人层面的得分不是公开值。群体仅拥有每位朋友 $i$ 和每家餐厅 $j$ 的份额 $[s_{ij}]$。 现在，由于秘密共享是线性的，群体可以通过相加份额来计算餐厅层面的得分。 对于餐厅 A，群组计算 $[40] + [42] + [36] + [30] = [148]$。 对于餐厅 B，群组计算 $[54] + [64] + [49] + [45] = [212]$。 对于餐厅 C，群组计算 $[27] + [28] + [36] + [32] = [123]$。 此时，群组拥有了最终餐厅得分的份额。 没有人知道其他人的可负担性评分。没有人知道其他人的饮食偏好评分。甚至没有人需要知道个人的个人层面得分。 需要公开的只有最终的餐厅得分。由于这是一个 2-out-of-4 的秘密共享方案，至少需要 2 位朋友公开得分。 假设 Alice 和 Chloe 被指定公开最终得分。他们公开最终餐厅得分的份额。使用拉格朗日插值法，群组重构出餐厅 A 的得分为 148，餐厅 B 的得分为 212，餐厅 C 的得分为 123。 现在群组比较得分：$212 > 148 > 123$。所以得分最高的餐厅是餐厅 B。 晚餐地点已决定。没有人需要透露他们能负担多少钱。没有人需要透露他们有多想去某家特定的餐厅。群组保持了和谐。群体晚餐的餐厅也已选出。 ## 总结 - 提前，每个人获得预计算的秘密共享三元组 $[a], [b], [c]$，其中 $c=ab$ - 每个人将他们的偏好和可负担性评分秘密共享 - 每个人互相传递他们的份额 - 收到信号后，每个人运行算法，并使用三元组 $[a], [b], [c]$ 利用恒等式 $xy = c + bd + ae + de$ 计算涉及的乘法 - 完成后，组内 2 名成员使用拉格朗日插值法公开群体层面的餐厅得分并向群组揭示结果 - 群体晚餐的餐厅已选出！