Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

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.
share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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