Salle 1 Tour IRMA
17 mars 2011 - 09h45
Décodage en liste des codes de Goppa Binaires et réduction de clé de McEliece
par Morgan Barbier de École Polytechnique - LIX
17 mars 2011 - 09h45
Décodage en liste des codes de Goppa Binaires et réduction de clé de McEliece
par Morgan Barbier de École Polytechnique - LIX
Résumé : Le premier décodage algébrique pour les codes de Goppa est dû à Patterson en 1975. Cette méthode décode jusqu'à t, la capacité de correction du code. Les codes de Goppa font partie de la famille des codes alternants, c'est-à-dire des codes restreints à un sous-corps de Reed-Solomon généralisé, il est donc possible d'adapter toutes les méthodes de décodages des codes de Reed-Solomon aux codes de Goppa, comme le célèbre algorithme de décodage en liste de Guruswami et Sudan. Ce procédé nous permet alors de décoder jusqu'à la borne de Johnson générique, qui est plus grand que t. Dans son mémoire de thèse, Guruswami propose une méthode pour décoder en liste les codes restreints géométriques jusqu'à la borne de Johnson q-aire, qui est plus grande que la borne de Johnson générique. On propose alors d'appliquer cette même méthode aux codes alternants, et tout particulièrement aux codes de
Goppa binaires. Bernstein, Lange et Peters expliquent comment dans le cryptosystème de McEliece, on peut utiliser le décodage en liste. On conclura alors par la réduction de clé de McEliece obtenue grâce à cet algorithme de décodage en liste.
Ce séminaire est un séminaire du LJK organisé par l'équipe BIPOP-CASYS
