Computational aspects of retrieving a representation of an algebraic geometry code (Q2437321)

Since the discovery of a polynomial time algorithm to factor numbers on a quantum computer (Shor algorithm) the interest in cryptographic primitives that are resistent against this algorithm has augmented. One of these so called post-quantum cryptographic primitives comes from coding theory. Two related encryption schemes have been proposed by Niederreiter and McEliece. The underlying trap door function is based on the fact, that decoding of a general linear code is hard, efficient decoding is possible only if the code has some extra structure. So this extra structure is the secret in the scheme. The original paper of McElice uses a \([1024,524,101]\) binary Goppa Code. Several investigations have been made in the meantime to use other Codes. The authors of this paper describe a structural attack against the use of so called very strong algebraic geometric codes, i.e. geometric codes represented by a triple \(({\mathcal X},{\mathcal P}, E)\) where \(\mathcal X\) is a curve over some finite field \(\mathbb{F}_{q}\) of genus \(g\), \(\mathcal P\) are \(n\) distinct rational points and \(E\) is a divisor of degree \(m\) with \(2g+2\leq m < n/2\) or \(n/2+2g-2<m\leq n-4\). A structural attack is one which aims to discover the hidden structure if only the code is given by its generator matrix. Marquez-Corbella et al. show and illustrate their results with two detailed examples how to get a curve \(\mathcal Y\), a collection of rational points \(\mathcal Q\) and a divisor \(F\) out of the generator matrix, such that \(({\mathcal Y}, {\mathcal Q}, F)\) is equivalent to the original \(({\mathcal X}, {\mathcal P}, E)\). The paper contains some trivial typos and in the second example the order of the base elements of the Riemann-Roch space is confused. It should be \(x_1,x_2,x_1^2, x_1x_2,x_2^2,x_1^3,x_1^2x_2,x_1x_2^2,x_2^3\). The construction of the curve \(\mathcal Y\) was developed in [\textit{I. Márquez-Corbella} et al., Des. Codes Cryptography 70, No. 1--2, 215--230 (2014; Zbl 1312.14075)]. The current paper answers mainly the question how to efficiently get the divisor \(F\). Although there are efficient decoding algorithms for AG-Codes it remains open how to get an efficient decoding algorithm for a given triple \(({\mathcal Y}, {\mathcal Q},F)\).