Cryptology ePrint Archive: Report 2010/410
Daniel J. Bernstein and 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.
Category / Keywords: public-key cryptography / McEliece cryptosystem, Niederreiter cryptosystem, Goppa codes, wild Goppa codes, list decoding
Publication Info: accepted to SAC 2010
Date: received 22 Jul 2010, last revised 6 Oct 2010
Contact author: c p peters at tue nl
Available format(s): PDF | BibTeX Citation
Note: expanded version of the SAC proceedings version
Version: 20101006:225811 (All versions of this report)
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]