Fiat-Shamirヒューリスティック
Fiat-Shamirヒューリスティックは、honest verifierかつpublic-coin(英語版)な対話証明プロトコルをハッシュ関数を用いる事で証明文作成プロトコルや電子署名方式に変換する方法。
対話証明プロトコルから証明文作成プロトコルを作成する方法は以下の通り:
対話証明プロトコルにおける、verifierからの送信メッセージ(チャレンジ)の代わりに、その時点までのverifierのviewのハッシュ値を用いる。証明プロトコル終了時点における、verifierのviewと送信したハッシュ値の組の列が証明文である。
より厳密には、対話証明プロトコル ( P ( w ) , V ) ( x ) {\displaystyle (P(w),V)(x)} から、作られた証明文作成プロトコルは以下の通り。
Set v ← x {\displaystyle v\gets x}
While(1){ Set c ← H ( v ) {\displaystyle c\gets H(v)} r ← {\displaystyle r\gets } (cを送信した時の P ( x , w ) {\displaystyle P(x,w)} のレスポンス) If( r = e n d {\displaystyle r=\mathbf {end} } ) break; else v ← v ∣∣ ( c , r ) {\displaystyle v\gets v\mid \mid (c,r)}
}
Return v
こうして作成された証明文vが正当なものであるかどうかを検証するには、まずverifierのviewのハッシュ値からチャレンジを作成し、次に証明プロトコルとしての検証操作をおこなう。