Cryptanalysis of McEliece Cryptosystem Based on Algebraic Geometry Codes and Their Subcodes

Abstract

We give polynomial time attacks on the McEliece public key cryptosystem-based either on algebraic geometry (AG) codes or on small co-dimensional subcodes of AG codes. These attacks consist in the blind reconstruction either of an error correcting pair (ECP), or an error correcting array (ECA) from the single data of an arbitrary generator matrix of a code. An ECP provides a decoding algorithm, that corrects up to ((d* - 1 - g)/2) errors, where d* denotes the designed distance and g denotes the genus of the corresponding curve, while with an ECA the decoding algorithm corrects up to ((d* - 1)/2) errors. Roughly speaking, for a public code of length n over F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> , these attacks run in O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> log(n)) operations in F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> for the reconstruction of an ECP and O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">5</sup> ) operations for the reconstruction of an ECA. A probabilistic shortcut allows to reduce the complexities respectively to O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">3</sup> ±ε log(n)) and O(n <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> ±ε). Compared with the previous known attack due to Faure and Minder, our attack is efficient on codes from curves of arbitrary genus. Furthermore, we investigate how far these methods apply to subcodes of AG codes.