I am eager to know that if there is any function that does not suffer birthday problem and how to prove it formally that the function is not suffering the birthday problem.
4
$\begingroup$
$\endgroup$
-
2$\begingroup$ When the birthday bound exceeds the number of atoms in the universe, do you still consider that "suffering from the problem"? For example, a 576-bit hash function $\endgroup$ – Richie Frame Apr 26 '16 at 2:48
4
$\begingroup$
$\endgroup$
If $f:\{0,1\}^m\rightarrow \{0,1\}^n$ with $n\geq m,$ then of course there are, the set of one-to-one functions, but such a function is not a cryptographic hash function, since it lacks the compression property. If $n<m,$ (or more generally if $|X|>|Y|$ for $f:X\rightarrow Y$), collisions will happen.
