Wild McEliece

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

33 Citations (Scopus)
1 Downloads (Pure)

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.
Original languageEnglish
Title of host publicationSelected Areas in Cryptography (17th International Workshop, SAC 2010, Waterloo, Ontario, Canada, August 12-13, 2010, Revised Selected Papers)
EditorsA. Biryukov, G. Gong, D.R. Stinson
Place of PublicationBerlin
PublisherSpringer
Pages143-158
ISBN (Print)978-3-642-19573-0
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6544
ISSN (Print)0302-9743

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

Cite this