Standardization of Post-Quantum Cryptography

Standardization of Post-Quantum Cryptography: Comparison

Please note this is a comparison between Version 2 by Fanny Huang and Version 1 by Duc-Thuan Dam.

Information security is a fundamental and urgent issue in the digital transformation era. Cryptographic techniques and digital signatures have been applied to protect and authenticate relevant information. However, with the advent of quantum computers and quantum algorithms, classical cryptographic techniques have been in danger of collapsing because quantum computers can solve complex problems in polynomial time. Stemming from that risk, researchers worldwide have stepped up research on post-quantum algorithms to resist attack by quantum computers.

post-quantum cryptography
PQC
NIST
standardization

1. Overview

The study of cryptography began to be carried out very early, starting from ancient times, thousands of years BC. After cryptography had gone through many different stages of development, NIST came up with the idea in the 1970s of choosing a cipher to become a common standard for the country, from which the data encryption standard (DES) algorithm was introduced, with a relatively small key size. After being broken in 1997 because of that drawback, NIST again asked for proposals for new block codes and received 50 submissions. By 2000, the AES algorithm was chosen and is widely used today as a standard for symmetric encryption. However, the advent of quantum computers and quantum cryptographic algorithms has threatened the existence of ciphers based on mathematical difficulty. Therefore, in 2016, NIST continued to call for proposals on post-quantum algorithms to find algorithms that resist the power of quantum computing. Currently, the NIST standardization process is in its fourth round.

2. First Round

The first round of NIST’s PQC standardization process began in December 2016 and ended in July 2019. During this period, NIST invited cryptographers and researchers worldwide to submit post-quantum cryptographic algorithms capable of replacing current public-key cryptosystems. NIST received 82 submissions, which were judged on their security, performance, and implementation characteristics. The first round consists of two phases. The first phase includes an initial screening of all submissions to identify those that do not meet the minimum security or functionality requirements. The second stage involves a more detailed evaluation of the remaining proposals. In the second phase, NIST established criteria for evaluating algorithms, including security for classical and quantum computers, flexibility, and ease of implementation. NIST also conducted several rounds of testing and analysis to ensure the algorithms met these criteria. At the end of the first round, NIST selected 26 candidate algorithms for further research and evaluation in the second round ^[1].

These candidate algorithms included many key encryption, signature, and agreement schemes. Overall, the first round of the NIST PQC standardization process is essential in identifying and assessing the strengths and weaknesses of various post-quantum encryption algorithms. It builds the foundation for further research and development in the field. It paves the way for the eventual selection of standardized PQC algorithms that can resist attacks from classical and conventional quantum computers. The PQC standardization process can be summarized in Figure 1.

Figure 1. PQC the standardization process of NIST.

3. Second Round

The second round of the PQC standardization process began in January 2019 and ended in July 2020. During this period, the focus was on evaluating and analyzing the 26 candidate algorithms selected from the first round. The goal was to determine their security, effectiveness, and suitability for different use cases. The second round involved extensive testing and evaluation of candidate algorithms, including software and hardware implementations. Submissions were evaluated based on their security against different types of attacks, their speed and memory consumption performance, and flexibility in terms of key size and security level. In addition to the technical assessments, the second round included two virtual workshops where applicants presented their algorithms and answered questions from the NIST team and other participants. Based on the second round assessment results, NIST selected seven finalists and eight alternate candidates who advanced to the third round of the standardized process ^[2]. The algorithms will be further analyzed and tested before NIST selects the final set of standardized PQC algorithms.

4. Third Round

The third round started in July 2020 and ran for 18 months, with 15 candidates selected after the end of the second round. In this round, NIST asked the candidates to analyze the proposals and prove they achieved adequate security in experiments and theory. In addition, the candidates also evaluated the performance of the algorithm on a variety of software and hardware platforms. In June 2021, NIST hosted the third PQC Standardization Conference. Candidates and researchers presented their updates and related results at this conference. After 18 months of selection, 7 out of 15 candidate algorithms were selected for the final of the third round, including four PKE/KEM encryption algorithms and three digital signature schemes; eight candidate algorithms were alternatives ^[3], where necessary, including five PKE/KEM algorithms and three digital signature schemes. Selected candidate algorithms are suitable for most applications and are ready for standardization, and alternative candidate algorithms are potential candidates for the future. Candidate algorithms were updated with minor modifications up until October 2020, before being posted on the NIST website and evaluated publicly.

Finalists include:

PKE/KEM algorithms: Classic McEliece, CRYSTALS-Kyber, NTRU, Saber;
Digital signature schemes: CRYSTALS-Dilithium, Falcon, Rainbow.

Alternative candidate algorithms include:

PKE/KEM algorithms: BIKE, FrodoKEM, HQC, NTRU Prime, SIKE;
Digital signature schemes: GeMSS, Picnic,

The PKE/KEM algorithm is CRYSTALS-Kyber;
$S P H I N C S^{+}$
Digital signatures are CRYSTALS-Dilithium, Falcon, and $S P H I N C S^{+}$ $S P H I N C S^{+}$ .

During the evaluation, the Rainbow digital signature algorithm was broken by Ward Beullens using a classical computer. After the selection process, NIST selected four algorithms to standardize right after the third round, including:

$S P H I N C S^{+}$
$S P H I N C S^{+}$ , in which Dilithium is the main algorithm.

NIST also selected four PKE/KEM candidate algorithms to continue the selection in the fourth round, including BIKE, Classic McEliece, HQC, and SIKE. These were selected for standardization after the end of the fourth round.

5. Fourth Round

In the fourth round, the four candidates selected for the standardization implementation for PKE/KEM had passed the third round. During the selection process, the SIKE candidate algorithm was broken by Wouter Castryck and Thomas Decru using a classical computer. Thus, only three candidates were left for this code-based PKE/KEM round. From 29 November 2022 to 1 December 2022, NIST held its fourth online conference on PQC. At this conference, NIST and researchers discussed candidate algorithms and valuable responses to reach conclusions, and candidates were also able to present their updates to the algorithm. After seven sections, the reports suggested the updates and hardware implementations of the nomination algorithms and their applications. From the positive results of the conference, NIST has the basis for choosing the appropriate algorithm for standardization shortly. To evaluate each scheme, the levels of security are defined by NIST as described in Table 1.

Table 1. The security levels of NIST.

Level	Description
1	At least as hard to break as AES128
2	At least as hard to break as SHA256
3	At least as hard to break as AES192
4	At least as hard to break as SHA384
5	At least as hard to break as AES256

6. Summary

Thus, after four rounds of selection, three rounds have been completed, and the final round is underway; three candidate algorithms are left for PKE/KEM standardization. Only four PKE/KEM algorithms and three digital signature schemes have been selected out of 69 valid candidates in the first round. Out of seven selected candidate algorithms, a PKE/KEM and three digital signature schemes will be standardized, while the remaining three PKE/KEM algorithms will be further selected when choosing a standard algorithm for PKE. The selection process is expected to close in 2023, and NIST have announced that the first standard will be published in 2024.

References

Alagic, G.; Alperin-Sheriff, J.; Apon, D.; Cooper, D.; Dang, Q.; Liu, Y.-K.; Miller, C.; Moody, D.; Peralta, R.; Perlner, R.; et al. Status Report on the First Round of the NIST Post-Quantum Cryptography Standardization Process; Technical Report; National Institute of Standards and Technolog: Gaithersburg, MD, USA, 2019.
Moody, D.; Alagic, G.; Apon, D.C.; Cooper, D.A.; Dang, Q.H.; Kelsey, J.M.; Liu, Y.-K.; Miller, C.A.; Peralta, R.C.; Perlner, R.A.; et al. Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process; Technical Report; National Institute of Standards and Technolog: Gaithersburg, MD, USA, 2020.
Alagic, G.; Apon, D.; Cooper, D.; Dang, Q.; Dang, T.; Kelsey, J.; Lichtinger, J.; Liu, Y.-K.; Miller, C.; Moody, D.; et al. Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process; Technical Report; National Institute of Standards and Technolog: Gaithersburg, MD, USA, 2022.