Ressource pédagogique : 3.10. Decoding One Out of Many

Informations pratiques sur cette ressource

Description de la ressource pédagogique

Description (résumé)

The final session of this week is devoted to Decoding One Out of Many. Decoding One Out of Many is interested in solving the following variant of Syndrome Decoding. In this variant, the only difference with the usual Syndrome Decoding is that we are interested in a set of syndromes rather than a single syndrome. So, the instance will be S, a set of syndromes of size N. H, a parity-check matrix and w an integer, the weight we are looking for. And we are interested in an error e, such that the syndrome of e is an element of the set S with e of weight w or less. We will denote CSD sub N of H, S, w, the set of all solutions to the above problem. As for CSD1 which is, in fact, the plain CSD, we will only consider solvable instances. And by solvable here instances, we mean something very strong, we mean that every syndrome in the set S belongs to that set. So, every syndrome in the set S corresponds to an error of weight w. We expect with this technique - and I will show you how we obtain this -, we expect to get all solutions, the N solution to the problem at the expense of a factor only ? N. Or alternatively, we expect to get a single solution to the problem, but to gain a factor ? N to obtain that solution. Again, I will start with Birthday Decoding. Now, I want to solve Birthday Decoding with multiple instances. I will now split the matrix into two parts, but you can see here that n1 will be larger than n2, that is the left part of the matrix is larger than the right part of the matrix. Also, the weight w, instead of being divided in two equal parts is divided in w1+w2, and possibly one of those weights, in fact, it will be w1, is greater than the other part w2. I define those two sets: the first set is simply a set of syndromes of errors e1*(H1 transpose) when the weight of e1 is w1. But the second list is in fact formed of the syndrome according to H2 that is e2*(H2 transpose) + any syndrome s. So, the list L2 will have a size equal to the number of syndromes N * (n2, w2) that is the number of errors of weight w2, when the first list L1 will have simply a size (n1,w1).

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