Paper 2010/331

A Distinguisher for High Rate McEliece Cryptosystems

Jean-Charles Faugère, Valérie Gauthier, Ayoub Otmani, Ludovic Perret, and Jean-Pierre Tillich

Abstract

The Goppa Code Distinguishing (GD) problem consists in distinguishing the matrix of Goppa code from a random matrix. Up to now, it was widely believed that this problem is computationally hard. The hardness of this problem was a mandatory assumption to prove the security of code-based cryptographic primitives like McEliece's cryptosystem. We present a polynomial time distinguisher for alternant and Goppa codes of high rate over any field. The key ingredient is an algebraic technique already used to asses the security McEliece's cryptosystem. Our method permits to indeed distinguish public keys of the CFS signature scheme for all parameters considered as secure and some realistic secure parameters of McEliece. The idea is to consider the dimension of the solution space of a linearized system deduced from a polynomial one. It turns out that this dimension depends on the type of code considered. We provide explicit formulas for the value of the dimension for ``generic" random, alternant, and Goppa code over any alphabet.

Note: Final version - accepted at IEEE Transactions on Information Theory.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Unknown where it was published
Keywords
public-key cryptographyMcEliece cryptosystemCFS signaturealgebraic cryptanalysisdistinguisherGoppa code distinguishing.
Contact author(s)
ludovic perret @ lip6 fr
History
2013-07-18: last of 4 revisions
2010-06-08: received
See all versions
Short URL
https://ia.cr/2010/331
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/331,
      author = {Jean-Charles Faugère and Valérie Gauthier and Ayoub Otmani and Ludovic Perret and Jean-Pierre Tillich},
      title = {A Distinguisher for High Rate McEliece Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2010/331},
      year = {2010},
      note = {\url{https://eprint.iacr.org/2010/331}},
      url = {https://eprint.iacr.org/2010/331}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.