Post-Quantum Cryptography Explained

Almost every secure connection you make today rests on a bet: that no one can factor a very large number or reverse an elliptic-curve operation in a useful amount of time. That bet has held for decades against classical computers. A sufficiently powerful quantum computer would break it. Post-quantum cryptography is the effort to replace the vulnerable pieces before that machine exists.

The word "before" is doing a lot of work. Nobody has built a quantum computer capable of breaking real keys, and credible estimates for when one might appear range widely. The reason to act now has nothing to do with certainty about dates. It has to do with data that must stay secret for a long time, and an attack strategy that does not need the quantum computer to exist yet.

What quantum computers actually break

The public-key cryptography that secures the internet relies on math problems that are easy in one direction and infeasible to reverse. RSA rests on the difficulty of factoring a large number back into its two prime components. Diffie-Hellman and elliptic-curve cryptography rest on the discrete logarithm problem. Classical computers have no efficient way to solve either at the sizes we use.

In 1994 Peter Shor showed that a quantum computer running his algorithm could solve both efficiently. Factoring and discrete logarithms fall together. That single result is why RSA, Diffie-Hellman and ECC are all considered quantum-vulnerable. For the underlying schemes, see How RSA Works and How Elliptic Curve Cryptography Works.

Symmetric cryptography is a different story. Grover's algorithm gives a quantum computer a speedup against brute-force key search, but a bounded one. It effectively halves the security level, so a 128-bit key offers something closer to 64 bits of quantum resistance. The fix is straightforward: use larger keys. AES-256 retains a comfortable margin, and modern hash functions like SHA-256 and SHA-3 remain secure with minor adjustments. This is why the migration effort concentrates on public-key algorithms.

It is worth being clear about why the two categories diverge so sharply. Shor's algorithm is not a faster search; it exploits deep mathematical structure that factoring and discrete logarithms happen to have, and it collapses those problems from infeasible to routine. Symmetric ciphers and hashes have no such structure to exploit, so the best a quantum computer can do against them is a generic square-root speedup on brute force, which larger keys absorb. That structural difference, and nothing about raw speed, is what decides which algorithms survive.

Primitive	Classical status	Quantum impact	Response
RSA	Secure at large key sizes	Broken by Shor's algorithm	Replace with PQC
Diffie-Hellman / ECC	Secure	Broken by Shor's algorithm	Replace with PQC
AES-128	Secure	Weakened by Grover's algorithm	Move to AES-256
SHA-256 / SHA-3	Secure	Mildly weakened	Larger output where needed

For the broader picture of what quantum machines can and cannot do to security, see Quantum Computing as a Cybersecurity Threat.

Harvest now, decrypt later

The uncomfortable part is that the threat does not wait for the hardware. An adversary can record encrypted traffic today, store it, and decrypt it years later once a capable quantum computer is available. This is called harvest-now-decrypt-later, and it turns a future capability into a present risk.

Whether this matters to you depends on how long your secrets need to stay secret. A session cookie that expires in an hour is safe regardless. Diplomatic cables, medical records, genomic data, intellectual property and long-lived root keys are a different case. If something you transmit today must remain confidential for ten or twenty years, an attacker recording it now is a real threat, even if the decryption happens much later.

What the NIST standards replace them with

Post-quantum algorithms are built on math problems believed to be hard for both classical and quantum computers. The leading families are based on structured lattices, hash functions, error-correcting codes and multivariate equations. Lattice-based schemes have become the workhorse because they offer a good balance of key size and speed.

In 2024 NIST published its first finalised post-quantum standards after a multi-year public competition. Conceptually they cover the two jobs that RSA and ECC do today:

• ML-KEM (FIPS 203), derived from the scheme formerly called CRYSTALS-Kyber, is a key-encapsulation mechanism. It handles the job of establishing a shared secret over an insecure channel, replacing quantum-vulnerable key exchange.
• ML-DSA (FIPS 204), derived from CRYSTALS-Dilithium, is a lattice-based digital signature scheme for authentication and integrity.
• SLH-DSA (FIPS 205), derived from SPHINCS+, is a hash-based signature scheme. It is a conservative backup whose security rests only on hash functions, useful where you want minimal new assumptions.

These are not drop-in replacements at the byte level. Post-quantum keys and signatures are generally larger than their RSA and ECC counterparts, which affects handshake sizes, certificates and storage. That is a real engineering cost, and it is one reason migration takes planning rather than a single switch. For how these fit alongside the symmetric side, see Symmetric vs Asymmetric Encryption.

NIST chose to standardise multiple algorithms on purpose. Relying on a single mathematical assumption is risky when the schemes are young, so having a lattice-based signature and a separate hash-based one means a future weakness in lattices would not leave defenders without options. The same logic drives ongoing work to standardise additional families based on different hard problems, so that the ecosystem never depends on one line of mathematics the way it depended on factoring for so long.

Why this migration is unusually hard

Cryptographic transitions are always slow, and this one has features that make it slower. The larger key and signature sizes ripple through protocols that were designed around compact RSA and ECC values, affecting TLS handshakes, certificate chains, embedded devices with tight memory, and any system that stores signatures long term. Constrained hardware such as smart cards and industrial controllers may struggle with the new sizes and cannot always be updated in the field.

There is also the sheer scale of the estate. Cryptography is embedded in operating systems, firmware, hardware security modules, protocols, libraries and countless applications, much of it invisible until you go looking. Organisations that tried to catalogue their own use of a single deprecated algorithm in the past often found it took years. The post-quantum transition touches far more than one algorithm, which is why the guidance emphasises starting the inventory early even though the algorithms themselves are the easy part.

Hybrid deployment and crypto-agility

Because the post-quantum schemes are newer and less battle-tested than RSA and ECC, most early deployments run them in a hybrid mode. A hybrid key exchange combines a classical algorithm with a post-quantum one so that the connection stays secure as long as either holds. If a flaw is found in the new lattice scheme, the classical part still protects you; if a quantum computer arrives, the post-quantum part does. Major browsers and platforms have already begun rolling out hybrid key exchange for exactly this reason.

The deeper lesson is crypto-agility: the ability to change algorithms without rebuilding your systems. Many organisations discovered during earlier migrations that their cryptography was hardcoded in ways that made swapping it painful. Building agility now makes this transition, and the next one, far cheaper.

How to start planning

1. Inventory your cryptography. You cannot migrate what you cannot see. Find every place RSA, ECC and Diffie-Hellman are used, in code, certificates, hardware and third-party services.
2. Classify data by lifetime. Flag anything that must stay confidential for many years. That is your harvest-now-decrypt-later exposure and your migration priority.
3. Build crypto-agility. Refactor so algorithms are configurable rather than hardcoded, so future swaps are routine.
4. Pilot hybrid key exchange on internal or low-risk services first, to gain operational experience with larger keys and handshakes.
5. Follow the NIST timeline. Track the official transition guidance and vendor support rather than acting on hype about quantum breakthroughs.

Post-quantum cryptography is a rare case where the security community saw a threat clearly and prepared standards ahead of it. The algorithms exist, the standards are published, and the engineering is understood. The work now is unglamorous: find your cryptography, know your data's shelf life, and migrate the pieces that matter while there is time to do it carefully. Resist the urge to overstate the timeline in either direction. No one needs to panic, and no one with long-lived secrets should wait for certainty.

A conceptual walkthrough of the threat model

It helps to separate the two things people conflate when they talk about the quantum threat, because they have very different timelines. The first is the existence of a cryptographically relevant quantum computer, a machine large and stable enough to run Shor's algorithm against the key sizes we actually use. That does not exist today, and estimates for when it might appear vary widely and honestly. The second is the exposure created by an attacker who records encrypted data now and waits. That exposure is present today, and it does not depend on the machine existing yet.

Trace a single protected message through this model. Today, two parties agree on a shared secret using a quantum-vulnerable key exchange, then encrypt their conversation with a symmetric cipher under that secret. An eavesdropper who captures the traffic sees only ciphertext and a key-exchange transcript, and against a classical computer that transcript is useless because recovering the secret would require solving a discrete logarithm. The eavesdropper stores the whole capture anyway.

Years later, a capable quantum computer runs Shor's algorithm against the stored key-exchange transcript, recovers the shared secret, and uses it to decrypt the archived symmetric traffic. The symmetric cipher itself was never the weak point. The weak point was the public-key step that established the secret, and it was broken retroactively. This is why the confidentiality of a message sent today depends on how long that message must stay secret and on when a quantum computer arrives, and why data with a long secrecy lifetime is already exposed even though the machine is hypothetical.

The authentication side has a different shape. A forged signature is only useful at the moment of use, so an attacker cannot meaningfully forge today a signature they need a future machine to produce. Signatures still need migration so that systems remain trustworthy once quantum computers exist, and the retroactive pressure that makes confidentiality urgent does not apply to them in the same way. Understanding that split, confidentiality is exposed retroactively while authentication is exposed prospectively, is what lets an organization prioritize sensibly.

Detection and readiness signals

Post-quantum readiness is not something you detect on the wire like an attack. It is something you assess about your own estate, and there are concrete indicators of whether you are ready or exposed.

The first indicator is visibility. If you cannot produce a current inventory of where RSA, elliptic-curve, and Diffie-Hellman are used across code, certificates, hardware security modules, and third-party services, you are not ready, because you cannot migrate what you cannot see. A mature program has an automated, refreshed inventory rather than a one-time spreadsheet.

The second is data-lifetime classification. If you cannot say which of your data must remain confidential for ten or twenty years, you cannot identify your harvest-now-decrypt-later exposure. The presence of long-retention data protected only by classical key exchange is the clearest exposure signal there is.

The third is crypto-agility. If swapping an algorithm requires changing application code in many places, redeploying firmware, or renegotiating with vendors, you are exposed to a slow migration regardless of when the threat lands. A ready system treats algorithms as configuration.

Readiness indicator	Ready state	Exposed state
Cryptographic inventory	Automated, current, covers dependencies	Unknown or manually guessed
Data-lifetime classification	Long-lived data flagged and prioritized	No mapping of secrecy lifetimes
Crypto-agility	Algorithms are configurable	Algorithms hardcoded across systems
Hybrid deployment experience	Piloted on real services	Never tested at larger key sizes
Vendor commitments	Post-quantum roadmaps in hand	No visibility into vendor plans

How post-quantum families compare

The post-quantum standards draw on more than one branch of mathematics on purpose, and the families have different strengths. Comparing them explains why NIST standardized several rather than one.

Family	Basis	Strength	Trade-off
Structured lattices	Hardness of lattice problems	Good balance of size and speed	Younger assumption, larger than ECC
Hash-based	Security of hash functions only	Very conservative, well-understood	Large signatures or statefulness
Code-based	Error-correcting code problems	Long-studied assumption	Large public keys
Multivariate	Systems of multivariate equations	Compact signatures in some schemes	History of broken parameter sets

Lattice schemes became the workhorse because they keep keys and signatures at sizes protocols can absorb while staying fast, which is why ML-KEM and ML-DSA are lattice-based. Hash-based signatures like SLH-DSA rest on nothing more than the security of hash functions, the most battle-tested assumption available, so they serve as a conservative backup where minimal new assumptions matter more than compactness. Keeping a lattice signature and a hash-based signature in the standard means a future weakness in lattices would not leave defenders without a signing option, which is the whole point of standardizing more than one line of mathematics.

Common misconceptions

"Quantum computers break all encryption." They do not. Shor's algorithm breaks the public-key schemes that rely on factoring and discrete logarithms. Symmetric ciphers like AES and hash functions like SHA-256 face only Grover's algorithm, a bounded speedup that larger keys absorb. The urgent problem is public-key cryptography, and the symmetric side needs only modest adjustment.

"There is no quantum computer yet, so there is nothing to do." Harvest-now-decrypt-later means an adversary can record encrypted traffic today and decrypt it once a machine exists. For data with a long secrecy lifetime, the recording is happening in the present and only the decryption is deferred, so waiting for the hardware means waiting too long.

"Doubling AES key size handles the whole problem." Moving to AES-256 restores the margin against Grover on the symmetric side, and it does nothing for the public-key step that establishes the keys in the first place. That step is what Shor breaks, and it needs a post-quantum replacement.

"Post-quantum algorithms are drop-in replacements." They are not, at the byte level. Post-quantum keys and signatures are generally larger than RSA and ECC values, which ripples through handshake sizes, certificates, and storage, and constrained hardware may struggle with them. Migration is an engineering program, which is why hybrid deployment and crypto-agility matter.

"Hybrid mode is a temporary hedge with no real value." Hybrid key exchange combines a classical and a post-quantum algorithm so the connection holds as long as either does. Given that the new schemes are younger and less tested, that hedge protects against both a flaw in the new mathematics and the arrival of a quantum computer, which is a durable reason to run it rather than a stopgap.

Frequently asked questions

When will a quantum computer break RSA? No one knows, and credible estimates range widely. The reason to act does not depend on a date. Harvest-now-decrypt-later makes long-lived secrets exposed today regardless of when the machine arrives, so the timeline uncertainty is a reason to start inventory and classification now rather than a reason to wait.

Do I need to replace AES? Not replace, adjust. AES faces Grover's algorithm, which effectively halves the security level, so moving from AES-128 to AES-256 restores a comfortable margin. The concentrated effort is on public-key algorithms, which Shor's algorithm breaks outright.

What are ML-KEM, ML-DSA, and SLH-DSA? They are the first finalized NIST standards. ML-KEM (FIPS 203) is a key-encapsulation mechanism for establishing shared secrets, ML-DSA (FIPS 204) is a lattice-based signature scheme, and SLH-DSA (FIPS 205) is a hash-based signature scheme kept as a conservative backup. Together they cover the two jobs RSA and ECC do today.

Should I deploy post-quantum algorithms alone or in hybrid mode? Most early deployments use hybrid mode, combining a classical algorithm with a post-quantum one so the connection stays secure as long as either holds. That protects against both a flaw in the young lattice schemes and the arrival of a quantum computer, which is why major platforms have rolled out hybrid key exchange first.

What is the first thing my organization should do? Inventory your cryptography and classify your data by secrecy lifetime. You cannot migrate what you cannot see, and you cannot prioritize without knowing which data must stay confidential for many years. Those two exercises define both the scope and the order of the migration.

Why standardize more than one algorithm? Relying on a single mathematical assumption is risky while the schemes are young. Standardizing a lattice-based signature and a separate hash-based one means a future weakness in one family does not leave defenders without options, and it drives ongoing work to add families based on different hard problems.

Does the larger key size actually matter in practice? It matters more than it first appears. Post-quantum keys and signatures are bigger than their RSA and ECC counterparts, and that size flows into every handshake, certificate chain, and stored signature. On a fast link between two capable servers the cost is small, and on constrained hardware with tight memory, or in protocols that were tuned around compact values, it becomes a real engineering constraint that shapes how and where you migrate first.

Is signature migration as urgent as key-exchange migration? The pressure differs. Confidentiality is exposed retroactively, because recorded traffic can be decrypted once a quantum computer exists, which makes key-exchange migration urgent for long-lived data. A forged signature is only useful at the moment of use, so signatures cannot be forged in advance and their migration is about staying trustworthy once quantum computers arrive rather than protecting something recorded today.

Related guides

• How RSA Works
• How Elliptic Curve Cryptography Works
• Quantum Computing as a Cybersecurity Threat
• Symmetric vs Asymmetric Encryption