Ressource pédagogique : 3.9. Generalized Birthday Algorithm for Decoding

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

The session nine is devoted to the application of the Generalized Birthday Algorithm to decoding. The Generalized Birthday Algorithm was presented by David Wagner in 2002, in a more general context. In fact, at order a, the Generalized Birthday Algorithm solves the following 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 Birthday Algorithm can be applied to solve the problem of decoding. In practice, it will apply mostly to instances of Computational Syndrome Decoding which have many solutions and, more than that, it aims at finding one solution only among those many solutions. I would revisit the Birthday Decoding again but this time I will change slightly the context. So now I would assume that there are many solutions. I will be more specific about how many solutions are needed when I am done with this slide. And among those many solutions, I only want to find one. So, I will build the lists exactly in the same manner as before. Here, I write s = s1 + s2 where I cut the target syndrome s arbitrarily. There is no specific reason to do that except to have a nice symmetry and it will be useful for higher order Generalized Birthday Algorithm. So, I have those two lists and I am interested by any element in the intersection. But since I only want one solution to my problem, I am only interested to have one element in the intersection. So, I only want the intersection whose size is L²/2^(n-k) where L is the size of both lists L1 and L2. I am interested that this size is larger than one. This will be the case if I choose L = 2^((n-k)/2). And in that case my lists are large enough to have a non-empty intersection, and the workfactor to obtain a non-empty intersection is L that is 2^((n-k)/2). Once this is set, it gives me the limit for the size list. I need a list of size 2^((n-k)/2) and I also know from the way the lists are constructed that L cannot 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 a Generalized Birthday Algorithm of order 2 for decoding. So, I do exactly the same thing as before except that I split everything in four parts instead of two.

"Domaine(s)" et indice(s) Dewey

• Analyse numérique (518)
• Théorie de l'information (003.54)
• données dans les systèmes informatiques (005.7)
• cryptographie (652.8)
• Mathématiques (510)

Thème(s)