Hcfyk

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_1oplus 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
$$expleft-frac^22^n+1right$$
there will be no collisions.

In the birthday paradox, for $N=2^n$ bins, the probability of no collisions after $m$ balls is roughly
$$expleft-fracm^22Nright$$
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.