Day 0 of a Post Quantum Cryptography World
Day 0 of a Post Quantum Cryptography World
NIST has a strong track record for defining standards that are widely adopted over the industry. This includes the standardization of AES and SHA-3. And, so, finally, the next great standard for cybersecurity has been announced [here]:
As expected, it is the lattice methods and especially CRYSTALS (Cryptographic Suite for Algebraic Lattices) that have won through in the end. Overall, lattice methods generally produce fairly small key sizes, and have good performance levels. They have also been fairly well researched.
With Kyber is now defined as an emerging standard for PKE/Key Exchange, and NIST could not seperate the lattice method of Dilithium and Falcon. As NIST do not want to rely on lattice method, the SPHIHCS+ has won through for a non-lattice digital signature method. Overall SPHINCS+ has small key sizes, but does not perform as well as lattice methods for signing and verifying signatures.
Kyber
With PKE/KEM, Kyber advances to a standard, NIST are keen to progress a non-lattice based method, and progress the following into the 4th round:
- BIKE (Code-based).
- Classic McEliece (Code-based). It failed to be accepted at this point because of its large public key.
- HQC (Code-based).
- SIKE (Isogenies). Many see isogenies as a great advancement, but they struggle at the current time for their key sizes and performance. But, it is likely that they will improve over the next few years.
A deadline of October 2022 has been set for tweaks of these methods. Those that did not progress are Saber (Lattice), NTRU (Lattice), and FrodoKEM (Lattice).
In my recent analysis of the PKE/KEM methods, we can see that Kyber512 (which has 128-bit AES equivalent security) was the fastest for key generation, key encapsulation and decapsulation [here]:
and when it comes to key sizes, we see that Kyber512 has a relatively small public key of 500 bytes, a ciphertext of 768 bytes, and a secret (private) key size of 1,632 bytes [here]:
With ECC, we have fairly small key sizes, such as 32 bytes for the private key and 64 bytes for the public key.
Dilithium, Falcon, and SPINHCS+
For signatures we have Dilithium, Falcon, and SPHINCS+, with Rainbow (Multivariate Quadratic) and Picnic (Hash-based ZKP) not progressing. For performance, Dilithium performs best of all the lattice methods, and is the strongest overall. While it is slower than Picnic for key generation, it is fastest for signing and verification [here]:
For key sizes, Dilithium2, has a 1,312 byte public key, 2,528 bytes for the private key, and 2,420 bytes for the signature. Falcon has similar sizes for the key sizes and signature [here]:
For key sizes, SPHINCS+ produces one of the smallest public (32 bytes) and private keys (64 bytes), but the signature size (17,088 bytes) is longer than the lattice methods. But, it struggled for performance against the lattice methods:
Conclusions
In a nice touch, NIST replied to my tweet [here]:
So, get building or start testing your software, and see what needs to change. We should now see banks, government departments, and many other organisations working out a strategy for the change over from ECC, RSA and discrete logs to the new NIST PQC standards.
It is good to see SIKE advance to the next round, too.
Exciting times! If you want to know more about the methods, try here: