マルチパーティプロトコル
マルチパーティプロトコルとは、複数の参加者がそれぞれ秘密情報を持つとき、秘密情報を他の人に漏らさず、秘密から計算できる値を計算する技術である。
前提知識
シャミアの秘密分散を前提知識としているが、本記事では解説しないものとする。
手順
- 秘密を持つ参加者が、シャミアの秘密分散を用いて秘密を分散させる。（この秘密を入力値シェアと呼ぶ）
- 各参加者が協力して、入力値シェアをもとに出力値シェアを計算し、公開する。
- 各参加者が公開された出力値シェアと、シャミアの秘密分散の復元を使って、秘密情報の和を計算する。
具体例
$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$の和である。
参考
足立智子, and 光野繁治. "RSA 分散復号 (代数系アルゴリズムと言語および計算理論)." (2009).
Shamir, Adi. "How to share a secret." Communications of the ACM 22.11 (1979): 612-613.
