By Dr. Matthias J. Kannwischer, Research Director of Chelpis Quantum Corp
13 August 2024 marks an important day in the Quantum-Era: After almost 7 years of public evaluation the US National Institute of Standards and Technology (NIST) published the first standards for quantum-safe cryptography: ML-KEM (standardized in FIPS 203) becomes the new standard for quantum-safe key establishment, ML-DSA (FIPS 204) becomes the preferred quantum-safe digital signature scheme, and SLH-DSA (FIPS 205) becomes an alternative digital signature scheme.
Experts at Chelpis Quantum Corp have been working with these cryptosystems since day one and are ready to bring those standards into the real world as soon as possible. Over the next weeks and months, these new standards will see wide deployment allowing the protection of data of billions of people against the threat of future quantum computers.
Post-Quantum Cryptography Standardization Process
In 2016, the US NIST announced that they are planning to update their standards for cryptographic key-establishment (NISTSP800-56A and NISTSP800-56B) and digital signatures (FIPS186). These two standards form the basis of secure communications and are deployed widely around the world. NIST asked cryptographers worldwide to submit their proposals with a submission deadline in late 2017. After the deadline, NIST accepted 69 submissions to be scrutinized over the following years. In 2019, NIST published its first-round report and announced the start of a second round with 26 candidate schemes advancing, of which 17 were key-establishment schemes and nine were signature schemes. Another year later in mid-2020, NIST announced the third round with 15 schemes advancing. NIST distinguished between seven finalists and eight alternate schemes. In July 2022, the selection of four schemes to be standardized was announced: Kyber, Dilithium, SPHINCS+, and Falcon. NIST also announced that those are to be renamed to ML-KEM, ML-DSA, SLH-DSA, and FN-DSA in the standardization process. In late 2023, drafts for the first three schemes were published with the last (FN-DSA) to follow approximately a year later in fall 2024. After 3 months of public commentary of the draft standards, NIST announced that taking public feedback into account, they are planning multiple small tweaks and standards are estimated to be available in summer 2024. The publication of the standards happened on August 13, 2024.
In parallel to finalizing the standards, the US government has started to prepare the migration to post-quantum cryptography. Most notable, through the publication of the National Security Memorandum 10 (NSM-10) and the National Security Agency announcing the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0) to include post-quantum cryptography standardized by NIST. NSM-10 focuses on the transition to quantum-resistant cryptography to protect national security systems from the future threats posed by quantum computing. It mandates that US federal agencies and critical infrastructure sectors begin identifying cryptographic systems vulnerable to quantum attacks and develop plans for their upgrade to post-quantum cryptographic standards. NSM-10 emphasizes the urgency of this transition and sets deadlines for agencies to complete inventories and assessments, ensuring that the U.S. remains ahead in securing its most sensitive information. CNSA 2.0 which is defined by the NSA is used to secure classified and unclassified information at the highest levels in the US. It plays a crucial role in safeguarding national security systems. This suite not only sets the standard for government agencies but also provides critical guidelines for private sector entities handling sensitive data, particularly those engaged in government contracts. The adoption of CNSA 2.0 across various industries is driven by the need for robust cryptographic security. Compliance with these standards is often mandatory, influencing global cryptographic practices as U.S. companies and international firms align with these protocols. The inclusion of post-quantum algorithms in CNSA 2.0 will drive the adoption in the US as many parties have to comply as soon as it becomes mandatory.
ML-KEM
ML-KEM (Module-lattice key-encapsulation mechanism; formally known as Kyber) is NIST’s sole new standard for post-quantum encryption. It is designed to ensure confidentiality and protect against potential quantum computer threats, including "harvest-now, decrypt-later" attacks. It is based on the Module Learning with Errors (MLWE) problem, which offers resistance to both classical and quantum attacks. For example, ML-KEM768 features a public key size of 1,184 bytes, a ciphertext size of 1,088 bytes, and a secret key size of 2,400 bytes. In comparison to traditional elliptic curve cryptography (ECC) algorithms like X25519, ML-KEM’s key and ciphertext sizes are considerably larger. X25519 has a public key and ciphertext sizes of 32 bytes each. While ML-KEM provides robust post-quantum security, its data sizes are notably larger. Nonetheless, ML-KEM's computational efficiency is designed to be competitive, often outperforming elliptic-curve cryptography.
ML-DSA
ML-DSA, or Module-Lattice digital signature algorithm, is the new standard for digital signatures. It was previously known as Dilithium. This post-quantum cryptographic algorithm is designed to resist attacks from classical and quantum computers and is used to guarantee authenticity. Like any digital signature algorithm, it can, for example, be used to digitally sign documents or to authenticate a user. Compared to traditional elliptic-curve cryptography, ML-DSA signatures and public keys are significantly larger. For example, the commonly used traditional signature algorithm Ed25519 uses 32-byte public keys and 64-byte signatures, while ML-DSA (ML-DSA-65) requires 1,952 bytes for the public key and 3,309 bytes for a signature. In addition, signing and verification are more computationally intensive than traditional elliptic-curve cryptography on some platforms.
SLH-DSA
SLH-DSA (Stateless Hash-based Digital Signature Algorithm) is NIST’s alternative digital signature algorithm that may be useful for certain use cases that cannot use ML-DSA. It is based on the SPHINCS+ proposal. It features a very small public key of as little as 32 bytes, but on the other hand, it comes with large signatures of at least 7,856 bytes. In addition, it is the most conservative among the new NIST standards as it only relies on the security of the underlying hash function which is much better understood as it has been studied for decades. This makes SLH-DSA an attractive signature scheme for cases in which the public key size is much more important than the signature sizes, or when a conservative scheme is preferable.
Note that NIST also has standards for stateful hash-based signatures (NISTSP800-208) which were published in 2020. However, those (as the name suggests) require the signer to maintain a state (i.e., persist how many signatures have already been generated with a certain secret key). Keeping this state is often impossible; especially when secret key backup is a requirement, and, hence, stateful schemes are restricted to a small number of use cases.
Future NIST Standardization
Even though initial standards have been produced, there is still a need for improved cryptosystems that perform better in certain applications. This in addition to the fear of potential breakthroughs in cryptanalysis of any of the existing schemes motivates the study and exploration of other constructions for potential future standardization. NIST continues the post-quantum standardization project in two directions. Firstly, they continue the evaluation of some schemes that were under consideration before. In particular, three code-based key establishment schemes (Classic McEliece, BIKE, and HQC) are being evaluated in a 4th round. While none of these schemes can compete with ML-KEM in terms of public key size, they offer small ciphertext sizes and rely on different mathematical problems offering diversity to a portfolio of post-quantum cryptography.
Additionally, NIST has announced that they intend to standardize more digital signature schemes, especially those with small signature sizes and faster verification than the existing choices. NIST called for submissions in 2022 and has accepted 40 candidates for evaluation in 2023. The analysis of those schemes is expected to last for multiple years with one or more additional standardized schemes at the end of the process.
Chelpis Quantum Corp is involved in two promising submissions to the digital signature competition named UOV and MAYO. Researchers at Chelpis have also recently conducted a large study of the performance of candidate algorithms.
Standardization Beyond NIST PQC
While NIST has been leading the international standardization of post-quantum cryptography and is driving forward the migration, other international standardization organizations have also started to update their standards to keep future quantum threats into account. Most notably, the International Standards Organization (ISO) has started to work on a new revision for their standard for asymmetric ciphers (ISO/IEC/18033-2) to include post-quantum cryptography. While this standard is still being developed, it is expected to be published within the next two years and will likely add additional cryptographic schemes in addition to ML-KEM.
Comments