Score:1

What is the security implication of non-full-rank systematic matrix in McEliece cryptosystem?

jp flag

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?

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.