Vidéo pédagogique

3.10. Decoding One Out of Many

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

The final session of this week isdevoted to Decoding One Out of Many. Decoding One Out of Manyis interested in solving the following variantof Syndrome Decoding. In this variant, the onlydifference with the usual Syndrome Decoding isthat we are interested in a set of syndromesrather than a single syndrome. So, the instance will be S, a set of syndromes of size N. H, a parity-checkmatrix and w an integer, the weight we are looking for. And we are interestedin an error e, such that the syndrome of e is anelement of the set S with e of weight w or less. We will denote CSD sub N of H, S, w, the set of allsolutions to the above problem. As for CSD1 which is, infact, the plain CSD, we will only consider solvable instances. And by solvable hereinstances, we mean something very strong, we meanthat every syndrome in the set S belongs to that set. So, every syndrome inthe set S corresponds to an error of weight w. We expect with thistechnique - and I will show you how we obtain this -, weexpect to get all solutions, the N solution to the problem atthe expense of a factor only √ N. Or alternatively, weexpect to get a single solution to the problem,but to gain a factor √ N to obtain that solution. Again, I will startwith Birthday Decoding. Now, I want to solveBirthday Decoding with multiple instances. I will now split the matrix intotwo parts, but you can see here that n1 will be larger than n2, that is the left partof 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 thoseweights, in fact, it will be w1, is greater thanthe other part w2. I define those two sets:the first set is simply a set of syndromes of errorse1*(H1 transpose) when the weight of e1 is w1. But the second listis in fact formed of the syndrome according to H2that is e2*(H2 transpose) + any syndrome s. So, the list L2 willhave 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).

Langue :
Conditions d'utilisation
Ces ressources de cours sont, sauf mention contraire, diffusées sous Licence Creative Commons. L’utilisateur doit mentionner le nom de l’auteur, il peut exploiter l’œuvre sauf dans un contexte commercial et il ne peut apporter de modifications à l’œuvre originale.
Citer cette ressource:
Inria. (2015, 5 mai). 3.10. Decoding One Out of Many. [Vidéo]. Canal-U. (Consultée le 22 mai 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème