解説

ハッシュ関数の安全性に関わる性質のうち、衝突発見困難性（衝突困難性、collision resistance）は、「同じハッシュ値になる異なる2つのメッセージ（衝突するメッセージの組）を見つけ出すことが計算量的に困難である」という性質です。ハッシュ関数は任意長のデータを固定長のハッシュ値に変換するため、原理的には異なるメッセージが同じハッシュ値になる衝突が存在しますが、それを意図的に見つけることが非常に難しいことが、改ざん検出やディジタル署名の安全性を支えます。選択肢dの「衝突発見困難性とは、ハッシュ値が一致する二つのメッセージの発見に要する計算量が大きいことによる、発見の困難性のことである」が、衝突発見困難性の定義そのものなので正解です。なお、ハッシュ値が与えられたときに元のメッセージを見つけることが困難である性質は「原像計算困難性（一方向性）」、あるメッセージと同じハッシュ値になる別のメッセージを見つけることが困難である性質は「第2原像計算困難性」と呼ばれ、衝突発見困難性とは区別されます。計算量に関する選択肢（256の2乗、2の256乗）は、性質の「定義」ではなく具体的な数値であり、定義を問う本問では適切ではありません。

なぜ他の選択肢は違うのか

選択肢 ア

「SHA-256の衝突発見困難性を示す、ハッシュ値が一致する二つのメッセージの発見に要する最大の計算量は、256の2乗である」は誤りです。衝突発見困難性は性質の定義として問われており、また誕生日攻撃を考えると衝突発見の計算量の目安は2の128乗程度で、256の2乗という値も正しくありません。衝突発見困難性は性質の定義として問われており、誕生日攻撃を考えると衝突発見の計算量の目安は2の128乗程度で、256の2乗という具体的な値も正しくありません。

選択肢 イ

「SHA-256の衝突発見困難性を示す、ハッシュ値の元のメッセージの発見に要する最大の計算量は、2の256乗である」は誤りです。これは衝突発見困難性ではなく、ハッシュ値から元のメッセージを求める原像計算困難性に関する記述に近く、性質の取り違えがあります。衝突発見困難性の定義としては不適切です。これは衝突発見困難性ではなく、ハッシュ値から元のメッセージを求める原像計算困難性に関する記述に近く、問われている衝突発見困難性とは性質を取り違えています。

選択肢 ウ

「衝突発見困難性とは、ハッシュ値が与えられたときに、元のメッセージの発見に要する計算量が大きいことによる、発見の困難性のことである」は誤りです。これは原像計算困難性（一方向性）の定義であり、同じハッシュ値になる2つのメッセージを見つける困難性を指す衝突発見困難性とは異なる性質を述べています。これはハッシュ値から元のメッセージを求めにくいという原像計算困難性（一方向性）の定義であり、同じハッシュ値になる2つのメッセージを見つける困難性とは別の性質です。

解くときのポイント

ハッシュ関数の3性質：原像計算困難性（ハッシュ値から元を求めにくい＝一方向性）、第2原像計算困難性（あるメッセージと同じハッシュになる別を見つけにくい）、衝突発見困難性（同じハッシュになる2つを見つけにくい）。定義の取り違えに注意。