Canal-U

Mon compte
Inria

3.1. From Generic Decoding to Syndrome Decoding


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_1_from_generic_decoding_to_syndrome_decoding.32857?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

3.1. From Generic Decoding to Syndrome Decoding

Welcome to the third week of the MOOC on code-based cryptography. This week, we will learn about message attacks. Among the ten sessions of this week, the first six will present the most essential part of generic decoding and the last four will be devoted to more advanced matters. The first session is about generic decoding; a   presentation of what a message attack and what generic decoding is about. A cryptogram in the McEliece encryption scheme has the following form. A cryptogram is composed by multiplying a message by a public key and adding a random error. The adversary knows the cryptogram and the public key and wish to recover the message or, equivalently, the error. Without any additional information on the public key, solving that problem is called generic decoding. Generic decoding, in contrast with the usual situation where the code is known in advance, takes as argument a q-ary linear code. It can be either a generator matrix, or a parity check matrix.
In the first case, we speak of generic decoding; it takes as argument a vector, presumably noisy, and a generator matrix and will return a message. The desirable feature of a generic decoder is to succeed in removing an error "e" as long as this error is small enough. By small, I mean small hamming weight. A generic syndrome decoder will take as argument a syndrome and a parity check matrix. It will succeed if it manages to correct an error whenever the weight of the error is small enough. Those two kind of decoders are equivalent and so, in the sequel of this course, we would only consider syndrome decoding. Syndrome decoding is an NP complete problem. It takes as argument a matrix, parity check matrix H, a syndrome s and an integer w, and try to return an error pattern that will correspond to this syndrome. In fact, we are trying to find w column in the matrix H such that their sum is equal to the target syndrome s. In other terms, we are looking for w indices, j1 to jw such that the corresponding column has a sum equal to s. The syndrome decoding problem may have one or several solutions. We will denote CSD(H,s,w) the set of all solutions to the above problem. Where a CSD stands for computational syndrome decoding.


  •  
    Label UNT : UNIT
  •  
    Date de réalisation : 5 Mai 2015
    Durée du programme : 4 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)
 

Dans la même collection

FMSH
 
Facebook Twitter
Mon Compte