Ressource pédagogique : 3.6. Stern/Dumer Algorithm

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

In this session, we will present the Stern algorithm for decoding. In fact, the idea is to combine two algorithms that we have seen before, the Lee and Brickell algorithm and the Birthday Decoding.  So, instead of a full Gaussian elimination, we will simply have a partial Gaussian elimination as presented here. And if we look at the lower part, what is called step 1, in red here in this slide, it is, in fact, a smaller CSD problem with a smaller matrix H', with a smaller target syndrome s' and with the weight p. So, now we are going to solve this smaller problem in the first step. In fact, we are going to find all or most solutions to that problem e'. And for every e'found in step 1, we will check in step 2 whether this particular solution e'can be extended to a solution of the full CSD problem. If we solve the first step using enumeration, as I presented as the very first algorithm, then we obtain an algorithm which is very similar to the Lee and Brickell algorithm. But, if we use for step 1 a Birthday Decoding, then we obtain a significant speedup for decoding and it is in fact the Dumer Algorithm. Now, I will describe this algorithm. So, we are trying to solve CSD of H, s, w and this time we have two additional integer parameters p and l. And we repeat the following: we pick a permutation matrix P, we make a partial Gaussian elimination as you can see on the right of the slide, obtaining U, H', H'', s', s''. We solve the small CSD problem with H', s' and p - we solve this one with Birthday Decoding - and  for every solution of the problem we will construct the second part of the error e''. And if we are lucky, this second part of the error pattern e''has a sufficiently small weight, and then, provides the solution to our problem.  So, what I presented is the Dumer algorithm. In fact, this algorithm was published in 1991. But Stern algorithm, which is slightly more expensive, was presented two years before.

"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)