ゼロ知識証明基礎3

ゼロ知識証明2では、攻撃の成功確率1/2で証明することができ、繰り返すことで0に近づけることが可能になる方法を説明した。これについては、繰り返しを減らす方法やさらになくす方法も提案されている。

減らすには、検証者が$b$を0以上$q$未満の値からランダムに選択して証明者に伝え、証明者は$c=r+bx \bmod q$を計算して検証者に返答する方法がある。このようにおいても、$g^c=ay^b$は成り立つ。これは1度で、攻撃の成功確率$1/q$で証明することができる。

なくす方法では、ハッシュ関数を使う。$p$, $q$, $g$, $y$, $a$を連結したものから証明者はハッシュを計算。さらにハッシュ値を$b$として、証明者は$c=r+bx \bmod q$を計算して、$a$, $b$, $c$を検証者に伝える。検証者は、同様の検証を行う。これにより、やはり、攻撃の成功確率$1/q$で証明することができる。