4
$\begingroup$

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.

$\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$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.