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.
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:
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:
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.
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.”
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.
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.”
Victoria de Quehen is a Cryptographer at InfoSec Global in Toronto. Her educational background includes an undergraduate degree in math from Queen’s University and a Master’s degree in Number Theory from McGill University. Professionally, she is developing innovative expertise in the field of digital security, where for the past 4 years she has been applying her knowledge of elliptic curves, and math in general, to conduct new cryptographic research on post-quantum encryption. She is actively involved in the post-quantum research community, and organizes international research workshops. Her main interest is in the optimization of post-quantum algorithms, with a special interested in hardware speed-ups, to improve security for information requiring long-term confidentiality.
.jpg)
.jpg)
