Paper 2008/318

Attacking and defending the McEliece cryptosystem

Daniel J. Bernstein, Tanja Lange, and Christiane Peters

Abstract

This paper presents several improvements to Stern's attack on the McEliece cryptosystem and achieves results considerably better than Canteaut et al. This paper shows that the system with the originally proposed parameters can be broken in just 1400 days by a single 2.4GHz Core 2 Quad CPU,or 7 days by a cluster of 200 CPUs. This attack has been implemented and is now in progress. This paper proposes new parameters for the McEliece and Niederreiter cryptosystems achieving standard levels of security against all known attacks. The new parameters take account of the improved attack; the recent introduction of list decoding for binary Goppa codes; and the possibility of choosing code lengths that are not a power of 2. The resulting public-key sizes are considerably smaller than previous parameter choices for the same level of security.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
McEliece cryptosystemStern attackminimal weight code wordlist decoding binary Goppa codessecurity analysis.
Contact author(s)
tanja @ hyperelliptic org
History
2008-08-08: revised
2008-08-02: received
See all versions
Short URL
https://ia.cr/2008/318
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2008/318,
      author = {Daniel J.  Bernstein and Tanja Lange and Christiane Peters},
      title = {Attacking and defending the McEliece cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2008/318},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/318}},
      url = {https://eprint.iacr.org/2008/318}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.