2
$\begingroup$

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?

|improve this question
$\endgroup$
  • $\begingroup$ @D.W. Could you please comment on this? $\endgroup$ – catpnosis Jul 28 '16 at 18:32
  • 1
    $\begingroup$ You can't ping people like that out of the blue, they need to actually be present in the comment chain $\endgroup$ – Thomas Jul 28 '16 at 20:00
  • $\begingroup$ I already found that it's similar to Generalization to multiple types. $\endgroup$ – catpnosis Jul 28 '16 at 23:24
3
$\begingroup$

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.$

Moreover in the crypto context the lists contain (pseudo)random outputs of hashes or other crypto primitives.

|improve this answer
$\endgroup$
2
$\begingroup$

It doesn't converge, it looks like it's just a different problem altogether that's been named the same (probably due to the similarities between them).

For example, this paper, and also wikipedia have the definitions you'ld expect the generalized birthday problem to have.

|improve this answer
$\endgroup$
  • 1
    $\begingroup$ Yeah, but I'm interested in Wagner's algorithm, in the context of Equihash. Equihash also uses single list, but references Wagner's algo which k-list. ¯\_(ツ)_/¯ $\endgroup$ – catpnosis Jul 28 '16 at 23:29

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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