For a Post-Quantum World, Is It All About Lattice Methods? No! Meet SPHINCS+, BIKE, and HQC
For a Post-Quantum World, Is It All About Lattice Methods? No! Meet SPHINCS+, BIKE, and HQC
Do you remember those who finish second? In future years, will anyone remember France in the World Cup in 2022 or that Matthew ‘Mack’ Robinson finished 4/10 of a second behind Jesse Owens? And, for the AES standard, do you remember that Ross Anderson’s Serpent symmetric key method ran Rijndael close for the AES standard and that BLAKE nearly beat Keccak for the SHA-3 standard?
But, in cybersecurity, being second to a winner is not a bad thing, as we need to be sure we have alternatives to the winner — just in case the winner falls in another race. So, let’s meet the 2nd placers in PQC (Post Quantum Cryptography).
NIST PQC: The Winner Takes It All?
And, so, NIST defined that CRYSTALS-KYBER (key-establishment) and CRYSTALS-Dilithium (Digital Signatures), and that FALCON and SPHINCS+ will also become standards for Digital Signatures. Why? Well, in Digital Signatures, on my assessment, Dilithium 2 (128-bit security) scored 28 points out of 30 for its all-round performance [here]:
And, for KYBER-512 performance (128-bit security), it was a perfect 30 out of 30 [here]:
But, three out of the four methods that are going to standardization are lattice methods. What happens if we find a weakness in lattice methods? If so, the whole of the Internet could be compromised. For now, we can pick and choose the key exchange and signatures methods (eg ECDH, RSA and DH for key exchange, and ECDSA and RSA for signatures), but in a lattice-only world, we could be dependent on the fundamental security of LWE (Learning With Errors — the core method used in lattices).
One of the major choices in selecting the lattice methods for key exchange is that they can fit within a TLS packet, as it would be too much of an overhead to have to send two or more packets for key exchange. Thus the size of the private key, the public key and the exchanged cipher are significant factors. In the following, we see that the KYBER-512 has a public key of 800 bytes, a cipher of 718 bytes, and a private key of 1632 bytes. As the private key is not passed over the network, we do not worry that it is more than 1500 bytes (for a single packet). In fact, we have enough space to include an ECC key in a single packet (to provide a hybrid key exchange method) [here]:
And so for digital signatures, it SPHINCS+
And, so, it was obvious that lattice methods are strong in virtually every respect — apart from us being totally dependent on them. Well, NIST has key exchange sorted with SPHINCS+ being defined as a forthcoming standard. SPHINCS+ is a hash-based signature method, and one of the great advantages of SPHINCS+ is that it provides a small public key (32 bytes) [here]:
We see that SPHINCS+ has one of the smallest public and private key sizes of all the contenders (but the signatures are relatively large) [here]:
The reason for this is that the private key is a set of random 32-byte values and that the public key is a Merkle hash of all these keys. Unfortunately, the performance of SPHINCS+ is not quite as good as the lattice methods, and is around 10 times slower for key generation than Dilithium [here]:
And, so, we have digital signatures methods with Dilithium or SPHINCS+ moving ahead. If relevant, developers and security architects should start thinking about supporting both of these in their stack.
It has to be BIKE or HQC for key exchange
But, what about key exchange? We only have CRYSTALS-KYBER! And, so, NIST has now opened up a 4th round of assessment and includes BIKE, Classic McEliece, HQC, and SIKE. The two favoured methods are BIKE and HQC. Both are not lattice methods, and are code-based, and have similar performance levels and key sizes. The public key for BIKE-L1 (128-bit security) is 1,541 bytes, and for HQC-128 is 2,249 bytes:
These would place the public key outside the limits of a TLS packet, but the overhead might not be too much. Unfortunately, Classic McEliece has virtually no chance of going anywhere near TLS, as it has a massive public key of over 260KB. For the isogeny-based method (SIKE), there is little chance of its being defined as an alternative, as a fellow method (SIDH) was cracked using a single laptop over a weekend. While it was the parameters selected, it brings into question the usage of isogenies. But, NIST still likes SIKE (!), so it’s still in there and will be probed a whole lot more.
Conclusions
We are well sorted for digital signatures with SPHINCS+ providing a forthcoming alternative to Dilithium. The course is less clear for key exchange methods, but it’s likely that BIKE and HQC will go to standardization, along with KYBER.
Learn more here: