Algebraic Cryptanalysis of McEliece Variants with Compact Keys

Jean-Charles Faugère 1, 2 Ayoub Otmani 3, 4 Ludovic Perret 1, 2 Jean-Pierre Tillich 3
1 SALSA - Solvers for Algebraic Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
4 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : In this paper we propose a new approach to investigate the security of the McEliece cryptosystem. We recall that this cryptosystem relies on the use of error-correcting codes. Since its invention thirty years ago, no efficient attack had been devised that managed to recover the private key. We prove that the private key of the cryptosystem satisfies a system of bi-homogeneous polynomial equations. This property is due to the particular class of codes considered which are alternant codes. We have used these highly structured algebraic equations to mount an efficient key-recovery attack against two recent variants of the McEliece cryptosystems that aim at reducing public key sizes. These two compact variants of McEliece managed to propose keys with less than 20,000 bits. To do so, they proposed to use quasi-cyclic or dyadic structures. An implementation of our algebraic attack in the computer algebra system MAGMA allows to find the secret-key in a negligible time (less than one second) for almost all the proposed challenges. For instance, a private key designed for a 256-bit security has been found in 0.06 seconds with about 2^17.8 operations.
Type de document :
Communication dans un congrès
Henri Gilbert. Eurocrypt 2010 - 29th International Conference on Cryptology, May 2010, Monaco, Monaco. Springer Verlag, 6110, pp.279-298, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13190-5_14〉
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00596632
Contributeur : Jean-Charles Faugère <>
Soumis le : lundi 30 mai 2011 - 13:29:39
Dernière modification le : vendredi 31 août 2018 - 09:25:54
Document(s) archivé(s) le : vendredi 9 novembre 2012 - 13:55:32

Fichier

Eurocrypt2010.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Jean-Charles Faugère, Ayoub Otmani, Ludovic Perret, Jean-Pierre Tillich. Algebraic Cryptanalysis of McEliece Variants with Compact Keys. Henri Gilbert. Eurocrypt 2010 - 29th International Conference on Cryptology, May 2010, Monaco, Monaco. Springer Verlag, 6110, pp.279-298, 2010, Lecture Notes in Computer Science. 〈10.1007/978-3-642-13190-5_14〉. 〈inria-00596632〉

Partager

Métriques

Consultations de la notice

575

Téléchargements de fichiers

316