Vidéo pédagogique

4.6. Attack against GRS codes

Réalisation : 5 mai 2015 Mise en ligne : 5 mai 2015
  • document 1 document 2 document 3
  • niveau 1 niveau 2 niveau 3
  • audio 1 audio 2 audio 3

In this session we willdiscuss the proposal of using generalized Reed-Solomon codesfor the McEliece cryptosystem. As we have already said,generalized Reed-Solomon codes were proposed in1986 by Niederreiter. Recall that these codes areMDS, that is, they attain the maximum error correctingcapacity which is interpreted as shorter keys for thesame level of security. Moreover, these codes haveefficient decoding algorithms so they are suitablecandidates for code-based cryptography. But this proposal issubject to a polynomial attack by Sidelnikov-Shestakov. Take notice that if we knowa generalized Reed-Solomon code associated to the pair(a,b) of dimension k and dimension k - 1, that iswe know two codes, then by solving the followingsystem, we can obtain the generalized Reed-Solomoncode of dimension k - 2. And the proof is very easy. Just take notice that thestar product of the known codes provide the square code ofthe generalized Reed-Solomon code of dimension k - 1. In other words, a polynomial of degree at most k-1times a polynomial of degree at most k, yields to apolynomial of degree at most 2k - 2. And this property can beused iteratively to build the following decreasing sequence. Note that the generalizedReed-Solomon code of dimension 1 is the set ofmultiples of the vector b. Thus we can retrievethe vector b and then by solving a linearsystem, we can obtain also a. However, from the McEliececryptosystem, just a generator matrix of the generalizedReed-Solomon code of dimension k is known. And we will explain inthis slide how to compute a generator matrix of thesame generalized Reed-Solomon code by dropping byone the dimension. Recall that the shortenof a generalized Reed-Solomon code is again ageneralized Reed-Solomon code. Moreover, the code locatorof the shortened code is again the same code locator butrestricted to some coordinates. In particular shortening atthe first position we get a new generalized Reed-Solomon code, associated to the same code locator withoutthe first coordinate, and it is easy to get a generatormatrix of such shortened code: we just apply GaussianElimination to our matrix.

Langue :
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.
Citer cette ressource:
Inria. (2015, 5 mai). 4.6. Attack against GRS codes. [Vidéo]. Canal-U. (Consultée le 20 mai 2022)

Dans la même collection

Avec les mêmes intervenants

Sur le même thème