Paper 2010/410

Wild McEliece

Daniel J. Bernstein, Tanja Lange, and Christiane Peters

Abstract

The original McEliece cryptosystem uses length-n codes over F_2 with dimension >=n-mt efficiently correcting t errors where 2^m>=n. This paper presents a generalized cryptosystem that uses length-n codes over small finite fields F_q with dimension >=n-m(q-1)t efficiently correcting floor(qt/2) errors where q^m>=n. Previously proposed cryptosystems with the same length and dimension corrected only floor((q-1)t/2) errors for q>=3. This paper also presents list-decoding algorithms that efficiently correct even more errors for the same codes over F_q. Finally, this paper shows that the increase from floor((q-1)t/2) errors to more than floor(qt/2) errors allows considerably smaller keys to achieve the same security level against all known attacks.

Note: expanded version of the SAC proceedings version

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. accepted to SAC 2010
Keywords
McEliece cryptosystemNiederreiter cryptosystemGoppa codeswild Goppa codeslist decoding
Contact author(s)
c p peters @ tue nl
History
2010-10-06: revised
2010-07-24: received
See all versions
Short URL
https://ia.cr/2010/410
License
Creative Commons Attribution
CC BY

BibTeX

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