Quantum-resistant algorithms play a crucial role in post-quantum cryptography, which protects against threats on digital signatures and current encryption methods.
It's only a matter of time before quantum computers reach the point where they can break commonly used encryption algorithms such as Rivest-Shamir-Adleman, Diffie-Hellman and Advanced Encryption Standard. We're entering the world of post-quantum cryptography, and the inevitable loss of protection for sensitive encrypted data now drives the development of new quantum-resistant algorithms.
Quantum-resistant algorithms offer new approaches using more complex mathematical problems that are not easily solved by quantum computers. Since no one knows how secure these new algorithms will be, multiple methods are available, should one or more be broken.
The importance of quantum-resistant algorithms
Cryptography algorithms currently in use are secure because computers need a long time to crack them -- possibly thousands of years. This is called computational security. With a quantum computer, that computational security goes away. A quantum computer with more than 4,000 stable quantum bits (qubits) would theoretically break Rivest-Shamir-Adleman (RSA) 2048 encryption in seconds.
No quantum computer today has more than a few dozen stable qubits, but predictions for when a cryptographically relevant quantum computer (CRQC) will arrive range from 2030 to 2035. That doesn't leave much time to prepare because it can take a large organization as much as 10 or more years to transition to a quantum-resistant algorithm.
Research in post-quantum cryptography (PQC) has been happening for years. In 1994, Peter Shor developed Shor's algorithm, the first quantum algorithm designed to break existing encryption algorithms. Since then, NIST has reviewed and certified four quantum-resistant algorithms, with a fifth pending to counter Shor's and other quantum algorithms.
"A realistic, near-term threat of quantum computing is its ability to break widely used public key cryptography systems, which jeopardizes the security and privacy of digital communications," said Nelly Porter, director of product management for confidential computing and encryption, Google Cloud.
Quantum computing also threatens the integrity of digital signatures, which verify the origin of a digital message or document and ensure that it hasn't been tampered with.
"This is crucial for establishing trust in digital communications," Porter said. "We have to ensure that we are preventing the forgery of digital signatures, especially for long-term firmware and software updates."
How do quantum-resistant algorithms work?
Today's encryption algorithms are based on creating private keys of two or more large prime numbers that are then multiplied together. The result becomes part of a public key that someone can use to encrypt a message they send to another person. The recipient can then decrypt the message using the original prime numbers. A quantum computer, however, can quickly calculate the private key from the public key.
RSA and other encryption algorithms have used progressively larger prime numbers to maintain computational security. That won't work when an adversary has a quantum computer, so the following alternative PQC methods are needed.
Lattice-based cryptography
LBC relies on complex mathematical problems using lattices -- think of an infinite grid of intersecting lines in multiple dimensions. The security of LBC depends on identifying specific points on this grid. One set of points could represent a private key while another is the public key. Deriving those key pairs would be relatively easy to do with only a few dimensions, so LBC would need hundreds of dimensions to stay ahead of the capabilities of a quantum computer.
Hash-based cryptography
Hash-based cryptography uses an algorithm called a hash function to convert a key, which can be any data, into a unique hash value or ciphertext. That hash value is a fixed-length string of alphanumeric characters called a digest. Hash-based one-time signature (OTS) schemes use a key pair only once to sign a message; otherwise, the OTS key pair is vulnerable to signature forgery.
Code-based cryptography
Code-based cryptography relies on cryptographic systems that use error-correcting codes. The process creates a public key by mathematically creating an altered version of the private key -- essentially introducing errors. Those errors can be decoded only by the recipient. Code-based cryptography is considered particularly resistant to compromise by quantum computers.
Examples of quantum-resistant algorithms
NIST has released the following four PQC encryption standards. Some are general encryption standards, while others encrypt digital signatures.
Federal Information Processing Standard (FIPS) 203 is the primary general encryption standard. It was selected partly for its relatively small encryption keys, which can be more easily exchanged, and its operating speed. FIPS 203 is a lattice-based algorithm based on the CRYSTALS-Kyber algorithm, now known as the Module-Lattice-Based Key-Encapsulation Mechanism (ML-KEM).
FIPS 204 is the primary standard for protecting digital signatures and is also lattice-based. It uses the CRYSTALS-Dilithium algorithm, now known as the Module-Lattice-Based Digital Signature Algorithm (ML-DSA).
FIPS 205, also designed for digital signatures, is derived from the hash-based Sphincs+ algorithm, now known as the Stateless Hash-Based Digital Signature Algorithm (SLH-DSA). NIST intends FIPS 205 as a backup to FIPS 204.
FIPS 206 is derived from the FALCON lattice-based algorithm. It is now referred to as FN-DSA, which stands for Fast-Fourier Transform over NTRU-Lattice-Based Digital Signature Algorithm. FIPS 206 is also intended for use with digital signatures.
The Hamming Quasi-Cyclic (HQC) algorithm, which has not been finalized, is intended as a general encryption standard to back up FIPS 203, should it become compromised. Like FIPS 203, HQC uses a key encapsulation method to create a shared secret key sent over public channels. However, HQC uses code-based cryptography, which offers high security but requires more computational overhead.
Some vendors have begun adopting NIST PQC standards into their products. For example, Google Cloud's Cloud KMS offers quantum-safe digital signatures employing FIPS 203, 204 and 205 using its API.
Challenges of developing quantum-resistant algorithms
The biggest and most obvious challenge of developing quantum-resistant algorithms is what researchers don't yet know. How capable will the first CRQC systems be, and how fast will they evolve? How far along are adversaries like China and Russia in their efforts to find vulnerabilities in quantum-resistant algorithms? This uncertainty is the reason NIST is certifying backup PQC encryption standards.
No one knows if the Chinese already have broken the CRYSTALS lattice algorithms of NIST.
John PriscoCEO, Safe Quantum
Quantum-resistant algorithms are likely to fail over time, said John Prisco, CEO of consultancy Safe Quantum. "No one knows if the Chinese already have broken the CRYSTALS lattice algorithms of NIST." Prisco recommends addressing such risks with a "defense in depth" approach using quantum science and mathematical algorithms.
What does the future hold for quantum-resistant development?
The primary goal of quantum-resistant development is diversity. Since none of the proposed algorithms can yet be tested in a CRQC environment, multiple options are needed should some become compromised. In the meantime, improvements will be made to existing PQC algorithms.
"Researchers will continue to work on post-quantum cryptography algorithms to make them more efficient, with smaller key sizes and faster computational speeds," Porter said. "This is particularly important for devices with limited resources."
Porter and others agree that quantum-resistant algorithms will do the following:
Become more diverse, with some serving general-purpose encryption needs and others tailored to specific applications.
Use more complex mathematical problems to develop stronger quantum-resistant algorithms.
Integrate into current encryption practices, software, hardware and communication protocols.
Combine with classical encryption algorithms to create hybrid cryptographic systems for greater security.
Prisco believes the best way to protect sensitive data in a PQC world is to combine quantum-resistant algorithms with quantum key distribution. QKD allows two parties to produce a shared random secret key that can then be used with a quantum-resistant algorithm to send encrypted messages securely. China is making a heavy investment in QKD, he said. "Like a Sputnik moment, that should wake up our U.S. quantum community to match the level of investment in QKD as well as PQC.
"Defense in depth is necessary to compete with today's security protection schemes," Prisco continued. "Information-theoretic is defined as an encryption technique that cannot be broken, given infinite time and infinite compute power to attempt a break. QKD is already information-theoretic and should be under increased deployment and development in the U.S.," he said.
However, QKD has a few drawbacks. It is relatively expensive, requires special equipment and dark fiber, and has distance limitations. IBM, which invented the QKD protocol BB84, is not doing much with it commercially. "QKD is good at solving certain types of problems, whereas post-quantum cryptography is a broad-based solution," said Ray Harishankar, IBM Fellow and lead for IBM Quantum Safe.
Quantum-resistant algorithms will go beyond corporate and government networks into devices businesses and consumers use. A particular quantum-resistant algorithm might not perform well in some of these devices.
"We have to look at alternates if you're looking at a smaller form factor, an ATM machine, an IoT device, something embedded in a car," Harishankar said. "There are so many places where encryption occurs. You may have medical devices that are encrypting information. There are so many scenarios where you will need different algorithms with different form factors. We'll find ways to improve the performance of existing algorithms, or we'll find newer algorithms that are more performant in the target device."
Michael Nadeau is an award-winning journalist and editor who covers IT and energy tech. He also writes the PowerTown blog on Substack for stakeholders in local renewable energy initiatives. Follow him on Bluesky at @mnadeau.bsky.social.
