Building For A Secure Future … Goodbye ECC and Hello To SABER, Kyber, NTRU or McEliece … or even…

Building For A Secure Future … Goodbye ECC and Hello To SABER, Kyber, NTRU or McEliece … or even SIKE!

The foundation of cybersecurity is CIA … Confidentiality, Integrity and Availability. At the core of this is the creation of secure and authenticated encryption tunnels, and a founding element of this is key exchange.

For most of our current implementations … such as the secure connection you are making to this Web page … we use ECDH (Elliptic Curve Diffie Hellman). But, wait! Elliptic Curve Cryptography (ECC) methods can be cracked with quantum computers. And so we will have to wean ourselves off ECDH and look elsewhere.

Luckily, NIST has been assessing the contenders for a standard method, and they are McEliece, SABER, NTRU and Kyber. I have implemented the methods here:

• SABER: here. It is a lattice method with Learning with Rounding (LWR).
• Kyber: here. it is a lattice method with LWE (Learning with Errors).
• NTRU (TRU (Nth degree TRUncated polynomial ring): here. It is a lattice method.
• McEliece: here. This uses error-correcting codes with errors.

In the end, we want to come up with a 32 byte (256-bit) secret, and which will be used as an encryption key for the secure tunnel. And so, for key exchange, I have been assessing these, and here are the results I have found for the key sizes of the methods:

We can see that NTRU provides the smallest of keys and ciphertext, but Kyber and SABER are close. The outlier is McEiece with a massive 261KB public key size, and a 6KB private key. But its ciphertext is fairly small for the key exchange. But look at the ciphertext for NTRU … it is just 32 bytes long.

In terms of performance on an ARM Cortex-M4 (32-bit RISC processor), the following is the number of cycles taken for various operations for key generation, key encapsulation and key decapsulation [1]:

And so while NTRU was way out in front for the key sizes, it struggles with the number of operations for the key generation, and where Kyber and SABER perform these much faster. For McEliece, it struggles again with key generation but settles down for the encryption of the key (encapsulation) and its decryption (decapsulation). While SIKE is not included in the final four, it is included as an alternative. A downside is its relative slowness for all three operations (more than 100 times slower than Kyber and SABER). But, it is interesting, and will likely speed up through new research.

Conclusions

In the end, I think NIST will like the short key sizes of NTRU, or they will like the general overall good performance of Kyber and SABER. The attractiveness of dropping NTRU into TLS just seems to be a winner, but the key generation part is still a bit slow. The winner, though, is almost certainly going to be a lattice-based method. They are efficient, well researched and still a hard problem in a post-quantum era. And for McEliece? It has been there from the start and still will be there as we go forward. Error-correcting codes have been around since the start of the Internet, and have been well studied. As for the future … well, perhaps SIKE has the answer with isogenies:

References

[1] Chen, M. S., & Chou, T. Classic McEliece on the ARM Cortex-M4 [here].