# Canal-U

Mon compte

## 3.10. Decoding One Out of Many

Copier le code pour partager la vidéo :
<div style="position:relative;padding-bottom:56.25%;padding-top:10px;height:0;overflow:hidden;"><iframe src="https://www.canal-u.tv/video/inria/embed.1/3_10_decoding_one_out_of_many.32905?width=100%&amp;height=100%" style="position:absolute;top:0;left:0;width:100%;height: 100%;" width="550" height="306" frameborder="0" allowfullscreen scrolling="no"></iframe></div> Si vous souhaitez partager une séquence, indiquez le début de celle-ci , et copiez le code : h m s
Contacter le contributeur
J’aime
Imprimer
partager

### 3.10. Decoding One Out of Many

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

•
Label UNT : UNIT
•
Date de réalisation : 5 Mai 2015
Durée du programme : 9 min
Classification Dewey : Analyse numérique, Théorie de l'information, données dans les systèmes informatiques, cryptographie, Mathématiques
•
Catégorie : Vidéocours
Niveau : niveau Master (LMD), niveau Doctorat (LMD), Recherche
Disciplines : Mathématiques, Informatique, Informatique, Mathématiques et informatique
Collections : 3: Message Attacks (ISD)
ficheLom : Voir la fiche LOM
•
Auteur(s) : MARQUEZ-CORBELLA Irene, SENDRIER Nicolas, FINIASZ Matthieu
•
Langue : Anglais
Mots-clés : algèbre linéaire, chiffrement à clé publique, cryptage des données, cryptographie, algorithmes
Conditions d’utilisation / Copyright : 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.

## commentaires

Ajouter un commentaire Lire les commentaires
*Les champs suivis d’un astérisque sont obligatoires.
Aucun commentaire sur cette vidéo pour le moment (les commentaires font l’objet d’une modération)