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 and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.