Paper 2014/064

A Polynomial Time Attack against Algebraic Geometry Code Based Public Key Cryptosystems

Alain Couvreur and Irene Márquez-Corbella and Ruud Pellikaan

Abstract

We give a polynomial time attack on the McEliece public key cryptosystem based on algebraic geometry codes. Roughly speaking, this attacks runs in $O(n^4)$ operations in $\mathbb F_q$, where $n$ denotes the code length. Compared to previous attacks, allows to recover a decoding algorithm for the public key even for codes from high genus curves.