A Distinguisher for High Rate McEliece Cryptosystems

Jean-Charles Faugère 1 Valérie Gauthier-Umana 2 Ayoub Otmani 3 Ludovic Perret 1 Jean-Pierre Tillich 4
1 PolSys - Polynomial Systems
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
2 Equipe AMACC - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Abstract : The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of a Goppa code from a random matrix. The hardness of this problem is an assumption to prove the security of code-based cryptographic primitives such as McEliece's cryptosystem. Up to now, it is widely believed that the GD problem is a hard decision problem. We present the first method allowing to distinguish alternant and Goppa codes over any field. Our technique can solve the GD problem in polynomial-time provided that the codes have sufficiently large rates. The key ingredient is an algebraic characterization of the key-recovery problem. The idea is to consider the rank of a linear system which is obtained by linearizing a particular polynomial system describing a key-recovery attack. Experimentally it appears that this dimension depends on the type of code. Explicit formulas derived from extensive experimentations for the rank are provided for "generic" random, alternant, and Goppa codes over any alphabet. Finally, we give theoretical explanations of these formulas in the case of random codes, alternant codes over any field of characteristic two and binary Goppa codes.
Type de document :
Article dans une revue
IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2013, 59 (10), pp.6830-6844. <http://dx.doi.org/10.1109/TIT.2013.2272036>. <10.1109/TIT.2013.2272036>
Liste complète des métadonnées

https://hal.inria.fr/hal-00776068
Contributeur : Ludovic Perret <>
Soumis le : lundi 14 janvier 2013 - 23:19:24
Dernière modification le : mercredi 25 novembre 2015 - 01:04:40
Document(s) archivé(s) le : lundi 15 avril 2013 - 04:09:14

Fichier

MAYA2-UPMCINRIA-adist-2.0.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Charles Faugère, Valérie Gauthier-Umana, Ayoub Otmani, Ludovic Perret, Jean-Pierre Tillich. A Distinguisher for High Rate McEliece Cryptosystems. IEEE Transactions on Information Theory, Institute of Electrical and Electronics Engineers, 2013, 59 (10), pp.6830-6844. <http://dx.doi.org/10.1109/TIT.2013.2272036>. <10.1109/TIT.2013.2272036>. <hal-00776068>

Partager

Métriques

Consultations de
la notice

402

Téléchargements du document

606