Skip to content

Post-Quantum Cryptography

Abstract

Post-quantum cryptography is public-key cryptography built on mathematical problems that a quantum computer is not known to solve faster than an ordinary one. Several such schemes are older than the threat itself: Robert McEliece’s code-based system dates from 1978 and NTRU’s lattices from 1996. Nobody used them while RSA and elliptic curves worked, because their keys were larger (McEliece’s by a factor of hundreds) and the best of them were patented. The push came from outside mathematics. In August 2015 the NSA told vendors to stop migrating to elliptic curves and prepare for “quantum resistant” algorithms; in December 2016 NIST opened a competition that drew 82 submissions from 25 countries and ended with the first three standards on 13 August 2024. Two candidates collapsed on the way, one on a laptop over a weekend and one in about ten minutes on a single processor core. The motive for deploying the survivors before any quantum computer exists is “harvest now, decrypt later”: traffic recorded today can be decrypted whenever the machine arrives. By December 2025 just over half of the human web traffic Cloudflare saw used a post-quantum key exchange.

The Problem Shor Posed

In 1994 Peter Shor showed that a large enough quantum computer could factor integers and compute discrete logarithms in polynomial time. That covered every widely used public-key system: RSA rests on factoring, and Diffie–Hellman and elliptic-curve cryptography on discrete logarithms (see Public Key Cryptography). Symmetric ciphers such as AES and hash functions were less affected, since the best known quantum attack on them, Grover’s algorithm, only halves the effective key length, which doubling the key repairs.

For two decades this changed little in practice, because the machine did not exist and the estimates of when it might were long. The Canadian quantum-computing researcher Michele Mosca put the problem as an inequality in a paper of November 2015. Let x be how long a secret must stay secret, y how long it takes to move a system to new cryptography, and z how long until a quantum computer can break the old one. If x + y > z, the data is already lost, because an adversary who records it now can wait. Mosca estimated “a 1/2 chance of breaking RSA-2048 by 2031.” Medical records, diplomatic cables and the design of long-lived weapons have an x measured in decades.

Schemes Nobody Wanted

The alternatives existed before the question. In 1978, the year after RSA, Robert McEliece of Caltech and the Jet Propulsion Laboratory published a public-key system in a JPL Deep Space Network progress report. It hid the structure of an error-correcting Goppa code, the kind of code JPL used to talk to spacecraft, inside a random-looking matrix; decrypting meant correcting errors, which is easy with the secret structure and hard without it. It has survived nearly fifty years of cryptanalysis in its original form. It also had a public key of more than half a million bits in the parameters McEliece proposed (a 524 × 1024 binary matrix), against a few hundred bits for RSA at the time, and its modern version, Classic McEliece, needs about a megabyte. Ralph Merkle’s hash-tree signatures of 1979 were safe against any attacker who could not break the hash function, but each key could sign only a fixed number of messages.

Lattices came next. At Brown University in 1996 the mathematicians Jeffrey Hoffstein, Jill Pipher and Joseph Silverman designed NTRU, an encryption scheme based on hard problems in polynomial rings; the name was a joke, “Number Theorists ‘R’ Us”. It was fast, but it was patented and sold through a company, NTRU Cryptosystems, which kept it out of most free software until the encryption patent was released to the public domain in 2017. The same year as NTRU, Miklós Ajtai at IBM showed that some lattice problems are as hard on average as in the worst case, which gave lattice cryptography a firmer footing than factoring ever had. In 2005 Oded Regev introduced the learning with errors problem, recovering a secret vector from linear equations each disturbed by a small random error, and proved it at least as hard as worst-case lattice problems for a quantum computer. The paper won the Gödel Prize in 2018, and learning-with-errors variants became the basis of the schemes that NIST eventually standardised.

The NSA Blinks

On 11 August 2015 the NSA’s Information Assurance Directorate changed its guidance. For a decade it had pushed vendors towards its “Suite B” of elliptic-curve algorithms. Now it told those who had not yet made the switch not to spend the money, and to prepare instead for “the upcoming quantum resistant algorithm transition”, because “the growth of elliptic curve use has bumped up against the fact of continued progress in the research on quantum computing.” The agency’s stated goal was “cost effective security against a potential quantum computer.”

Cryptographers read it closely because it came from the NSA. Bruce Schneier thought a secret working prototype “unlikely” but concluded that the agency expected practical quantum computers sooner than his own estimate of thirty to forty years, an estimate he withdrew. Neal Koblitz, co-inventor of elliptic-curve cryptography, and his long-time collaborator Alfred Menezes wrote a paper titled “A Riddle Wrapped in an Enigma” listing the theories on offer, from a quantum breakthrough to a classical weakness in elliptic curves that the agency knew and nobody else did. The announcement settled one practical matter: the US government would move, and so the standards had to exist.

The Competition

NIST announced its call for proposals in December 2016 and received 82 submissions by the deadline of 30 November 2017, 69 of which it accepted as complete. The families were those of the preceding forty years: lattices (Kyber, Dilithium, Falcon, NTRU, Saber), codes (Classic McEliece, BIKE, HQC), hashes (SPHINCS+), multivariate equations (Rainbow) and isogenies between elliptic curves (SIKE). NIST cut the field to 26 in January 2019 and to seven finalists and eight alternates in July 2020, relying on public cryptanalysis by the research community in the manner of the AES and SHA-3 contests.

On 5 July 2022 NIST chose CRYSTALS-Kyber for key establishment and CRYSTALS-Dilithium, Falcon and SPHINCS+ for signatures. The standards followed on 13 August 2024 as FIPS 203 (ML-KEM, from Kyber), FIPS 204 (ML-DSA, from Dilithium) and FIPS 205 (SLH-DSA, from SPHINCS+); Falcon’s standard was still in draft in 2026. In March 2025 NIST added the code-based HQC as a backup key-establishment scheme, so that the whole of public-key encryption would not rest on lattices alone. The project’s leader, the NIST mathematician Dustin Moody, told administrators to “start integrating them into their systems immediately, because full integration will take time.”

Dead End: Broken in the Final

Two of the finalists and alternates were broken with ordinary computers.

Rainbow was a multivariate signature scheme, a round-three finalist whose security rested on the difficulty of solving systems of quadratic equations over finite fields. In February 2022 Ward Beullens of IBM Research Zurich posted a paper whose title gave the result: “Breaking Rainbow Takes a Weekend on a Laptop.” Given a public key at the lowest security level, his attack returned the secret key after an average of 53 hours on a standard laptop. NIST dropped it.

SIKE, Supersingular Isogeny Key Encapsulation, was the most elegant candidate and the smallest: its keys were a few hundred bytes, close to elliptic curves. It had survived into the fourth round in July 2022 as an alternate. Weeks later Wouter Castryck and Thomas Decru of KU Leuven posted a key-recovery attack built on a theorem about products of elliptic curves that Ernst Kani had published in 1997. Their implementation in the Magma computer-algebra system broke the parameters for the lowest security level “in about ten minutes on a single core.” The attack needed no quantum computer at all.

Neither break reached users, because the schemes had not been deployed except in experiments, and the experiments had been built for exactly this case. Nearly all early deployments were hybrid: they combined the post-quantum scheme with a classical one such as X25519, so that an attacker had to break both.

Deployment

The first large test ran before the competition started. From July to November 2016 Google’s Chrome Canary builds used CECPQ1, a hybrid of X25519 with the lattice scheme NewHope, on connections to Google’s servers. Adam Langley reported that the median connection became one millisecond slower while the slowest 1 percent lost 150 milliseconds, mostly because of the larger messages, and that Google had found no “unexpected impediment to deploying something like NewHope.” Google then switched the experiment off on purpose, not wanting to make a one-company scheme a de-facto standard.

Real deployment came in the 2020s, still ahead of the standards. OpenSSH 9.0, released on 8 April 2022, made a hybrid of Streamlined NTRU Prime and X25519 its default key exchange, citing attacks where an adversary could “capture now, decrypt later.” Signal added its PQXDH handshake, combining X25519 with Kyber, on 19 September 2023. Chrome 124, released in April 2024, turned on a hybrid X25519Kyber768 key exchange by default for all desktop users, and the result showed how brittle the installed internet was: firewalls and other middleboxes from several vendors rejected the larger opening message of the handshake, and Google had to give companies a temporary policy switch to turn it off. Apple announced its PQ3 protocol for iMessage on 21 February 2024, with a post-quantum key renewal about every fifty messages.

Once the standards were final, Chrome 131 moved in November 2024 from draft Kyber to ML-KEM. Cloudflare, which terminates a large share of the web’s encrypted connections, counted 29 percent of human traffic protected by post-quantum key exchange at the start of 2025 and 52 percent in early December, the jump driven by browsers and by Apple enabling it by default in iOS 26 in September. Key exchange was the easy half. Signatures, which protect certificates and software updates, are larger in every standardised post-quantum scheme than the elliptic-curve signatures they replace, and a certificate chain carries several of them in every handshake.

📚 Sources