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 _q , these attacks run in O(n ⁴ log(n)) operations in F _q for the reconstruction of an ECP and O(n ⁵ ) operations for the reconstruction of an ECA. A probabilistic shortcut allows to reduce the complexities respectively to O(n ³ ±ε log(n)) and O(n ⁴ ±ε). 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.

This paper defines the $q$-analogue of a matroid and establishes several properties like duality, restriction and contraction. We discuss possible ways to define a $q$-matroid, and why they are (not) cryptomorphic. Also, we explain the motivation for studying $q$-matroids by showing that a rank metric code gives a $q$-matroid.

This paper investigates the generalized rank weights, with a definition implied by the study of the generalized rank weight enumerator. We study rank metric codes over $L$, where $L$ is a finite extension of a field $K$. This is a generalization of the case where $K=\mathbb{F}_q $ and $L={\mathbb{F}_{{q^m}}}$ of Gabidulin codes to arbitrary characteristic. We show equivalence to previous definitions, in particular the ones by Kurihara-Matsumoto-Uyematsu ^[12,13], Oggier-Sboui ^[16] and Ducoat ^[6]. As an application of the notion of generalized rank weights, we discuss codes that are degenerate with respect to the rank metric.