Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I recently got a question that I’ld like to share here, since answers might be useful (or at least interesting) for people diving into Merkle-Damgård hash constructions for the first time.
We know that the Merkle-Damgård hash function is based on a fixed size $\{0,1\}^{m+t} \rightarrow \{0,1\}^m$ compression function.
Why can an arbitrary compression function mapping $\{0,1\}^{m+2^m} \rightarrow \{0,1\}^m$ not seriously be considered collision resistant?
There are two cases. In the first case, $m$ is very small, and in such a case you can find collisions by the birthday paradox. In the second case, $m$ is not very small, and $2^m$ is too large to be considered feasible. This argument is obvious in the concrete setting (consider $m=64$; this is ridiculously small and collisions can be found in just $2^{32}$ time, but a message of $2^{64}$ size is not feasible).
Asymptotically, the same argument can be made. In order for the function to be collision resistant, you must have $m=\omega(\log n)$, where $n$ is the security parameter. This is necessary since otherwise $\sqrt{2^m} = \sqrt{n}$ which is very small (in particular, it's polynomial). Otherwise, just to be concrete, consider $m=\log n\log\log n$. In this case $2^m = 2^{\log n\log\log n} = n^{\log n}$, which is not polynomial. However, this means that it's not possible to run the function with an input of length $2^m$.
