Vidéo pédagogique
Notice
Sous-titrage
Anglais
Langue :
Anglais
Crédits
Irene Marquez-Corbella (Intervention), Nicolas Sendrier (Intervention), Matthieu Finiasz (Intervention)
Conditions d'utilisation
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.
DOI : 10.60527/qene-rr63
Citer cette ressource :
Irene Marquez-Corbella, Nicolas Sendrier, Matthieu Finiasz. Inria. (2015, 5 mai). 4.4. Attack against subcodes of GRS codes , in 4: Key Attacks. [Vidéo]. Canal-U. https://doi.org/10.60527/qene-rr63. (Consultée le 14 juillet 2025)
logo Inria
Inria - Institut national de recherche en sciences et technologies du numérique
S'abonner
Contacter

4.4. Attack against subcodes of GRS codes

Réalisation : 5 mai 2015 - Mise en ligne : 21 février 2017
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
Descriptif

In this session, we willtalk about using subcodes of a Generalized Reed–Solomon codefor the McEliece Cryptosystem. Recall that to avoid theattack of Sidelnikov and Shestakov, Berger andLoidreau proposed to replace Generalized Reed–Solomoncodes by some random subcodes of small codimension.However, this attack has been broken by Wieschebrink in 2006using square code considerations. The idea of theattack is very simple.
The public key is a subcodeof large dimension, otherwise a generic attack could be applied. And we also know theerror-correcting capacity of the Generalized Reed–Solomon code. With high probability, thesquare of this subcode is again a GeneralizedReed–Solomon code of maximal dimension. Thus, we just need to applySidelnikov and Shestakov to retrieve the code locatorand the column multiplier. And thus, we have an efficientdecoding algorithm for the Generalized Reed–Solomoncode, which is also a decoding algorithm for the chosen subcode. We correct up to t errors. But what happens if thesquare code is the whole space? Then, a similar attack couldbe applied but to a shortened code. Recall the definitionof a shortened code. First of all, some notations. The process ofdeleting columns from a parity-check matrix of a linear codeis known as shortening. In other words, theshortened code, at the J-locations, is the set of codewords thathave a zero in the J-locations restricted to the coordinatesindexed by the relative complement of J. In a simple way, supposethat we have a generator matrix and we have the identity at thebeginning of its first J-columns. Then, a basis of theshortened code can be easily
obtained by extracting thecomponents that we indicate in the figure, that is by extractingthese columns of the generator matrix. Generalized Reed–Solomoncodes behave specially with the shortening operation.Since we have that the shortened of a GeneralizedReed–Solomon code is again a Generalized Reed–Solomon code. To simplify the proof, wewill just shortened the first position, but the generalization toother positions is straightforward. So, let G be a matrix of aGeneralized Reed–Solomon code of dimension kassociated to the pair (a,b). We labelled its rows by g1, g2, … , gk. We apply Gauss elimination toget a matrix of the following form. Then, this sub-matrix isa generator matrix for the shortened code at the first position.


Intervention
Thème
Disciplines :
Documentation
Support de présentation au format PDF

Dans la même collection

Voir tout

Avec les mêmes intervenants et intervenantes

Sur le même thème