マルチパーティプロトコル

マルチパーティプロトコルとは、複数の参加者がそれぞれ秘密情報を持つとき、秘密情報を他の人に漏らさず、秘密から計算できる値を計算する技術である。

前提知識

シャミアの秘密分散を前提知識としているが、本記事では解説しないものとする。

手順

1. 秘密を持つ参加者が、シャミアの秘密分散を用いて秘密を分散させる。（この秘密を入力値シェアと呼ぶ）
2. 各参加者が協力して、入力値シェアをもとに出力値シェアを計算し、公開する。
3. 各参加者が公開された出力値シェアと、シャミアの秘密分散の復元を使って、秘密情報の和を計算する。

具体例

$N$人の参加者がそれぞれの秘密情報$s_i$を漏らさず、秘密情報の和$s = s_1 + s_2 + s_3 + ... + s_N$を求める手順について、以下に述べる。

1. 準備

参加者間で秘密情報の和より大きい素数$p$決めて共有する。

2. 入力シェアの計算

すべての参加者がそれぞれ以下の操作を行う。参加者の番号を$i$番目として説明する。

a. 多項式の決定

$f_i(0) = s$を満たす多項式$f_i$を作成する。

具体的には$a_i$ ~ $a_N$をランダムに選び、次のように定義する。
$$\displaystyle f_i(x) = s + a_1x + a_2x^2 + ... + a_{N-1}x^{N-1} + a_Nx^N$$

b. シェアの計算

他の参加者に対して、それぞれ$v_{ij} = f_i(j)$を計算し、暗号化した状態で送る。（$j$は送る相手の番号）

3. 出力シェアの計算

すべての参加者が以下の操作を行う。参加者の番号を$j$番目として説明する。

次のように出力シェア$v_{j}$を計算し公開する。
$$v_{j} = v_{1j} + v_{2j} + ... + v_{(N-1) j} + v_{Nj} \pmod p$$

4. 復元

$f(j) = v_{j}$ を満たす $t–l$ 多項式関数$f$を計算する。

これは$v_1$ ~ $v_N$を用いて、シャミアの秘密分散の復元と同じように計算できる。

$s = f(0)$が秘密情報$s_1$ ~ $s_N$の和である。

参考

1. 足立智子, and 光野繁治. "RSA 分散復号 (代数系アルゴリズムと言語および計算理論)." (2009).

2. Shamir, Adi. "How to share a secret." Communications of the ACM 22.11 (1979): 612-613.