Vendredi 21 mars 2014 à 14h30 en salle C47
Irene Márquez (LIX)

Titre : Cryptanalyse du Système de McEliece sur les codes géométriques

Résumé :
L'idée d'utiliser la difficulté du décodage d'un code aléatoire comme primitive de cryptographie à clé publique à été introduite par McEliece en 1978. La proposition originelle de McEliece repose sur l'utilisation des codes de Goppa binaires. Par la suite, d'autres familles de codes ont été proposées pour ce schéma de chiffrement dans le but de réduire la taille des clés. La principale exigence est d'avoir un algorithme de décodage rapide et corrigeant beaucoup d'erreurs. Par example (et cette liste est loin d'être exhaustive), les codes de Reed-Solomon généralisés, leur sous-codes et les codes Reed-Muller binaires ont été proposés. Tous ces systèmes sont soumis à des attaques en temps polynomial ou sous-exponentiel. Les codes géométriques ont été proposés par Janwa et Moreno. Faure et Minder ont proposé une attaque structurelle de ce système lorsque les codes proposés sont construits à partir de courbes de genre g<3. Leur approche rend toutefois très difficile toute extension au cas de courbes de genre supérieur. Dans cet exposé je présenterai une attaque polynomiale du schéma de McEliece basé sur les codes géometriques. Cette attaque permet de retrouver une algorithme de décodage pour les clés proposées en moins de O(n^4) opérations.

Remarques : Travail commun avec Alain Couvreur et Ruud Pellikaan