The Classic McEliece cryptosystem has the following key generation procedure:

  1. Choose a field $\mathbb{F}_{2^m}$, an irreducible polynomial $g(x)$ of degree $t$, and $n$ field elements $\alpha_1, \cdots, \alpha_n$.
  2. Build the $t \times n$ matrix $\tilde{H} = (h_{ij}), h_{ij} = \frac{\alpha_j^{i - 1}}{g(\alpha_j)}$
  3. Replace each component in $\tilde{H}$ with a binary vector of length $m$, to get a matrix $\hat{H}$ of size $mt \times n$.
  4. 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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.