Wild McEliece

Daniel J. Bernstein, Tanja Lange, Christiane Peters

Research output: Contribution to journalConference articleResearchpeer-review

Abstract

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
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume6544 LNCS
Pages (from-to)143-158
ISSN0302-9743
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event17th International Workshop on Selected Areas in Cryptography - Waterloo, Canada
Duration: 12 Aug 201013 Aug 2010
Conference number: 17

Workshop

Workshop17th International Workshop on Selected Areas in Cryptography
Number17
CountryCanada
CityWaterloo
Period12/08/201013/08/2010

Cite this