In David Wagner's article A Generalized Birthday Problem, he said and I quote:

Our algorithm works only when one can extend the size of the lists freely, i.e, in the special case where there are sufficiently many solutions to the k-sum problem.

  1. Does that means that the generalized birthday attack only applies for the problems with multiple solutions?
  2. Why is it not suitable for the problem with one solution?

Edit: Let me try and explain further. It is because the algorithm looks for restricted solutions that it finds on average one of the $$\frac{(2^{d/3})^4}{2^d}=2^{d/3}$$ solutions present in the lists $L_i$ as chosen below. This is the price paid for having complexity $2^{d/3}$ instead of the $2^{d/2}$ complexity of Shamir Schroeppel.

Taking the case $k=4,$ which is when you are looking for a solution $$x_0+x_1+x_2+x_3=0,\quad x_i \in L_i$$ Wagner randomly generates 4 lists $L_i~(1\leq i\leq 4)$ of size $2^{d/3}$ where $d$ is the bitlength.

By statistical arguments you'd have a single solution with constant probability bounded away from zero when the lists are size $2^{d/4}$ (consider the fact that there are $(2^{d/4})^4=2^d$ 4-sums that can be drawn from these lists and with constant probability the value $0$ will be hit). But the point is there is no efficient way of finding this single solution except by Shamir-Schroeppel method which has efficient memory but time complexity $2^{d/2}.$

What Wagner does is recursively generate the solutions, but the solutions have special structure. The first third of the bits of the candidates from $L_0,L_1$ are matched, similarly for $L_2,L_3$ etc.

Because the solutions are structured you need to generate more solutions than the minimum number required so that your algorithm finds a single solution with good probability.

  • $\begingroup$ I've deleted my comment... $\endgroup$
    – kelalaka
    Jul 6 '21 at 13:54
  • $\begingroup$ In the case of one solution, if we apply the Wagner algorithm of case $k=4$, i.e, $L_i (1 \leq i \leq 4 )$, after the match of $L_0$ and $L_1$, the expect match elements are $\frac{|L_0||L_1|}{2^{d/3}} = 2^{d/3}$. Similarly for L2,L3 etc. In expectation, it seems that we still can get $1$ element at last, which is the solution. Why it doesn't work? For this reason, I can't tell the difference between these two cases. $\endgroup$
    – Laura
    Jul 7 '21 at 1:56
  • $\begingroup$ But $2^{d/3}$ is much larger than $2^{d/4}$ for moderate to large $d$ $\endgroup$
    – kodlu
    Jul 7 '21 at 3:08

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.