検証可能秘密分散法
一般的に使用されるシンプルなVSSの例は、Paul Feldmanによるプロトコルである。これは、Shamirの秘密分散法に準同型性を持つ一方向性関数を組み合わせた方式である。この方式は、元のShamir法とは異なり計算量理論的な安全性しか持たない。つまり、計算能力が制限された攻撃者に対してのみ安全である。方式のアイディアは以下に示すとおりである。この方式では、g が公表されるため、ディーラーの秘密sについての情報を漏らしてしまうことに注意。
まず、素数位数 p {\displaystyle p} の巡回群 G {\displaystyle \mathbb {G} } と、 G {\displaystyle \mathbb {G} } の生成元 g {\displaystyle g} がシステムパラメーターとして公開される。ただし、グループ G {\displaystyle \mathbb {G} } での離散対数の計算が困難でなければならない。(典型的には、 q − 1 {\displaystyle q-1} が p {\displaystyle p} で割り切れるような素数 q {\displaystyle q} を選び、 Z q ∗ {\displaystyle \mathbb {Z} _{q}^{*}} の部分群を G {\displaystyle \mathbb {G} } として用いる。)
次にディーラーは、P(0)=s を満たす Z p {\displaystyle \mathbb {Z} _{p}} 上のランダムなt次多項式 P を選ぶ。ただし、s は分散したい秘密情報である。