What Is the “Birthday Paradox” and How Does It Relate to Collision Attacks?

The Birthday Paradox is the counter-intuitive probability that in a relatively small group of people, two will share the same birthday. In cryptography, it shows that a collision in an n-bit hash function can be found with a probability of 50% after only 2^(n/2) attempts, not 2^n.

This drastically reduces the computational effort required for a collision attack, making it the theoretical benchmark for the strength of collision resistance.