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.
1 Answer
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.