Post-Quantum Cryptography: Preparing Encryption for the Quantum Computing Threat

Why Shor's Algorithm Breaks RSA and Elliptic-Curve Cryptography

Modern public-key cryptography, including RSA and elliptic-curve systems, is built on mathematical problems that are easy to compute in one direction but extraordinarily hard to reverse using classical computers. RSA's security relies on the difficulty of factoring the product of two large prime numbers, while elliptic-curve cryptography relies on the discrete logarithm problem within elliptic-curve groups. For decades, no classical algorithm has been found that solves either problem efficiently as key sizes grow, which is why these systems have remained secure even against the fastest supercomputers. Peter Shor's 1994 quantum algorithm changed that assumption entirely. Shor demonstrated that a quantum computer, exploiting superposition and quantum Fourier transforms, could factor large numbers and compute discrete logarithms in polynomial time, a dramatic speedup over any known classical method. The catch, at least for now, is that running Shor's algorithm against real-world key sizes requires a large-scale, fault-tolerant quantum computer with millions of stable, error-corrected qubits, far beyond what exists today. Current quantum hardware is still noisy and limited in scale. But research is advancing quickly, and once such a machine is built, it could theoretically decrypt essentially all RSA and elliptic-curve protected communications, from online banking to secure messaging to government secrets, rendering today's most widely deployed encryption standards obsolete almost overnight.

Harvest Now, Decrypt Later: The Threat Is Already Here

The quantum threat to encryption is not purely a future concern, because of a strategy known as "harvest now, decrypt later." In this scenario, adversaries, including nation-states and well-resourced criminal organizations, intercept and store encrypted data traffic today, even though they cannot yet break the encryption protecting it. They simply archive the ciphertext and wait. Once large-scale quantum computers capable of running Shor's algorithm become available, potentially years from now, that stored data can be decrypted retroactively. This makes the threat immediate rather than hypothetical for any information that must remain confidential for a long time. Medical records, state secrets, intellectual property, trade agreements, and personal communications that need to stay private for a decade or more are all at risk today, even though the quantum computers capable of breaking their encryption may not exist for years. Organizations handling long-lived sensitive data, such as governments, healthcare providers, financial institutions, and defense contractors, face pressure to adopt quantum-resistant protections now, well before quantum computers reach the scale needed to pose a practical threat. Waiting until fault-tolerant quantum computers actually arrive would be too late for anything encrypted and harvested beforehand, which is why security agencies worldwide are urging early migration to post-quantum cryptographic standards rather than treating this as a problem for the future.

The Quantum-Resistant Toolbox: Lattices, Codes, and Hashes

Cryptographers have spent years developing alternative mathematical foundations believed to resist attacks from both classical and quantum computers. Three major families dominate the field. Lattice-based cryptography relies on the difficulty of finding the shortest or closest vector in a high-dimensional geometric lattice, a problem with no known efficient quantum solution. It offers a strong balance of security, speed, and relatively compact keys, making it the leading candidate for general-purpose encryption and key exchange. Code-based cryptography draws on error-correcting codes originally designed for reliable data transmission, and its security rests on the hardness of decoding a general linear code without knowing its special structure. This approach, dating back to the 1978 McEliece cryptosystem, has withstood decades of cryptanalysis, though it typically requires much larger public keys. Hash-based cryptography is used specifically for digital signatures and relies only on the well-studied security properties of cryptographic hash functions, such as their resistance to collisions and preimage attacks. Because hash functions are already thoroughly analyzed and quantum attacks against them are comparatively weaker, hash-based signatures are considered a conservative, highly trustworthy option, though signatures can be large or stateful. Other candidate families, including multivariate polynomial and isogeny-based systems, have also been explored, though several have suffered setbacks from newly discovered attacks, underscoring why diversity across multiple mathematical approaches matters for long-term security.

NIST's Standardization Effort and the 2024 Milestone

Recognizing the urgency of the quantum threat, the U.S. National Institute of Standards and Technology, NIST, launched a public, multi-year competition in 2016 to evaluate and standardize post-quantum cryptographic algorithms. Cryptographers worldwide submitted candidate schemes, which were then subjected to years of rigorous public scrutiny, cryptanalysis, and performance testing across multiple rounds of elimination, similar to the process that previously produced the Advanced Encryption Standard. In 2024, NIST finalized its first official post-quantum standards, marking a major milestone for global cybersecurity. CRYSTALS-Kyber, a lattice-based key encapsulation mechanism, was standardized as ML-KEM (Module-Lattice-Based Key-Encapsulation Mechanism), providing a quantum-resistant method for securely establishing shared encryption keys. CRYSTALS-Dilithium, also lattice-based, was standardized as ML-DSA (Module-Lattice-Based Digital Signature Algorithm), offering quantum-resistant digital signatures for authentication and data integrity. A third algorithm, SPHINCS+, was standardized as SLH-DSA, providing a hash-based signature alternative valued for its conservative, well-understood security assumptions. These standards give organizations concrete, government-vetted algorithms to begin implementing today, and they are increasingly being incorporated into browsers, operating systems, and communication protocols worldwide, with additional algorithms still under evaluation for future standardization rounds.

The Migration Challenge: Bigger Keys and Hybrid Approaches

Transitioning the world's digital infrastructure to post-quantum cryptography is a massive undertaking, complicated by real practical tradeoffs. Post-quantum algorithms generally require larger key sizes, ciphertexts, and signatures than their classical counterparts. For example, ML-KEM keys and ML-DSA signatures are significantly bigger than equivalent RSA or elliptic-curve values, which can strain bandwidth-constrained systems, increase storage requirements, slow down protocol handshakes, and require updates to network infrastructure, firmware, hardware security modules, and software libraries that were never designed with these larger data structures in mind. Legacy systems, embedded devices, and protocols with strict size limits may need substantial redesign. Because post-quantum algorithms are newer and have not faced the same decades of cryptanalytic scrutiny as RSA, many organizations are cautious about relying on them exclusively during the transition period. As a result, a common strategy is adopting hybrid cryptographic schemes, which combine a classical algorithm, such as elliptic-curve Diffie-Hellman, with a post-quantum algorithm, such as ML-KEM, in the same handshake or key exchange. In a hybrid scheme, an attacker would need to break both the classical and post-quantum components to compromise the system, providing a safety net against the possibility that an unforeseen weakness is later discovered in the newer algorithms. Major browsers, cloud providers, and messaging platforms have already begun rolling out hybrid post-quantum key exchange as a pragmatic, risk-managed path toward full migration.

Frequently asked questions

Try it live

Everything above runs in your browser — open Post-Quantum Cryptography: Preparing Encryption for the Quantum Computing Threat and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.