Beaver Triplesの理解：秘密分散における安全な乗算の実現

秘密計算（MPC）の領域において、秘密分散は、参加者が入力を非公開に保ったまま、それらの入力を用いて関数を共同で計算することを可能にします。秘密分散における加算は、その線形性により単純ですが、乗算は大きな技術的障壁となります。単に2つの秘密分散された多項式を乗算すると、結果の多項式の次数が上昇し、その結果、秘密を復元するために必要な参加者の数が増えてしまいます。

これを解決するために、暗号学者はBeaver Triplesという手法を用います。この手法により、当事者は多項式の次数を増やすことなく、また元の秘密を明かすことなく、秘密分散された値の乗算を行うことができます。本記事では、プライバシーを保護したグループ意思決定プロセスの実用的な例を通じて、Beaver Triplesの仕組みを解説します。

問題点：乗算のボトルネック

4人の友人がレストランを決める場面を想像してください。プライバシーを保つため、各友人は各レストランに対して2つのスコアを提供します。すなわち、手頃な価格スコア（$a$）と好みのスコア（$f$）です。目標は、「友人レベルのスコア」($s = a imes f$) を計算し、それらの合計から「グループレベルのスコア」($S = \sum s$) を算出することです。

秘密分散スキーム（Shamir'sなど）を使用する場合、各入力はシェア（分散値）に変換されます。例えば、Aliceの価格手頃度スコアは$[a]$となり、彼女の好みスコアは$[f]$となります。これらのシェアを足し合わせることは簡単ですが、掛け合わせることは容易ではありません。

シェアを多項式 $p(x) = a + px$ および $q(x) = f + qx$ として表すと、それらを乗算すると2次多項式になります：$pqx^2 + (fp + aq)x + af$。これにより、復元しきい値が増加します。もし元の秘密が復元に2人を必要としていた場合、積は3人を必要とします。大規模なシステムでは、この「次数の増大（degree bloat）」はすぐに維持不能なものとなります。

Beaver Triplesの幾何学的な直感

多項式の次数を増やすことなく2つの秘密の値 $x$ と $y$ を乗算するために、幾何学的な恒等式を利用できます。辺の長さが $x$ と $y$ である長方形を考えてみましょう。その長方形の中に任意の点 $(a, b)$ を選ぶと、$x$ と $y$ を次のように表現できます：

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

ここで、$d = x - a$ および $e = y - b$ です。

大きな長方形の面積 ($xy$) は、以下の4つの小さな領域に分解できます：

$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): 信頼できるディーラー、または安全なプロトコルによって、$c = ab$ となるようなトリプル $[a], [b], [c]$ が生成されます。各参加者はこれらの値のシェアを受け取ります。
  2. マスキング (Masking): 秘密シェア $[x]$ と $[y]$ を乗算するために、参加者は差分のシェアを計算します：
    • $[d] = [x] - [a]$
    • $[e] = [y] - [b]$
  3. 公開 (Opening): 参加者は $d$ と $e$ の値を開示（公開）します。$a$ と $b$ はランダムなマスクであるため、$d$ と $e$ は元の秘密 $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]$。

重要なセキュリティ制約

このシステムが安全であり続けるためには、2つの絶対的なルールがあります：

  1. ランダム性 (Randomness): $a$ と $b$ は真にランダムでなければなりません。もし $a$ が既知の定数であれば、$d = x - a$ を明かすことは $x$ を即座に明かすことになります。
  2. 一回限りの使用 (One-Time Use): 各トリプルは正確に1回だけ使用されなければなりません。もし同じトリプル $[a, b, c]$ が2つの異なる乗算 $(x, y)$ と $(x', y')$ に使用された場合、観測者は $d' - d = x' - x$ を計算でき、$x$ と $x'$ の間の関係性が明かされてしまいます。

まとめ

Beaver Triplesは、非線形な乗算という複雑な問題を、一連の線形操作と公開情報の開示への変換します。重い処理を事前計算フェーズに移行させることで、MPCプロトコルは、グループの夕食場所の合意形成のような複雑な関数を、個々のデータが厳密に機密であることを保証しながら、効率的に計算することができます。

Sources