NIST’s Standardisation of PQC
In one of the previous blogs and on a recent PQC webinar we have discussed the public-key cryptography’s vulnerability to quantum attacks, specifically to attacks relying on Shor’s algorithm.
Presently, public-key algorithm standards are described in a series of NIST publications [1,2,3]. It is expected, though, that soon a migration will start to a new class of quantum-resistant algorithms. In order for the migration to be orderly and for the algorithms to satisfy the highest security requirements, standards have to be defined. In the end of 2016, this lead NIST to put out a public call for PQC submissions.
November 2017 was the deadline for submitting algorithm proposals. Out of 82 submitted candidates, 13 were almost immediately broken or found otherwise lacking. So, in December 2017 69 total candidates were accepted into the first selection round. A few months after that, in April 2018, the 1st NIST PQC standardisation conference was held, where algorithms and potential attacks on them were discussed by researchers from both NIST and wider academia. In the beginning of 2019, 26 candidates were chosen to proceed in the 2nd round, followed by the 2nd NIST PQC standardisation conference, held that summer. Finally, on 22nd of July this year, 7 3rd round finalists were announced. NIST also publicly published a report of the selection process.
The Seven Chosen Algorithms
Let us take a look at the finalists. We can divide them with respect to two main criteria. What is their use? And what mathematical problem are they based on?
The algorithms that are being selected in this NIST standardisation process are meant to replace the present public-key algorithms. But unlike RSA or ECC which could be applied in different use-cases, the PQC algorithms are more specific. Therefore, the first division is according to their use: they are either used for public-key encryption/KEMs (key encapsulation mechanism) or for creating digital signatures, but not both. Out of 7 algorithms in total, 4 are for public-key encryption, and 3 for creating digital signatures.
The second division references their underlying mathematical problem. The security of RSA is based on the problem of factoring an integer into its prime factors. The security of ECC is based on the discrete logarithm problem. But since both of those are broken by Shor’s algorithm, entirely new classes of problems had to be used for PQC algorithms. Most of the proposals are based on the structured lattices scheme (CRYSTALS-KYBER, CRYSTALS-DILITHIUM, NTRU, SABER, FALCON), one on multivariate problems (Rainbow), and one on code-based problem (Classic McEliece).
One additional difference between the suggested PQC algorithms and the ones we use today is the difference in signature and public-key size. On the table above, you can see where RSA and ECC are placed on the chart in comparison to the new algorithms, some lattice-, some hash-, and some multivariate-based. Notice the exponential scale. One can see that the algorithms we will be using in the future will either have vastly larger signature size (hash-based algorithms), vastly larger public-key size (most of the multivariate-based algorithms), or be somewhere in the middle (lattice-based).
Alternative Candidates and Plans for the Future
Besides the seven finalists, NIST has also selected eight alternative candidates for the 3rd round. These algorithms assuredly will not be standardised with the end of the next round, but NIST does permit the possibility that, with additional modifications, they can enter a potential 4th round. After that, those with a good enough performance and proven resiliency against cryptanalysis, can still become standardised.
Originally, NIST planned to host a 3rd NIST PQC standardization conference in the spring or summer of 2021. It remains to be seen how the COVID-19 pandemic will impact these plans. It is expected that a small number of candidates will be selected for standardization by early 2022. Therefore, according to NIST, the third round will serve as a final round for the first phase of standardization.
 FIPS 186-4, Digital Signature Standard (DSS)
 SP 800-56A Rev. 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography
 SP 800-56B Rev. 2, Recommendation for Pair-Wise Key-Establishment Using Integer Factorization Cryptography
Prepared by: Nastja Cepak, PhD Cryptography / CREAplus