Canal-U

Mon compte
Inria

4.4. Attack against subcodes of 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_4_attack_against_subcodes_of_grs_codes.32937?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.4. Attack against subcodes of GRS codes

In this session, we will talk about using subcodes of a Generalized Reed–Solomon code for the McEliece Cryptosystem. Recall that to avoid the attack of Sidelnikov and Shestakov, Berger and Loidreau proposed to replace Generalized Reed–Solomon codes by some random subcodes of small codimension. However, this attack has been broken by Wieschebrink in 2006 using square code considerations. The idea of the attack is very simple.
The public key is a subcode of large dimension, otherwise a generic attack could be applied. And we also know the error-correcting capacity of the Generalized Reed–Solomon code. With high probability, the square of this subcode is again a Generalized Reed–Solomon code of maximal dimension. Thus, we just need to apply Sidelnikov and Shestakov to retrieve the code locator and the column multiplier. And thus, we have an efficient decoding algorithm for the Generalized Reed–Solomon code, which is also a decoding algorithm for the chosen subcode. We correct up to t errors. But what happens if the square code is the whole space? Then, a similar attack could be applied but to a shortened code. Recall the definition of a shortened code. First of all, some notations. The process of deleting columns from a parity-check matrix of a linear code is known as shortening. In other words, the shortened code, at the J-locations, is the set of codewords that have a zero in the J-locations restricted to the coordinates indexed by the relative complement of J. In a simple way, suppose that we have a generator matrix and we have the identity at the beginning of its first J-columns. Then, a basis of the shortened code can be easily
obtained by extracting the components that we indicate in the figure, that is by extracting these columns of the generator matrix. Generalized Reed–Solomon codes behave specially with the shortening operation. Since we have that the shortened of a Generalized Reed–Solomon code is again a Generalized Reed–Solomon code. To simplify the proof, we will just shortened the first position, but the generalization to other positions is straightforward. So, let G be a matrix of a Generalized Reed–Solomon code of dimension k associated to the pair (a,b). We labelled its rows by g1, g2, … , gk. We apply Gauss elimination to get a matrix of the following form. Then, this sub-matrix is a generator matrix for the shortened code at the first position.


  •  
    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 : 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