3
$\begingroup$

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?

$\endgroup$

2 Answers 2

4
$\begingroup$

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.
$\endgroup$
2
$\begingroup$

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:

Table from McBits paper

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.