Someone Is Already Keeping Your Secrets

There is a small padlock at the left of your address bar, and almost nobody knows what it is claiming. Not that the page is safe, or honest, or well made. Something far stranger: that a few milliseconds ago your machine and a machine you have never met agreed on a secret number while every device between you was listening, and that none of those listeners can work out what the number is.

That should sound impossible, and for most of the history of secret writing it was. Until the 1970s, two parties who wanted to exchange coded messages had to first exchange a key by some other, trusted means—a courier, a meeting, a book both sides owned. Public-key cryptography removed that requirement, and it is the single invention the commercial internet rests on. It works because of a small number of arithmetic facts that are easy to perform in one direction and, as far as anyone knows, catastrophically hard to undo.

That qualifier is doing an enormous amount of work, and this essay is about what happens when it stops holding.

The Trapdoor

Take two large prime numbers and multiply them. Your laptop does this instantly, however large they are. Now hand somebody only the product and ask which two primes you started from. For numbers of the size actually used—around six hundred digits—there is no known method that does this in any reasonable time. Not a slow method. No method, beyond dressed-up versions of trying possibilities, and the number of possibilities exceeds the number of atoms in the observable universe.

⤢ enlarge

That gap between the easy direction and the hard one is a one-way function with a trapdoor, and RSA—for Rivest, Shamir and Adleman, who published in 1977—turns it into a cipher. Elliptic-curve cryptography, which is what your phone actually uses most of the time, rests on a structurally identical asymmetry: adding points on a curve is easy, and recovering how many times a point was added to itself is not. Between them these two ideas protect essentially everything. Your banking. Your messages. The update your car’s braking software accepted last month because it carried a valid signature.

And nobody has ever proved that either problem is hard. Sit with that for a second. There is no proof. What there is is fifty years of extremely motivated people failing to find a fast algorithm, which is evidence of a real kind and is not the same thing at all. The privacy of modern life rests on a conjecture.

What a Quantum Computer Actually Does

The popular account is that a quantum computer tries all the answers at once. This is wrong in a way that makes the real thing impossible to understand, so it is worth replacing properly.

A quantum system is described by amplitudes—complex numbers, one for each possible outcome. The probability of an outcome is the squared magnitude of its amplitude. Because amplitudes are complex they carry a phase as well as a size, and phases can cancel. Two paths arriving at the same wrong answer with opposite phase annihilate each other and leave nothing behind.

That is the entire resource. A quantum algorithm is a piece of choreography arranged so that the amplitudes of wrong answers interfere destructively and the right one survives. It is far closer to a lens than to a parallel processor. And it explains something otherwise puzzling: quantum computers are not generally faster. You get a speedup only where the problem has structure your interference pattern can grip. For most problems there is no such structure and a quantum computer is an extraordinarily expensive slow one.

There is a cleaner way to see this. After you prepare a superposition over every input and compute your function into a second register, the machine really is holding all the answers at once—and if you measure at that point you get one uniformly random, useless value. Superposition on its own buys nothing whatsoever. Everything depends on what you do between preparing the superposition and looking at it.

Shor’s Trick: Ask a Different Question

Peter Shor’s 1994 algorithm is not a fast factoriser. It is a fast period-finder, bolted to a piece of number theory that turns period-finding into factoring.

Here is the number theory, and you can check it by hand. Take the number to factor—say 33. Pick a smaller number sharing no factor with it—say 2. Compute the powers of 2, wrapping around modulo 33 each time: 2, 4, 8, 16, 32, 31, 29, 25, 17, 1. And then it begins again: 2, 4, 8. The sequence is periodic, and here the period is 10.

⤢ enlarge

Knowing the period is 10, take 2 to the power of half of it—2 to the fifth, 32—and compute the greatest common divisor of 32 plus or minus 1 with 33. Out come 3 and 11. The factors fall out of a period. This reduction long predates quantum computing and was useless, because finding the period of a six-hundred-digit modulus classically is exactly as hard as the factoring you were avoiding.

The quantum computer supplies the missing step. Prepare a superposition over the exponents, compute the modular powers into a second register, and what remains is a state that is periodic in the index. Then apply the quantum Fourier transform, which does to a superposition what an ordinary Fourier transform does to a sound: it converts something that repeats into a sharp spike at the corresponding frequency. Every candidate period except the true one cancels itself out. Measure, apply continued fractions, and you have the period.

The machine never factors anything. It measures how often a sequence repeats, and hands the number to Euclid.

It is worth knowing why this single idea is so destructive. Factoring and the discrete logarithm are both instances of one abstract problem—finding a hidden subgroup of a commutative group—and the Fourier machinery solves that problem in general. So RSA, finite-field Diffie-Hellman, DSA, ElGamal, elliptic-curve Diffie-Hellman and ECDSA do not fall separately. They are the same problem wearing different clothes, and they fall together. Elliptic curves, for what it is worth, fall with a *smaller* machine than RSA does.

Grover, and a Number Everybody Gets Wrong

The other quantum algorithm people worry about is Grover’s, which searches an unstructured space of N possibilities in about the square root of N steps. The standard summary is that this halves the security of symmetric encryption: a 128-bit key drops to 64 bits, a 256-bit key to 128. That summary is a reasonable design heuristic and a terrible statement of fact.

Two things wreck the naive reading. First, Grover’s algorithm barely parallelises. It has been proved that the best you can do with M machines is split the search space between them, which buys you a factor of the square root of M. Classical brute force, by contrast, is embarrassingly parallel: double your machines, halve your time. That is precisely how real attackers scale—botnets, ASIC farms, rented cloud—and a Grover attacker cannot buy their way out. The iterations must run essentially serially, on one machine, holding coherence throughout.

Second, the standards body did the arithmetic in public and nobody read it. NIST’s own call for proposals caps the depth of any serial quantum computation at a plausible ceiling and prices AES-128 key recovery, on that assumption, at around 2 to the 106th quantum gates—not 2 to the 64th. It then suggests each logical quantum gate should be costed at billions of times a classical one. The clinching detail is structural: NIST defined its lowest security category as the cost of key search on AES-128. It did not treat AES-128 as broken. It treated it as the floor.

So the threat is narrow and specific, and it is worth stating cleanly. Symmetric encryption survives. Hash functions survive. Public-key cryptography—the part that lets strangers agree a secret in public—does not survive at all.

How Big a Machine, and How Far Away

Here the story stops being mathematics and becomes engineering, and the numbers have been moving in an uncomfortable direction.

Physical qubits are appallingly noisy, so long computations need error correction: many physical qubits spending their whole existence keeping one reliable logical qubit alive. The real question is therefore never how many qubits a machine has.

In 2019 Craig Gidney and Martin Ekera published the estimate that became the field’s reference point: breaking RSA-2048 would take roughly 20 million noisy physical qubits running for about eight hours. That was reassuring. Machines then had dozens of qubits.

In 2025 Gidney revised his own number. Better arithmetic circuits, better error-correcting codes, cleverer magic-state handling: under a million noisy qubits, in under a week. He held every physical assumption fixed—same grid, same gate error, same cycle time. Nothing about the physics changed. The requirement fell by a factor of twenty in six years purely because people got better at the theory, and it fell while the hardware was climbing towards it from the other side. That is the actual shape of the risk, and it is not the shape most people picture: the finish line has been moving towards the runner.

Two pieces of honesty about that figure. The 2019 paper is peer-reviewed; the 2025 revision is so far an unrefereed preprint. And a separate 2025 result, presented at a major conference, cut the requirement along a different axis entirely—around 1,730 logical qubits, run about forty times. Do not compare that number to the million: one counts logical qubits and the other physical ones, and conflating them is the single commonest error in writing about this.

What exists today: Google’s Willow chip has 105 superconducting qubits and, more importantly, demonstrated that scaling the error-correcting code halves the logical error rate at each step—the first convincing below-threshold result on that platform. Quantinuum’s trapped-ion Helios has 98 qubits with two-qubit gate errors around 8 in ten thousand. Note what that implies: Gidney assumes a gate error of one in a thousand, and current trapped-ion hardware is already about eight times better than that. Fidelity is not the binding constraint. Count and scale are.

Why the Deadline Has Already Passed

Now the part that turns this from an interesting future problem into a present one. An adversary does not have to wait. They can record your encrypted traffic today, store it, and decrypt it whenever the machine arrives. The practice is called harvest now, decrypt later.

Michele Mosca turned the consequence into arithmetic that every security team now recites. Let x be how long your secret must stay secret. Let y be how long your migration will take. Let z be the time until a cryptographically relevant quantum computer exists. If x plus y exceeds z, you have a problem today—because anything you transmit now, protected by the old mathematics, can be opened before its secrecy has expired.

⤢ enlarge

Is anyone actually doing it? The most solid evidence is not an intelligence leak but a legal document. The NSA’s declassified minimisation procedures for one of its collection programmes specify that ordinary intercepted communications may be retained for five years—and then carve out an exception. Encrypted material, or material reasonably believed to contain secret meaning, may be kept for any period during which it is subject to, or of use in, cryptanalysis. Indefinitely, in other words, and specifically because it is encrypted. Whatever else is true, harvest-now-decrypt-later is written into retention policy.

In fairness, not everyone thinks it is the main threat. Britain’s National Cyber Security Centre has been notably cooler: it accepts the risk exists but judges it worthwhile only for very high-value information, given what it costs to warehouse traffic for decades against an uncertain payoff, and considers the threat to digital signatures the more broadly urgent one. That is a genuine disagreement between serious agencies and it deserves saying.

The New Hard Problems

So the world needs different mathematics: problems hard for quantum computers as well as classical ones. The requirement is subtle. It is not enough to be hard today—the problem must lack the hidden commutative structure that a Fourier transform can find, because that structure is exactly what Shor exploits.

The leading answer is lattices. A lattice is the set of points you reach by adding and subtracting whole-number multiples of a few basis vectors—in two dimensions, wallpaper. The problems are easy to state: find the shortest vector in the lattice, or find the lattice point nearest to some target that is not on it. In two dimensions your eye solves this instantly. In a thousand dimensions, with a deliberately awkward basis, nobody knows how.

⤢ enlarge

The cryptographic version is usually phrased as learning with errors, and it is beautifully simple. Take a system of linear equations, which any schoolchild solves by elimination, and add a small random error to each one. Now elimination fails—not gracefully, catastrophically—because every row operation multiplies the errors along with everything else, and after a few dozen steps the noise has swallowed the signal. There is no solve-then-denoise. The whole security of the scheme is a handful of small random numbers that make an easy problem unrecoverable.

There is a genuine theoretical prize here that also gets overstated, so let me state it carefully. Oded Regev proved a reduction showing that solving random average-case instances of learning with errors would let you solve the worst case of certain lattice problems. That is a guarantee no factoring-based system has ever offered: RSA has weak moduli that are far easier than typical ones, and learning with errors has no known weak class. But the reduction is itself quantum, it is not tight, and if you push real deployed parameters through it the guarantee that comes out the other end is vacuous. Actual parameters are chosen by direct cryptanalysis. The theorem is a structural sanity check, not a parameter-selection tool.

The other families hedge different risks. Hash-based signatures need nothing but a hash function behaving like a hash function—no groups, no rings, no lattices, nothing algebraic for a future cryptanalyst to grip. That makes their assumption the most conservative in all of cryptography, and it is conservative in a specific way worth appreciating: you are already making that assumption anyway. Every TLS session and every code-signing check already trusts SHA-2. Hash-based signatures add no new attack surface at all. They pay for that with signatures of eight to fifty kilobytes, against about two and a half for the lattice scheme.

Two Schemes That Died, and Why It Matters

The competition ran for eight years in the open, and the most instructive thing that happened is that things broke.

Rainbow was a signature scheme and a Round-3 finalist—one of three, a single step from becoming a standard. In February 2022 Ward Beullens published a paper titled, accurately, *Breaking Rainbow Takes a Weekend on a Laptop*. Average time to recover the secret key: about 53 hours, on a normal computer. Years of public scrutiny had not found it.

SIKE was an isogeny-based scheme, still in the running in a later round. On 30 July 2022 Wouter Castryck and Thomas Decru posted an attack that broke its main parameter set in about an hour on a single core; the polished version got it down to ten minutes. It worked by noticing that the protocol had to publish some auxiliary data to function at all, and that a theorem from a neighbouring area of geometry turned that data into a key. The break came from what the protocol was obliged to reveal, not from the underlying problem being easy.

Then watch what happened next. On 8 August a second group generalised the attack to arbitrary starting conditions. On 10 August a third made it unconditional and classical polynomial time. Eleven days from first preprint to complete collapse, by three independent groups working in public. That is not a failure of the process. It is the process, and it is the entire argument for doing this in the open and for standardising across families that share no mathematics—lattices, hashes, and codes—rather than betting the world on one.

There is a third episode worth keeping, because it cuts the other way. In April 2024 a respected researcher posted a claimed polynomial-time quantum algorithm for learning with errors—which, had it held, would have taken the whole lattice edifice down with it. Eight days later he posted an update: two experts had independently found a bug in step nine, and he did not know how to fix it. The claim was withdrawn by its own author, in public, within a working week. Both halves of that story are worth carrying: that the foundations are attackable, and that the field notices fast.

What Was Swapped Out Underneath You

This is the part that answers the practical question, and the answer is that most of it already happened without anything reaching your screen.

In August 2024, after the eight-year public competition, the first standards were published. FIPS 203 is the key-establishment mechanism built on module lattices, known during the contest as Kyber. FIPS 204 is the main signature scheme, formerly Dilithium. FIPS 205 is the conservative hash-based signature, formerly SPHINCS+. A code-based backup was selected in March 2025 specifically so the world is not standing on lattices alone.

And then it shipped, fast, and almost silently. Chrome turned on hybrid post-quantum key exchange by default on desktop in early 2024; Firefox followed that autumn; OpenSSH made it the default in April 2025; Apple rolled it out across its systems in late 2025. By April 2026, more than two-thirds of human-generated web traffic reaching one of the largest networks on the internet was post-quantum protected. Two years earlier the figure was under three per cent. This month, the relevant specification stopped being a draft and became a published internet standard.

Note the word hybrid. Every one of these deployments runs the old elliptic-curve exchange and the new lattice one together, and combines both results, so an attacker must break both. Nobody is confident enough in mathematics this young to stand on it alone. It costs a little bandwidth and buys the right to be wrong about one of the two.

Messaging went first and went further. Signal added a post-quantum handshake in 2023 and then, in late 2025, extended it to the ongoing ratchet that re-keys every message—closing the gap where a conversation’s long-term forward secrecy still leaned on elliptic curves. Apple shipped an equivalent for iMessage in 2024.

The Part That Is Genuinely Hard

Key exchange was the easy half, because both ends are software and both ends update. Signatures are the hard half, and that is where the next decade of grinding work actually lies.

Signatures are everywhere and they are long-lived. Certificate authorities. Code signing. Firmware verification. The hardware root of trust burned into a chip in a factory, which cannot be changed because it is physically unchangeable. And the new ones are big: where an elliptic-curve signature is 64 bytes, the lattice replacement is about 2,400, with a public key of 1,300 more. That sounds trivial until you remember a certificate chain must fit inside a handshake, or a firmware image inside a fixed memory region.

The fourth standard, a compact lattice signature that would have eased exactly this problem, still has no published draft six years after selection—its signing procedure needs floating-point arithmetic that is extraordinarily difficult to implement without leaking the key through timing. Serious engineers now project it as usable around 2033. The working assumption across the industry has become: the large signature is what we have, so build around it.

Then there is the long tail. A car sold today will still be verifying updates in 2040 with a key baked into a module nobody plans to replace. Industrial controllers run for thirty years. There are satellites in orbit that will never receive a cryptographic upgrade of any kind. Some of this equipment will simply reach the end of its life still running mathematics we expect to be broken, and the plan for it is, honestly, attrition.

What It Is Reasonable to Believe

Governments have now committed to dates, which is new. A June 2026 executive order requires United States federal high-value systems to use post-quantum key establishment by the end of 2030 and post-quantum signatures by the end of 2031, with everything else migrated by 2035. Britain, Canada and the European Union have converged on the same 2035 endpoint. Australia is the outlier and the most aggressive: its signals directorate has said RSA and elliptic-curve cryptography will not be approved beyond 2030, full stop.

There is a small irony worth recording. Several of those national roadmaps justify the 2035 date by citing an American technical document specifying that the old algorithms be disallowed after 2035—and that document is still an unfinalised draft, nearly two years after its comment period closed.

As for when the machine arrives: nobody knows. The best available instrument is an annual survey of the people actually building them, and the most recent found a cryptographically relevant quantum computer quite possible—28 to 49 per cent—within ten years, and likely, at 51 to 70 per cent, within fifteen. Read those honestly. They are not a prediction; they are a distribution of opinion, from a panel that has been shrinking, with no respondents from China.

It also cuts the other way, and the field is worse at saying this. No quantum computer has factored any number of cryptographic relevance, by any method that would work on a real modulus. The largest genuine factorisations by Shor’s algorithm are 15 and 21, and even those used a compiled version of the algorithm that has the answer built in. The periodic headlines are, without exception so far, either numbers constructed to be easy or computations where a classical algorithm did the work. One paper made the point by reproducing a widely-reported quantum factoring record on a 1980s home computer.

And the migration carries its own risk that gets far too little attention. The new schemes are young. Factoring has been attacked continuously since the 1970s. Lattice cryptography has had a fraction of that scrutiny, and the two schemes that died showed how fast a well-regarded design can fall when somebody arrives with an unexpected tool. It is not impossible that we spend a decade migrating to lattices and then migrate again.

But that is an argument for hedging, which is what the hybrid deployments and the deliberately non-lattice backup standard are for. It is not an argument for waiting, because the asymmetry is stark. Migrate early and the machine never comes, and you have wasted engineering effort. Wait and it does, and everything you sent in the interval was already collected.

There is a last thought I keep returning to, and it is not about risk at all. Every cipher humanity has ever used has been a bet that some particular piece of mathematics is hard, and we have never once won that bet on paper. Not for factoring, not for discrete logarithms, not for lattices. Proving any of them genuinely hard would settle questions in complexity theory that have stood open for fifty years. So the privacy of eight billion people rests, and has always rested, on a conjecture—and the current alarm is not that the conjecture was disproved. It is that somebody worked out how to walk around it.