Post-Quantum Cryptography, Explained

Computers deploy a collection of cryptographic algorithms—a set of instructions or steps—known as a “cryptosuite” to protect vulnerable information. Any security service that deploys a cryptosuite to secure data is known as a “cryptosystem.”

A cryptosystem supports secure communication by deploying algorithms to establish a shared secret value, known as a “key,” used for encryption and decryption purposes. A cryptosystem also allows communicating entities to verify one another’s identity via a “digital signature.” A digital signature authenticates a user through the use of a value which is privately known by the user and a mathematically related, publicly known value accessible to all parties in communication. Algorithms using a pair of private and public values, instead of a single shared value, are known as “asymmetric cryptographic algorithms” or public-key cryptography.

Cryptosystems permeate our daily activities. To read this explanation of PQC, your laptop established a key with Booz Allen’s server. A secure session was established, and the server provided your computer with a digital signature and a method to authenticate the digital signature, allowing you to read on with the confidence that this article is really from Booz Allen. 

Global cryptosystems are essential in today’s digital world—protecting access to utilities, ensuring financial transactions, and verifying proper access to information, as well as guaranteeing the security and operations of hospitals, schools, financial institutions, and more. Failed cryptosystems—in addition to causing massive disruptions in the use of mobile phones, social media, personal banking, and other technologies—would create severe risks for agencies that protect the nation. If cryptosystems no longer function, all internet-based communication is vulnerable.

In 1994, mathematician Peter Shor developed an algorithm that demonstrated the potential disruptive capacity of quantum computers. Quantum computers are computational devices that exploit the properties of quantum physics to solve certain problems differently and, in some cases, faster or more efficiently than what is otherwise possible. Shor’s Algorithm challenged the encryption at the foundation of many modern cryptosystems by establishing a "quantum algorithm" that can rapidly solve the same math problems that underpin the security of today’s asymmetric cryptographic algorithms. This means that, if bad actors have access to sufficiently advanced quantum computing hardware, they could use an existing quantum algorithm to break digital communications secured with today’s cryptosystems.

The use of Shor’s Algorithm (and other quantum algorithms) could create a chaotic environment for sharing and storing vital information. Although the hardware necessary to run Shor’s Algorithm does not currently exist, quantum developers are working on actualizing a "cryptographically relevant quantum computer" (CRQC) within the next few decades. To mitigate the threat a CRQC poses, any plan to modernize and secure cryptosystems must treat its arrival as an inevitability. 

In the future, adversaries could launch cyberattacks that are supported by CRQCs executing quantum algorithms. To sustain operations, organizations that protect critical infrastructure will need a new approach: post-quantum cryptography (PQC). PQC runs on “classical” computers, rather than quantum computers. PQC algorithms are created using underlying mathematical problems which no known classical or quantum algorithm can solve to efficiently recover a user’s privately known secret key. This means that organizations that deploy PQC are protected from hackers with access to both classical and quantum computing hardware, and, because the solution is classical, this process can begin today.

Led by the National Institute of Standards and Technology (NIST), a comprehensive public-private collaboration is well under way to identify, refine, and operationalize several PQC algorithms before researchers can successfully build a CRQC.

Preparing for CRQCs and adopting PQC will be difficult and time-consuming. The first CRQCs will likely be operational within our lifetime. To thwart future quantum-based attacks, organizations will use classical computers to encrypt existing, stored data all over again with PQC. They’ll also need to remove obsolete records and archives from their systems. This overhaul will impact different facets of a cryptosystem, such as the authentication of users, key exchange, and digital signatures. Due to this, the process of migrating to PQC could take decades. Complexities include the potential need to match specific PQC algorithms with particular applications, the nuances of hardware and operating systems, and uncertainty over what measures are already in place.

Anything not updated to PQC may become vulnerable as soon as a CRQC is available. Whether it’s social media accounts, patient health records, bank account passwords, or battlefield intelligence, bad actors and adversaries will be able to steal, change, or delete information. With so much at stake, organizations will need support to align their migration processes with NIST’s standards and systematically implement robust PQC algorithms over time.

President Biden’s January 2022 memo on modernizing cybersecurity for national security, defense, and intelligence systems provides direction on planning for comprehensive cybersecurity improvements. The directive includes migration from unsupported cryptography to post-quantum protocols. Integrating PQC adoption with larger modernization efforts offers agencies multiple advantages such as increased cost control, efficient change management, and accelerated workforce upskilling. Organizations can also inform their adoption preparation with analysis from the National Security Agency and the Department of Homeland Security as well as NIST. President Biden’s May 2022 National Security Memorandum on U.S. leadership in quantum further details requirements for mitigating specific encryption risks. 

In July 2022, NIST announced the first wave of PQC algorithms selected as potential 2024 cryptographic standards. The new 2024 standards are meant to replace currently deployed algorithms used to establish keys for secure communication and authenticate users through digital signatures. CRYSTALS-KYBER was announced as a candidate for a method that can be used by two parties to agree on a key, a step which precedes secure communication between those parties. As of August 2022, CRYSTALS-KYBER has demonstrated resilience against attacks using both classical and quantum algorithms.

NIST also selected three digital signature algorithms to provide quick and efficient methods to verify users’ identities: CRYSTALS-Dilithium, FALCON, and SPHINCS⁺:

• CRYSTALS-Dilithium, like CRYSTALS-KYBER, has demonstrated strong resilience against potential attacks.
• FALCON was selected to support specific use cases that have smaller resource requirements than what is needed with CRYSTALS-Dilithium.
• CRYSTALS-Dilithium and FALCON use the same underlying mathematics; therefore, SPHINCS+ was selected as an additional digital signature algorithm based on different mathematics.

The practice of choosing algorithms that rely on different mathematics to make it harder for sensitive data to be decrypted, known as “cryptographic diversity,” is critical to the overall success of PQC modernization efforts. Relying on one type of algorithm would prevent a rapid response to the constantly changing threat landscape related to the security of cryptographic algorithms.

The same NIST announcement notified the public of four additional key-establishment algorithms proceeding to a fourth round of consideration. However, shortly after the announcement of the fourth round, researchers were able to break one of the candidate PQC algorithms from a previous round of NIST’s standardization competition. The discovery of exploits in an algorithm that cleared three rounds of NIST’s official process reinforces the need for flexibility in the implementation of cryptosystems, also known as “crypto-agility,” which would permit cryptographic algorithms to be updated as more information on their security and longevity becomes available.

Organizations should begin transitioning to PQC as soon as possible. Adopting a multi-phased approach to PQC adoption will help ensure that communication systems and data remain secure. An effective transition strategy should first inventory all cryptography-dependent systems and applications while assessing available algorithms and relevant cryptographic standards and their requirements. Next, organizations should seek to improve their crypto-agility by defining how to quickly integrate the first slate of new PQC standards while ensuring enough cryptosystem flexibility to be able to incorporate additional PQC algorithms in the future. They should then test how their systems perform with those new algorithms. 

Quantum technologies are advancing rapidly, underscoring the need for organizations to begin planning their migrations to PQC as soon as possible. Booz Allen’s cybersecurity practitioners work with nearly every federal, defense, and intelligence agency as well as commercial organizations in all critical infrastructure sectors. We combine our extensive cybersecurity experience with cutting-edge quantum expertise to deliver defensive solutions to help our clients stay ahead of emerging threats.