The original McEliece cryptosystem uses length-n codes over F2 with dimension ≥n-mt efficiently correcting t errors where 2m ≥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 errors where q m ≥n. Previously proposed cryptosystems with the same length and dimension corrected only errors for q≥3. This paper also presents list-decoding algorithms that efficiently correct even more errors for the same codes over Fq. Finally, this paper shows that the increase from errors to more than errors allows considerably smaller keys to achieve the same security level against all known attacks. © 2011 Springer-Verlag Berlin Heidelberg.
Keyword: Decoding,McEliece cryptosystem,Goppa codes,wild Goppa codes,Niederreiter cryptosystem,Errors,Cryptography,list decoding