Décodage générique de codes linéaires

Abstract : Nous étudions ici le comportement asymptotique des meilleurs algorithmes de décodage générique des codes linéaires binaires lorsque le poids de l’erreur w est faible, c’est-à-dire w = o(n) où n est la longueur du code.Cette étude sert à comprendre la sécurité du système cryptographique de type McEliece basé sur les codes correcteurs d’erreurs. Les principales variantes utilisent soit des codes Goppa (ou plus généralement des codes alternants) auquel cas w = O( n/ log2(n)), soit des codes MDPC auquel cas w = O(n^{1/2}). Les algorithmes étudiés ici sont l’algorithme de Prange, de Stern, de Dumer, de May, Meurer et Thomae , et de Becker, Joux, May et Meurer. Nous montrons que pour un taux de transmission fixé R = k/n (k la dimension du code), si le poids de l’erreur w est une fonction de n telle que w = o(n), alors nous avons que la complexité est O(2^{c w}) avec c une constante identique pour tous les algorithmes mentionnés.
Type de document :
Mémoires d'étudiants -- Hal-inria+
Cryptographie et sécurité [cs.CR]. 2015
Liste complète des métadonnées

Littérature citée [7 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01244864
Contributeur : Rodolfo Canto Torres <>
Soumis le : mercredi 16 décembre 2015 - 13:05:48
Dernière modification le : vendredi 25 mai 2018 - 12:02:05
Document(s) archivé(s) le : jeudi 17 mars 2016 - 14:11:02

Identifiants

  • HAL Id : hal-01244864, version 1

Collections

Citation

Rodolfo Canto Torres. Décodage générique de codes linéaires. Cryptographie et sécurité [cs.CR]. 2015. 〈hal-01244864〉

Partager

Métriques

Consultations de la notice

392

Téléchargements de fichiers

116