Vidéo pédagogique
Notice
Sous-titrage
Anglais
Langue :
Anglais
Crédits
Irene Marquez-Corbella (Intervention), Nicolas Sendrier (Intervention), Matthieu Finiasz (Intervention)
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.
DOI : 10.60527/qy46-p902
Citer cette ressource :
Irene Marquez-Corbella, Nicolas Sendrier, Matthieu Finiasz. Inria. (2015, 5 mai). 3.10. Decoding One Out of Many , in 3: Message Attacks (ISD). [Vidéo]. Canal-U. https://doi.org/10.60527/qy46-p902. (Consultée le 6 juillet 2025)
logo Inria
Inria - Institut national de recherche en sciences et technologies du numérique
S'abonner
Contacter

3.10. Decoding One Out of Many

Réalisation : 5 mai 2015 - Mise en ligne : 20 février 2017
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

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


Intervention
Thème
Disciplines :
Documentation
Support de présentation au format PDF

Dans la même collection

Voir tout

Avec les mêmes intervenants et intervenantes

Sur le même thème