Birthday paradox

The birthday paradox states that if there are 23 people in a room then there is a chance of more than 50% that at least two of them will have the same birthday. This means that in a typically-sized school class, where the 'paradox' is often cited, an even higher probability often applies. For 60 or more people, the probability is already greater than 99%. This is not a paradox in the sense of leading to a logical contradiction; it is a paradox in the sense that it is a mathematical truth that contradicts common intuition. Most people estimate that the chance is much lower than 50:50. Calculating this probability (and related ones) is the birthday problem. The mathematics behind it has been used to devise a well-known cryptographic attack named the birthday attack.

Applications

The birthday paradox in its more generic sense applies to hash functions: the number of N-bit hashes that can be generated before probably getting a collision is not 2N (this is the probability that a specific hash gets repeated), but rather only 2N/2 (this is the probability that any 2 generated hash values are the same). This is exploited by birthday attacks on cryptographic hash functions.

Related Topics:
Hash function - Bit - Birthday attack - Cryptographic hash function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The theory behind the birthday problem was used in under the name of capture-recapture statistics to estimate the size of fish population in lakes.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~