## Smaller Decoding Exponents:
Ball-Collision Decoding

**Daniel J. Bernstein, Tanja Lange, and Christiane Peters**

*
University of Illinois at Chicago, USA;
Technische Universiteit Eindhoven, Netherlands;
and Technische Universiteit Eindhoven, Netherlands*
**Abstract.**
Very few public-key cryptosystems are known that can encrypt and
decrypt in time *b*^{2+o(1)}
with conjectured security level 2^{b}
against conventional computers and quantum computers. The oldest of
these systems is the classic McEliece code-based cryptosystem.

The best attacks known against this system are generic decoding attacks
that treat McEliece’s hidden binary Goppa codes as random
linear codes. A standard conjecture is that the best possible *w*-error-decoding
attacks against random linear codes of dimension *k* and length *n*
take time 2^{(α(R,W)+o(1))n}
if *k*/*n*→*R* and *w*/*n*→*W* as *n*→∞.

Before this paper, the best upper bound known on the exponent α(*R*,*W*)
was the exponent of an attack introduced by Stern in 1989. This paper introduces
“ball-collision decoding” and shows that it has a smaller exponent for
each (*R*,*W*): the speedup from Stern’s algorithm to
ball-collision decoding is exponential in *n*.

**Keywords:**
McEliece cryptosystem, Niederreiter cryptosystem, postquantum
cryptography, attacks, information-set decoding, collision decoding.