検証可能秘密分散法

暗号理論において、検証可能秘密分散法とは、シェアが整合性を持っていることを各プレーヤーが検証できる秘密分散法である。より正式には、検証可能秘密分散法は、ディーラーが悪意を持っていたとしても、復元するプレーヤーの組によらず、必ず同じ秘密情報が復元されることを保証する。 （普通の秘密分散法では、ディーラーは正直であると想定される。）検証可能秘密分散（VSS）の概念は、1985年にBenny Chor、 Shafi Goldwasser 、 Silvio Micali 、およびBaruchAwerbuchによって最初に導入された。

検証可能秘密分散法は、分散フェーズと再構築フェーズの2つのフェーズで構成される。

分散フェーズ：秘密情報を持つディーラーが、秘密情報からシェアや検証用の情報を作り分散するフェーズ。ディーラーが、シェアを保持する各パーティに一方的にシェアを送るだけでなく、パーティ間で通信を行うなど、複数ラウンドの場合もある。ディーラーやパーティー間の通信として、安全な秘密通信路や、全員に対してのブロードキャスト通信路が用いられる。

復元フェーズ：複数のプレーヤーが分散フェーズで得た情報を元に、秘密情報を復元するフェーズ。

検証可能な秘密分散は、安全なマルチパーティ計算にとって重要な要素技術である。マルチパーティ計算は通常、各入力値を秘密分散法でパーティ間に分散し、その後、分散したまま入力値の演算を行う。アクティブな攻撃者（つまり、パーティを乗っ取ってプロトコルから逸脱した動作をさせる攻撃者）の存在を想定する場合、パーティがプロトコルを放棄するかもしれず、その場合にも残りのパーティでプロトコルを継続できるように、秘密分散方式が検証可能である必要がある。

フェルドマンの方式

一般的に使用されるシンプルなVSSの例は、Paul Feldmanによるプロトコルである。これは、Shamirの秘密分散法に準同型性を持つ一方向性関数を組み合わせた方式である。この方式は、元のShamir法とは異なり計算量理論的な安全性しか持たない。つまり、計算能力が制限された攻撃者に対してのみ安全である。方式のアイディアは以下に示すとおりである。この方式では、g^s が公表されるため、ディーラーの秘密sについての情報を漏らしてしまうことに注意。

まず、素数位数 $p$ の巡回群 $\mathbb {G}$ と、$\mathbb {G}$ の生成元 $g$ がシステムパラメーターとして公開される。ただし、グループ $\mathbb {G}$ での離散対数の計算が困難でなければならない。（典型的には、$q-1$ が $p$ で割り切れるような素数 $q$ を選び、$\mathbb {Z} _{q}^{*}$ の部分群を $\mathbb {G}$ として用いる。）

次にディーラーは、P(0)=s を満たす $\mathbb {Z} _{p}$上のランダムなt次多項式 P を選ぶ。ただし、s は分散したい秘密情報である。 n 人のパーティはそれぞれ値 P(1), ..., P(n) modulo p を受け取る。t+1 人のパーティは、modulo p における多項式補間法を使用して秘密 s を復元することができるが、t 人以下のパーティは、秘密を復元することができない。（実際、この時点では、高々t 人のパーティの集合には、s に関して全く情報を与えない。）

ここまでは、Shamirの秘密分散法と全く同じである。シェアを検証可能にするには、ディーラーは多項式 P(x) の各係数のコミットメントを計算して公開する。もし P(x) = s + a₁ x + ... + a_t x^t であるならば、コミットメントは次のとおりである。

• c₀ = g^s,
• c₁ = g^a₁,
• ...
• c_t = g^a_t.

これらが与えられれば、どのパーティも自分のシェアを検証することができる。たとえば、 v =P(i) modulo p であることをチェックするためには、パーティi は以下でそれを確認できる。

$g^{v}=c_{0}c_{1}^{i}c_{2}^{i^{2}}\cdots c_{t}^{i^{t}}=\prod _{j=0}^{t}c_{j}^{i^{j}}=\prod _{j=0}^{t}g^{a_{j}i^{j}}=g^{\sum _{j=0}^{t}a_{j}i^{j}}=g^{P(i)}$ 。

ベナローの方式

ベナロー（Benaloh）の検証可能秘密分散法は、Shamirの秘密分散法に，カットアンドチューズテクニックを組み合わせた方式であり、情報理論的な安全性を持つ。

VSSにおいてn 個のシェアがパーティに配布されているとき、各パーティは、すべてのシェアが t-consistentであること（つまり、n個のうちのどの t 個のシェアを用いても、同じ秘密の値が復元されること）を検証できなければいけない。（秘密の情報をあかすことなく。）

シャミアの秘密分散法では、シェアs₁ 、s₂ , ... , s_nは、点 (1, s₁), (2, s₂ ), ..., (n, s_n) が高々d = t-1 次の多項式に乗っているときに、t-consistentである。

ベナローのVSSの分散フェーズでは、次の5ステップで、ディーラーが正しくシェアを生成したことを検証する。

1. ディーラーは高々 t-1 次の多項式 P(x) を選択し、シェア P(i) を生成して各パーティに送る（シャミアの秘密分散法に従って）。
2. ディーラーは十分大きな数を k とし、k 個の t-1次以下の多項式 $P_{1}(x),\ldots ,P_{k}(x)$ を生成し、$P_{1}(i)...,P_{k}(i)$ をパーティ i に送る。
3. パーティは m(<k) 個の多項式をランダムに選ぶ。
4. ディーラーは、m 個の選択された多項式$P_{i_{1}}(x),\ldots ,P_{i_{m}}(x)$を公開する。また、$P(x)$と残りの k-m個の多項式の和${\tilde {P}}(x)=P(x)+\textstyle \sum _{j={m+1}}^{k}P_{i_{j}}(x)$を計算して ${\tilde {P}}(x)$${\tilde {P}}(x)=P(x)+\textstyle \sum _{j={m+1}}^{k}P_{i_{j}}(x)$を公開する。さらに ${\tilde {P}}(i)$ ${\tilde {P}}(i)$${\tilde {P}}(i)$${\tilde {P}}(i)$をパーティ i に送る。
5. 各パーティは、ステップ4で公開されたすべての多項式の次数が t-1 以下であること、および、自分の持つ $P(i),P_{i_{m+1}}(i),\ldots ,P_{i_{k}}(i)$の和が、${\tilde {P}}(i)$と等しいかチェックする。

不正なディーラーの不正な動作を高い確率で検出するには、上記のステップ2～5を何度か繰り返す。

直感的な証明：不正なディーラーが、ステップ１で t-consistence でないシェア $(P(1),\ldots ,P(n))$をパーティに渡したとしよう。つまり、次数が t-1 より大きい多項式P(x) を使ってシェアを生成したとする。

ステップ2では、k個の多項式 $P_{i}(x)$ を生成するが、そのうちのいくつかはステップ4で公開しなければならない。もし、k個の $P_{i}(x)$ の中に次数が t-1 よりも大きいものがあった場合、ステップ5で不正が検出される（一度の繰り返しでは、不正な$P_{i}(x)$ は公開しないで済むかもしれないが、何度か繰り返すと、高い確率で不正は検出される。）もし、全ての $P_{i}(x)$ が t-1次多項式であり、${\tilde {P}}(x)$も t-1 次数であれば（そうでなければ、ステップ5で不正が検出される）、${\tilde {P}}(x)-\textstyle \sum _{j={m+1}}^{k}P_{j}(x)$ も t-1 次以下であるから、ステップ5において ${\tilde {P}}(i)=P(i)+\textstyle \sum _{j={m+1}}^{k}P_{j}(i)$ が成り立たない i が存在するはずであり、不正が検出される。(もしすべての i について ${\tilde {P}}(i)=P(i)+\textstyle \sum _{j={m+1}}^{k}P_{j}(i)$ が成り立つならば、つまり、 $P(i)={\tilde {P}}(i)-\textstyle \sum _{j={m+1}}^{k}P_{j}(i)$ が成り立つならば、シェア P(i) は t-1 次の多項式の上に乗っていることになり、不正をしていないことになる。）

検証可能な秘密分散のラウンド数の最適性

VSSプロトコルのラウンド複雑さ(round complexity)は、分散フェーズでの通信ラウンドの数として定義される。（復元フェーズは常に1回のラウンドである。）情報理論的な安全性を持つVSSに対しては、ラウンド数には下限が知られており、しきい値 t が2以上の場合、プレーヤーの数 n に関係なく、1ラウンドVSSを作ることができない。VSSのラウンド数の下限は次の表のとおりである。

ラウンド数	パラメータ
1	t = 1、n> 4
2	n> 4t
3	n> 3t

関連項目

• 秘密分散
• 安全なマルチパーティ計算

参考文献

• B. Chor, S. Goldwasser, S. Micali and B. Awerbuch, Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults, FOCS85, pp. 383-395. doi:10.1109/SFCS.1985.64
• P. Feldman, A practical scheme for non-interactive verifiable secret sharing. IEEE Symposium on Foundations of Computer Science, pages 427--437. IEEE, 1987. doi:10.1109/SFCS.1987.4
• T. Rabin and M. Ben-Or, Verifiable secret sharing and multiparty protocols with honest majority. In Proceedings of the Twenty-First Annual ACM Symposium on theory of Computing (Seattle, Washington, United States, May 14 - 17, 1989). doi:10.1145/73007.73014
• Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin, The Round Complexity of Verifiable Secret Sharing and Secure Multicast. In Proceedings of the thirty-third annual ACM symposium on Theory of computing ( Hersonissos, Greece, Pages: 580 - 589, 2001 )
• Matthias Fitzi, Juan Garay, Shyamnath Gollakota, C. Pandu Rangan, and Kannan Srinathan, Round-Optimal and Efficient Verifiable Secret Sharing. Theory of Cryptography, Third Theory of Cryptography Conference, TCC 2006, ( New York, NY, USA, March 4-7, 2006 )
• Oded Goldreich, Secure multi-party computation
• Josh Cohen Benaloh, Secret Sharing Homomorphisms: Keeping Shares of a Secret. Proceedings on Advances in cryptology---CRYPTO '86. pp. 251-260, 1987