Cryptanalysis of Public-key Cryptosystems Based on Algebraic Geometry Codes

Abstract

This paper addresses the question of retrieving the triple $(\mathcal{X},\mathcal{P},\mathcal{E})$ from the algebraic geometry code $\mathcal{C}_L(\mathcal{X},\mathcal{P},\mathcal{E})$, where $\mathcal{X}$ is an algebraic curve over the finite field $\mathbb{F}_q, \mathcal{P}$ is an $n$-tuple of $\mathbb{F}_q$-rational points on $\mathcal{X}$ and $E$ is a divisor on $\mathcal{X}$. If deg($E$) $\geq 2g + 1$ where $g$ is the genus of $\mathcal{X}$, then there is an embedding of $\mathcal{X}$ onto $\mathcal{Y}$ in the projective space of the linear series of the divisor $E$. Moreover, if deg($E$) $\geq 2g + 2$, then $I(\mathcal{Y})$, the vanishing ideal of $\mathcal{Y}$, is generated by $I_2(\mathcal{Y})$, the homogeneous elements of degree two in $I(\mathcal{Y})$. If $n > 2$ deg($E$), then $I_2(\mathcal{Y}) = I_2(\mathcal{Q})$, where $\mathcal{Q}$ is the image of $\mathcal{P}$ under the map from $\mathcal{X}$ to $\mathcal{Y}$. These two results imply that certain algebraic geometry codes are not secure if used in the McEliece public-key cryptosystem.