理解 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. 預計算 (Precomputation): 一個受信任的發行者 (dealer) 或一個安全協議會生成三元組 $[a], [b], [c]$，使得 $c = ab$。每位參與者都會收到這些值的分享值。
  2. 遮罩 (Masking): 為了相乘秘密分享值 $[x]$ 和 $[y]$，參與者會計算差值的分享值：
    • $[d] = [x] - [a]$
    • $[e] = [y] - [b]$
  3. 揭露 (Opening): 參與者會揭露 (open) $d$ 和 $e$ 的值。因為 $a$ 和 $b$ 是隨機遮罩，所以 $d$ 經由 $x - a$ 和 $e$ 經由 $y - b$ 揭露了關於原始秘密 $x$ 和 $y$ 的任何資訊。
  4. 最終計算 (Final Computation): 現在 $d$ 和 $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. 隨機性 (Randomness): $a$ 和 $b$ must 必須是真正的隨機值。如果 $a$ 是已知常數，揭露 $d = x - a$ 就會立即揭露 $x$。
  2. 一次性使用 (One-Time Use): 每個三元組必須恰好使用一次。如果同一個三元組 $[a, b, c]$ 被用於兩個不同的乘法 $(x, y)$ 和 $(x', y')$，觀察者可以計算 $d' - d = x' - x$，從而揭露兩者之間的關係。

總結

Beaver Triples 將複雜的非線性乘法問題轉化為一系列線性操作和公開揭露。透過將繁重的計算工作移至預計算階段，MPC 協議可以高效地計算複雜函數——例如群體對晚餐地點的共識——同時確保個人數據保持嚴格保密。

Sources