Efficient decoding of irreducible binary Goppa codes and the role of matrix P in McEliece cryptosystem

Question

If we assume that the support for an irreducible binary Goppa code $\gamma_1, ..., \gamma_n$ is publicly known, when is it possible to efficiently decode the code? I know it's possible if one knows the generator polynomial $g(x)$, and also, if one can obtain a parity check matrix $H$ of the form $XYZ$, where

$ X = \left( \begin{array}{cccc} g_t & 0 & \dots & 0 \\ g_{t-1} & g_t & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ g_1 & g_2 & \dots & g_t \\ \end{array}\right) $

$ Y = \left( \begin{array}{cccc} 1 & 1 & \dots & 1 \\ l_1 & l_2 & \dots & l_n \\ l_1^2 & l_2^2 & \dots & l_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ l_1^{t-1} & l_2^{t-1} & \dots & l_n^{t-1} \\ \end{array}\right) $

$ Z = \left( \begin{array}{cccc} \frac{1}{g(l_1)} & & & \\ & \frac{1}{g(l_2)} & & \\ & & \ddots & \\ & & & \frac{1}{g(l_n)} \\ \end{array}\right) $

as in the paper by Engelbert, Overbeck and Schmidt (1, 2), since here we are able to recover a multiple of the matrix $X$ and so a multiple of g(x) which generates the same code. My question is, is it possible to efficiently decode the code whenever one knows ANY generator matrix or ANY parity check matrix for the binary irreducible Goppa code?

Also, on p.15, Sec. 3.1 of the Engelbert et al. paper an attacker is assumed to know a generator matrix $SG'$ for the Goppa code and a corresponding systematic check matrix $H'$. The attacker is then assumed to be able to recover matrices P an M such that $M^{-1}H'P^{-1}=H$ where $H=XYZ$ is of the above form (and thus, decode the code). Why is this assumption feasible? How would an attacker know at all when $H=XYZ$? Also, why should H generate the same subspace as H'?

Finally, the section 3.1 of the paper claims that if in a McEliece system with public code generator matrix $G=SG'P$ the matrix $P$ is revealed, then it is possible to recover $g(x)$. How? The only way I can think of it is that if $c$ is a codeword in a code generated by $SG'P$ then $cP^{-1}$ is a codeword in a Goppa code generated by $SG'$ and so the syndrome $S_{cP^{-1}}(x)=\sum (cP^{-1})_i/(X-\gamma_i)$ which the attacker can calculate is congruent to zero modulo $g(x)$. Is this a way to obtain $g(x)$?

Answer 1

If one knows $\gamma_1,\cdots,\gamma_n$ and $g(x)$ then for any $n$-long binary vector $V$ one can form the polynomial $$v(x):=\prod_{i:V\cdot e_i} (x-\gamma_i)$$ and the syndrome polynomial $s(x)=v'(x)/v(x)\pmod{g(x)}$. This is all the information required by Paterson's decoding algorithm, independent of the basis used for the generator matrix and/or parity check matrix.

Section 3.1 should be read as an argument of the importance of keeping $M$ and $P$ secret as they are essentially the private key. It should be a very unreasonable assumption that the attacker can obtain these as this would break the system.

The recovery of $g(x)$ starts off as pretty much as you describe. For $V$ any codeword, compute the corresponding $v'(x)$ which we know is a multiple of $g(x)$. If we do this for two codewords, we can take the GCD which must also be a multiple of $g(x)$. After a handful of GCDs we have almost certainly recovered $g(x)$.

Note that that there is a equivalence between Goppa codes where columns are relabelled according to a linear function and $g(x)$ undergoes the corresponding linear change of variable. Recovering the columns labels of any equivalent code would also allow decoding.