Post-Quantum Cryptography, Explained

Written by Dylan Rudy, Isabella Bello Martinez, and Taylor Michelle Hernandez 

woman using a cell phone and laptop

What Are Cryptosystems?

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. 

How Critical Are Cryptosystems?

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.

How Will Cryptosystems Become 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. 

“Safeguarding U.S. infrastructure and interests requires federal and commercial organizations to stay ahead of future quantum computing threats. Quantum computing is rapidly evolving toward large-scale, practical applications. The first noticeable impact society will see is existing asymmetric cryptography being vulnerable to decryption with quantum computers. Now is the time to prepare for new cryptographic solutions.”

What Can Organizations Do to Protect Cryptosystems?

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.

Why Do Organizations Need to Prepare Now?

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.

What Has the Federal Government Done So Far?

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. 

NIST Algorithm Selections—First Wave

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.

What's the Best Approach to PQC Adoption?

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. 

“Booz Allen conducts PQC prototyping in sandbox environments to help our clients rapidly evaluate the impact of PQC adoption on mission-critical use cases. This testing enables clients to assess the impact of the future migration process, including its potential costs and computing requirements.”

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. 

Explore More Quantum Insights

At the Forefront of the Quantum Revolution

Through legislation and executive action, the federal government is working to ensure U.S. leadership in the field of quantum information science. Booz Allen is committed to supporting this vision.

woman with VR headset

Quantum's Potential to Unlock Finance Insights

Booz Allen’s team of quantum researchers is working to demonstrate how today’s challenging financial questions can be addressed with quantum technology.

Planning for a Quantum Talent Bottleneck

Quantum information science and technology (QIST) is poised to change the world. Luckily, lessons learned from AI implementation can help leaders prepare for the talent challenges ahead for QIST.

woman with VR headset

Quantum for Health Sciences and Technology

The federal government has mandated multiple agencies to support research and development in quantum sciences and technology and to develop programs for growing the future quantum workforce. 

About the Authors:

Taylor Michelle Hernandez
is a lead scientist on Booz Allen’s quantum team. Taylor leads the post-quantum cryptography capability and specializes in the development of quantum-safe applications. She holds bachelor’s degrees in physics and mathematics from the University of Notre Dame.

Dylan Rudy is a quantum physicist at Booz Allen Hamilton, specializing in providing high-impact quantum solutions for clients. He also creates and facilitates educational opportunities to learn more about post-quantum cryptography and fully homomorphic encryption. Dylan earned his Ph.D. from Texas Tech University where he researched vulnerabilities in various key exchange protocols.

Isabella Bello Martinez is a quantum technologist at Booz Allen Hamilton, specializing in strategic thinking for long-term quantum growth strategies and quantum technologies application research. She leads the firm’s outreach initiatives for quantum investment and the delivery of analytical products for a variety of clients. She holds degrees from Brown University and the University of Notre Dame.

Contact Us

Contact us to learn more about preparing for your migration and identifying the best practices you will use. It’s important to consider strategy, cryptosystems inventories, testing, and other key areas to streamline this essential transformation.

1 - 4 of 8