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?
2 Answers
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.
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: