3.9. Generalized Birthday Algorithm for Decoding

The session nine isdevoted to the application of the Generalized BirthdayAlgorithm to decoding. The Generalized BirthdayAlgorithm was presented by David Wagner in 2002, in amore general context. In fact, at order a,the Generalized Birthday Algorithm solves thefollowing problem: we are given 2^a lists of vectors of size L and we want to find xi, one in every list Li,such that the sum of all the xi is 0. If the lists Li are large enough,then the algorithm runs in time 2^(l/(a+1)). Note that the case a=1 corresponds to the usual birthday paradox. This Generalized BirthdayAlgorithm can be applied to solve the problem of decoding. In practice, it willapply mostly to instances of Computational SyndromeDecoding which have many solutions and, more than that,it aims at finding one solution only amongthose many solutions. I would revisit theBirthday Decoding again but this time I will changeslightly the context. So now I would assume thatthere are many solutions. I will be more specificabout how many solutions are needed when I amdone with this slide. And among those manysolutions, I only want to find one. So, I will build the listsexactly in the same manner as before. Here, I write s = s1 + s2 where I cut the targetsyndrome s arbitrarily. There is no specific reasonto do that except to have a nice symmetry and it willbe useful for higher order Generalized Birthday Algorithm. So, I have those two listsand I am interested by any element in the intersection. But since I only want onesolution to my problem, I am only interested to have oneelement in the intersection. So, I only want theintersection whose size is L²/2^(n-k) where L is the size ofboth lists L1 and L2. I am interested that thissize is larger than one. This will be the case ifI choose L = 2^((n-k)/2).And in that case my listsare large enough to have a non-empty intersection, andthe workfactor to obtain a non-empty intersectionis L that is 2^((n-k)/2). Once this is set, itgives me the limit for the size list. I need alist of size 2^((n-k)/2) and I also know fromthe way the lists are constructed that Lcannot exceed (n/2,w/2). So, I need the condition here in red in order to be able to apply this version of Birthday Decoding. Now, I can define aGeneralized Birthday Algorithm of order 2 for decoding. So, I do exactly the samething as before except that I split everything infour parts instead of two.