Fiat-Shamirヒューリスティック

Fiat-Shamirヒューリスティックは、honest verifierかつpublic-coin（英語版）な対話証明プロトコルをハッシュ関数を用いる事で証明文作成プロトコルや電子署名方式に変換する方法。

対話証明プロトコルから証明文作成プロトコルを作成する方法は以下の通り:

対話証明プロトコルにおける、verifierからの送信メッセージ(チャレンジ)の代わりに、その時点までのverifierのviewのハッシュ値を用いる。証明プロトコル終了時点における、verifierのviewと送信したハッシュ値の組の列が証明文である。

より厳密には、対話証明プロトコル $(P(w),V)(x)$ から、作られた証明文作成プロトコルは以下の通り。

Set

v\gets x

While(1){

Set

c\gets H(v)

r\gets

(cを送信した時の

P(x,w)

のレスポンス)

If(

r=\mathbf {end}

) break;

else

v\gets v\mid \mid (c,r)

}

Return v

こうして作成された証明文vが正当なものであるかどうかを検証するには、まずverifierのviewのハッシュ値からチャレンジを作成し、次に証明プロトコルとしての検証操作をおこなう。証明プロトコルとしての検証を通れば証明文は正当であるとみなす。

対話証明プロトコルから署名方式を作成する方法もほぼ同様である。チャレンジとして、viewのハッシュ値の代わりに、viewと署名したいメッセージとのコンカチネーションのハッシュ値を用いる。証明プロトコル終了時点における、verifierのviewとハッシュ値の組の列が署名文である。

より厳密には、対話証明プロトコル $(P(w),V)(x)$ から作られた署名アルゴリズムは以下の通り。

Input 署名したい文章 M

Set

v\gets x