Wild McEliece

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.