In response to the quantum threat in 2015, the National Institute of Standards and Technology (NIST) initiated a project to develop Post Quantum Cryptography (PQC) that will remain secure even in the age of large-scale quantum computers. Recently NIST has posted a list of new submissions to their PQC standardization project. This post aims to clarify how these new candidates fit into NIST’s ongoing PQC standardization efforts and the algorithms that NIST has already selected for standardization.
What type of algorithms are involved in NIST’s PQC standardization project?
While quantum computers do not threaten the security of sufficiently strong hash functions or symmetric encryption, large-scale quantum computers would be able to break classical public-key cryptography, including algorithms like RSA, Diffie-Hellman, and elliptic curve cryptography. The two main types of public-key cryptographic algorithms that need to be replaced are key establishment algorithms and digital signature algorithms. The type of key establishment algorithm that NIST has requested for PQC standardization is a Key Encapsulation Mechanism (KEM).
Why would NIST standardize more than one algorithm of the same type?
NIST wants algorithms from multiple areas of cryptography for two main reasons:
- Different use-cases: Each algorithm has different statistics when it comes to properties such as efficiency, key sizes, signature sizes, and even confidence in the algorithm’s security. Different PQC algorithms provide different trade-offs and lend themselves to different use cases.
- Back-up algorithms: The different algorithms come with different security assumptions and security proofs. Having algorithms from multiple areas of PQC would ensure that there is always an unbroken, standardized back-up algorithm, in case one of the algorithms is broken.
Which algorithms have already been standardized or selected for standardization?
The algorithms that have already been standardized or selected for standardization are from the well-studied areas of lattice-based and hash-based cryptography:
1. Lattice-based algorithms:
- All-purpose solutions: for most applications, these are favoured due to their efficiency and reasonable key sizes.
- Security: this area of cryptography is well-studied, which is why NIST fast-tracked them without requiring them to undergo additional scrutiny (see Round 4 below).
- Kyber: a lattice-based KEM that has been selected for standardization.
- Dilithium and FALCON: lattice-based digital signature algorithms that have been selected for standardization.
2. Hash-based algorithms:
- Security: these algorithms are as secure theoretical as the hash functions they utilize.
- Only signatures: this area of cryptography provides digital signature algorithms only, and not KEMs.
- LMS and XMSS: stateful hash-based algorithms that have already been standardized.
- SPHINCS+: a stateless hash-based algorithm that has been selected for standardization.
The algorithms Kyber, Dilithium, FALCON, and SPHINCS+ that have been selected for standardization are expected to be standardized within the next year.
What is Round 4 of NIST’s PQC standardization process?
Currently, NIST has only selected a single KEM for standardization, however, there are additional candidates from the original 2017 submissions that are undergoing further review. This is because while algorithms from lattice-based and hash-based cryptography have been well-studied and could already be selected, NIST announced a Round 4 for those candidates that they believed required additional scrutiny. The Round 4 isogeny-based algorithm SIKE has been broken, leaving 3 remaining code-based algorithms as possible candidates for future standardization.
What is NIST looking for in the additional digital signature schemes?
While there are additional KEMs from the original 2017 submissions that are appropriate for Round 4 of the standardization process, NIST has instead opened the field to new digital signature schemes. Part of this is due to the construction of new digital signature algorithms and cryptanalysis that has been published since 2017, when the original submissions were due.
NIST has stated diversity as a main goal for these additional signature algorithms: “NIST is primarily interested in additional general-purpose signature schemes that are not based on structured lattices.” However, NIST has also suggested a particular interest in “signature schemes that have short signatures and fast verification” or structured lattice-based signature proposals that “significantly outperform CRYSTALS-Dilithium and FALCON.”
What types of additional digital signature schemes have been submitted?
There have been 40 submissions that are listed on NIST’s website as complete and adhering to NIST’s minimum acceptability requirements. These submissions come from a variety of areas of cryptography. In some of these cryptographic areas, the candidates are a result of either advancements since 2017 (i.e., commutative isogeny-based cryptography) or previous submissions having been broken and new updated submissions (i.e., multivariate cryptography).
Crypto-agility as a way forward!
While we expect the standardization of these new digital signature algorithms to take several years, we hope that some of these candidates will provide better options for specialized use-cases, and possibly even outperform the current favourites. As the list of standardized PQC algorithms continues to evolve, it is important to design products that are crypto-agile, such as InfoSec Globals’ Cryptographic Agility Management Platform, where the cryptography can be easily replaced if a new algorithm becomes more advantageous.
