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.

Snow 3G is the backup encryption algorithm used in the mobile phone UMTS technology to ensure data confidentiality. Its design - a combiner with memory - is derived from the stream cipher Snow 2.0, with improvements against algebraic cryptanalysis and distinguishing attacks. No attack is known against Snow 3G today. In this paper, a fault attack against Snow 3G is proposed. Our attack recovers the secret key with only 22 fault injections.

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 ⁴ ) operations in F _q , where n denotes the code length. Compared to previous attacks, the present one allows to recover a decoding algorithm for the public key even for codes from high genus curves.

It has been widely known that complete decoding for binary linear codes can be regarded as a linear integer programming problem with binary arithmetic conditions. Conti and Traverso [9] have proposed an algorithm which uses Gröbner bases to solve integer programming with ordinary integer arithmetic conditions. Ikegami and Kaji [12] extended the Conti-Traverso algorithm to solve integer programming with modulo arithmetic conditions. It is natural to consider for those problems the Graver basis associated to them which turns out to be the minimal cycles of the matroid associated to the code, i.e. minimal support codewords in the binary case and its geometry. This provides us a universal test set for the programs considered.