ハッシュ関数の安全性に関する考察

摘要

本稿では，ハッシュ関数あるいはハッシュ関数族の原像計算困難性，第二原像計算困難性，ユニバーサルー方向性の関係について論じる．最初に原像計算困難性を満たす任意のハッシュ関数を用いて第二原像計算困難性を満たすハッシュ関数を構成する方法を示す．ただし，この方法ではRompelによる任意の一方向関数を利用したユニバーサル一方向ハッシュ関数族の構成を利用するため，効率は良くない．次に，ハッシュ関数族の第二原像計算困難性に関して，RogawayとShrimptonにより与えられたSec，eSec，aSecと呼ばれる性質について，Secを満たすハッシュ関数族を用いてeSecあるいはaSecを満たすハッシュ関数族を構成する方法について論じる．なお，eSecはNaorとYungによるユニバーサル一方向性の定義，SecはSimonによるユニバーサル一方向性の定義に相当する．