ハッシュ関数
hash function
任意長のメッセージを入力すると、メッセージを代表する固定長の値を出力する関数
同じハッシュ関数に同じメッセージが入力された時、同じハッシュ値が出力されなければならない
入力値が大きくても、高速でハッシュ値を計算できることが求められる
理想的な振る舞い
nビットのハッシュ値を出力するとする
メッセージが入力されると、それがリストに記録されていなければ、コインをn回降るような動作をする
コインを振って表が出れば0、裏が出れば1としてn回振った結果を連結して出力
リストに記録されていなければ、該当レコードから以前出力した値を調べて、それを出力する
しかし、このような理想的なハッシュ関数を具体化したものは見つかっていない
ハッシュ関数の標準的な安全性
異なる2つのデータのハッシュ値が同じになった場合、これを「ハッシュの衝突(hash colision)」という
第2原像計算困難性を破ること（第2原像性を求めること）と衝突困難性を破ること（任意の衝突ペアを見つけること）を比較した時、攻撃者にとっては後者の方がやりやすい ハッシュ値が指定されている状況よりも、任意のハッシュ値でよい状況の方が条件は厳しくないため
そのため、通常は衝突困難性の方が安全性が高いように設計される
ある$ nビットハッシュ関数（ビットのハッシュ値を返すハッシュ関数）のハッシュ値が与えられた時、そのハッシュ値となるデータを見つける試行回数のオーダーは$ 2^nになる
$ 2^n回の試行で同じハッシュ値となるデータを見つける確率が十分高い
したがって、このハッシュ関数のセキュリティビットは$ n
誕生日のパラドックスにより、同じアルゴリズムでも衝突困難性は、弱衝突耐性または原像計算困難性よりもビットセキュリティが小さく、あるハッシュ関数への衝突攻撃でまず初めに破られるのは比較的突破が簡単な強衝突耐性