Repairable Threshold Scheme - Develop with pleasure!

最近、Schnorrベースの閾値署名スキームFROSTをベースにして、暗号技術だけでt-of-nのマルチシグの設定を動的に調整可能にする提案が行われている。その中で、母数nの数を増やす際に利用されているのが、RTS（Repairable Threshold Scheme）。

RTSは、シャミアの秘密分散法などを使って、複数のパーティでシェアを分散して保持するスキームにおいて、後から参加者のシェアを復元できるようにするスキーム。↑の提案では、既存のシェアの復元ではなく、新しい参加者用に新しいシェアを作るのにRTSを利用することで、母数を増やす。

今回は、↓サーベイ論文に掲載されている内の１つEnrollementスキームについて調べてみた。

https://eprint.iacr.org/2017/1155.pdf

RTS

論文は、ディーラーがいるモデルで書かれており、参加者の母数をn、閾値をtとした場合、ディーラーはシークレット値を含むt-1次の多項式f(x)を生成し、n人の参加者に対して、割り当てられたインデックス ${ID_i}$ で多項式を評価した結果 ${(ID_i, f(ID_i))}$ をシェアとして配布する。

この場合、多項式を知っているディーラーがいればシェアの復元は可能だが、ディーラーが利用できない場合でも、閾値数分の参加者がいればシェアを復元できるようにするのがこのスキームの目標。

※ RTSをt - 1人で実行できると追加のシェアが作成され閾値tを超えるシェアを入手できてしまうため、必ずt人以上で実行しないと再構築できないようなプロトコルになっている必要がある。

※ また、閾値分のシェアが集まれば多項式補間で多項式が復元できシェアを計算できるようになるが、シェアを集める参加者が登場することになり実質ディーラーとなれるので、そういうアプローチではない。

シェアの復元

シェアを復元したい参加者を ${P_r}$ 、復元を支援するt人の参加者を ${P_1, ..., P_t}$ とする。各参加者が保持しているシェアを ${\phi_i = f(ID_i)}$ とした場合、 ${\phi_r = f(ID_r)}$ を求めるのが目標。

ラグランジュ補間公式を利用すると ${f(ID_r)}$ は以下を計算することで入手できる。

${f(ID_r) = \lambda_1(ID_r)\phi_1 + ... + \lambda_t(ID_r)\phi_t}$

ここで、各ラグランジュ係数 ${\lambda_j(ID_r)}$ （1≦ j ≦ t）は、

$\lambda_j(ID_r) = \Pi_{0 \leq m \leq t, (m \neq j)} \frac{ID_r - ID_m}{ID_j - ID_m} = \frac{(ID_r - ID_1) \cdot \cdot \cdot (ID_r - ID_t)}{(ID_j - ID_1)\cdot \cdot \cdot (ID_j - ID_t)}$

であり、各参加者の識別子（ ${ID_1, ..., ID_t}$ ）が分かっていれば計算できる。

Enrollementプロトコルでは以下の手順で、 ${P_r}$ が ${\phi_r}$ の値を計算できるようにする。

t人の各参加者 ${P_i}$ は、 ${\lambda_i(ID_r)\phi_i = \sum_{j=1}^{t}\delta_{i, j}}$ となるようなt個のランダム値 ${\delta_{i, j}}$ （1≦ j ≦t ）を生成する。各参加者は自分のシェアと上記のラグランジュ係数から ${\lambda_i(ID_r)\phi_i}$ を計算できるので、t - 1個の ${\delta_{i, j}}$ をランダムに生成して、最後の値は ${\lambda_i(ID_r)\phi_i - \sum_{j=1}^{t-1}\delta_{i, j}}$ で計算すればいい。
各参加者 ${P_i}$ は、計算した ${\delta_{i, j}}$ を他の支援者 ${P_j}$ に送信する。
各参加者 ${P_j}$ は、 ${\sigma_{j} = \sum_{i=1}^{t}\delta_{i, j}}$ を計算し、 ${\sigma_{j}}$ を新しい参加者 ${P_r}$ に送信する。
${P_r}$ は、 ${\phi_r = \sum_{j=1}^{t}\sigma_j}$ を計算し、シェア ${\phi_r}$ を入手する。