Applied Algebra Group at the University of Zürich


Generalization of Algorithms for Decoding Random Linear Codes

Nicole Rohrer's talk
Date: 21.11.18   Time: 15.00 - 17.00   Room: Y27H12

In post-quantum cryptography, the McEliece cryptosystem is one of the main candidates to replace current public key cryptosystems, such as RSA. It has been shown to be NP-complete using Goppa codes. However, information set decoding (ISD) attacks still need to be considered. A major drawback of the McEliece scheme implemented with Goppa codes is its large public key size. An idea of how to reduce it, without lowering its security, is to implement the code over a general finite field.
One of the more recent and most efficient ISD attacks is the ball-collision decoding attack published by Bernstein, Lange, and Peters in 2010. In this talk, we look at the binary ball-collision decoding algorithm and present our generalization of it to general finite fields. We analyze its complexity and give some parameter examples.