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

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 <italic>error correcting pair (ECP)</italic>, or an <italic>error correcting array (ECA)</italic> from the single data of an arbitrary generator matrix of a code. An ECP provides a decoding algorithm, that corrects up to <inline-formula> <tex-math notation="LaTeX">$(({d^{*}-1-g})/{2})$ </tex-math></inline-formula> errors, where <inline-formula> <tex-math notation="LaTeX">$d^{*}$ </tex-math></inline-formula> denotes the designed distance and <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> denotes the genus of the corresponding curve, while with an ECA the decoding algorithm corrects up to <inline-formula> <tex-math notation="LaTeX">$(({d^{*}-1})/{2})$ </tex-math></inline-formula> errors. Roughly speaking, for a public code of length <inline-formula> <tex-math notation="LaTeX">$n$ </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">$ \mathbb {F}_{q}$ </tex-math></inline-formula>, these attacks run in <inline-formula> <tex-math notation="LaTeX">$O(n^{4}\log (n))$ </tex-math></inline-formula> operations in <inline-formula> <tex-math notation="LaTeX">$\mathbb F_{q}$ </tex-math></inline-formula> for the reconstruction of an ECP and <inline-formula> <tex-math notation="LaTeX">$O(n^{5})$ </tex-math></inline-formula> operations for the reconstruction of an ECA. A probabilistic shortcut allows to reduce the complexities respectively to <inline-formula> <tex-math notation="LaTeX">$O(n^{3+\varepsilon } \log (n))$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$O(n^{4+\varepsilon })$ </tex-math></inline-formula>. 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.