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

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

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

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

より厳密には、対話証明プロトコルから、作られた証明文作成プロトコルは以下の通り。

Set 
While(1){
Set 
(cを送信した時ののレスポンス)
If() break;
else 
}
Return v

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

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

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

Input 署名したい文章 M
Set 
While(1){
Set 
(cを送信した時ののレスポンス)
If() break;
else 
}
Return v

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

関連項目 
 暗号理論
 ランダム・オラクル
 ゼロ知識証明
 電子署名
 Shnorr署名

暗号技術

ru:Протокол Фиата — Шамира