The following is an excerpt from A Generalized Birthday Problem - David Wagner:

One of the best-known combinatorial tools in cryptology is the birthday problem:
Problem 1. Given two lists $L_1, \space L_2$ of elements drawn uniformly and independently at random from $\{0, 1\}^n$, find $x_1 \in L_1$ and $x_2 \in L_2$ such that $x_1 \oplus x_2 = 0$.

It's not so intuitive for me to understand. In my understanding, the birthday problem is about the probability that at least 2 people in a room have the same birthday. How does the birthday problem transfers to this? Please give me some hints.


$x_1 \oplus x_2 = 0$ is equivalent to $x_1=x_2$ (because $\oplus$ is bitwise XOR, and that equivalence stands for bits, and multibit quantities being equal in all their respective bits is equivalent to these quantities being equal).

Now assume that $x_i$ is the birthday of person $i$ in the room, expressed as days since the first day of the year, in binary, with a year of $2^n$ days, and what's meant should be clear.

Notice that the problem studied in the quote is about two lists/rooms, rather than one in the standard birthday problem.


Note that $x_1=x_2$, i.e., there is a birthday collision in $\{0,1\}^n$ if and only if $x_1\oplus x_2=0.$ In a general additive group $G$, $x_1=x_2$, i.e., there is a birthday collision in $G$ if and only if $x_1-x_2=0.$

If you have two lists $L_1,L_2,$ then with probability roughly $$\exp\left\{-\frac{|L_1|^2|L_2|^2}{2^{n+1}}\right\}$$ there will be no collisions.

In the birthday paradox, for $N=2^n$ bins, the probability of no collisions after $m$ balls is roughly $$\exp\left\{-\frac{m^2}{2N}\right\}$$ while here we have $|L_1||L_2|$ pairs to consider so $m=|L_1||L_2|.$

Wagner's paper is about finding efficient algorithms for vectors adding to zero for higher numbers (e.g., 4) of lists.


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.