Wild McEliece

D.J. Bernstein, T. Lange, C.P. Peters

Research output: Book/ReportReportAcademic

Abstract

The original McEliece cryptosystem uses length-$n$ codes over $\rm{F}_2$ with dimension $\geq n-mt$ efficiently correcting t errors where $2^m \geq n$. This paper presents a generalized cryptosystem that uses length-$n$ codes over small finite fields $\rm{F}_q$ with dimension $\geq n-m(q-1)t$ efficiently correcting $\lfloor qt/2 \rfloor$ errors where $q^m \geq n$. Previously proposed cryptosystems with the same length and dimension corrected only $\lfloor (q-1)t/2 \rfloor$ errors for $q \geq 3$. This paper also presents list-decoding algorithms that efficiently correct even more errors for the same codes over $\rm{F}_q$. Finally, this paper shows that the increase from $\lfloor (q-1)t/2 \rfloor$ errors to more than $\lfloor qt/2 \rfloor$ errors allows considerably smaller keys to achieve the same security level against all known attacks. Keywords: McEliece cryptosystem, Niederreiter cryptosystem, Goppa codes, wild Goppa codes, list decoding.
Original languageEnglish
PublisherIACR
Number of pages17
Publication statusPublished - 2010

Publication series

NameCryptology ePrint Archive
Volume2010/410

Fingerprint

Dive into the research topics of 'Wild McEliece'. Together they form a unique fingerprint.

Cite this