NIST seeks comments on three draft FIPS documents covering post-quantum cryptography by Nov. 22

The National Institute of Standards and Technology (NIST) announced Thursday that it has released draft standards for three of the four algorithms it selected last year. A draft standard for FALCON, the fourth algorithm, will be released in about a year. The agency has called for feedback on three draft Federal Information Processing Standards (FIPS) that cover post-quantum cryptography standardization. These proposed standards specify key establishment and digital signature schemes that are designed to resist future attacks by quantum computers, which threaten the security of current standards. 

The agency selected four algorithms designed to withstand attack by quantum computers, and has now begun the process of standardizing these algorithms — the final step before making these mathematical tools available so that global organizations can integrate them into their encryption infrastructure.

Each new publication is a draft FIPS document concerning one of the four algorithms NIST selected last July: 

• CRYSTALS-Kyber, designed for general encryption purposes such as creating secure websites, is covered in FIPS 203. 
• CRYSTALS-Dilithium, designed to protect the digital signatures we use when signing documents remotely, is covered in FIPS 204.
• SPHINCS+, also designed for digital signatures, is covered in FIPS 205.
• FALCON, also designed for digital signatures, is slated to receive its own draft FIPS in 2024.

In a Thursday notice published in the Federal Register, interested members in the worldwide cryptographic community have been invited to provide feedback on FIPS 203, FIPS 204, or FIPS 205 no until Nov. 22, 2023. It added that after the comment period closes, NIST will analyze the comments, make changes to the documents as appropriate, and then propose the drafts FIPS 203, FIPS 204, and FIPS 205 to the Secretary of Commerce for approval. Eventually, the completed post-quantum encryption standards will replace three NIST cryptographic standards and guidelines that are the most vulnerable to quantum computers: FIPS 186-5, NIST SP 800-56A and NIST SP 800-56B.

“We’re getting close to the light at the end of the tunnel, where people will have standards they can use in practice,” Dustin Moody, a NIST mathematician and leader of the project, said in a media statement. “For the moment, we are requesting feedback on the drafts. Do we need to change anything, and have we missed anything?”

The NIST notice recognized that these “proposed standards specify key establishment and digital signature schemes that are designed to resist future attacks by quantum computers, which threaten the security of current standards. The three algorithms specified in these standards are each derived from different submissions in the NIST post-quantum cryptography standardization project.” 

The three algorithms are FIPS 203, Module-Lattice-Based Key-Encapsulation Mechanism Standard; FIPS 204, Module-Lattice-Based Digital Signature Standard; and FIPS 205, Stateless Hash-based Digital Signature Standard, are each derived from different submissions to the NIST Post-Quantum Cryptography (PQC) standardization project. 

The draft of FIPS 203 specifies a cryptographic scheme called Module Learning with errors Key Encapsulation Mechanism, or MLWE–KEM, which is derived from the CRYSTALS–KYBER submission, the notice disclosed. “A Key Encapsulation Mechanism (or KEM) is a particular type of key establishment scheme which can be used to establish a shared secret key between two parties communicating over a public channel. Current NIST-approved key establishment schemes are specified in SP 800–56A Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm-Based Cryptography and SP 800–56B, Recommendation for Pair-Wise Key Establishment Schemes Using Integer Factorization Cryptography.”

The drafts of FIPS 204 and 205 each specify digital signature schemes, which are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. 

The notice said that FIPS 204 specifies the Module Learning with errors Digital Signature Algorithm, or ML–DSA, which is derived from CRYSTALS-Dilithium submission. FIPS 205 specifies the Stateless Hash-based Digital Signature Algorithm, or SLH–DSA, derived from the SPHINCS+ submission. “Current NIST-approved digital signature schemes are specified in FIPS 186–5, Digital Signature Standard and SP 800–208, Recommendation for Stateful Hash-based Signature Schemes. In the future, NIST intends to develop a FIPS specifying a digital signature algorithm derived from FALCON as an additional alternative to these standards.”

Over the past several years, there has been steady progress toward building quantum computers. The security of many commonly used public-key cryptosystems would be at risk if large-scale quantum computers were ever realized. In particular, this would include key-establishment schemes and digital signatures that are based on integer factorization and discrete logarithms (both over finite fields and elliptic curves). 

As a result, in 2017, the NIST initiated a public process to select quantum-resistant public-key cryptographic algorithms for standardization. These quantum-resistant algorithms would augment the public-key cryptographic algorithms already contained in FIPS 186–5, Digital Signature Standard (DSS), as well as NIST Special Publication (SP) 800–56A Revision 3, Recommendation for Pair-Wise Key-Establishment Schemes Using Discrete Logarithm Cryptography, and SP 800–56B Revision 2, Recommendation for Pair-Wise Key Establishment Using Integer Factorization Cryptography.

NIST issued a public call for submissions to the PQC standardization process in December 2016. Ahead of the November 2017 deadline, a total of 82 candidate algorithms were submitted. Shortly thereafter, the 69 candidates that met both the submission requirements and the minimum acceptability criteria were accepted into the first round of the standardization process. Submission packages for the first-round candidates were posted online for public review and comment.

After a year-long review of the candidates, NIST selected 26 algorithms to move on to the second round of evaluation in January 2019. These algorithms were viewed as the most promising candidates for eventual standardization, and were selected based on both internal analysis and public feedback. During the second round, there was continued evaluation by NIST and the broader cryptographic community. After consideration of these analyses and other public input received throughout the evaluation process, NIST selected seven finalists and eight alternates to move on to the third round in July 2020.

The third round began in July 2020 and continued for approximately 18 months. During the third round, there was a more thorough analysis of the theoretical and empirical evidence used to justify the security of the candidates. There was also careful benchmarking of their performance using optimized implementations on a variety of software and hardware platforms. Similar to the first two rounds, NIST also held the (virtual) Third NIST PQC standardization conference in June 2021. NIST summarized its decisions in a report at the end of each round; NISTIR 8240 for the first round, NISTIR 8309 for the second round, and NISTIR 8413 for the third round. These reports are available online.

After three rounds of evaluation and analysis, NIST selected four algorithms it will standardize as a result of the PQC Standardization Process. The public-key encapsulation mechanism selected was CRYSTALS–KYBER, along with three digital signature schemes – CRYSTALS–Dilithium, FALCON, and SPHINCS+. It is intended that these algorithms will be capable of protecting sensitive U.S. government information well into the foreseeable future, including after the advent of quantum computers.

In addition to the four algorithms NIST selected last year, the project team also selected a second set of algorithms for ongoing evaluation, intended to augment the first set. NIST will publish draft standards next year for any of these algorithms selected for standardization. These additional algorithms — likely one or two, Moody said — are designed for general encryption, but they are based on different math problems than CRYSTALS-Kyber, and they will offer alternative defense methods should one of the selected algorithms show a weakness in the future. 

This need for backups was underscored last year when an algorithm that initially was a member of the second set proved vulnerable: Experts outside NIST cracked SIKE with a conventional computer. Moody said that the break was unusual only in that it came relatively late in the evaluation process. “It was mainly an indication that our process is working as it should,” he said.

Earlier this week, the Cybersecurity and Infrastructure Security Agency (CISA), National Security Agency (NSA), and NIST published a factsheet on the impacts of quantum capabilities and providing necessary steps to begin planning for migration to PQC. These agencies urge organizations, especially those that support critical infrastructure, to begin early planning for migration to PQC standards by developing their own quantum-readiness roadmap.

Anna Ribeiro

Industrial Cyber News Editor. Anna Ribeiro is a freelance journalist with over 14 years of experience in the areas of security, data storage, virtualization and IoT.