# Why k-lists generalized birthday problem when $k=2$ is classical birthday problem?

David Wagner in his article A Generalized Birthday Problem in CRYPTO 2002 says that in k-dimensional (also k-lists) generalization of birthday problem (GBP), when $k=2$ "this is just the extremely well-known birthday problem." Why is that so? As I understand it, in classical birthday problem we search for collisions in one list $L$, where $x_1$ and $x_2$ is supposed to be $\in L$), but, in k-lists GBP we have k number of lists, when $k=2$ it's $L_1, L_2$, we find $x_1 \in L_1$ and $x_2 \in L_2$ such that $x_1 \oplus x_2 = 0$.

So, how does k-lists GBP converges to classical birthday problem when $k=2$? Or I'm missing something?

• @D.W. Could you please comment on this? Jul 28, 2016 at 18:32
• You can't ping people like that out of the blue, they need to actually be present in the comment chain Jul 28, 2016 at 20:00
• I already found that it's similar to Generalization to multiple types. Jul 28, 2016 at 23:24

They are essentially the same, certainly in terms of complexity. Any collision $x=y$ with $x\in L_x$ and $y\in L_y$ is a collision in a single list $L_x \cup L_y$ of size at most twice the size of the larger list.
Any collision in a single list is compatible with about half the partitions of that list into two equal sized halves. So an algorithm that finds a collision in the union randomly has found a collision in the two-list problem with probability $1/2.$