NIST: Technical Summary of the New PQC Standards Process
To avoid the threat that quantum computers pose to our communication infrastructure, the US National Institute of Standards and Technology (NIST) is in the process of standardizing new Post-Quantum Cryptographic algorithms (PQC). These algorithms, unlike current cryptographic algorithms, are designed to be secure even after powerful quantum computers become reality.
NIST is Standardizing Two Types of PQC Algorithms
When people think of cryptography they often think of encryption. There are already standardized encryption algorithms that will remain secure against future quantum computers. However, in today’s world it is not enough just to have encryption standardized. Before encryption takes place, digital signatures and key establishment algorithms are often used for authentication and establishing a shared secret encryption key. All three algorithms work in tandem to achieve secure connections and communications.
For this reason, NIST is standardizing the following two types of cryptographic algorithms:
- Key Encapsulation Mechanisms (KEM), which are algorithms used for establishing a shared secret encryption key, and
- Digital Signature Algorithms, which are most famously used for authentication.
The Reason for Selecting Multiple Algorithms
If you look at their PQC standardization website, NIST does not plan on standardizing just one single KEM and one digital signature algorithm. Instead NIST wants to standardize multiple KEMs and digital signature algorithms. There are two main reasons for this:
- Different Algorithms, Different Advantages: Take digital signatures, for example. Each algorithm has a different key generation speed, signing speed, verification speed, public key size, signature size, ease of implementation, side-channel attacks, and security analysis. Each particular application may have certain fixed constraints, and within those constraints it may be best to optimize for one or more of these attributes.
- Security through Diversity: One problem with the currently standardized algorithms is that many of them are based on similar mathematical ideas. This means if the underlying mathematical problem is broken, all of these standards become vulnerable. To rectify this situation NIST wants to standardize KEMs and digital signature algorithms from different areas of mathematics. This also allows the highly cautious to combine multiple algorithms from different areas of mathematics to make a hybrid algorithm that will remain secure unless all of its component algorithms are broken.
Stateful Hash-Based Algorithms
You may have heard about stateful hash-based algorithms and be wondering how they fit into NIST’s PQC standardization process. Hash-based cryptography is a type of cryptography whose security is largely based on the security of well-trusted hash functions. There are two types of hash-based cryptography: stateful and stateless.
Stateful algorithms are considered mature and well-vetted. Following documents released by the Internet Engineering Task Force (RFC 8391 and RFC 8554), NIST fast-tracked the standardization of the two most prominent stateful hash-based signatures XMSS and LMS/HSS. NIST’s special publication which covers these algorithms, Recommendation for Stateful Hash-Based Signature Schemes SP 800-208, is a post-quantum cryptography standard.
It is certainly reasonable to deploy the stateful algorithms XMSS or LMS/HSS in certain applications. However, NIST states, “stateful hash-based signature schemes are not suitable for general use because they require careful state management. As such, stateful hash-based signatures were not in the scope of the NIST Call for Proposals for the PQC Standardization Process.”
On the other hand, NIST’s PQC process will also standardize a stateless hash-based algorithm, as explained below.
The Timeline of NIST’s PQC Standardization Process
- 2016 - Initial call for proposals for NIST’s PQC standardization process.
- 2017 - Deadline for Submissions. There were 69 different submissions accepted from teams around the world.
- 2019 - End of Round 1 of the analysis and the candidate pool narrowed to the 26 most promising candidates. This allowed researchers to concentrate their scrutiny on fewer algorithms.
- 2020 - End of Round 2 of the analysis and further narrowing of the candidate pool to 8 finalist candidates and 7 alternate candidates.
- 2020 - In a separate process two stateful post-quantum digital signature algorithms, XMSS and LMS/HSS, were standardized in NIST’s Special Publication SP 800-208.
- 2022 - NIST ended Round 3 of the analysis. NIST selected 4 algorithms for standardization. KYBER was chosen as a KEM. DILITHIUM, FALCON and SPHINCS+ were chosen for digital signatures. NIST chose 4 additional KEMs for a fourth round of analysis: SIKE, BIKE, HQC and Classic McEliece.
- 2023 - Submissions are due for a separate process to standardize additional digital signature algorithms.
- 2024 - NIST expects to publish a standard for its complete cryptographic suite of PQC algorithms.
- 20XX - A timeline for the additional standardization process starting in 2023, has yet to be announced.
KEM – KYBER
Currently, NIST has only selected a single KEM for standardization, KYBER. This is an algorithm that comes from a well-studied branch of cryptography based on a type of mathematical object called a structured lattice. Structured lattice-based cryptography is favoured due to its efficiency, reasonable key sizes, and strong confidence in its security. NIST’s rational for their choice is that “KYBER has excellent performance overall in software, hardware and many hybrid settings.”
Digital Signatures – DILITHIUM, FALCON, SPHINCS+
DILITHIUM is a lattice-based digital signature algorithm that was chosen – in addition to the usual benefits of lattice-based cryptography – for its ease of implementation. In cryptography a simpler algorithm means there is less potential for security vulnerabilities being introduced during the implementation phase. NIST states, DILITHIUM is “an excellent choice for a broad range of cryptographic applications and is, thus, the primary signature algorithm selected by NIST for standardization at this time.”
FALCON is a second lattice-based digital signature algorithm that was chosen for specific use cases. It has a small bandwidth (public key size plus signature size) and fast verification time. Its key generation and signing times are somewhat slower than DILITHIUM’s. As NIST explains, “due to its low bandwidth and fast verification, FALCON may be a superior choice in some constrained protocol scenarios.”
SPHINCS+ is a stateless hash-based digital signature algorithm, for which InfoSec Global is pleased to have been a contributor. Hash-based algorithms are known for their strong cryptographic security, and SPHINCS+ is viewed as a conservative option.
Future Work
NIST states that the Round 4 KEM candidate SIKE – an isogeny-based algorithm for which InfoSec Global was a contributor – “remains an attractive candidate for standardization because of its small key and ciphertext sizes.” It is also likely that NIST will standardize at least one of the other fourth round KEM candidates BIKE, HQC and Classic McEliece, which are all code-based algorithms.
Finally, the reasons given for a separate standardization process for additional digital signature algorithms is: “NIST primarily seeks to diversify its signature portfolio with non-structured lattice signature schemes. NIST may also be interested in signature schemes that have short signatures and fast verification.”
