Is key size the only barrier to the adoption of the McEliece cryptosystem, or is it considered broken/potentially vulnerable?

Question

A recent paper showed that the McEliece cryptosystem is not, unlike RSA and other cryptosystems, weakened as drastically by quantum computing because strong Fourier sampling cannot solve the hidden subgroup problem.

However, in 2008, new parameters were proposed after the old ones were found to be vulnerable.

So my question – as someone who hasn't much knowledge on this particular cryptosystem – is: Why isn't it in greater usage?

It would seem that if the promise of quantum computing is fulfilled, we may soon have need for cryptosystems not vulnerable to it. So, is the requirement for a large matrix (and therefore a large key) the only barrier, or are there other concerns/potential weaknesses? Or is there a better candidate for a post-quantum public key system?

Answer 1

The huge key is definitely an issue. Another is the lack of standardization or recommendations. Should you use OAEP with McEliece, or some other padding? What parameters are actually secure? And so on.

Part of the problem is that, while it has been around since the 70s, it was not considered particularly interesting until quite recently—so it probably hasn't had that many research years spent on its security properties. And so far as I know, it's never been deployed in the real world.

Other potential candidates for post-quantum crypto include NTRU and HFEv-, which are fast and have small keys. Unfortunately, both are patented. If you're interested in post-quantum cryptography, I would highly recommend picking up Post-Quantum Cryptography by Bernstein, et al, which is a good survey text.

Answer 2

Wide adoption of an asymmetric encryption algorithm, or a digital signature algorithm, requires at least the following:

• There must exist a reasonably clear standard which unambiguously says where each byte goes. It must cover endianness and similar issues. PKCS#1 is such a standard, for RSA.

• The algorithm must provide reasonably good performance, in particular with regards to key size, signature size (when signing), data overhead (when encrypting), CPU cost of private and public key operations, and code size. Note that "reasonable" is a relative notion. Right now, the basis for comparison is RSA.

• The algorithm must rely on not-too-complex mathematics (e.g. BLS signatures have a huge handicap there, due to the pairing which relies on field extensions and rational functions over some specially crafted elliptic curves, and most engineers have trouble grokking that). This is needed even when using an existing implementation, because adopters must have a feeling that they somehow understand what is going on.

• RSA must die.

This last point is critical. The continued life of RSA, specifically RSA as with the PKCS#1 v1.5 ("old-style") padding, currently prevents wide adoption of not only ECDSA, but also the newer RSA PKCS#1 padding (PSS). DSA is relatively widely supported only because it was a US federal must-have standard, and this was due to the RSA patent (which has expired ten years ago). People who need signatures or asymmetric encryption use RSA because RSA is the most widely supported algorithm, and this makes RSA even more widely supported. RSA has built momentum.

Assuming that a quantum computer can be built, RSA, DSA and ECDSA are killed, and the McEliece / Niederreiter key size, while still big, is less "unreasonable" since the competition has disappeared. Mathematics of McEliece are "easy" (mere linear algebra). It would still require someone stepping out and writing a standard. But without the quantum computer, RSA remains, so no McEliece.

As for security, there is no known serious flaw in McEliece, only a general lack of interest (maybe if it were widely deployed would people begin to look at it seriously).

Answer 3

We looked into post-quantum digital signature schemes for the Tahoe-LAFS "100 Year Cryptography" project but I stopped looking at all but one of them when David-Sarah Hopwood observed that they all rely on a secure hash function to generate a message representative for the digital signature scheme to sign. Therefore, all of them (except for that one) are vulnerable to either a break of the digital signature scheme or a break of the secure hash function. The one remaining one is hash-based digital signatures.

Hash-based digital signature schemes are secure if the underlying hash function is secure (of course we can and should be more precise about what we mean by "secure" here, but this is good enough for now). Therefore, a hash-based digital signature scheme has one fewer ways to break than any other scheme. That is: a hash-based digital signature scheme can be broken if you can break the underlying secure hash function. All other digital signature schemes can be broken if you can break the secure hash function that they use for generating a message representative, or if you can break the digital signature scheme itself.

So, for Tahoe-LAFS's "100 Year Cryptography" project, we are looking at using hash-based digital signatures. Unfortunately, the best designs we've found or invented so far are still somewhat efficient in both processing time and key size, compared to a high performance quantum-vulnerable scheme like the new ed25519 which can take maybe 88,000 cycles to do a signature or around 280,000 cycles to do a verification (on certain modern Intel chips), with a public key of size 32 bytes and a signature size of 64 bytes.

Julian Wälde has implemented a hash-based digital signature scheme (warning: the details of the scheme have not been widely vetted, so this particular scheme might not retain the security guarantee, predicated on the security of the underlying secure hash function, that I alluded to above), and reported 4 signatures per second, 1700 verifications per second, a public key size of 32 bytes, and signature size of 11,000 bytes. If we assume Julian's development machine is a modern Intel chip running at 2.4 GHz, then it took about 600,000,000 cycles to sign and about 1,400,000 cycles to verify.

On the other hand, it compares well in certain respects to other post-quantum crypto schemes, like McEliece. The Bernstein, Lange, Peters paper you referenced proposes parameters for 128-bit security McEliece signatures in which the public key is 192,000 bytes. That makes the 11,000 byte public keys in Julian's hack look not as terrible.

In fact, Julian's scheme may already perform well enough for our purposes, without any further performance improvements. See the Tahoe-LAFS mailing list for discussion of that.

Answer 4

A problem with the original McEliece construction is the large keys of size up to megabytes. It has motivated various attempts to decrease the key sizes but most of them have been unsuccessful. Recently however, a very interesting version of the McEliece PKC was Proposed, the [QC-MDPC scheme]. This is a McEliece PKC that uses so-called moderate density parity check codes (MDPC codes) in quasi-cyclic (QC) form. The quasi-cyclic form allows us to represent a matrix by its first row, which leads to a small public key]