NIST Publishes First Draft Standards for Post-Quantum Cryptography

The first draft standards for quantum-resistant public key cryptography based on algorithms chosen by the National Institute for Standards and Technology (NIST) are now available for public comment.

On Aug. 24, NIST published three of the four algorithms that the standards body selected last year: Crystals-Kyber, Crystals-Dilithium, and Sphynx+. The formal names of the draft standards will be known respectively as ML-KEM, ML-DSA, and SLH-DSA, NIST revealed. Because the fourth algorithm, Falcon, requires significantly more complex computation, NIST is aiming to publish that draft standard, to be named NL-DSA, early next year.

The publication of NIST's first post-quantum cryptographic (PQC) draft standards marks an important milestone in its effort, launched in 2016, to address the potential for quantum computers to break existing RSA encryption and elliptic-curve cryptography (ECC).

The release of the draft standard opens 90 days for public comment, says Dustin Moody, a mathematician at NIST who leads its PQC standardization project.

"Hopefully, within a few months after that, we'll be able to make any changes and publish the finalized versions of the standards," Moody says.

The release of the drafts sets the stage for the Internet Engineering Task Force (IETF) to focus on interoperability, adds Tim Hollebeek, industry and technical standards strategist at DigiCert.

"People can now see what we want to use for key exchange and key encapsulation, which is Kyber, and we now know that Dilithium will be the primary signing algorithm that we'll be using," says Hollebeek, who co-chairs the IETF's Limited Additional Mechanisms for PKIX and SMIME (LAMPS) working group.

PQC Implementation Testing to Begin

With the release of the draft standards, engineers can start working on prototypes of various capabilities, such as how secure email and the implementation of TLS might work in the future, Hollebeek says.

"One of the important things about asymmetric cryptography is the entire use case is around two people trying to communicate with each other securely," he says.

During a live workshop last week at NIST's National Cybersecurity Center of Excellence (NCCoE) — its first live gathering since the pandemic — Hollebeek participated in a panel discussion on interoperability.

"We need to know that everybody's implementation of the protocols will work correctly with everybody else's implementation of the protocols," he said

Looking ahead, various stakeholders will gather in November for hackathons in advance of the next IETF meeting in Prague, where they will test each other's implementations of the PQC draft standards.

"We're working together with some of our competitors and some of our friends on making sure that our reading of the standards and their readings of the standards agree," Hollebeek says. "And a lot of times when people find out that the implementations don't interoperate with each other, what it does is it points out ambiguities in the standard — things that people didn't specify correctly."

Among those that will work with vendors such as DigiCert and Entrust is PKI provider Keyfactor, whose co-founder and CTO, Ted Shorter, says ensuring interoperability is complex.

"All these algorithms have different parameters, key lengths, and exponent sizes, and all these different things that you can use as a part of a cryptographic algorithm," Shorter says. "And there's different parameter sets that must be considered."

Shorter says the four algorithms selected by NIST are now supported in the open source project it sponsors. Bouncy Castle includes a set of lightweight cryptographic APIs for Java and C#, as well as providers for the Java Cryptography Extension (JCE), Java Cryptography Architecture (JCA), and Java Secure Socket Extension (JSSE).

Call for More Signature Algorithms

Building on the four algorithms that will become the first PQC standards, NIST put out a calllast September for additional digital signature proposals — specifically not based on structure lattices. NIST requested algorithms with short signatures that enable rapid verification for applications, such as certificate transparency.

NIST emphasized that any structured lattice-based signature proposal must substantially outperform Dilithium and Falcon. Moody says NIST received 50 submissions, 40 of which met the criteria for consideration.

Fears that quantum computers could break current encryption began to emerge in 1994 when MIT professor Peter Shor famously described how a quantum computer could easily do so. Unlike conventional computers, which process ones and zeros to perform calculations, quantum computers use qubits, described as subatomic particles, such as electrons or photons.

Only a handful of companies claim the resources to develop quantum computers; several have revealed advances in recent years. Among those that have revealed their quantum computing capabilities are IBM, Google, Microsoft, and Quantinuum, a company spun out of Honeywell.

Experts in computing, cybersecurity, and physics have debated for some time when a quantum computer capable of running what is known as Shor's algorithm can break current encryption. No one knows when a commercially viable quantum computer will emerge because it will require breakthroughs in physics yet to be achieved.

Still, many experts predict quantum computing capability could surface within the next decade. Some say it could happen sooner, while others see no time frame. Perhaps the most notable skeptic is famous cryptographer Adi Shamir.

During the Cryptographers Panel at this year's RSA Conference, Shamir gave what he admitted was a harsh view.

"I must say that the main things which have been delivered are more promises, and as of today, not a single practical problem has been shown to be solvable by one of the available quantum computers faster than on a classical computer," he said.

Although Shamir didn't suggest that quantum computers would never be a threat to cryptography, he said a usable system could be 30 or more years in the future. Nevertheless, Shamir conceded, "Using older algorithms such as RSA or elliptic curves might become decryptable in the future."

However, many believe a quantum system that could break existing encryption could surface within the next decade; the National Security Agency (NSA) shares those concerns. In September 2022, the NSA announced a migration path from the current Commercial National Security Algorithm (CNSA) Suite 1.0, which includes the 256-bit Advanced Encryption Standard (AES), Elliptic-curve Diffie–Hellman, and the Elliptic Curve Digital Signature Algorithm.

Bringing more urgency to the debate, late last year US President Joe Biden signed the Quantum Computing Cybersecurity Preparedness Act into law, directing the Office of Management and Budget (OMB) to implement the NIST-approved cryptographic algorithms.

In September 2022, the NSA issued an order mandating government agencies to ensure all of their systems are migrated to the NIST-selected quantum-resistant algorithms by 2035.

While it may be an ambitious goal, NIST's Moody believes it's a reasonable path.

"We're trying to help get this transition migration happening as quickly as possible," Moody says. "Crypto transitions always take way longer than we expect or want them to. We're glad that they're trying to make sure agencies are going as fast as they can."