はじめに

この記事では、シャミア秘密分散法をベースにしたマルチパーティ計算(MPC:Multi-party Computation)のプロトコルであるBGWプロトコルについて解説します。

MPC・秘密分散法については下記記事を参考にしてください。

https://acompany.tech/privacytechlab/multi-party-computation/

https://acompany.tech/privacytechlab/mpc-secret-sharing/

BGWプロトコルは1988年にBen-Or、Goldwasser、Wigdersonによって提案されたMPCの基本的なプロトコルであり、以下の特徴を持っています。

シャミア秘密分散法をベースにしている
値を秘密にしたまま加算と乗算ができる
参加者の半数未満の不正者に対して耐性がある

ただし、参加者はプロトコルから逸脱しない場合を扱います。逸脱する場合のプロトコルは別の記事で解説します。

シャミア秘密分散法

まずは下準備として、BGWプロトコルがベースにしているシャミア秘密分散法について見ていきましょう。

シャミア秘密分散法は、$t$ 次元多項式を用いて秘密情報を分散させる方法です。具体的には以下の方法によって秘密情報$s$ を分散化させます。

以下のようなランダムな$t$ 次元多項式$P(x)$ を用意する
$P(x)=s + p_1 x + \cdots + p_tx^t$
多項式上の点$(\alpha_i, P(\alpha_i))$ を$t+1$ つ以上選択し、それを分散した値とする
ただし、$t+1 \le N$

ここで、分散させた値のことをシェアと呼ぶことにします。

次に、シェアを用いて秘密情報$s$ を復号する方法を示します。

シェアを$t+1$ 個集める
$t+1$ 個の点から多項式補間を用いて$P(x)$ を復元する
$P(0)$ から秘密情報$s$ を得る

数式だけでは理解が難しいので、簡単のために$t=1$ の場合を考えます。この場合、1次元多項式$P(x)=s + p_1x$ となり、グラフ上では直線として表現することができます。この時$s$ の値は直線の切片になっていることがわかります。つまり、直線の式を知っていれば秘密情報も知っていることになります。

次に、直線上から2点を取り出しシェアとします。シェアは2つ集めることで、直線の式を導出することができます。したがって、シェアを2つ集めることで秘密情報$s$ を手に入れることができます。

重要な点として、一つ一つのシェアは何の情報も漏らさない点が挙げられます。さらに、多項式上の点はどれだけ取り出しても良いので、いくつでもシェアを作成することができます。

BGWプロトコル

BGWプロトコルは、$N$ 人の参加者間でシャミア秘密分散法によって生成された秘密情報$s$ のシェアに対し、加算と乗算を行う方法を提供します。これにより、任意の計算回路が作成でき、任意の計算を実行することができることになります。

ここで、簡単のために、参加者によって秘密情報$s$ がシェアの状態で保持されていることを$[s]$ と表します。

それでは、加算と乗算の方法を見ていきましょう。

加算

秘密情報$a, b$ のシェア$[a],[b]$ が与えられた時、$[a+b]$ を計算することを目指します。

加算の場合は、シェア同士を直接加算するだけで完了します。つまり、各参加者が手元にもつシェアを加算するだけで、$[a+b]$ が得られます。

以下詳細な説明です。

シェア$[a],[b]$ が、$t$ 次元多項式$P(x), Q(x)$ でシェア化されている場合、シェア同士の加算は$P(\alpha_i) + Q(\alpha_i)$ を表します。この時、得られるシェアは新たな$t$ 次元多項式$R(x) := P(x) + Q(x)$ 上の点になります。このとき、$R(0)=P(0) + Q(0) = a + b$ です。

さらに、次元が$t$ であるため、復号に必要なシェアの数も同じです。したがって、シェア同士の加算を直接行った結果が$[a+b]$ になります。

乗算

秘密情報$a, b$ のシェア$[a],[b]$ が与えられた時、$[ab]$ を計算することを目指します。

加算の場合と同じように直接乗算を実行することで、$[ab]$ を計算することができます。しかし、生成されたシェアは新たな$2t$ 次元多項式$R(x):=P(x)Q(x)$ 上の点であるため、秘密情報の復元には$2t + 1$ つのシェアが必要になります。ただし、$2t + 1 \le N$ を満たす必要があります。さらに、乗算を行う毎に次元数が増加するため、事前に大量のシェアを用意せねばなりません。これは非現実的です。したがって、シェア同士の乗算は次元削減を行う必要があります。

BGWプロトコルでは以下の方法によってシェア同士の乗算を行います。

$2t + 1$ 人の参加者は$R(\alpha_i) = P(\alpha_i)Q(\alpha_i)$ を計算する
ただし、$2t+1 \le N$
参加者は$R(\alpha_i)$ をランダムな$t$ 次元多項式でシャミア秘密分散させてシェア$[R(\alpha_i)]$ を作り、それぞれ他の参加者に送信する
$[R(\alpha_1)],...,[R(\alpha_{2t+1})]$ の状態になる
各参加者は$[ab]=[R(0)]=\sum_{i=1}^{2t+1}\lambda_i [R(\alpha_i)]$ を計算する
ただし、$\lambda_i = \prod_{j = 1, j \ne i}^{2t + 1} \frac{\alpha_i}{\alpha_j - \alpha_i}$

重要な点は、ラグランジュ補間公式から導出される以下の式を用いる点です。

$$ R(0) = \sum_{i = 1}^{2t+1}\lambda_i R(\alpha_i) $$

詳細な説明は省きますが、ラグランジュ係数$\lambda_i$ はシェアの$x$ 座標である$\alpha_i$ のみから計算できます。したがって、各参加者は手元で定数倍とシェア同士の加算を行うことで、$t$ 次元多項式によるシェア$[R(0)]$ を保持することができます。

以上の方法により、シェア同士の乗算結果のシェアを$2t$ 次元から$t$ 次元へ落とすことができました。ただし、$R(0)$ の値が正しいかどうかを確認するために$2t + 1 \le N$ を満たす必要があります。これは、参加者のうち半分未満の不正者を許容するプロトコルであると言えます。

まとめ

以上で、BGWプロトコルによる加算と乗算の実現方法を解説しました。

この記事のまとめは以下となっています。

BGWプロトコルは、シャミア秘密分散法をベースにしたMPCのプロトコル
Ben-Or, Goldwasser, Wigderson によって1988年に提案された
値を秘密にしたまま加算と乗算を実現できる
プロトコルから逸脱しない半分未満の不正者に耐性がある

参考文献

A Pragmatic Introduction to Secure Multi-Party Computation

【動画】Secure Multi Party Computation part 1- The BGW Protocol - Gilad Asharov

https://www.jaist.ac.jp/~fujisaki/2020/I486S-2020-0519.pdf

暗号プロトコル理論

プレゼンテーション1.pptx