After much anticipation, the National Institute of Standards and Technology (NIST) issued its first Post Quantum Cryptography (PQC) standards today. They are intended to defeat efforts by quantum computers powerful enough to decrypt data and communications that have been encrypted mostly using the RSA (Rivest-Shamir-Adleman) cryptosystem. This is significant step forward and expected to prompt a flood of new tools and products to implement the new standards.

Begun in 2016, NIST’s PQC program has worked in collaboration with industry to select new algorithms that would be less susceptible to attack by quantum computers. There’s also a formal Migration to Post Quantum Cryptography Project, run out of the NIST’s National Cybersecurity Center of Excellence, intended to develop practices and tools to ease companies’ efforts in adopting the new standards.

While the PQC race loosely began in 1994 when Shor’s Algorithm was shown to be able to crack existing RSA codes if run on a sufficiently powerful quantum computer, it didn’t speed up until a decade ago as efforts to develop practical quantum computers accelerated. Since then the sense of urgency has grown. The National Security Agency, for example, has already introduced PQC technology based on NIST draft standards into its Commercial National Security Algorithm Suite issued in 2022.

NIST has now formalized the following three PQC standards to strengthen modern public-key cryptography infrastructure for the quantum era:

• ML-KEM (derived from CRYSTALS-Kyber) — a key encapsulation mechanism selected for general encryption, such as for accessing secured websites
• ML-DSA (derived from CRYSTALS-Dilithium) — a lattice-based algorithm chosen for general-purpose digital signature protocols
• SLH-DSA (derived from SPHINCS+) — a stateless hash-based digital signature scheme

A fourth algorithm, FALCON, is expected to become a standard in 2024.

As wryly noted in IEEE Spectrum’s coverage, “These four winning algorithms had intense-sounding names: CRYSTALS-Kyber, CRYSTALS-Dilithium, Sphincs+, and FALCON. Sadly, the names did not survive standardization: The algorithms are now known as Federal Information Processing Standard (FIPS) 203 through 206. FIPS 203, 204, and 205 are the focus of today’s announcement from NIST. FIPS 206, the algorithm previously known as FALCON, is expected to be standardized in late 2024.”

The algorithms fall into two categories: general encryption, used to protect information transferred via a public network, and digital signature, used to authenticate individuals.

In the official announcement, Deputy Secretary of Commerce Don Graves, said, “The advancement of quantum computing plays an essential role in reaffirming America’s status as a global technological powerhouse and driving the future of our economic security. Commerce bureaus are doing their part to ensure U.S. competitiveness in quantum, including the National Institute of Standards and Technology, which is at the forefront of this whole-of-government effort. NIST is providing invaluable expertise to develop innovative solutions to our quantum challenges, including security measures like post-quantum cryptography that organizations can start to implement to secure our post-quantum future”

Bracing for Q-Day

How near the decryption-by-quantum-computers threat actually is remains a matter of debate. It’s thought that it will take fault-tolerant quantum computers to effectively run Shor’s algorithm. That could be decades away, although the quick pace of quantum computing advances keeps shrinking the time-frame. Moreover, it’s now thought full-fault-tolerance may not be required and the term “cryptographically relevant quantum computer” (CRQC) has begun being used.

One worry is the so-called Harvest-Now-Decrypt-Later strategy in which bad actors steal and store existing encrypted data and simply store it until sufficiently powerful quantum computers become available. Today, virtually all data — financial, medical, personal, et.c —is encrypted somehow, much of it using RSA methods. It’s been reported that perhaps more than 20 billion devices will need to upgrade their software to PQC.

• 

  Dustin Moody, a leader of NIST PQC project, told HPCwire, “The United States government is mandating their agencies to it, but industry as well as going to need to be doing this migration. The migration is not going to be easy [and] it’s not going to be pain free. Very often, you’re going to need to use sophisticated tools that are being developed to assist with that. Also talk to your vendors, your CIOs, your CEOs to make sure they’re aware and that they’re planning for budgets to do this. Just because a quantum computer [able to decrypt] isn’t going to be built for, who knows, maybe 15 years, they may think I can just put this off, but understanding that threat is coming sooner than than you realize is important.”

• Celia Merzbacher, executive director of the Quantum Economic Development Consortium (QED-C), said, “The new PQC standards are an important element of a robust cybersecurity strategy for all enterprises that have data they need to protect. Quantum computers that can break current encryption pose threats in the future, but also today due to the ability to “harvest now and decrypt later.” As a consortium representing the broad quantum community, QED-C encourages the timely adoption of the PQC standards across all sectors, including those responsible for critical infrastructure such as transportation, energy, and financial systems.”

QED-C has produced an excellent primer report, Quantum Technology for Securing Financial Messaging, that explains the two primary PQC tools – Post Quantum Cryptography and Quantum Key Distribution (QKD) – available for fighting decryption by quantum computers. While focused on FS, the ideas in the report are widely applicable.

Here’s a brief excerpt:

“According to current best estimates, the likelihood that a quantum computer capable of breaking RSA-2048 within 24 hours will emerge within the next ten years is materially high. Furthermore, any classically encrypted communication transmitted through an unprotected network, such as the internet, is at risk today, and possibly already subject to exfiltration…The stakes are high, given that data protection mechanisms for internet communications, digital signatures, passwords, contracts, and other documents would become instantly obsolete as soon as a sufficiently powerful quantum computer became operational.”

The PQC standard development process was interesting and typical for cryptography. Basically, regulators look for hard math problems that have proven difficult or impossible to solve. NIST invites the broader community to submit possibilities, then tests them against its own and community resources. After the winnowing process, NIST picks winners which can be used as the base of PQC tools.

Among the criteria for selecting algorithm are their strengths in resisting attack and the amount of compute resources required to perform data encryption/decryption. Organizations can, to some extent, choose which standards to use based on their security needs (strength) against their available compute resources (processors, memory, power), and performance requirements (speed, time to solution).

With official publishing of the NIST standards, the deluge of related tools and services will formally begin and many have been actively preparing for this next step.

IBM, for example, held a virtual briefing in July featuring NIST mathematician Lily Chen, IBM cryptography researcher Vadim Lyubashevsky, Richard Marty, CTO LGT Financial Services, and Joost Renes, principal security architect and cryptographer & PQC security architecture domain lead, NXP Semiconductors to discuss PQC plans.

At that briefing, Chen said, “[It’s important] for everyone to understand that NIST selected these algorithms from the worldwide submissions. We received 82 submissions to from 25 countries and in six continents. So the whole procedure, evaluation, analysis and public is under the public scrutiny, I think, for these algorithms. So that’s to [show] it an open and transparent process.”

Renes of NXP said, “We’ve been talking to customers for many years, even going back as far as 2016, although post quantum algorithms were just being developed. Back then the questions were typically things like, when is a quantum computer going to be here? Or even, how does a quantum computer work? Technically interesting questions, but not very focused on migration or adoption yet. Today, this is very different. We see a lot of customers are now starting to ask, which algorithm should we choose? When is the final standard going to be here? When are the protocol standards going to be here?”

Not surprisingly, IBM is touting its contribution to the new PQS standards () as well as its its Quantum Safe tools and practices — “The standards include three post-quantum cryptographic algorithms: two of them, ML-KEM (originally known as CRYSTALS-Kyber) and ML-DSA (originally CRYSTALS-Dilithium) were developed by IBM researchers in collaboration with several industry and academic partners. The third published algorithm, SLH-DSA (initially submitted as SPHINCS+) was co-developed by a researcher who has since joined IBM. Additionally, a fourth IBM-developed algorithm, FN-DSA (originally called FALCON), has been selected for future standardization.”

Indeed, comments from throughout the community are likely to begin pouring in. This is from, Duncan Jones, head of cybersecurity, trapped ion quantum computing specialist Quantinuum: “We welcome NIST concluding this vital industry-wide process. Today represents a crucial first step towards protecting all our data against the threat of a future quantum computer that could decrypt traditionally secure communications. Every CISO now has a mandate to urgently adopt these new standards alongside other methods for hardening their cybersecurity systems. We know that data stolen today could be decrypted at any time in the future, and sensitive data such as health records or financial data falling into the wrong hands would be damaging. We work with a wide range of enterprise customers, and it’s clear that successful CISOs recognize quantum is an ally as well as a threat.”

Google today posted a blog offering advice on how to manage the transition to PQC. Here’s an excerpt:

“Migrating to new cryptographic algorithms is often a slow process, even when weaknesses affect widely-used crypto systems, because of organizational and logistical challenges in fully completing the transition to new technologies. For example, NIST deprecated SHA-1 hashing algorithms in 2011 and recommends complete phase-out by 2030.

“That’s why it’s crucial to take steps now to improve organizational preparedness, independent of PQC, with the goal of making your transition to PQC easier.

“These crypto agility best practices can be enacted anytime:

Cryptographic inventory Understanding where and how organizations are using cryptography includes knowing what cryptographic algorithms are in use, and critically, managing key material safely and securely

Key rotation Any new cryptographic system will require the ability to generate new keys and move them to production without causing outages. Just like testing recovery from backups, regularly testing key rotation should be part of any good resilience plan

Abstraction layers You can use a tool like Tink, Google’s multi-language, cross-platform open source library, designed to make it easy for non-specialists to use cryptography safely, and to switch between cryptographic algorithms without extensive code refactoring

End-to-end testing PQC algorithms have different properties. Notably, public keys, ciphertexts, and signatures are significantly larger. Ensure that all layers of the stack function as expected

“Our 2022 paper ‘Transitioning organizations to post-quantum cryptography’ provides additional recommendations to help organizations prepare and this recent post from the Google Security Blog has more detail on cryptographic agility and key rotation.”

There will be plenty of resources available.

The Migration to Post-Quantum Cryptography (MPQC) project, being run out of NIST’s National Cybersecurity Center of Excellence (NCCoE), is running at full-tilt and includes on the order of 40 commercial participants. The list of project consortium participants with links (from MPCC websites) is at the end the article. It is also supposed to provider best-practice guidance.

In its own words, “The project will engage industry in demonstrating use of automated discovery tools to identify all instances of public-key algorithm use in an example network infrastructure’s computer and communications hardware, operating systems, application programs, communications protocols, key infrastructures, and access control mechanisms. The algorithm employed and its purpose would be identified for each affected infrastructure component.”

In the past, encryption-decryption technology has been infused throughout IT infrastructure (software and devices). Simply finding it can be a daunting task, hence Moody’s comment, “The migration is not going to be easy [and] it’s not going to be pain free. Very often, you’re going to need to use sophisticated tools that are being developed to assist with that.”

Today the security community talks about crypto-agility and modular architecture in which various cryptography technologies can be quickly found and revised or swapped out as needed. (See HPCwire article, NIST Q&A: Getting Ready for the Post Quantum Cryptography Threat?, and another, The Race to Ensure Post Quantum Data Security, for background.)

Link to NIST announcement, https://www.hpcwire.com/off-the-wire/nist-releases-first-3-finalized-post-quantum-encryption-standards

Link to NIST PQC Explainer, https://www.nist.gov/cybersecurity/what-post-quantum-cryptography

Threat Figure from Quantum Treat Timeline Report released in December by the Global Risk Institute (GRI)

List of MPQC Project Consortium Participants

• Amazon Web Services, Inc. (AWS) 
• ATIS
• Cisco Systems, Inc.
• Cloudflare, Inc.
• Comcast
• Crypto4A Technologies, Inc.
• CryptoNext Security
• Cybersecurity and Infrastructure Security Agency (CISA)
• Data-Warehouse GbmH
• Dell Technologies
• DigiCert
• Entrust
• HP, Inc.
• HSBC
• IBM
• Information Security Corporation
• InfoSec Global
• ISARA Corporation
• JPMorgan Chase Bank, N.A.
• Keyfactor
• Kudelski IoT
• Microsoft
• National Security Agency (NSA)
• NXP Semiconductors
• Palo Alto Networks
• Post-Quantum
• PQShield
• QuantumXchange
• SafeLogic, Inc.
• Samsung SDS Co., Ltd.
• SandboxAQ
• Santander
• SSH Communications Security Corp
• Thales DIS CPL USA, Inc.
• Thales Trusted Cyber Technologies
• Utimaco
• Verizon
• wolfSSL