# What does this paraphrase of the birthday problem mean?

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.