Math behind perfect hash

Question

I am reading material on cryptographic hash functions and it says

"Collision resistant property : for a hash of length L, a perfect hash would take $2^{L/2}$ attempts."

Can someone explain why?

Thanks you

Answer 1

If an attacker repeatedly generated hash values at random, the collision question is "how many attempts would it take to generate a value that had been seen before"? This is an example of the generalized birthday problem: If you repeatedly sample items at random with replacement from a set of $d$ items, how large must $n$ be before there is a reasonable chance of seeing an item twice? The answer is $n$ is proportional to $\sqrt d$.

Application to perfect hashing: The length $L$ of a hash is the number of bits it outputs. A perfect hash would return $2^L$ possible values, so by the birthday problem it would take on the order of $\sqrt{2^L}=2^{L/2}$ attempts to generate a collision.