Canal-U

Mon compte
Inria

3.6. Stern/Dumer Algorithm


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_6_stern_dumer_algorithm.32891?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
Auteur(s) :
MARQUEZ-CORBELLA Irene
SENDRIER Nicolas
FINIASZ Matthieu

Producteur Canal-U :
Inria
Contacter le contributeur
J’aime
Imprimer
partager facebook twitter Google +

3.6. Stern/Dumer Algorithm

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.


  •  
    Label UNT : UNIT
  •  
    Date de réalisation : 5 Mai 2015
    Durée du programme : 7 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) : SENDRIER Nicolas, FINIASZ Matthieu, MARQUEZ-CORBELLA Irene
  •  
    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)
 

Dans la même collection

FMSH
 
Facebook Twitter Google+
Mon Compte