Structural Cryptanalysis of McEliece Schemes with Algebraic Geometry codes
Résumé
Code-based Cryptography together with lattice-based cryptography, multivariate cryptography and hash-based cryptography are the principal available techniques for Post-quantum cryptography. McEliece proposed the first cryptosystem based on the theory of error correcting codes in 1978. The principle of code-based cryptography is based on the following one-way trapdoor function: it is easy and fast to encode a message using linear transformation;
but the general decoding problem was proven to be NP-complete in 1978 for the Hamming metric. Decoding is also believed to be hard for a quantum computer. The trapdoor information is that there exists families of codes that have efficient decoding algorithms.
McEliece proposed to use binary Goppa codes. But several proposals based on other families of algebraic codes appeared in the literature. For instance, Generalized Reed-Solomon codes, subcodes of them and Binary Reed-Muller codes. All of these shemes are subject to polynomial or sub-exponential time attacks.
Another attempt, suggested by Janwa and Moreno was to introduce Algebraic Geometry codes. This scheme was broken for codes on curves of genus g 2 by Faurer and Minder. However this attack has several drawbacks which makes it impossible to extend to higher genera. In this talk we present a general attack against this proposal based on square
code considerations, that is the component wise product of codewords. The point is that evaluation codes do not behave like random codes with respect to the star product “the square of Algebraic Geometry codes has smaller dimension than that of the square of a random code of the same dimension”.
The attack presented in this talk consist in pushing this argument forward in order to compute a filtration of the public code by a family of very particular subcodes. This filtration methods yields to an Error Correcting Pair of the public code in O(n4) operations in Fq where n denotes the code length. This Error-Correcting Pair allows to decrypt any encrypted message in O(n3) operations. This alternative attack has been implemented in Magma and broke for instance a [729; 404] 126–error correcting Hermitian code (with genus 36) over F81 (which had 182-bits security with respect to ISD attacks)in 21 minutes. Using an Intel r CoreTM 2 Duo 2.8 GHz.