����TV

Co-authored by Shane Kelly

There’s one crucial detail missing from many of the conversations around NIST’s long-awaited release of the final specifications for several post-quantum cryptography (PQC) algorithms: What’s the difference between the initial public draft (IPD) and the final version NIST released?

Let’s dive into the technical aspects of the NIST PQC algorithms to explore what’s changed and discuss the complexity involved with implementing the new standards.

The journey to the final specifications

A bit of history for context: In 2017, ����TV took a proactive role in engaging with the (NIST) in their efforts to establish new cryptographic standards to address the threat quantum computers will pose to traditional encryption methods.

Our involvement was twofold: contributing to the standards development process and working closely with researchers and manufacturers to gain a deeper understanding of the challenges quantum computing will present.

Throughout this journey, ����TV collaborated with a diverse group of industry leaders and academic institutions to tackle these challenges head-on. Our partners included Thales (formerly Gemalto), Utimaco, Microsoft Research, ISARA Corporation, the University of Illinois at Urbana-Champaign, and the University of Waterloo. These collaborations were instrumental in advancing our understanding and development of quantum-resistant cryptography, ensuring that we remain at the forefront of securing the future against emerging technological threats.

How the PQC algorithms came to be

In 2016, NIST kicked off a aimed at addressing quantum computing’s potential to render current public key cryptography algorithms obsolete. The effort yielded four candidate algorithms—one Key Encapsulation Mechanism (KEM) and three digital signature schemes.

On August 24, 2023, NIST released for three of these algorithms, publishing the almost exactly one year later on August 13, 2024.

Throughout the course of the competition, the names of the selected schemes underwent a few changes:��

• Federal Information Processing Standard (FIPS) 203, referred to in the specifications as ML-KEM, is a Module Lattice-based KEM originally submitted under the name CRYSTALS-Kyber.
• FIPS 204, known as ML-DSA in the specifications, is a Module Lattice-based Digital Signature Algorithm initially submitted as CRYSTALS-Dilithium.
• FIPS 205, labeled SLH-DSA in the specifications, is a stateless hash-based signature scheme that began as Sphincs+.
• FIPS-206, designated FN-DSA (Fast Fourier Transform over NTRU-Lattice-Based Digital Signature Algorithm), was originally submitted as FALCON. The final specifications for this candidate weren’t yet included in the recent release.

Comparing the IPD to the final versions

Each algorithm underwent a series of revisions throughout the competition, ranging from minor byte-order adjustments to significant changes in the underlying lattice structure. With each update, the cryptographic community adapted their implementations to align with the latest version.

The release of the final draft was no exception—the implementations had to be updated once more. To show you what that looked like, we’ve drawn up a comparison that focuses on three aspects of each standardized algorithm from the IPD to the final version. For each specification, we’ll compare the key differences between the IPD and final versions, then look at the versions’ interoperability, and finally the change difficulty of the implementations.

ML-KEM/FIPS 203

Differences

The primary distinction lies in how the public value ⍴ and the secret seed σ are generated. In the revised approach, these values are derived using a domain separator that incorporates the parameter 𝐾, specific to each ML-KEM variant. The parameter 𝐾 varies across different ML-KEM variants and serves as a unique identifier in the generation process. The values ⍴ and σ are produced by a hash function 𝐺. While they were previously generated by invoking 𝐺(𝑟𝑎𝑛𝑑𝑜𝑚 _ 𝑠𝑒𝑒𝑑), the new method involves calling 𝐺(𝑟𝑎𝑛𝑑𝑜𝑚 _ 𝑠𝑒𝑒𝑑||𝐾), ensuring the inclusion of the variant-specific parameter 𝐾 in the process.

Interoperability

There will be no interoperability issues between implementations of ephemeral versions of ML-KEM that follow the IPD specification and those conforming to the final draft version. This is because the value ⍴, which is transmitted as part of the public key, remains consistent, and both Encapsulation and Decapsulation processes are indifferent to how ⍴ is computed. But there is a potential for interoperability issues with static versions of ML-KEM, particularly when private keys generated using the IPD version are loaded into a FIPS-validated final draft version of ML-KEM. This potential issue hinges on how the pairwise consistency test for ML-KEM is enforced. Although this scenario is possible, it’s unlikely and can generally be disregarded.

Change difficulty

The change is trivial.

ML-DSA/FIPS 204

Differences

A new hash-then-sign variant called HashML-DSA has been introduced into the specification. While the Keygen function remains unchanged, new signing and verification functions, HashML-DSA.Sign (Algorithm 4) and HashML-DSA.Verify (Algorithm 5), have been added. The specification also recommends using distinct Object Identifiers (OIDs) to differentiate between ML-DSA and HashML-DSA.

An additional parameter known as the context string has been introduced to the sign and verify functions. This context string, along with its length, is prepended to the message before signing. In signature verification, the function HintBitUnpack (Algorithm 21; previously Algorithm 15 in IPD) now includes a check for malformed hints. This check has been reintroduced to prevent buffer overruns.

Modifications have been made to the generation of the verifier's challenge. Instead of using only the first 256 bits of the commitment hash, the entire commitment hash is now passed into the SampleInBall function. This change does not impact ML-DSA-44, as its commitment hash outputs 256 bits, but it does affect ML-DSA-65 and ML-DSA-87.

There’s also a change in the generation of the public value ⍴ and the secret seeds ⍴' and 𝐾. These values are now generated using a domain separator that incorporates the parameters 𝐾 and 𝐼, specific to each ML-DSA variant. The hash function 𝐻 produces ⍴, ⍴', and 𝐾. Previously, these were generated by invoking 𝐻(𝑟𝑎𝑛𝑑𝑜𝑚 _ 𝑠𝑒𝑒𝑑); now, they’re generated by calling 𝐻(𝑟𝑎𝑛𝑑𝑜𝑚 _ 𝑠𝑒𝑒𝑑∣∣𝐾∣∣𝐼).

Lastly, the function ExpandMask, which is used to compute the signer’s commitment, was purportedly modified. However, upon examining the two algorithms (Algorithm 34; previously Algorithm 28 in IPD), no differences were observed.

Interoperability

The introduction of a signature context string parameter completely disrupts interoperability. Even if this parameter is not exposed to customers, backward compatibility is still compromised. As a result, HashML-DSA is incompatible with ML-DSA, both now and the future.

Change difficulty

Integrating ML-DSA and HashML-DSA at the protocol level will present significant challenges. Since the two are incompatible and users aren’t mandated to use HashML-DSA for hash-then-sign operations, these differences will lead to protocol-level difficulties

SLH-DSA/FIPS 205

Differences

A hash-then-sign variant named HashSLH-DSA has been introduced into the specification. While the Keygen function remains unchanged, new signing and verification functions, hash_slh_sign (Algorithm 23) and hash_slh_verify (Algorithm 25), have been added. The specification doesn’t mention any Object Identifier (OID) differences between SLH-DSA and HashSLH-DSA. An additional parameter called the context string has been added to the sign and verify functions. This context string, along with its length, is prepended to the message prior to signing.

Interoperability

Due to the addition of the signature context string, there’s no backward compatibility for SLH-DSA. Going forward, HashSLH-DSA will not be compatible with SLH-DSA.

Change difficulty

The addition of the hash-then-sign variants presents the same challenges as the hash-then-sign versions of ML-DSA. Once the challenges associated with ML-DSA are solved, those solutions will apply directly to SLH-DSA. All other changes are trivial.

What’s next for PQC?

The concept of domain-separated signatures for hash-then-sign and “pure” signing is new for NIST, and it requires careful consideration to ensure the best outcome for all users.

A secondary concern involves the handling of the context string in signatures. It may be wise to consult with experts in the cryptography community to help shape the industry standard. There’s a possibility that this option could be universally hidden, allowing it to be safely disregarded.

Implementing these changes in our cryptographic systems will be straightforward and shouldn’t take long. But challenges will arise when creating test vectors and conducting compatibility tests with other implementations, as none currently exist.

At ����TV, we’ve implemented the PQC signature algorithms in a variety of our products, and our ����TV^® ONE PKI management platform already supports all three. The ����TV^® TrustCore SDK developer toolkit is also equipped to support ML-KEM/FIPS 203 alongside the full suite of PQC signatures.

The latest developments in digital trust

Want to learn more about topics like post-quantum cryptography, encryption, and PKI? Subscribe to the ����TV blog to ensure you never miss a story.