Talk: Violetta Weger (July 18, 2019 at 10:50 AM, LNT Library N2405)


On July 18, 2019 at 10:50 AM, Violetta Weger from University of Zurich will be giving a talk in the LNT Library N2405 about "Generalization of the Ball-Collision Algorithm".

Generalization of the Ball-Collision Algorithm

Violetta Weger

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.