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

摘要

The indifferentiability is an important concept in order to discuss the provable security of hash functions. NIST (National Institute of Standards and Technology) has opened a public competition referred to as SHA-3 project to develop new cryptographic hash functions. Though many security properties such as preimage resistance, second preimage resistance and collision resistance have been discussed as the requirements of hash functions, their relationships with the above "concept is not recognised explicitly.rnIn this talk, we will survey recent progress on theoretical and practical researches on hash function, and will explain 1) the necessity of the Indifferentiability theory for the design methodology of hash functions, and 2) the above security requirements can be derived from this theory.%ハッシュ関数の証明可能安全性を議論するとき，理論的には強識別不可能性が重要である．一方，米国標準技術局（NIST）が2012年に次世代ハッシュ関数（SHA-3）の制定を目指して，SHA-3Projectを進めている．そこでは，ハッシュ関数がみたすべき安全性要件として衝突耐性（原像攻撃，第二原像攻撃，衝突攻撃に要する計算量の下限値など）を規定しており，強識別不可能性との関連は陽に記述されていない．本稿では，ハッシュ関数の理論研究と攻撃法に関わる研究動向を調査して，1）ハッシュ関数設計で強識別不可能性を議論することの必然性，2）強識別不可能性から上記安全要件の計算量の導出可能性などについて論じる．