Error-correcting pairs and arrays from algebraic geometry codes

The security of the most popular number-theory public key crypto (PKC) systems will be devastatingly affected by the success of a large quantum computer. Code-based cryptography is one of the promising alternatives that are believed to resist classical and quantum computer attacks. Many families of codes have been proposed for these cryptosystems, one of the main requirements is having an efficient t-bounded decoding algorithm. In [16, 17] it was shown that for the so called very strong algebraic geometry codes C which is a collection of codes C = CL(X,P,E), where X is an algebraic curve over Fq, P is an n-tuple of mutually distinct Fq-rational points of X and E is a divisor of X with disjoint support from P, an equivalent representation can be found. Moreover in [19] an efficient computational approach is given to retrieve a triple that is isomorphic with the original representation, and, from this representation, an efficient decoding algorithm is obtained. In this talk, we will show how an efficient decoding algorithm can be retrieved from an algebraic geometry code C by means of error-correcting pairs [20] and arrays directly, that is without the detour via the representation (X,P,E) of the code C = CL(X,P,E). As a consequence we will have that algebraic geometry codes with certain parameters are not secure for the code-based McEliece public key cryptosystem. Keywords: Code based cryptography, McEliece public key cryptosystem, algebraic geometry codes, error-correcting pairs and arrays.