強識別不可能性理論とSHA-3プロジェクト：ハッシュ関数設計のための理論研究と実装研究の現状

摘要

ハッシュ関数の証明可能安全性を議論するとき，理論的には強識別不可能性が重要である．一方，米国標準技術局（NIST）が2012年に次世代ハッシュ関数（SHA-3）の制定を目指して，SHA-3 Projectを進めでいる．そこでは，ハッシュ関数がみたすべき安全性要件として衝突耐性（原像攻撃，第二原像攻撃，衝突攻撃に要する計算量の下限値など）を規定しており，強識別不可能性との関連は陽に記述されていない．本稿では，ハッシュ関数の理論研究と攻撃法に関わる研究動向を調査して，1）ハッシュ関数設計で強識別不可能性を議論することの必然性，2）強識別不可能性から上記安全要件の計算量の導出可能性などについて論じる．