Fiat-Shamirヒューリスティック
証明プロトコルとしての検証を通れば証明文は正当であるとみなす。
対話証明プロトコルから署名方式を作成する方法もほぼ同様である。 チャレンジとして、viewのハッシュ値の代わりに、viewと署名したいメッセージとのコンカチネーションのハッシュ値を用いる。 証明プロトコル終了時点における、verifierのviewとハッシュ値の組の列が署名文である。
より厳密には、対話証明プロトコル ( P ( w ) , V ) ( x ) {\displaystyle (P(w),V)(x)} から作られた署名アルゴリズムは以下の通り。
Input 署名したい文章 M
Set v ← x {\displaystyle v\gets x}
While(1){ Set c ← H ( v , M ) {\displaystyle c\gets H(v,M)} 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と署名したいメッセージとのコンカチネーションのハッシュ値からチャレンジを作成し、次に証明プロトコルとしての検証操作をおこなう。証明プロトコルとしての検証を通れば署名文は正当であるとみなす。