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
-
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},
url = {https://eprint.iacr.org/2010/331}
}
