I am not able to understand why if we consider a regular hash function, it is possible to say that we are partitioning the starting set and then apply the the birthday paradox/problem. Can anyone explain?


Consider the classical birthday problem, where in a group (say, of students in a course) we want to know how (im)probable it is that there are at least two students with their birthday on the same day. A mathematical analysis tells that, under the assumption that the birthday is a uniform random variable (a fair approximation), and with only two inputs: the number $n$ of persons in the group, and the number $k$ of possible birthdays (about 365).

When selecting a partition of that group (say, for a lab class with limited capacity), that mathematical analysis will apply to the subgroup with $n'\ll n$, or not, depending on how the selection is made. If that's from a list sorted by birthday and split in intervals, the analysis can fail miserably. However, if the partition is random, or made with no clue about the birthdays (say from a list initially sorted alphabetically not showing the birthday), the analysis stands.

We can model a hash function as a (uniformly selected) random function from its input/starting set (perhaps, the infinite set of all bitstrings $\{0,1\}^*$ or finite subset of that) to its output set of $b$-bit bitstrings $\{0,1\}^b$ (with $k=2^b$ elements). When partitioning the starting set, if the selection is random, or made with no clue about the hash value of an element selected, then the mathematical analysis of the birthday problem applies (the basics are in this answer).

For a given hash function, it is easy to build a partition of $\{0,1\}^*$ such that this analysis fails, with collisions either much more or much less likely than predicted. To avoid this, we often use hash functions with internal parameter(s) (often called Initialization Vector) and a proof/argument that an adversary ignoring the IV would be unable to build a partition defeating the analysis better than by chance. We then pick the IV as a nothing-up-my-sleeves number, and can be confident that the mathematical analysis applies to any selection method making no reference to the IV (such as: the set of bitstrings that are the binary representation of the square of integers less than a billion).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.