Quantum-Proof: NIST redefines the future of encryption

Co-Author: Rose Quijano-Nguyen

NIST approves post-quantum cryptography algorithms

Over the past several years, there has been steady progress toward building quantum computers. The security of many commonly used public-key cryptosystems will be at risk when large-scale quantum computers are realized.  By many accounts, this will occur by the end of this decade.  This will break traditional key-establishment schemes and digital signature schemes based on integer factorization and discrete logarithms (both over finite fields and elliptic curves). In anticipation, NIST initiated a public Post-Quantum Cryptography (PQC) Standardization process in 2016 to select quantum-resistant public-key cryptographic algorithms for standardization. A total of 82 candidate algorithms were submitted to NIST for consideration.  The first official approval was LMS and XMSS as documented in SP 800-208, published October 2020, with the caveat that, due to difficulties with state management, they were not recommended for general use but rather for early adopters of constrained devices (long life without update ability).  On August 13, 2024, after much anticipation, NIST released the official standards for several post-quantum cryptographic algorithms approved for general use.

Module-Lattice-based Key-Encapsulation Mechanism (ML-KEM) (FIPS 203)

A key encapsulation mechanism (KEM) is a specific type of key establishment scheme used to establish a shared secret key between two parties communicating over a public channel.  SP 800-227 is a new draft publication that discusses the general properties of KEMs in detail, including security properties and requirements for the secure use of KEMs in applications, including FIPS 140 validation. The encapsulation algorithm of ML-KEM accepts an encapsulation key (ek) – i.e., the other party's public key, as input.  It requires randomness and outputs a shared secret key (K) as well as ciphertext (c) containing the encrypted shared secret to be sent to the other party.  The decapsulation algorithm of ML-KEM uses the owner’s private decapsulation key (dk) and the ML-KEM ciphertext (c) as input, does not use any randomness, and outputs a shared secret key (K’).  The standard utilizes the hash functions SHA3-256 and SHA3-512, as well as the eXtendable-Output Functions (XOF) SHAKE128 and SHAKE256 as defined in FIPS 202.  The following table indicates the sizes (in bytes) of the related elements:

Module-Lattice-based Digital Signature Algorithm (ML-DSA) (FIPS 204)

ML-DSA is a signature generation and signature verification scheme.  Like other asymmetric schemes, it has public and private keys of varying sizes, reflective of varying security strength levels. The following table indicates the sizes (in bytes) of the related elements for the approved parameter sets:

There is also a HashML-DSA variant accepts a pre-hash of the message using any approved hash function and then performs ML-DSA on the result.  The signing operation takes a random, but while not recommended, it can be zero, which is referred to as the deterministic vs. hedged variant of the algorithm.

StateLess Hash-based Digital Signature Algorithm (SLH-DSA) (FIPS 205)

FIPS 205 specifies the Stateless Hash-Based Digital Signature Standard.  This contrasts with the stateful systems of LMS and XMSS.   

The following table summarizes the parameter sizes (in bytes) for the different parameter sets.

Like ML-DSA, SLH-DSA also has a HashSLH-DSA, deterministic, and hedged variants.

The three different parameter sets for each scheme correspond to increasing security strength.  These generally correspond to 128, 192, and 256 bits of security strength.  Security strength is discussed in more depth in SP 800-57, with an anticipated update related to these new PQC standards.  These algorithms were added to the FIPS 140 standard through inclusion in the SP 800-140C and SP 800-140D list of approved algorithms.  The NIST ACVTS has already implemented testing for these algorithms, excluding XMSS, which means specific implementations can be validated to obtain official NIST CAVP certificates.   FIPS 140-3 compliance, among other things, requires operational self-tests as described in the FIPS 140-3 Implementation Guide (IG).  

NIST is also developing FIPS 206 that specifies the FN-DSA digital signature algorithm derived from FALCON, which utilizes floating point arithmetic as an additional alternative to these standards.  The draft release of FIPS 206 is imminent.  Additionally, there was a fourth round of review in which NIST selected HQC as an additional KEM and expects to release a draft standard for comment in about a year.  NIST also initiated a review for additional digital signature schemes.  Of 40 accepted 14 have been selected for advancement to the next round of review.  The adoption of PQC represents a significant worldwide technology retooling and adoption effort, making it a critical activity for long development cycle and long-life products.

References:

NIST Special Publications and FIPS Standards

• SP 800-208: Recommendation for Stateful Hash-Based Signature Schemes
• SP 800-227: Recommendations for Key-Encapsulation Mechanisms (Initial Public Draft)
• SP 800-57 Part 1 Rev. 5: Recommendation for Key Management: Part 1 – General
• SP 800-140C: CMVP Approved Security Functions
• SP 800-140D: CMVP Approved Sensitive Parameter Generation and Establishment Methods
• FIPS 203: Module-Lattice-Based Key-Encapsulation Mechanism Standard
• FIPS 204: Module-Lattice-Based Digital Signature Standard
• FIPS 205: Stateless Hash-Based Digital Signature Standard
• FIPS 140-3: Security Requirements for Cryptographic Modules
• FIPS 140-3 Implementation Guidance (IG): FIPS 140-3 IG PDF

NIST Projects and Validation Systems

• NIST Post-Quantum Cryptography (PQC): Post-Quantum Cryptography Project Overview
• NIST IR 8528: Status on the First Round of the Additional Digital Signature Schemes for the NIST Post-Quantum Cryptography Standardization Process
• NIST IR 8545: Status Report on the Fourth Round of the NIST Post-Quantum Cryptography Standardization Process
• NIST ACVTS: How to Access the Automated Cryptographic Validation Testing System (ACVTS)

About the Co-Author

Dr. Rose Quijano-Nguyen is a visionary Security Privacy Leader in Intel’s HW Security IP organization, shaping the future of cybersecurity. With deep security compliance and risk management expertise, she drives cutting-edge initiatives that fortify Intel’s technological edge. Her leadership ensures the highest protection standards, safeguarding data, privacy, and innovation. As a field trailblazer, she continues redefining excellence in security and trust. Rose holds an MBA with an emphasis on Technology Management from the University of Phoenix and a doctorate in Leadership, Education, and Change from Fielding Graduate University.