The Classic McEliece cryptosystem has the following key generation procedure:
- Choose a field $\mathbb{F}_{2^m}$, an irreducible polynomial $g(x)$ of degree $t$, and $n$ field elements $\alpha_1, \cdots, \alpha_n$.
- Build the $t \times n$ matrix $\tilde{H} = (h_{ij}), h_{ij} = \frac{\alpha_j^{i - 1}}{g(\alpha_j)}$
- Replace each component in $\tilde{H}$ with a binary vector of length $m$, to get a matrix $\hat{H}$ of size $mt \times n$.
- Reduce $\hat{H}$ to the row-echelon form $H$ (called "systematic form")
The NIST proposal says that if $H$ does not have full-rank (meaning, there are empty rows in the row-echelon form), then the key should be abandoned. This paper (p.8) claims without proof that the non-full-rank situation is extremely rare, with probability less than $2^{-256}$.
What would be the security implication if one uses a non-full-rank public key? Since they are very rare, would it be much easier to find the private key if one knows the public key has $r$ empty rows?
