After eight years of intensive review and analysis, the U.S. National Institute of Standards and Technology (NIST) has released the final, approved specifications for the first three Post Quantum Cryptography (PQC) algorithms. The effort start in 2016 with 82 algorithms initially submitted with 69 algorithms accepted for further review. And after three rounds of analysis, NIST has selected the first three algorithms for final approval. The three algorithms include the following:
| Specification Number | Name | Based Upon | Usage Type |
| FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard | ML-KEM | Crystals-Kyber | Key Encapsulation |
| FIPS 204, Module-Lattice-Based Digital Signature Standard | ML-DSA | Crystals-Dilithium | Digital Signature |
| FIPS 205, Stateless Hash-Based Digital Signature Standard | SLH-DSA | SPHINCS+ | Digital Signature |
For enterprise Chief Information Officers (CIO) and Chief Security Officers (CSO) this is a signal for them to start implementing PQC in their IT infrastructure to protect their organizations against cybersecurity attacks from future large scale quantum computers that run algorithms which break existing encryption codes. NIST is encouraging computer system administrators to begin transitioning to these new standards as soon as possible. The U.S. government has put in motion plans to upgrade all the government’s IT systems to the new standards. A new report titled Report on Post Quantum Cryptography provides and outline of the strategy and timeline for the government to upgrade its internal systems to these new standards and estimates they will spend about $7.1 billion on it between 2025 and 2035.
Global Quantum Intelligence (GQI) is also recommending that IT departments implement these new algorithms as soon as possible. In our Quantum Safe Outlook report, we point out that users consider a Worst Case mindset, because of the possible that an algorithm that attacks existing asymmetric encryption codes is found earlier than anticipated.
A number of commercial companies have also issued blogs and press releases in support of the algorithms and a recommendation to start now. These include a press release and blog which point out that IBM researchers had a hand in developing these three algorithms. Other announcements have come out today from SandboxAQ, Terra Quantum, Thales, PQShield, Quantum Xchange, and many others also in support of this recommendation.
But Wait! There’s More!
It is important to understand that there are still many more years of work left in this program. One of the concerns about the software based PQC algorithms is that no one has been able to create a theoretical proof that these new algorithms are unbreakable. What can be proven is that some algorithms can be broken by showing people how it can be done. This did occur with several of the original 69 algorithms that NIST started out with in 2016. The ones that have survived and are being standardized survived years of attempts from researchers trying to break them without seeing success. But that does not say that someday in the future, some clever PhD student will find a way to break one of these algorithms in a way that no one had done before.
Because of this potential jeopardy, NIST is pursuing a strategy of developing and finalizing several different asymmetrical encryption algorithms using a variety of different mathematical approaches such that if one is eventually broken users can switch to one of the other ones. They are also recommending that IT departments utilize a strategy of quantum agility in the deployment. This implement the upgrades in a modular way, such that if one needs to replace one algorithm with another it can be easily done.
So this is where the 45 other candidates come in. As shown in the table above, of the three algorithms that have been finalized, one is intended for usage for key encapsulation and the other two are intended for use with digital signatures. That is not enough that they are continue to work on finalizing and approving more algorithms.
The next algorithm expected to be standardized is called FALCON. It uses a structured lattice class of algorithms similar to ML-DSA. It was selected along with the first three of the project but hasn’t yet gone through the full process of developing a draft standard, receiving comments, making corrections, and receiving the final Secretary of Commerce’s approval. The draft standard for FALCON is expected to be available in late 2024 with final approval in 2025.
Next, there were four algorithms analyzed during Round 3 with the others where NIST felt that additional analysis was needed. So these algorithms which are named BIKE, HQC, SIKE, and Classic McEliece are currently being analyzed in a Round 4 for additional algorithms to use in key encapsulation. BIKE, HQC, SIKE and Classic McEliece are based upon a code-based mathematical approach while SIKE is based on an Isogeny mathematical approach. There were chosen by NIST for Round 4 because the are all based upon a different approach than the ML-KEM already chosen for key encapsulation and provide some diversity and protection against being broken. An issue was found with SIKE, so we do not expect it to be standardized. But we do expect that NIST will approve one of the other three code-based algorithms.
Finally, in 2022 NIST was concerned that they also need additional diversity in algorithms for the digital signatures. SLH-DSA and Falcon were both based upon a Lattice approach and SPHINCS+ is based upon a Hash based approach, they requested additional submissions for new digital signature algorithms to be evaluated that don’t use a Lattice approach. In July 2023, they received 40 new candidate algorithms and they are current in a Round 1 analysis of these. These 40 candidates include 6 Code-based, Isogeny-based, 7 Lattice based, 7 MPC-In-The-Head, 10 Multivariate-based, 4 Symmetric-based, and 5 others types of approaches. A list of these 40 additional signature candidates has been posted on the NIST website here.
For more about the announcement of the standardization of these first three algorithms, you can view an announcement posted on the NIST website here and also another announced that will be posted in the U.S. Federal Register here. For an overview of the overall project that includes information on all the rounds and all the algorithm candidates, you can visit the NIST PQC project webpage here.
August 13, 2024
