Generalization of the Ball-Collision Algorithm
University of Zurich
Department of Mathematics
Since 1978 it is known that decoding a random linear code is an NP-complete problem, this was shown by Berlekamp, McEliece and van Tilborg. One of the methods to decode a random linear code is called Information Set Decoding (ISD). Many improvements for the ISD algorithm over the binary field have been suggested, among them is the ball-collision algorithm by Bernstein, Lange and Peters. The problem of decoding a random linear code has recently received prominence with the McEliece cryptosystem, since ISD attacks on this cryptosystem determine the choices of secure parameters and hence the key size. Since some of the new variants of the McEliece cryptosystem involve codes over general finite fields, we present in this talk the generalization of the ball-collision algorithm to an arbitrary finite field.
Violetta Weger obtained her degree in mathematics at the University of Zurich and is now a Ph.D. student at the Zurich Graduate School in Mathematics working under the supervision of Professor Joachim Rosenthal.