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

摘要

本稿では，ハッシュ関数あるいはハッシュ関数族の原像計算困難性，第二原像計算困難性，ユニバーサルー方向性の関係について論じる.最初に原像計算困難性を満たす任意のハッシュ関数を用いて第二原像計算困難性を満たすハッシュ関数を構成する方法を示す.ただし，この方法ではRompelによる任意の一方向関数を利用したユニバーサルー方向ハッシュ関数族の構成を利用するため，効率は良くない.次に，ハッシュ関数族の第二原像計算困難性に関して，RogawayとShrimptonにより与えられたSec，eSec，aSecと呼ばれる性質について，Secを満たすハッシュ関数族を用いてeSecあるいはaSecを満たすハッシュ関数族を構成する方法について論じる.なお，eSecはNaorとYungによるユニバーサルー方向性の定義，SecはSimonによるユニバーサルー方向性の定義に相当する.%This article discusses relationships between preimage resistance, second-preimage resistance and universal one-wayness of a hash function or a hash function family. First, a method is presented to construct a second-preimage-resistant hash function from any preimage-resistant hash function. Actually, it is not efficient since it uses Rompel's method to construct a universal one-way hash function family from any one-way function. Second, three kinds of second-preimage resistance of a hash function family called Sec, eSec and aSec are discussed. They were formalized by Rogaway and Shrimpton. Some methods are presented to construct an eSec or aSec hash function family from a Sec hash function family. eSec is universal one-wayness given by Naor and Yung, and Sec is universal one-wayness given by Simon.