検証可能秘密分散法

暗号理論において、検証可能秘密分散法とは、シェアが整合性を持っていることを各プレーヤーが検証できる秘密分散法である。より正式には、検証可能秘密分散法は、ディーラーが悪意を持っていたとしても、復元するプレーヤーの組によらず、必ず同じ秘密情報が復元されることを保証する。 （普通の秘密分散法では、ディーラーは正直であると想定される。）検証可能秘密分散（VSS）の概念は、1985年にBenny Chor、 Shafi Goldwasser 、 Silvio Micali 、およびBaruchAwerbuchによって最初に導入された。
検証可能秘密分散法は、分散フェーズと再構築フェーズの2つのフェーズで構成される。
分散フェーズ：秘密情報を持つディーラーが、秘密情報からシェアや検証用の情報を作り分散するフェーズ。ディーラーが、シェアを保持する各パーティに一方的にシェアを送るだけでなく、パーティ間で通信を行うなど、複数ラウンドの場合もある。ディーラーやパーティー間の通信として、安全な秘密通信路や、全員に対してのブロードキャスト通信路が用いられる。
復元フェーズ：複数のプレーヤーが分散フェーズで得た情報を元に、秘密情報を復元するフェーズ。
検証可能な秘密分散は、安全なマルチパーティ計算にとって重要な要素技術である。マルチパーティ計算は通常、各入力値を秘密分散法でパーティ間に分散し、その後、分散したまま入力値の演算を行う。アクティブな攻撃者（つまり、パーティを乗っ取ってプロトコルから逸脱した動作をさせる攻撃者）の存在を想定する場合、パーティがプロトコルを放棄するかもしれず、その場合にも残りのパーティでプロトコルを継続できるように、秘密分散方式が検証可能である必要がある。
フェルドマンの方式.
一般的に使用されるシンプルなVSSの例は、Paul Feldmanによるプロトコルである。これは、Shamirの秘密分散法に準同型性を持つ一方向性関数を組み合わせた方式である。この方式は、元のShamir法とは異なり計算量理論的な安全性しか持たない。つまり、計算能力が制限された攻撃者に対してのみ安全である。方式のアイディアは以下に示すとおりである。この方式では、"g""s" が公表されるため、ディーラーの秘密"s"についての情報を漏らしてしまうことに注意。
まず、素数位数 formula_1 の巡回群 formula_2 と、formula_3 の生成元 formula_4 がシステムパラメーターとして公開される。ただし、グループ formula_3 での離散対数の計算が困難でなければならない。（典型的には、formula_6 が formula_7 で割り切れるような素数 formula_8 を選び、formula_9 の部分群を formula_10 として用いる。）
次にディーラーは、"P(0)=s" を満たす formula_11上のランダムな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"1 "x" + ... + "a""t" "x""t" であるならば、コミットメントは次のとおりである。
これらが与えられれば、どのパーティも自分のシェアを検証することができる。たとえば、 "v" ="P"(i) modulo "p" であることをチェックするためには、パーティ"i" は以下でそれを確認できる。
formula_12 。
ベナローの方式.
ベナロー（Benaloh）の検証可能秘密分散法は、Shamirの秘密分散法に，カットアンドチューズテクニックを組み合わせた方式であり、情報理論的な安全性を持つ。
VSSにおいて"n" 個のシェアがパーティに配布されているとき、各パーティは、すべてのシェアが t-consistentであること（つまり、n個のうちのどの t 個のシェアを用いても、同じ秘密の値が復元されること）を検証できなければいけない。（秘密の情報をあかすことなく。）
シャミアの秘密分散法では、シェア"s1 、s2 , ... , sn"は、点 "(1, s1), (2, s2 ), ..., (n, sn)" が高々d = t-1 次の多項式に乗っているときに、t-consistentである。
ベナローのVSSの分散フェーズでは、次の5ステップで、ディーラーが正しくシェアを生成したことを検証する。
不正なディーラーの不正な動作を高い確率で検出するには、上記のステップ2～5を何度か繰り返す。
直感的な証明：不正なディーラーが、ステップ１で t-consistence でないシェア formula_26をパーティに渡したとしよう。つまり、次数が t-1 より大きい多項式P(x) を使ってシェアを生成したとする。
ステップ2では、k個の多項式 formula_27 を生成するが、そのうちのいくつかはステップ4で公開しなければならない。もし、k個の formula_28 の中に次数が t-1 よりも大きいものがあった場合、ステップ5で不正が検出される（一度の繰り返しでは、不正なformula_28 は公開しないで済むかもしれないが、何度か繰り返すと、高い確率で不正は検出される。）もし、全ての formula_28 が t-1次多項式であり、formula_31も t-1 次数であれば（そうでなければ、ステップ5で不正が検出される）、formula_32 も t-1 次以下であるから、ステップ5において formula_33 が成り立たない i が存在するはずであり、不正が検出される。(もしすべての i について formula_33 が成り立つならば、つまり、 formula_35 が成り立つならば、シェア P(i) は t-1 次の多項式の上に乗っていることになり、不正をしていないことになる。）
検証可能な秘密分散のラウンド数の最適性.
VSSプロトコルのラウンド複雑さ(round complexity)は、分散フェーズでの通信ラウンドの数として定義される。（復元フェーズは常に1回のラウンドである。）情報理論的な安全性を持つVSSに対しては、ラウンド数には下限が知られており、しきい値 t が2以上の場合、プレーヤーの数 n に関係なく、1ラウンドVSSを作ることができない。VSSのラウンド数の下限は次の表のとおりである。