Post-quantum cryptography

Why a working quantum computer breaks RSA, Diffie-Hellman and ECC outright while only weakening symmetric ciphers, and the three families of algorithm designed to survive that shift.

Explain what Shor's algorithm does to the factoring and discrete logarithm problems, and name which schemes that breaks.
Explain what Grover's algorithm does to symmetric key search, and state the resulting effective key strength.
Name the three post-quantum cryptography families the lecture lists.

12 min read

Intuition

Every scheme in this module, RSA, Diffie-Hellman, elliptic curve cryptography, rests on a problem that is hard for an ordinary computer: factor a large number, or take a discrete logarithm. Quantum computing does not make computers faster in general; it makes a small set of specific problems dramatically easier, and factoring and discrete logarithms happen to be on that list. A cryptosystem whose entire security argument is “this problem is hard” stops being secure the moment the problem stops being hard, no matter how large its key is.

Mechanism

Shor’s algorithm efficiently factors large integers and computes discrete logarithms on a sufficiently large quantum computer. Both are exactly the hard problems this module has built on:

RSA rests on factoring $n = pq$ being infeasible. Shor’s algorithm factors it directly.
Diffie-Hellman rests on the discrete logarithm problem, $y = g^x \bmod p$ . Shor’s algorithm solves it.
Elliptic curve cryptography rests on the elliptic curve discrete logarithm problem. Shor’s algorithm has an elliptic-curve variant that solves this too.

All three become breakable, and no increase in key length fixes it. The underlying problem itself stops being hard, so a bigger $n$ or a bigger $p$ only delays the same attack, it does not stop it.

Threat

A sufficiently large quantum computer running Shor’s algorithm recovers the private key directly from the public key for RSA, Diffie-Hellman and ECC alike, not by brute force, but by solving the exact mathematical problem each scheme depends on. The public information already published is enough.

Control

Migrate to algorithms whose hard problem is not one Shor’s algorithm solves: the post-quantum families below. This is a wholesale algorithm replacement, not a key-size increase. The slides note that Australia plans to phase out RSA entirely by 2030, ahead of when large-scale quantum computers are expected to be practical.

Mechanism

Symmetric cryptography is comparatively resilient. Symmetric ciphers such as AES do not rely on factoring or discrete logarithms. Their security is just the size of the key space. The relevant quantum algorithm here is different: Grover’s algorithm gives a quadratic speedup for brute-forcing a key, rather than solving a structural weakness. That speedup halves the effective security level measured in bits, not the number of bits in the key itself.

Formula

Grover's algorithm: effective symmetric key strength

b_{\text{eff}} = \frac{b}{2}

$b$: the nominal key length, in bits
$b_{\text{eff}}$: the effective security level against a quantum adversary

A 256-bit key offers security comparable to a 128-bit key against a quantum adversary.

Control

Double the key size. A 256-bit symmetric key under Grover’s algorithm still offers roughly 128-bit effective security, which is the same margin AES-128 offers today against a classical attacker. Unlike RSA, Diffie-Hellman and ECC, symmetric ciphers survive the transition to a quantum-capable adversary with a parameter change, not an algorithm change.

Mechanism

Post-quantum cryptography (PQC). The lecture names three families of algorithm designed around problems Shor’s algorithm does not help with:

Lattice-based cryptography, built on the hardness of problems involving lattice structures in high-dimensional spaces.
Code-based cryptography, built on the hardness of decoding a random linear code.
Hash-based cryptography, built on the security properties of cryptographic hash functions.

None of these three problems is known to reduce to factoring or a discrete logarithm, so Shor’s algorithm gives no advantage against them. This is the same trapdoor-function logic from earlier in this module, applied to a different set of candidate hard problems, chosen specifically because quantum computing does not help solve them.

Exam detail

Keep the two quantum algorithms and what each one does separate: Shor’s algorithm solves factoring and discrete logarithms outright, breaking RSA, Diffie-Hellman and ECC regardless of key size. Grover’s algorithm only speeds up brute-force key search, halving a symmetric cipher’s effective strength in bits, a problem a larger key still fixes. A question asking which scheme is “more vulnerable” to quantum computing is asking you to know this distinction, not just recite that quantum computers are a threat.

Pitfall

“Quantum computers break encryption” is not precise enough for this unit. They break specific mathematical problems. Asymmetric schemes built on factoring or discrete logarithms fail outright; symmetric ciphers only need a longer key. Treat the two cases separately in an answer, not as one blanket statement about quantum risk.

Recall

A 128-bit AES key and a 2048-bit RSA key are both considered secure today. Which one needs replacing, rather than just lengthening, once large-scale quantum computers exist?

RSA. Shor’s algorithm solves the factoring problem RSA depends on directly, so no length of RSA key restores security. The fix is a different algorithm, drawn from the post-quantum families. AES only faces Grover’s algorithm, a quadratic brute-force speedup, so doubling its key length to 256 bits restores the original security margin without changing the algorithm.

Source

Week 5 slides PDF