1

The length of public-key matrix in McEliece cryptosystem is $n \times k$. Then the key size is $\frac{n \times k}{8}$ bytes. But I find that the key size is $\frac{(n-k) \times k}{8}$ bytes. why ?

Raoul722
  • 2,836
  • 2
  • 20
  • 39
Nour28
  • 23
  • 3

1 Answers1

5

Let $G$ be the public key matrix. With Gaussian elimination, you can find a Matrix $G'$ with $G = (E_k | G')$, where $E_k$ is the identity matrix with dimension $k$. Then, you only have to store $G'$. And $G'$ has the dimension $(n-k) \times k$.

Source: German Wikipedia (https://de.wikipedia.org/wiki/McEliece-Kryptosystem)

Christine
  • 343
  • 2
  • 5