The NIST PQC decision

On the 5th of July 2022, NIST has published their 3rd round decision in the post-quantum standardization effort. As this decision was the center of my work when I researched in the PQC field, I just wanted to summarize my thoughts. Yes, July not January was decisive.

The following algorithms will be standardized:

key encapsulation mechanisms = {CRYSTALS-Kyber}
signature schemes = {Dilithium, FALCON, SPHINCS+}

So one lattice-based KEM candidate will be standardized as well as two lattice-based signature schemes and SPHINCS+ is a hash-based candidate. A fourth round shall investigate whether the following algorithms are also suitable, but might not make it in the end:

Here, the first three candidates are code-based candidates and SIKE is a representative of supersingular isogeny-based schemes.

So the KEM decision was made in favor of CRYSTALS-Kyber. Not so much Saber, which used a description very suitable for hardware implementations. And neither NTRU which dominated the lattice-based cryptography field in the beginning (1996 until about 2005). NTRU would have had the advantage of a lack of decryption failures. In extremely rare cases, Saber and CRYSTALS-Kyber can generate ciphertexts which decode to the wrong key (but this error is detected in the protocol). Thus, one needs to reissue the negotiation process. NTRU does not have this problem. But more so, NTRU has a longer history of cryptanalysis. In the end, I agree that CRYSTALS-Kyber received most attention from the community and also our paper used Kyber for demonstration purposes.

On the signature side, CRYSTALS-Dilithium is also a candidate which received much attention. Dilithium is acceptably comprehensible whereas FALCON is pretty complex to implement. I tried to attack Dilithium in my research, but failed doing so. If you start with hash-based cryptography, you will find some very interesting structures. SPHINCS+, as hash-based candidate, features these constructions, but has a certain implementation complexity. NIST emphasizes that the security is well-understood. Among hash-based algorithms there are two classes of algorithms. SPHINCS+ is stateless and thus trades the lack of a persistent memory for the signer with a larger signatures sizes. By the way, SP 800-208 covering stateful algorithms did not become invalidated.

Interestingly, Classic McEliece did not make it as a winner. This is a little unexpected, because a non-lattice-based KEM as winner would be nice if the new field of lattice cryptography has some fundamental problems not discovered yet. Classic McEliece was the only candidate here.

Frankly, our implementations (1, 2, 3) do not cover any winner. When I decided to offer implementations as bachelor theses, I decided against CRYSTALS-Kyber, because it is among the easiest to implement (IMHO). Classic McEliece is still a 4th round candidate though. Because I left the field of PQC, I don’t have any motivation to implement it now in pure rust. If you are interested in commercial work, you can hire me for it. Write me an email then. All the implementations will stay in maintenance mode (i.e. I’ll fix bugs but won’t develop features).

It is good to see some decisions after 6 years of a running competition. I decided upon the PQC topic in 2019, but stopped my PhD studies after 2 years. This decision is a good milestone to finally stop caring about this topic and focus on other ideas.