For the McEliece/Niederreiter cryptosystems, an efficient seemingly secure choice of code is an irreducible binary Goppa code, defined by an irreducible $g(x)\in GF(2^m)[x]$ of degree $t$ and a support vector $L=(\alpha_0,\ldots,\alpha_{n-1})$ with distinct $\alpha_i\in GF(2^m)$.
The code itself is the $GF(2)$-valued vectors in the kernel of the parity-check matrix
$$
H=\left(
\begin{array}{cccc}
g(\alpha_0)^{-1}&g(\alpha_1)^{-1}&\ldots&g(\alpha_{n-1})^{-1}\\
g(\alpha_0)^{-1}\alpha_0&g(\alpha_1)^{-1}\alpha_1&\ldots&g(\alpha_{n-1})^{-1}\alpha_{n-1}\\
\vdots&\vdots&\ldots&\vdots\\
g(\alpha_0)^{-1}\alpha_0^{t-1}&g(\alpha_1)^{-1}\alpha_1^{t-1}&\ldots&g(\alpha_{n-1})^{-1}\alpha_{n-1}^{t-1}\\
\end{array}\right).
$$
Note that $H$ is full-rank. To produce a parity-check matrix $H'$ over $GF(2)$, one can replace the entries of $H$ with column vectors in $GF(2)$ (using some basis for the extension $GF(2^m)/GF(2)$).
Almost all sources I consult list the resulting code as $[n,k]=[n, n-mt]$, but the general construction (say for alternant codes) gives $k=n-mt$ as a lower bound for the dimension $k$ of the resulting subspace code.
My questions are:
- How often is the resulting rank $k=n-mt$? In the AG setup, I guess this is a Riemann-Roch dimension so maybe an algebraic geometer can answer.
- Does it matter if we have redundant rows in the parity-check $H'$? Does this affect implementations of the cryptosystem?
I guess this addressed in the key generator from https://eprint.iacr.org/2017/595.pdf (section 5.2), if only to return a failure and restart the key generation process when rref isn't achieved; they give 29% as a probability of success based on the density of $GL_{mt}(GF(2))$ in $Mat_{mt\times mt}(GF(2))$, i.e. the asymptotic density is
$$
\prod_{i=1}^{\infty}\left(1-\frac{1}{2^i}\right)=0.288\ldots.
$$
On second thought regarding 1), I guess it's more of a question about when the kernel of a linear map is defined over a subfield (e.g. the kernel of $x-\sqrt{2}y$ has dimension one over $\mathbb{Q}(\sqrt{2})$ but dimension zero when restricted to $\mathbb{Q}$).