Algebraic Attack against Variants of McEliece with Goppa Polynomial of a Special Form

Jean-Charles Faugère 1 Ludovic Perret 1 Frédéric De Portzamparc 1, 2
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : In this paper, we present a new algebraic attack against some special cases of Wild McEliece Incognito, a generalization of the original McEliece cryptosystem. This attack does not threaten the original McEliece cryptosystem. We prove that recovering the secret key for such schemes is equivalent to solving a system of polynomial equations whose solutions have the structure of a usual vector space. Consequently, to recover a basis of this vector space, we can greatly reduce the number of variables in the corresponding algebraic system. From these solutions, we can then deduce the basis of a GRS code. Finally, the last step of the cryptanalysis of those schemes corresponds to attacking a McEliece scheme instantiated with particular GRS codes (with a polynomial relation between the support and the multipliers) which can be done in polynomial-time thanks to a variant of the Sidelnikov-Shestakov attack. For Wild McEliece & Incognito, we also show that solving the corresponding algebraic system is notably easier in the case of a non-prime base eld Fq. To support our theoretical results, we have been able to practically break several parameters de ned over a non-prime base field q in {9; 16; 25; 27; 32}, t < 7, extension degrees m in {2,3}, security level up to 2^129 against information set decoding in few minutes or hours.
Type de document :
Communication dans un congrès
Advances in Cryptology Asiacrypt 2014, Dec 2014, Kaohsiung, Taiwan. Springer, 8873, pp.21-41, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-45611-8_2〉
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01064687
Contributeur : Jean-Charles Faugere <>
Soumis le : mardi 16 septembre 2014 - 21:01:57
Dernière modification le : lundi 29 mai 2017 - 14:24:35
Document(s) archivé(s) le : mercredi 17 décembre 2014 - 11:55:24

Fichier

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

Identifiants

Collections

Citation

Jean-Charles Faugère, Ludovic Perret, Frédéric De Portzamparc. Algebraic Attack against Variants of McEliece with Goppa Polynomial of a Special Form. Advances in Cryptology Asiacrypt 2014, Dec 2014, Kaohsiung, Taiwan. Springer, 8873, pp.21-41, 2014, Lecture Notes in Computer Science. 〈10.1007/978-3-662-45611-8_2〉. 〈hal-01064687〉

Partager

Métriques

Consultations de la notice

300

Téléchargements de fichiers

308