Canal-U

Mon compte
Inria

3.3. Information Set Decoding: the Power of Linear Algebra


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_3_information_set_decoding_the_power_of_linear_algebra.32875?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) :
FINIASZ Matthieu
MARQUEZ-CORBELLA Irene
SENDRIER Nicolas

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

3.3. Information Set Decoding: the Power of Linear Algebra

In this third session, we will present the most important concept of the week: Information Set Decoding. The problem of decoding is not only a combinatorial problem. Because we are dealing with linear code, we may also use Linear Algebra. In particular, we are able to transform the Computational Syndrome Decoding problem by multiplying the matrix by a permutation P on the right and a nonsingular matrix U on the left. This will transform the problem of syndrome decoding into an equivalent one. It is very easy to prove that the following equivalence holds. In fact, this implies that the two computational syndrome decoding that are presented here are equivalent.
If I solve one of them, I solve the other. In particular, I can choose H'in the following form which is called systematic form or standard form. If the first n-k columns of matrix H*P are independent, then I am able to compute such a form. If this is the case, the last k column of the matrix forms an information set. If I am lucky, the permutation P will send the w error position in the left part of the position. If this happens, then the modified syndrome s'will have a weight equal to the weight of the error. And I can check that very easily. I can transform that into an algorithm. So, I want to solve the computational syndrome decoding presented here. I will repeatedly pick a permutation P, compute the following systematic form using Gaussian elimination, and check whether the transformed syndrome s*(U transpose) is a weight w. When this hapens, I can return the following vector which is valid solution to the original syndrome decoding problem. Here, each iteration of this algorithm will cost n*(n-k) column operations that is the cost of the Gaussian elimination. And I have to repeat that a certain number of times, until one of the solutions to my problem has all its non-zero coordinates "all left". In the next session, I will present Complexity Analysis of that algorithm in particular as long as tools to make the complexity analysis of the variance of information set decoding I will present throughout this course.

  •  
    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 Google+
Mon Compte