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

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

前提知識

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

手順

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_{1}x+a_2{x}^2+...+a_{N-1}{x}^{N-1}+a_N{x}^N}$$

b. シェアの計算

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

3. 出力シェアの計算

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

次のように出力シェア$v_j$を計算し公開する。
$$v_j=v_{1j}+v_{2j}+...+v_{(N-1)j}+v_{Nj}(\mathrm{mod}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.