ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。

選択肢

• アSHA-256の衝突発見困難性を示す，ハッシュ値が一致する二つのメッセージの探索に要する最大の計算量は，256の2乗である。
• イSHA-256の衝突発見困難性を示す，ハッシュ値の元のメッセージの探索に要する最大の計算量は，2の256乗である。
• ウ衝突発見困難性とは，ハッシュ値が与えられたときに，元のメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。
• エ衝突発見困難性とは，ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。

正解と解説

正解：エ 衝突発見困難性とは，ハッシュ値が一致する二つのメッセージの探索に要する計算量の大きさによる，探索の困難性のことである。

衝突発見困難性とは、同じハッシュ値になる2つの異なるメッセージを見つけることが計算量的に困難である性質です。ハッシュ値から元のメッセージを求めにくい性質は原像計算困難性であり、別の性質です。誕生日のパラドックスにより、衝突探索の計算量はハッシュ長の半分程度が目安になります。

選択肢ごとの解説

• ア誤り。計算量の表し方が誤っており、衝突探索は2の128乗程度が目安。
• イ誤り。元のメッセージの探索は原像計算困難性の話で、衝突発見困難性ではない。
• ウ誤り。これは原像計算困難性の定義。
• エ正しい。同じハッシュ値となる2つのメッセージを見つける困難さを指す。

同じ分野の他の問題

• SHA-512/256の説明はどれか。2025年度 春期 午前II 問3
• ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち,適切なものはどれか。2023年度 春期 午前II 問4
• ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち,適切なものはどれか。2021年度 春期 午前II 問3
• ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。2019年度 春期 午前II 問4
• ハッシュ関数の性質の一つである衝突発見困難性に関する記述のうち，適切なものはどれか。2017年度 秋期 午前II 問4