McEliece key size

Question

There's a lot of references about McEliece key size being the barrier for proper usage of the algorithm, exactly (or roughly) how large are the keys?

Answer 1

As you probably know the public key in McEliece is an $k \times n $ binary matrix, encoding a generator matrix for a randomly permuted Goppa code (i.e. $G_{\mathsf{pub}} = SGP$, where $S$ is any $k \times k$ invertible binary matrix, $G$ a $k \times n$ generator matrix for an $(n, k, t)$ binary Goppa code, and $P$ a $n \times n$ permutation matrix).

McEliece originally proposed the use of a (1024,524,101) binary Goppa code. That would translate to a public key size of roughly 32kB (calculated as: $(n-k) \times k / (8 * 2^{10})$). However, later cryptanalysis have made this choice of parameters obsolete. More up-to-date parameter sets can be found here (Table 2). Drawing a few values from that table we have:

• For an expected security level of $2^{80}$ using a (1702,1219,91) code: 72kB;
• For an expected security level of $2^{96}$ using a (2440,1877,101) code: 129kB;
• For an expected security level of $2^{109}$ using a (2804,2048,133) code: 189kB.

Answer 2

McEliece public keys need about 100 kByte to 1 MByte depending on the desired security level.

• 65 kB for 80 bits of security (too low, corresponds to 1024 bit RSA)
• 150 kB for 112 bits of security
• 220 kB for 128 bits of security
• 1000 kB for 256 bits of security

The McBits paper contains the following table: