Vidéo pédagogique

4.8. Attack against Algebraic Geometry 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 will present anattack against Algebraic Geometry codes (AG codes). Algebraic Geometry codesis determined by a triple. First of all, analgebraic curve of genus g, then a n-tuple of rational pointsand then a divisor which has disjoint support from the n-tuple P. Then, the AlgebraicGeometry code is obtained by evaluating at P allfunctions that belong to the vector space associated to the divisor E. Some properties of thesecodes are nearly optimal codes, that is, their designed minimumdistance is nearly the optimal one. Moreover, the dual of anAG-code is again an AG-code. What about using AlgebraicGeometry codes in code-based cryptography? Janwa andMoreno suggest to use Algebraic Geometry codes for theMcEliece cryptosystem. This is a suitable proposalsince these codes are nearly optimal and haveefficient decoding algorithms. If we talk about codes overcurves of genus zero then we are talking aboutgeneralized Reed-Solomon codes, as we will see in the next slides.So, for a curve of genus 0, this proposal is broken. If we talk about codes overcurves of genus 1 and 2, then this proposal isbroken by Faure and Minder. However, this attack hasseveral drawbacks which makes it impossible to extend to ahigher genera. But there is an attack for the general case. We will explain here thisgeneral attack. First over generalized Reed-Solomoncodes and then we will give an idea on how it worksfor the general case. Recall that thegeneralized Reed-Solomon codes are Algebraic Geometry codesover curves of genus 0. Indeed, if we consider theprojective line, this curve has genus 0 and itspoints are of the form (x:y) Now, we will consider P the n-tuple of points formed by thesepoints and we take E to be K-1 times the point at the infinity. A basis of thevector space associated to this divisor is the following one. And if we evaluate thisbasis at the points P, we get a generator matrix of thisAG code, which is also a generator matrix of ageneralized Reed-Solomon code of dimension k associated to thepair (a,1), the all-ones vector.

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.8. Attack against Algebraic Geometry 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