Question

What is birthday paradox?Explain with it an example.what is the probability of finding a collision for an ideal 60 bit hash function?what is the main reason for this probability?

Answer 1

Birthday paradox :

In probability theory, birthday paradox concerns the probability that, in a set of n randomly chosen people, some pair of them will have the same birthday. By the pigeonhole principle, the probability reaches 100% when the number of people reaches 367.

Example:

How many people must be there in a room to make the probability 100% that at-least two people in the room have same birthday?
Answer: 367

Reason: since there are 366 possible birthdays, including February 29

Using the Birthday Paradox formula simply tells you at what point you need to start worrying about a collision happening. This is at around Sqrt[n] where n is the total number of possible hash values. In this case n = 2^60 so the Birthday Paradox formula tells you that as long as the number of keys is significantly less than Sqrt[n] = Sqrt[2^60] = 2^30 ( or approximately 4 billion), you don't need to worry about collisions. The higher the n, the more accurate this estimation. In fact the probability p(k) that a collision will occur with k keys approaches a step function as n gets larger, where the step occurs at k=Sqrt[n]

In mathematics, probability theory often goes against what feels “right” or “natural”, it can even seem illogical until proven true, and it doesn’t get much more counter-intuitive than the birthday paradox.