5.11.10 What Is Post-Quantum Cryptography?
- What Is Post-Quantum Cryptography?
- Why Is Post-Quantum Cryptography Needed?
- Does Post-Quantum Cryptography Replace Everything?
- Why Can't We Wait Until Quantum Computers Exist?
- What Makes a Good Post-Quantum Algorithm?
- Which Mathematical Problems Are Used?
- How Were the New Standards Selected?
- Which Algorithms Have Been Standardized?
- Why Are There Several Different Algorithms?
- Will Existing Systems Need to Change?
- What Is Hybrid Cryptography?
- What Challenges Remain?
- Does Post-Quantum Cryptography Mean Quantum Computers Are Needed?
- What Is the Future of Cryptography?
- Why Is Post-Quantum Cryptography Important?
Description
Learn how a new generation of cryptographic algorithms is being developed to resist future quantum-computer attacks. Explore lattice-based cryptography, code-based cryptography, hash-based signatures, and the new NIST post-quantum cryptographic standards that will secure tomorrow's communications.
Introduction
For more than forty years, modern cryptography has relied upon mathematical problems that are believed to be computationally infeasible for conventional computers to solve. Public-key algorithms such as RSA and Elliptic Curve Cryptography (ECC) have become the foundation of secure Internet communications, protecting everything from online banking and electronic commerce to government communications and digital signatures.
The emergence of quantum computing, however, has fundamentally changed the long-term outlook for these systems. As discussed in the previous FAQ, sufficiently powerful quantum computers could use Shor's algorithm to solve the mathematical problems upon which many of today's public-key algorithms depend.
This realization has led to one of the largest transitions in the history of cryptography. Researchers throughout the world have been developing new cryptographic algorithms that remain secure against both classical and quantum computers. Collectively, these algorithms are known as post-quantum cryptography.
Unlike quantum cryptography, which uses quantum mechanics to protect information, post-quantum cryptography consists of conventional mathematical algorithms that can run on today's computers while resisting future quantum attacks.
What Is Post-Quantum Cryptography?
Post-quantum cryptography (PQC) is the branch of cryptography concerned with developing encryption and digital-signature algorithms that remain secure even if large-scale quantum computers become available.
These algorithms are intended to replace vulnerable public-key systems such as:
- RSA;
- Diffie–Hellman;
- Elliptic Curve Cryptography (ECC);
- Elliptic Curve Diffie–Hellman (ECDH);
- Elliptic Curve Digital Signature Algorithm (ECDSA).
Importantly, post-quantum algorithms do not require quantum computers.
They operate entirely on conventional computers, servers, smartphones, and embedded systems.
Why Is Post-Quantum Cryptography Needed?
The need arises because quantum computers threaten many of today's public-key algorithms. Large-scale quantum computers could potentially:
- recover private keys;
- forge digital signatures;
- decrypt previously secure communications.
Replacing vulnerable algorithms before such computers become available is therefore essential.
The transition is expected to take many years because cryptography is embedded throughout modern digital infrastructure.
Does Post-Quantum Cryptography Replace Everything?
No.
Most concern centres on public-key cryptography. Symmetric algorithms such as AES remain highly secure. Increasing key sizes—for example, using AES-256 rather than AES-128—provides substantial protection against known quantum attacks.
Similarly, modern cryptographic hash functions remain suitable with relatively modest adjustments. The largest changes therefore affect:
- public-key encryption;
- digital signatures;
- key exchange.
Why Can't We Wait Until Quantum Computers Exist?
Replacing cryptographic infrastructure is a lengthy process.
Operating systems, web browsers, banking systems, communication protocols, satellites, industrial control systems, and military networks all contain cryptographic components. Many remain operational for decades. Waiting until practical quantum computers appear would leave insufficient time to replace vulnerable algorithms. Furthermore, attackers may already be storing encrypted information today with the intention of decrypting it in the future when quantum computers become available.
This threat is commonly known as Harvest Now, Decrypt Later.
What Makes a Good Post-Quantum Algorithm?
A practical post-quantum algorithm should satisfy several requirements.
It should:
- resist both classical and quantum attacks;
- provide strong mathematical security;
- operate efficiently;
- require reasonable memory;
- integrate with existing communication protocols;
- support practical key sizes and digital signatures.
Achieving all of these objectives simultaneously is a significant engineering challenge.
Which Mathematical Problems Are Used?
Because integer factorization and discrete logarithms are vulnerable to quantum attack, researchers have explored other mathematical foundations.
Several major families of post-quantum algorithms have emerged.
- Lattice-based cryptography. These algorithms rely upon the difficulty of solving certain geometric problems involving high-dimensional lattices. Lattice-based cryptography currently represents the most widely adopted approach.
- Code-based cryptography. These algorithms build upon concepts from error-control coding theory. They exploit the difficulty of decoding certain classes of linear error-correcting codes. Interestingly, they demonstrate another important application of the coding theory discussed in the previous chapter.
- Hash-based signatures. These schemes use cryptographic hash functions rather than number-theoretic problems. They provide highly secure digital signatures and have been studied for many years.
- Multivariate cryptography. These algorithms are based on systems of multivariate polynomial equations. Although several promising candidates have been proposed, many have subsequently been broken during public evaluation.
- Isogeny-based cryptography. These algorithms rely upon properties of elliptic-curve isogenies. Initially considered highly promising, several proposed schemes were later successfully attacked, illustrating the importance of extensive public cryptanalysis.
How Were the New Standards Selected?
Recognizing the importance of the transition, the U.S. National Institute of Standards and Technology (NIST) began an international competition in 2016.
Researchers from around the world submitted candidate algorithms. The evaluation process lasted several years and included extensive public cryptanalysis by the international cryptographic community. Algorithms that survived this scrutiny were selected for standardization.
This open evaluation process resembles the earlier competition that selected the Advanced Encryption Standard (AES).
Which Algorithms Have Been Standardized?
The first generation of standardized post-quantum algorithms includes:
- ML-KEM (Module-Lattice Key Encapsulation Mechanism), derived from the CRYSTALS-Kyber algorithm, for public-key encryption and key establishment.
- ML-DSA (Module-Lattice Digital Signature Algorithm), derived from CRYSTALS-Dilithium, for digital signatures.
- SLH-DSA, derived from SPHINCS+, providing a hash-based digital-signature alternative.
These standards represent the beginning rather than the end of the migration to post-quantum cryptography.
Additional algorithms continue to be evaluated.
Why Are There Several Different Algorithms?
No single cryptographic algorithm is ideal for every application.
Different systems place different emphasis on:
- computational speed;
- memory usage;
- key size;
- signature size;
- implementation complexity.
Some applications require extremely fast key exchange. Others prioritize compact digital signatures or long-term security.
Standardizing multiple algorithms provides flexibility for different applications.
Will Existing Systems Need to Change?
Yes.
Over time, many communication systems will require updates.
These include:
- web browsers;
- Internet servers;
- VPNs;
- mobile-phone networks;
- satellite communication systems;
- cloud services;
- secure email;
- financial systems;
- government networks.
Fortunately, most changes can be introduced through software updates rather than replacing physical communication equipment.
What Is Hybrid Cryptography?
Many organizations are adopting hybrid cryptographic systems during the transition.
These systems use:
- a conventional public-key algorithm; and
- a post-quantum algorithm.
Both operate simultaneously. Only if both algorithms were compromised would security fail.
Hybrid approaches allow gradual migration while maintaining compatibility with existing infrastructure.
What Challenges Remain?
Although great progress has been made, several challenges remain.
Post-quantum algorithms often require:
- larger public keys;
- larger digital signatures;
- increased memory;
- additional processing.
Researchers continue to improve efficiency while maintaining security.
The standardization process is therefore expected to continue for many years.
Does Post-Quantum Cryptography Mean Quantum Computers Are Needed?
No.
This is a common misunderstanding. Post-quantum cryptographic algorithms run on ordinary computers. They are designed because quantum computers may eventually exist—not for quantum computers.
Their purpose is to ensure that today's communication systems remain secure in tomorrow's computing environment.
What Is the Future of Cryptography?
Cryptography has evolved continuously for thousands of years.
Simple substitution ciphers gave way to mechanical encryption machines, which were replaced by electronic algorithms, public-key cryptography, and modern symmetric encryption. Post-quantum cryptography represents the next stage in this evolution.
As computing technology advances, cryptographic algorithms will continue to evolve to address new threats while preserving the confidentiality, integrity, and authenticity upon which modern communication systems depend.
Why Is Post-Quantum Cryptography Important?
Post-quantum cryptography is one of the most significant developments in modern communications security. It provides a practical path for replacing vulnerable public-key algorithms before quantum computers become capable of attacking them.
Although the underlying mathematics differs from earlier systems, the objective remains unchanged: enabling people and organizations to communicate securely, even in the presence of increasingly powerful computers.
Summary
Post-quantum cryptography is the next generation of public-key cryptography, designed to remain secure against both classical and quantum computers. Rather than relying on integer factorization or discrete logarithms, it employs new mathematical foundations such as lattices, error-correcting codes, and hash functions.
The standardization of algorithms such as ML-KEM, ML-DSA, and SLH-DSA marks the beginning of a long-term transition that will affect virtually every secure communication system. Although quantum computers capable of breaking today's encryption have not yet been realized, preparing now will ensure that the confidentiality, integrity, and authenticity of digital communications continue well into the future.
Back to reading