検証可能秘密分散法のソースを表示


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

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

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

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


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

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

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

次にディーラーは、''P(0)=s'' を満たす <math>\mathbb{Z}_p  </math>上のランダムな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''<sub>1</sub> ''x'' + ... + ''a''<sub>''t''</sub> ''x''<sup>''t''</sup> であるならば、コミットメントは次のとおりである。

* ''c''<sub>0</sub> = ''g<sup>s</sup>'',
* ''c''<sub>1</sub> = ''g<sup>a</sup>''<sup><sub>1</sub></sup>,
* ...
* ''c<sub>t</sub>'' = ''g<sup>a<sub>t</sub></sup>''.

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

<math>
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)}
</math> 。

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

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

[[電子割符|シャミアの秘密分散法]]では、シェア''s<sub>1</sub> 、s<sub>2</sub> , ... , s<sub>n</sub>''は、点 ''(1, s<sub>1</sub>), (2, s<sub>2</sub> ), ..., (n, s<sub>n</sub>)'' が高々d = t-1 次の多項式に乗っているときに、t-consistentである。

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

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

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

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

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

== 検証可能な秘密分散のラウンド数の最適性 ==
VSSプロトコルのラウンド複雑さ(round complexity)は、分散フェーズでの通信ラウンドの数として定義される。（復元フェーズは常に1回のラウンドである。）情報理論的な安全性を持つVSSに対しては、ラウンド数には下限が知られており、しきい値 t が2以上の場合、プレーヤーの数 n に関係なく、1ラウンドVSSを作ることができない。VSSのラウンド数の下限は次の表のとおりである。
{| class="wikitable"
!ラウンド数
!パラメータ
|-
|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
[[Category:暗号技術|けんしようかのうひみつふんさんほう]]