On the unique representation of very strong algebraic geometry codes (Q2436568)

Given an algebraic geometry code \(\mathcal{C}=\mathcal{C}_{\mathcal{L}}(\mathcal{X},\mathcal{P},E)\), where \(\mathcal{X}\) is an algebraic curve over the finite field \(\mathbb{F}_q\), \(\mathcal{P}\) is a set of \(n\) \(\mathbb{F}_q\)--rational points on \(\mathcal{X}\), and \(E\) is a divisor on \(\mathcal{X}\). The problem of retrieving the triple \((\mathcal{X},\mathcal{P},E)\) from the generator matrix of \(\mathcal{C}\) is of great interest. In this paper, the author shows (under some condition on \(\deg(E)\)) how to find an AG--representation \((\mathcal{Y},\mathcal{Q},F)\) of the code \(\mathcal{C}\), where \(\mathcal{Y}\) is the image of \(\mathcal{X}\) under the embedding of the linear series of the divisor of \(E\) and \(Q\) is the image of the points in \(P\) and \(F\) is the image of \(E\) under the embedding \(\phi_E:X \to Y\). Moreover, \((\mathcal{X},\mathcal{P},E)\) and \((\mathcal{Y},\mathcal{Q},F)\) are stictly isomorphic, i.e., \(\phi_E(E) \equiv_\mathcal{Q} F\). The main result of this paper is that under the hypothesis \(2g+2 \leq \deg(E) \leq \frac{n}{2}\), an AG--representation \((\mathcal{Y},\mathcal{Q},F)\) of \(\mathcal{C}\) can be obtained using only the generator matrix of \(\mathcal{C}\), where \(\mathcal{Y}\) is as above, a normal curve in \(\mathbb{P}^{\deg(E)-g}\). Moreover, The vanishing ideal of \(\mathcal{Y}\) is generated by degree two homogeneous elements, i.e., \(I(Y)=I_2(Y)\). The authors shows also that under the hypothesis above, \(I_2(Y)=I_2(Q)\), i.e., the quadratic polynomials that vanish on \(\mathcal{Q}\) generate the ideal of \(\mathcal{Y}\). Also an efficient algorithm to compute \(I_2(Q)\) is provided. This means an efficient decoding algorithm can be found to decode very strong algebraic geometry code (VSAG) from its generator matrix. This means a McEliece public key cryptosystem is vulnerable to cryptanalysis if it is used with VASG for some range of \(\deg(E)\).