Canal-U

Mon compte
Inria

4.6. Attack against GRS codes


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/4_6_attack_against_grs_codes.32947?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 +

4.6. Attack against GRS codes

In this session we will discuss the proposal of using generalized Reed-Solomon codes for the McEliece cryptosystem. As we have already said, generalized Reed-Solomon codes were proposed in 1986 by Niederreiter. Recall that these codes are MDS, that is, they attain the maximum error correcting capacity which is interpreted as shorter keys for the same level of security. Moreover, these codes have efficient decoding algorithms so they are suitable candidates for code-based cryptography. But this proposal is subject to a polynomial attack by Sidelnikov-Shestakov. Take notice that if we know a generalized Reed-Solomon code associated to the pair (a,b) of dimension k and dimension k - 1, that is we know two codes, then by solving the following system, we can obtain the generalized Reed-Solomon code of dimension k - 2. And the proof is very easy. Just take notice that the star product of the known codes provide the square code of the generalized Reed-Solomon code of dimension k - 1. In other words, a polynomial of degree at most k-1 times a polynomial of degree at most k, yields to a polynomial of degree at most 2k - 2. And this property can be used iteratively to build the following decreasing sequence. Note that the generalized Reed-Solomon code of dimension 1 is the set of multiples of the vector b. Thus we can retrieve the vector b and then by solving a linear system, we can obtain also a. However, from the McEliece cryptosystem, just a generator matrix of the generalized Reed-Solomon code of dimension k is known. And we will explain in this slide how to compute a generator matrix of the same generalized Reed-Solomon code by dropping by one the dimension. Recall that the shorten of a generalized Reed-Solomon code is again a generalized Reed-Solomon code. Moreover, the code locator of the shortened code is again the same code locator but restricted to some coordinates. In particular shortening at the first position we get a new generalized Reed-Solomon code, associated to the same code locator without the first coordinate, and it is easy to get a generator matrix of such shortened code: we just apply Gaussian Elimination to our matrix.

  •  
    Label UNT : UNIT
  •  
    Date de réalisation : 5 Mai 2015
    Durée du programme : 6 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 : 4: Key Attacks
    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, code correcteur, algorithmes, GRS code
    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