Goodbye to the 64-byte public keys of ECDH and Hello to 640KB public keys?

Mceliece is more suited to public key encryption than key exchange?

And, so, one thing we know from Peter Shorr is that quantum computers will break discrete log and elliptic curve problems. Over the next few years, we will have to deprecate ECDH (Elliptic Curve Diffie Hellman) and move towards a quantum robust approach. A note here is that ECDH is involved in virtually every connection we make with a website — so it’s a critical part of the Web.

For this, NIST is proposing that the Kyber lattice method will replace ECDH. For this, our 64-byte public key value that Bob and Alice will pass to each other will rise to 800 bytes. This is fine, as it will fit in a single packet. But what if lattice methods were cracked? We thus need a fall-back method that doesn’t involve lattices. One method — Classic Mceliece — has been around for a long time and is still uncracked, so it might be a strong contender. As we will find, though, it will have a significant impact on our key exchange methods — especially in the size of the public key.

And, so, did you know that if Classic Mceliece is adopted for TLS handshaking, the public key will be 261,120 bytes in size and will thus require 174 data packets to pass it? The key sizes for other…