The Trapdoor Problem: Why Public-Key Cryptography Was Always Going to Break
The Trapdoor Problem
Public-key cryptography was always going to be breakable by something, because the structure that makes it work is the structure an attacker attacks. Quantum computing turned out to be the something.
The problem that made public-key necessary
Symmetric encryption is old, fast and, as far as anyone knows, quantum-proof. AES takes a key, scrambles your data beyond recognition, and unscrambles it with the same key. Nothing in this article threatens it.
It has one flaw, and the flaw is not mathematical. Both parties need the same key. Before 1976 the only way to establish one was to physically deliver it — couriers, sealed envelopes, diplomatic bags, code books on submarines. That works for two embassies. It does not work for a browser opening a connection to a server it has never contacted, on a network where every packet is visible, at a rate of millions of connections a second.
The obvious response is that the problem is unsolvable, and for most of history everyone assumed it was. You cannot agree on a secret with a stranger while an eavesdropper listens to every word. Except that in 1976 Whitfield Diffie and Martin Hellman showed that you can,[1] and a year later Rivest, Shamir and Adleman turned it into a usable construction.[2] It is one of the genuinely astonishing results of the century and it is the reason the internet has commerce on it.
What a trapdoor is, and why it costs you something
The mechanism they found is called a trapdoor function: something easy to compute forwards, hard to reverse, and equipped with a secret that makes reversing it easy again.
| Easy direction | Hard direction | The secret that reopens it | |
|---|---|---|---|
| RSA | Multiply two large primes | Factor the product | Knowing one of the primes |
| Diffie–Hellman | Compute gx mod p | Recover x from the result | Having chosen x yourself |
| Elliptic curve | Add a point to itself x times | Recover x from the endpoint | Having chosen x yourself |
Now the observation that this whole article turns on. You cannot build a trapdoor out of a mess.
Take a genuinely structureless function — a good hash, say. It is hard to reverse, which is the first thing you wanted. But it is hard to reverse for everybody, including you, and there is no secret you could be given that would make it easy. A mess has no trapdoor because a trapdoor is a piece of structure: a mathematical regularity that a person holding the right information can walk through and a person without it cannot.
So public-key cryptography does not merely happen to use structured mathematics. It is obliged to. The demand for a legitimate shortcut is a demand for regularity, and regularity is the thing an attacker looks for. Every public-key scheme is a bet that a particular piece of structure admits exactly one shortcut and that nobody will find a second.
A trapdoor is a deliberate weakness with a lock on it. The whole game is whether anyone can get through the weakness without the lock.
What actually happens when you load a web page
This is worth spelling out, because it bounds the damage and almost every popular account gets it wrong.
Your browser does not encrypt the page with RSA. Public-key cryptography is far too slow for bulk data. What happens instead is a hybrid, and it has two stages:
| Stage | What it does | How much data | Quantum-vulnerable? |
|---|---|---|---|
| 1. Handshake | Public-key cryptography agrees a fresh symmetric key and authenticates the server | A few kilobytes, once | Yes — Shor breaks it |
| 2. Bulk transfer | AES encrypts the actual page, video, payment details | Everything else | No — only Grover, which is not enough |
So the honest version of “quantum computers break the internet” is that they break the first few kilobytes. Which is entirely sufficient, because those kilobytes contain the key to all the rest. Recovering the handshake hands you the AES key, and the unbreakable part is then read with the key it was encrypted with.
The bounding still matters, though, and in a practical direction: the fix only has to replace stage one. AES stays. The hash functions stay. The enormous, mature, fast machinery of symmetric cryptography is untouched, and the migration is confined to key agreement and signatures.
Why Shor gets in
The companion piece works through the mechanism; the summary is that both surviving trapdoor families have the same shape underneath. RSA rests on factoring, which reduces to finding the period of ax mod N. Diffie–Hellman and elliptic curves rest on discrete logarithms, which is the same hidden-periodicity problem wearing different clothes. A quantum Fourier transform exposes periodicity by making every wrong candidate cancel, and both fall to the same algorithm.
The counter-intuitive ordering
Elliptic-curve cryptography is likely to break first. Smaller keys are a virtue everywhere else in cryptography — a 256-bit elliptic-curve key offers roughly the security of a 3072-bit RSA key, at a fraction of the size — but here the small key means a smaller quantum computer suffices. On current resource estimates ECC needs materially fewer logical qubits than RSA-2048.[3] The most modern deployed public-key cryptography is the most exposed.
And the deadline is not the arrival of the machine. It is harvest now, decrypt later: an adversary records your encrypted traffic today and stores it until a machine exists. Whether that matters depends entirely on the shelf life of the secret. A video stream is worthless in ten years. A medical record, a genome, an identity document, a diplomatic cable, the design of a weapons system or a chip — those are not, and they are being recorded now.
What replaces it, and what a lattice actually is
The replacement strategy is not to find a quantum-proof method. It is to find a different hard problem — one that still admits a trapdoor, so the scheme works at all, but whose structure is not the kind Shor's algorithm can grip. In August 2024 NIST finalised the first standards built that way: ML-KEM for key agreement, ML-DSA and SLH-DSA for signatures.[4] They are classical algorithms. They run on ordinary computers, and your laptop is running some of them already.
Two of the three rest on lattices, and “lattice” is where most explanations stop. It should not, because the idea is genuinely simple.
A lattice is the set of every whole-number combination of a few vectors. Take two arrows, add and subtract whole multiples of them in every combination, and the points you can reach form an infinite regular grid. The arrows you started with are called a basis — and the essential fact is that the same lattice can be described by many different bases.
Here is the hard problem: given a target point that is not on the lattice, find the lattice point nearest to it.
With the good basis this is trivial. The arrows are short and at right angles, so you round each coordinate to the nearest whole number and you are done. With the bad basis — which describes the identical infinite grid — you have no such move. The vectors are long and nearly parallel, every point is reachable only as a large difference of two large multiples, and searching becomes hopeless as the number of dimensions climbs. Real schemes use several hundred dimensions rather than two.
That gap is the trapdoor. The good basis is the private key. The bad basis is published. Anyone can use the public description to scramble a message into a point near the lattice; only the holder of the short basis can round it back.
Why lattices are believed to resist quantum attack
Shor's algorithm works by exposing periodicity — a global repeating structure that a Fourier transform turns into interference, so that wrong answers cancel. Factoring and discrete logarithms both have it. In the language of complexity theory both are instances of the abelian hidden subgroup problem, and Shor solves that problem in general.
The best-known reduction for lattice problems lands instead on the dihedral hidden subgroup problem, which is not abelian, and for which no efficient quantum algorithm is known despite thirty years of trying.[5] There is no period in a lattice for a Fourier transform to find. That is the entire basis of the confidence, and it is worth noticing how much weaker a statement it is than a proof.
The part nobody puts in the press release
None of the post-quantum standards is proven secure. Not one. What they have is resistance to every attack anyone has published, which is the same guarantee RSA had for forty-seven years and still has against classical computers.
How much weight that guarantee bears is not a rhetorical question, because the competition itself produced the answer. SIKE — Supersingular Isogeny Key Encapsulation — was elegant, had the smallest keys of any candidate, and survived to the fourth round of the NIST process. In July 2022, while it was still under consideration, Wouter Castryck and Thomas Decru published an attack that recovered the key in about an hour on a single classical core.[6]
No quantum computer was involved. A mathematician found a piece of structure nobody had noticed, in a scheme that had been studied for a decade by people looking for exactly that. SIKE was withdrawn.
The lesson, stated plainly
The threat to a cryptographic scheme is not primarily that someone builds a machine. It is that someone finds the second shortcut — and a trapdoor function is, by construction, a thing with at least one shortcut in it already.
Lattices are a better bet than SIKE was: more scrutiny, longer history, and a reduction to a problem that has resisted attack since the 1990s. A better bet is what it is, though. It is not a proof, and anyone who tells you the post-quantum problem is solved has skipped the only interesting sentence.
What to actually do
Unusually for this subject, the practical advice is short, uncontroversial, and mostly not about physics.
| Action | Why | Urgency |
|---|---|---|
| Inventory where you use public-key | Most organisations cannot answer this, which makes every later step unschedulable | Now, and it is the slow one |
| Move off AES-128 to AES-256 | Grover halves the effective key length; 256 leaves a 128-bit margin | Easy, do it |
| Deploy hybrid key agreement | Classical and post-quantum KEM combined, so an attacker must break both. Already default in major browsers and CDNs | Now — it protects against harvest-now |
| Plan signature migration | Less urgent for confidentiality, but code-signing and CA roots have decade-long lifetimes | Slower, still real |
The hybrid row deserves emphasis, because it is the one piece of genuinely good news. You do not have to bet on lattices. Combining a classical key exchange with a post-quantum one produces a channel that stays secure unless both are broken — so the SIKE scenario, a post-quantum scheme falling to classical mathematics, costs you nothing. It is the correct response to a guarantee that is empirical rather than proved, and it is already how most encrypted web traffic works.
And note what dominates the effort. Not qubit counts, not error rates, not any question a physicist could answer. Finding out where your systems use public-key cryptography, and replacing it, is a decade of unglamorous engineering, and it is the actual race. The standards were finished before the threat arrived. Whether the migration is finished before the machine is a matter of institutional attention, which historically is the scarcer resource.
The shape of the whole thing
Public-key cryptography was a remarkable invention that solved an apparently impossible problem, and it did so by finding mathematical structures with exactly one door in them. That was always a wager. The structure that lets the legitimate key-holder through is the same structure that an attacker studies, and the only question was ever whether a second way through existed and who would find it first.
For RSA and elliptic curves, the answer arrived in 1994, in a paper, thirty years before the machine that could run it. The replacements are a fresh wager on a different structure, hedged by running the old and new schemes together. That is a reasonable way to proceed and it is not certainty, and the distance between those two things is where all the honest discussion of this subject lives.
Related reading
The Interference Machine for what a quantum computer does and the short list of things it is good at; The Machinery of Cancellation for Shor's algorithm derived in full. For the migration itself, NIST's post-quantum project pages are the authoritative source and are written for practitioners rather than physicists.
References
- Diffie, W. & Hellman, M. (1976). “New Directions in Cryptography.” IEEE Transactions on Information Theory 22(6), 644–654.
- Rivest, R., Shamir, A. & Adleman, L. (1978). “A Method for Obtaining Digital Signatures and Public-Key Cryptosystems.” Communications of the ACM 21(2), 120–126.
- Gidney, C. (2025). “How to factor 2048 bit RSA integers with less than a million noisy qubits.” arXiv:2505.15917. For elliptic curves see Roetteler, M. et al. (2017), “Quantum resource estimates for computing elliptic curve discrete logarithms.” ASIACRYPT 2017.
- NIST (2024). FIPS 203 (ML-KEM), FIPS 204 (ML-DSA), FIPS 205 (SLH-DSA), finalised 13 August 2024. csrc.nist.gov
- Regev, O. (2009). “On lattices, learning with errors, random linear codes, and cryptography.” Journal of the ACM 56(6), 1–40. Originally STOC 2005; awarded the Gödel Prize in 2018.
- Castryck, W. & Decru, T. (2023). “An Efficient Key Recovery Attack on SIDH.” EUROCRYPT 2023. Preprint circulated July 2022; independent attacks followed from Maino & Martindale and from Robert.
Comentários
Enviar um comentário