検証可能秘密分散法
VSSプロトコルのラウンド複雑さ(round complexity)は、分散フェーズでの通信ラウンドの数として定義される。(復元フェーズは常に1回のラウンドである。)情報理論的な安全性を持つVSSに対しては、ラウンド数には下限が知られており、しきい値 t が2以上の場合、プレーヤーの数 n に関係なく、1ラウンドVSSを作ることができない。VSSのラウンド数の下限は次の表のとおりである。
)もし、全ての P i ( x ) {\displaystyle P_{i}(x)} が t-1次多項式であり、 P ~ ( x ) {\displaystyle {\tilde {P}}(x)} も t-1 次数であれば(そうでなければ、ステップ5で不正が検出される)、 P ~ ( x ) − ∑ j = m + 1 k P j ( x ) {\displaystyle {\tilde {P}}(x)-\textstyle \sum _{j={m+1}}^{k}P_{j}(x)} も t-1 次以下であるから、ステップ5において P ~ ( i ) = P ( i ) + ∑ j = m + 1 k P j ( i ) {\displaystyle {\tilde {P}}(i)=P(i)+\textstyle \sum _{j={m+1}}^{k}P_{j}(i)} が成り立たない i が存在するはずであり、不正が検出される。(もしすべての i について P ~ ( i ) = P ( i ) + ∑ j = m + 1 k P j ( i ) {\displaystyle {\tilde {P}}(i)=P(i)+\textstyle \sum _{j={m+1}}^{k}P_{j}(i)} が成り立つならば、つまり、 P ( i ) = P ~ ( i ) − ∑ j = m + 1 k P j ( i ) {\displaystyle P(i)={\tilde {P}}(i)-\textstyle \sum _{j={m+1}}^{k}P_{j}(i)} が成り立つならば、シェア P(i) は t-1 次の多項式の上に乗っていることになり、不正をしていないことになる。)
n 人のパーティはそれぞれ値 P(1), ..., P(n) modulo p を受け取る。t+1 人のパーティは、modulo p における多項式補間法を使用して秘密 s を復元することができるが、t 人以下のパーティは、秘密を復元することができない。(実際、この時点では、高々t 人のパーティの集合には、s に関して全く情報を与えない。)
ここまでは、Shamirの秘密分散法と全く同じである。シェアを検証可能にするには、ディーラーは多項式 P(x) の各係数のコミットメントを計算して公開する。もし P(x) = s + a1 x + ... + at x であるならば、コミットメントは次のとおりである。
c0 = g,
c1 = g,
...
ct = g.
これらが与えられれば、どのパーティも自分のシェアを検証することができる。たとえば、 v =P(i) modulo p であることをチェックするためには、パーティi は以下でそれを確認できる。
g v = c 0 c 1 i c 2 i 2 ⋯ c t i t = ∏ j = 0 t c j i j = ∏ j = 0 t g a j i j = g ∑ j = 0 t a j i j = g P ( i ) {\displaystyle 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)}} 。