はじめに
この記事では、多項式秘密分散を用いたMPCプロコルであるBGWプロトコルを紹介します。
MPC Overviewページ <- ここにMPC各記事へのリンクがあります。
BGWプロトコル
Ben-Or–Goldwasser–Wigdersonプロトコルは、情報理論的安全性を提供し、$t < n/3$ の閾値まで耐性があります。
Shamir秘密分散
秘密 $s$ を次数 $t$ の多項式 $f(x)$ の定数項として共有：
$$
f(x) = s + a_1x + a_2x^2 + \dots + a_tx^t
$$
各パーティ $P_i$ はシェア $s_i = f(i)$ を受け取ります。再構成はLagrange補間により行います。
$$
s = \sum_{i=1}^{t+1} s_i \cdot \lambda_i, \quad
\lambda_i = \prod_{j \neq i} \frac{j}{j - i}
$$
次元$t$の多項式を考えた時に、$t+1$点の値が分かっていたら、多項式が特定できます。
例えば、二次関数を考えた時に2点だけでは向きが逆の関数も存在します（$f(x)=x^2-1$と$f(x)=-x^2+1$ではどちらもy軸との交点は同じだが、向きが違う）。そのため、次元数+1の点があれば多項式が一意に特定できます。
これで共有されたシェアを使って、各パーティは計算を行います。
加算
加算は非常に簡単です。
各参加者が 自分の share を足すだけ。
前提（秘密は多項式で共有されている）
秘密 $a$ は次数 $t$ の多項式
$$
p(x)=a+p_1x+\dots+p_tx^t
$$
秘密 $b$ は別の次数 $t$ の多項式
$$
q(x)=b+q_1x+\dots+q_tx^t
$$
各参加者 $P_i$ はそれぞれ
$$
a_i = p(i), \quad b_i = q(i)
$$
という share を持っています。
$$
c_i = a_i + b_i
$$
つまり
$$
c_i = p(i) + q(i)
$$
これは何を意味しているか？
多項式を足した新しい多項式を考えます。
$$
r(x)=p(x)+q(x)
$$
そうすると、各パーティのシェアは以下のようになっています。
$$
r(i)=c_i
$$
ここで、$r(x)$ の定数項は
$$
r(0)=a+b
$$
なので、参加者たちは そのまま $(a+b)$ の秘密分散を持っている 状態になります。
ここでそれぞれのシェアを集めれば$r(0)$が求まるので、$a+b$の計算を行うことができます。
ここでポイントなのは加算の時はパーティ同士の通信が発生しないことです。次の乗算の時はパーティ同士の通信が必要になります。
乗算
乗算は加算と違って、各参加者が自分の share を掛けるだけでは終わりません。理由は「次数が増える」からです。この部分は追って説明するので、プロトコルの内容を見ていきます。
前提（秘密は多項式で共有されている）
ここは加算の時と同じです。
秘密 $a$ は次数 $t$ の多項式
$$
p(x)=a+p_1x+\dots+p_tx^t
$$
秘密 $b$ は別の次数 $t$ の多項式
$$
q(x)=b+q_1x+\dots+q_tx^t
$$
各参加者 $P_i$ はそれぞれ
$$
a_i = p(i), \quad b_i = q(i)
$$
という share を持っています。
まずローカルに掛け算する
加算の時と同様に、各参加者は自分の share だけで計算してみましょう。
$$
d_i = a_i \cdot b_i
$$
を計算できます。つまり
$$
d_i = p(i)\cdot q(i)
$$
です。
ここで何が起きているか（次数が 2t になる）
多項式の積を
$$
s(x)=p(x)\cdot q(x)
$$
と置くと、$p(x), q(x)$ がそれぞれ $t$ 次なので、$s(x)$ は最大で $2t$ 次になります。
このとき
$$
s(i)=d_i
$$
なので、$d_i$ は「$s(x)$ の share」になっています。
また、求めたい値は定数項なので
$$
s(0)=p(0)\cdot q(0)=a\cdot b
$$
です。
しかしこのままだと困る（しきい値が崩れる）
BGWでは「次数 $t$ の Shamir sharing」を保ちながら計算を進めたいです。
これは、最初に決めた安全性の条件「最大 $t$ 人まで結託しても秘密が漏れない」という性質が、次数 $t$ の多項式によって保証されているからです。
ところが、乗算をそのまま行うと、多項式の次数が $2t$ に増えてしまいます。
次数が $2t$ になると、もはや「$t$ 人まで安全」という元の保証が成り立ちません。
つまり、安全性の前提が崩れてしまい、その後の計算を同じルールで続けることができなくなります。
そのため BGW では、乗算のあとに必ず「次数を $t$ に戻す」処理（degree reduction）を行い、再び同じ安全性を満たす形の秘密分散に整え直してから次の計算へ進みます。
そもそも何で$2t$ になると、「$t$ 人まで安全」という元の保証が成り立たないのかは、最後に補足で説明しますので一旦そういうものとして次に進んでください。
次数削減（degree reduction）の考え方
直感的には「$2t$ 次で共有されている $ab$ を、$t$ 次で共有し直す」操作です。
各参加者 $P_i$ は、自分が持っている値 $d_i$ を新たにランダムな $t$ 次多項式で再共有します。
定数項が $d_i$ になるような多項式
$$
g_i(x)=d_i + \alpha_{i,1}x + \dots + \alpha_{i,t}x^t
$$
を作り、各参加者 $P_j$ に $g_i(j)$ を送ります。
各参加者 $P_j$ は、全員から受け取った値を足し合わせて
$$
e_j = \sum_{i=1}^{n} g_i(j)
$$
を計算します。
すると $(e_1,\dots,e_n)$ は、ある $t$ 次多項式 $r(x)$ の評価値になっていて
$$
e_j = r(j)
$$
が成り立ちます。
この $r(x)$ の定数項は最終的に
$$
r(0)=a\cdot b
$$
となるため、参加者たちは $ab$ を次数 $t$ の Shamir sharing として持ち直した 状態になります。
補足
何で$2t$ になると、「$t$ 人まで安全」という元の保証が成り立たないのかを具体例で説明します。
例：t=1 の場合（1人攻撃者が混じっても安全にしたい）
最初に、秘密 $a$ を「次数 $t=1$ の多項式」で共有します。
$$
p(x)=a + \alpha x
$$
これは1次多項式です。
このときの安全性は、
- 任意の1人（$t=1$）が share を見ても、
- 定数項 $a$ は特定できない
というものです。
参加者が3人いるとする（n=3）
それぞれが持っている share は、
$$
a_1=p(1), \quad a_2=p(2), \quad a_3=p(3)
$$
1人だけでは直線は決まりません。
2点あれば直線が一意に決まるので、
「2人結託すると秘密が分かる」という設計です。
ここで乗算をする
同様に
$$
q(x)=b + \beta x
$$
も1次多項式。それぞれがローカルで掛け算すると、
$$
d_i = p(i) q(i)
$$
これに対応する多項式は以下のようになりまうs。
$$
s(x)=p(x)q(x)
$$
次数がどうなるか？
1次 × 1次 なので：
$$
s(x)
$$
は 2次多項式 になります。つまり、以下のようになります。
$$
s(x)=ab + (\dots)x + (\dots)x^2
$$
2次多項式は3点あれば一意に決まりますが、今回 $n=3$ なので、全員の share を集めれば復元できます。
しかし、元々$t=1$まで攻撃者が混じるのを許容するという安全設計だったので、3人全員が正直にプロトコルに則った処理をしないと秘密の計算ができません。これが安全性が崩れるということです。