There is an encryption apocalypse quietly scheduled for some unknown date in the future, and the whole security world is already evacuating the building. The trigger is Shor's algorithm: a large, error-corrected quantum computer running it would factor huge numbers and solve discrete logarithms in polynomial time — and factoring and discrete log are precisely the hard problems that RSA, Diffie–Hellman, and elliptic-curve cryptography are built on. In one stroke, essentially all of today's public-key infrastructure — the machinery behind every padlock in your browser, every signed software update, every secure login — would fall.

No such machine exists yet. So why is the migration already underway? Because the answer isn't to build a quantum defence — it is post-quantum cryptography (PQC): ordinary, classical cryptography, running on the laptops and phones we have now, but rebuilt on mathematical problems believed to be hard even for a quantum computer. This page is about which cryptography breaks, which merely bends, what we are replacing it with, and why the clock started ticking long before the hardware arrived.

The threat: Shor guts public-key cryptography

Public-key cryptography is the trick that lets two strangers agree on a secret over an open wire, or lets anyone verify a signature without knowing the signer's private key. Every widely deployed public-key scheme leans on one of two problems being computationally hopeless for classical machines:

• Integer factoring — RSA is secure because nobody can factor a 2048-bit product of two primes in reasonable time.
• The discrete logarithm — Diffie–Hellman and elliptic-curve cryptography (ECDH, ECDSA) are secure because recovering an exponent from g^x is intractable.

Shor's algorithm solves both in polynomial time. Its quantum core finds the period of a modular-exponentiation function, and a short classical wrapper turns that period into a factorisation — or, with a small twist, into a discrete log. So a single scalable quantum computer doesn't chip away at these schemes; it collapses them. The security margin that took "longer than the age of the universe" to brute-force classically evaporates to an afternoon.

Symmetric crypto only bends: Grover's quadratic nudge

Now the good news. Symmetric ciphers (like AES) and hash functions (like SHA-256) are not built on factoring or discrete log — they have no exploitable algebraic structure. The only quantum tool that touches them is Grover's search, which brute-forces an N-key space in about \sqrt N tries instead of N. That is a quadratic speedup, not an exponential one — worlds apart from what Shor does to RSA.

A key of b bits has N = 2^b possibilities. Grover searches it in

which is exactly the effort of brute-forcing a b/2-bit key classically. In other words, Grover halves the effective security level. The fix is beautifully simple: double the key length. AES-128 drops to a still-uncomfortable 64-bit security under Grover, but AES-256 keeps a comfortable 128-bit margin — safe again, no new mathematics required. Hashes behave the same way: prefer a longer digest (SHA-384/512) and the quantum discount is absorbed.

Worked example 1: which schemes break, and which just bend?

Sort the four everyday primitives \{\text{RSA-2048},\ \text{ECC},\ \text{AES-256},\ \text{SHA-256}\} by their fate against a quantum adversary. The dividing line is public-key vs symmetric: public-key schemes rest on factoring / discrete log, so Shor breaks them; symmetric schemes only face Grover's \sqrt N, so they are merely weakened and rescued by bigger parameters.

The pattern to memorise: Shor is the exponential catastrophe, and it lands only on public-key crypto; Grover is a mild quadratic tax that a longer key pays off. RSA and ECC leave the building; AES-256 and SHA-256 stay, just wearing a bigger coat.

Worked example 2: why doubling a symmetric key defeats Grover

Let's make the "double the key" rule concrete. Suppose we want 128 bits of security to survive a quantum attacker. Grover finds a b-bit key in 2^{b/2} steps, so the effective post-quantum security of a b-bit key is

Set b/2 = 128 and solve: b = 256. So an AES-256 key gives 2^{256/2} = 2^{128} Grover operations — an attacker would need 2^{128} steps, still astronomically out of reach. Compare the two lengths:

Doubling the key from 128 to 256 bits doesn't just add a little margin — it moves the exponent from 64 back up to 128, restoring the full classical security level. That is the whole reason a quantum threat forces new mathematics for public-key crypto but only bigger numbers for symmetric crypto: Grover's square root can always be undone by squaring the search space, whereas Shor's polynomial-time factoring cannot be out-run by any practical key size.

The response: hard problems quantum computers can't crack

PQC rebuilds public-key cryptography on problems for which no efficient quantum algorithm is known — problems that lack the neat periodic/hidden-subgroup structure Shor exploits. Four families lead the field:

• Lattice-based — the front-runner. Security rests on problems like Learning With Errors (LWE) and finding short vectors in a high-dimensional lattice (the shortest-vector problem). The relevant hidden-subgroup version is the dihedral one, which quantum algorithms are not known to solve efficiently. Fast, compact keys — this is why lattices won.
• Hash-based signatures — signatures whose security reduces only to a hash function being hard to invert (which Grover barely dents). Conservative and very well understood.
• Code-based — e.g. McEliece, resting on the hardness of decoding a random linear error-correcting code. Decades old and unbroken, but with large keys.
• Multivariate — based on solving systems of multivariate polynomial equations over finite fields.

Between 2022 and 2024, NIST standardised the first winners of a years-long public competition — all lattice-based for the headline roles:

• ML-KEM (formerly Kyber) — the standard for key exchange / encapsulation.
• ML-DSA (formerly Dilithium) — a lattice-based digital signature, with SPHINCS+ (hash-based) as a conservative backup.

The through-line back to this course: these schemes survive precisely because the quantum algorithms we do know — Shor for periods, Grover for unstructured search — don't apply to lattice, code, or hash problems. PQC is a bet that this gap in the quantum toolbox is permanent.

The urgency: "harvest now, decrypt later"

Here is the argument that turns a distant hypothetical into a present emergency. Encrypted data crossing the internet today can be quietly copied and stored by any well-resourced adversary. It is gibberish now — but if it is still secret in ten or twenty years, and a quantum computer exists by then, that stored ciphertext gets decrypted retroactively. The attack is launched in the future; the victim is chosen now. Step through it:

This is why nobody is waiting for the hardware to appear. Anything that must stay confidential for a long time — medical records, state secrets, long-lived credentials — is already at risk today, because its ciphertext can be banked now and cracked later. Migration to PQC has to finish before capable quantum computers exist, which means it has to start long before them.

Summary