2
$\begingroup$

I understand that the McEliece cryptosystem is an asymmetric encryption algorithm developed in 1978 by Robert McEliece, almost around the same time RSA came about.

Why has the McEliece cryptosystem never gained much acceptance in the cryptographic community, but now is a candidate for post-quantum cryptography?

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Short answer: Huge keys, but no Shor. $\endgroup$
    – yyyyyyy
    Feb 28 '18 at 9:37
3
$\begingroup$

The simple answer is that there are two reasons:

  1. The lack of a standard implementation. RSA has an acknowledged standard while McEliece doesn't.
  2. The size of the key. It's huge! In the multi-megabit range. In terms of today's communication networks, that is bad, but - in my opinion - not too bad. It means it takes time to exchange, but once you have built up your local DB of keys for actors that you communicate with, well, so what. But storing the keys is another matter. You can't just pop them in to a varchar field: you need to really think about your local key storage issues.

That said, I think that there is a definite use case for McEliece coming. Especially if you have secrets that have to be secure for a long period of time.

Current PKE used for thanks like SSL and bank transactions is fine: the time to live for the transaction is relatively small. But think of the security around a property transaction using smart contracts: lots of property is held for > 20 years. If the title deeds are proven via a secure document then you need the security on that document to live at least that long - probably many times that length.

Just for fun, I downloaded a version of McEliece called CodeCrypt, compiled that and generated a key. It took 9 minutes of CPU time!

Now, if I have done this all correctly, the public key is only 4K, and the private secret 20K, which is either way too short, or (more probably) I have made a mistake somewhere.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Currently your answer reads "The size of the key". But, as we're talking about asymmetric crypto, please indicate which key, public or private or both. $\endgroup$
    – Maarten Bodewes ♦
    Feb 28 '18 at 10:43
  • $\begingroup$ Hello Adrian. Please note that you can edit your existing answer instead of posting a new one. For your convenience, I've merged both. $\endgroup$
    – e-sushi
    Feb 28 '18 at 12:53
  • 1
    $\begingroup$ Actually, CodeCrypt does not use McEliece, instead, it uses QC-MDPC $\endgroup$
    – poncho
    Feb 28 '18 at 13:53
  • 1
    $\begingroup$ There are modern implementations of McEliece's ideas—with better analysis for the parameter sizes, and better implementation strategies for serious performance. May I suggest comparing the Classic McEliece submission to NIST PQCRYPTO? (There are a few other related submissions too, but that one is closest to the original McEliece cryptosystem.) $\endgroup$
    – Squeamish Ossifrage
    Feb 28 '18 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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