Provably Secure Double-Block-Length Hash Functions in a Black-Box Model

摘要

In CRYPTO'89, Merkle presented three double-block-length hash functions based on DES. They are optimally collision resistant in a black-box model, that is, the time complexity of any collision-finding algorithm for them is Ω(2~(l/2)) if DES is a random block cipher, where l is the output length. Their drawback is that their rates are low. In this article, new double-block-length hash functions with higher rates are presented which are also optimally collision resistant in the black-box model. They are composed of block ciphers whose key length is twice larger than their block length.