A Criterion to Determine True Minimum Distances of Goppa Codes

Abstract

Goppa codes play an important role in code-based cryptography due to their efficient decoding algorithms and their use as underlying private codes in the McEliece cryptosystem. To determine the true minimum distances of Goppa codes is a notoriously difficult problem. In this paper, we establish a criterion for a Goppa code to attain its designed distance. We consider Goppa polynomials of the form $G(x)=U(x)H(x)+V(x)H^{\prime }(x)$, where $°(G)=t$ and $H(x)\in {\mathbb{F}}_q[x]$ is a monic irreducible polynomial of degree $t+1$ whose roots are contained in the support $L$. We prove that the corresponding Goppa code $\Gamma (L,G)$ contains a codeword of weight $t+1$ if and only if \[ \frac{V(α_{i_{t+1}})}{V(α_{i_j})}\in\mathbb{F}_q^*, \qquad 1\leq j\leq t, \] where ${\alpha }_{i_1},\dots ,{\alpha }_{i_{t+1}}$ are the roots of $H(x)$. Based on this criterion, we derive a general family of Goppa codes that attain their designed distance by developing an interpolation-based construction of Goppa polynomials. We further obtain families of Goppa codes whose Goppa polynomials are determined by considering monomial, binomial, and their product of the auxiliary polynomial $V(x)$. By taking $H(x)$ to be different irreducible binomials and trinomials, we obtain several explicit families of Goppa codes whose minimum distances are equal to designed distance.

arXiv comment26 pages, 5 tables