Paper 2009/187

Compact McEliece Keys from Goppa Codes

Rafael Misoczki and Paulo S. L. M. Barreto

Abstract

The classical McEliece cryptosystem is built upon the class of Goppa codes, which remains secure to this date in contrast to many other families of codes but leads to very large public keys. Previous proposals to obtain short McEliece keys have primarily centered around replacing that class by other families of codes, most of which were shown to contain weaknesses, and at the cost of reducing in half the capability of error correction. In this paper we describe a simple way to reduce significantly the key size in McEliece and related cryptosystems using a subclass of Goppa codes, while also improving the efficiency of cryptographic operations to $\tilde{O}(n)$ time, and keeping the capability of correcting the full designed number of errors in the binary case.

Note: Updated version with binary codes only. QD codes over extension fields are susceptible to structural attacks by Faugère et al. and by Umana and Leander. The text discusses why binary QD codes are not affected by those attacks. A few typos were also corrected.

Metadata
Available format(s)
PDF PS
Category
Public-key cryptography
Publication info
Published elsewhere. The final version of this paper was published in Selected Areas in Cryptography -- SAC'2009, LNCS 5867, pp. 376--392, Springer, 2009. DOI: 10.1007/978-3-642-05445-7 http://www.springerlink.com/content/a352901271645444/
Keywords
post-quantum cryptographysyndrome decodingefficient parameters and algorithms
Contact author(s)
pbarreto @ larc usp br
History
2010-04-10: last of 18 revisions
2009-05-02: received
See all versions
Short URL
https://ia.cr/2009/187
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/187,
      author = {Rafael Misoczki and Paulo S.  L.  M.  Barreto},
      title = {Compact McEliece Keys from Goppa Codes},
      howpublished = {Cryptology ePrint Archive, Paper 2009/187},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/187}},
      url = {https://eprint.iacr.org/2009/187}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.