Vidéo pédagogique

4.9. Goppa codes still resist

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

All the results that we have seen this week doesn't mean that code basedcryptography is broken. So in this session we willsee that Goppa code still resists to all these attacks. So recall that it isassumed that Goppa codes are pseudorandom, that isthere exist no efficient distinguisher for Goppacode. An efficient distinguisher was built for the case of high rate codes, where the rateis very close to 1, but no generalization of thisdistinguisher is known. The best known attacks arebased on the Support Splitting Algorithm and haveexponential runtime. In the third session ofthis week, we have seen that Generalized Reed-Solomon codesbehave differently than random codes, with respect to the squareproduct that is the dimension of the square of aGeneralized Reed-Solomon code is very small compared to what it'sexpected for a random code of the same length and dimension. Since an alternant code isa subfield subcode of a Generalized Reed-Solomoncode, we might suspect that the star product of alternant codes alsobehave differently from random codes. As we will see, this is truebut just for a very few cases. The following propositionshows that the star product of two alternant codes is anotheralternant code and the proof is very easy. We just need to recallthat alternant codes are subfield subcodes ofGeneralized Reed Solomon code. So how works this proof?Let c1 be a codeword of an alternant code and c2 beanother codeword of a different alternant code with the same support. Then, there exist twopolynomials of degree smaller than n-s and another polynomialof degree smaller than n-r such that the evaluationof these polynomials at the correspondingelements give our codewords.

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.9. Goppa codes still resist. [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