What’s Next After Lattice Cryptography? Will it be BIKE, HQC, or McEliece?
What’s Next After Lattice Cryptography? Will it be BIKE, HQC, or McEliece?
Wow! It has been a crazy time in the world of NIST PQC (Post Quantum Cryptography). First, the multivariate cryptography method of Rainbow was cracked using a relatively old laptop over a weekend, and then SIKE/SIDH was defined as being insecure.
The winners
The two winners were CRYSTALS-Kyber for key exchange and CRYSTALS-Dilithum, SPHINCS+, and FALCON for digital signatures. Both of the methods are lattice-based, and both have good performance and reasonable key sizes. Kyber is the fastest of all the Round 3 contenders [here]:
And, while SIDH and SIKE had the shortest key sizes, Kyber also produces reasonable sizes, such as 800 bytes for the public key [here]:
For digital signatures, it was Dilithium that showed good overall performance [here], with the fastest signing and verification method, but a little shower than Picnic for key generation [here]:
And for key sizes, Dilithium cannot compete with SPHINCS and Picnic, but a 1,312 key size for the public key is reasonable [here]:
Round 4
So now we enter Round 4, and where NIST is seeking an alternative to the lattice methods. For key exchange/public key, we have now BIKE, Classic McEliece, and HQC. But, what about SIKE and SIDH? Well, they have been marked as insecure and that they should not be used. And, while the SIKE team considered withdrawing, they are aiming to submit an updated version of the SIKE for the 4th round [here]:
But, isogenies are still a strong area, and still well-liked by researchers. NIST has defined that the work of isogenies should continue, especially the methods which are not based on SIDH. These include CGL, CSIDH and SQIsign [here]:
So, what about BIKE, HQC and McElliece? Well, they are all code-based methods. BIKE and HQC have a similar performance level, but for McEliece, the key generation is extremely slow, but the encapsulation speed is around the same as BIKE and HQC [here]:
And for key sizes, again BIKE and HQC have similar key sizes (such as 3083 bytes for the public key in BIKE), but the public key for McEliece is large (but the private key is small) [here]:
Conclusions
Isogenies are not dead, they are just sleeping, and will hopefully come back stronger than before. The whole point of these rounds is to fully probe the methods, and it has been successful in weeding out the weak methods. As for the Round 4 winner, there’s not much between BIKE and HQC, but McEliece has a couple of Achilles heels … the key generation time and the size of the public key. But, in the memory of the mighty Robert J. MeEliece, it would some reward for his work all those years ago: