Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Birthday problem
Summary
In probability theory, the birthday problem asks for the probability that, in a set of n randomly chosen people, at least two will share a birthday. The birthday paradox refers to the counterintuitive fact that only 23 people are needed for that probability to exceed 50%.
The birthday paradox is a veridical paradox: it seems wrong at first glance but is, in fact, true. While it may seem surprising that only 23 individuals are required to reach a 50% probability of a shared birthday, this result is made more intuitive by considering that the birthday comparisons will be made between every possible pair of individuals. With 23 individuals, there are 23 × 22/2 = 253 pairs to consider, far more than half the number of days in a year.
Real-world applications for the birthday problem include a cryptographic attack called the birthday attack, which uses this probabilistic model to reduce the complexity of finding a collision for a hash function, as well as calculating the approximate risk of a hash collision existing within the hashes of a given size of population.
The problem is generally attributed to Harold Davenport in about 1927, though he did not publish it at the time. Davenport did not claim to be its discoverer "because he could not believe that it had not been stated earlier". The first publication of a version of the birthday problem was by Richard von Mises in 1939.
From a permutations perspective, let the event A be the probability of finding a group of 23 people without any repeated birthdays. Where the event B is the probability of finding a group of 23 people with at least two people sharing same birthday, P(B) = 1 − P(A). P(A) is the ratio of the total number of birthdays, , without repetitions and order matters (e.g. for a group of 2 people, mm/dd birthday format, one possible outcome is divided by the total number of birthdays with repetition and order matters, , as it is the total space of outcomes from the experiment (e.g. 2 people, one possible outcome is . Therefore and are permutations.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.
Ontological neighbourhood
Related lectures (11)
Hash Tables: Birthday Paradox
Explores hash tables through the Birthday Paradox, collisions, and implementation methods.
Bayes' Theorem: Defective Parts Detection
Explores Bayes' Theorem for defective parts detection, discrete random variables, and distribution functions, with practical examples and exercises.
Cryptographic Security Fundamentals
Covers cryptographic security fundamentals, including collision search algorithms, public-key cryptography, and risks of underestimating collision attacks.
Related publications (11)
Related people (2)
Related concepts (7)
Birthday attack
A birthday attack is a type of cryptographic attack that exploits the mathematics behind the birthday problem in probability theory. This attack can be used to abuse communication between two or more parties. The attack depends on the higher likelihood of collisions found between random attack attempts and a fixed degree of permutations (pigeonholes). With a birthday attack, it is possible to find a collision of a hash function in , with being the classical security.
Cryptographic hash function
A cryptographic hash function (CHF) is a hash algorithm (a map of an arbitrary binary string to a binary string with a fixed size of bits) that has special properties desirable for a cryptographic application: the probability of a particular -bit output result (hash value) for a random input string ("message") is (as for any good hash), so the hash value can be used as a representative of the message; finding an input string that matches a given hash value (a pre-image) is unfeasible, assuming all input str
Collision resistance
In cryptography, collision resistance is a property of cryptographic hash functions: a hash function H is collision-resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b where a ≠ b but H(a) = H(b). The pigeonhole principle means that any hash function with more inputs than outputs will necessarily have such collisions; the harder they are to find, the more cryptographically secure the hash function is.