Post-quantum cryptography

Post-quantum cryptography is cryptography designed to stay secure once large quantum computers exist. A big enough quantum computer would break the public-key systems that protect nearly every secure connection today (RSA, Diffie-Hellman and elliptic curves), and would weaken, but not break, symmetric ciphers such as AES. No such computer exists yet. The new standards exist because the secrets people send today may still matter on the day one does.

What a quantum computer changes

A quantum computer isn't a faster ordinary computer. It can do a few specific things much faster than any known ordinary method, and two of them matter here.

• Shor's algorithm (Peter Shor, mid-1990s; the journal version is from 1997) finds the period of a repeating sequence efficiently. That one skill is enough to factor large numbers and to compute discrete logarithms, in ordinary prime fields and on elliptic curves alike. It spells the end of RSA, Diffie-Hellman, ElGamal, DSA and ECDSA at any key size, once a computer with enough reliable qubits exists.
• Grover's algorithm (Lov Grover, 1996) searches an unsorted space of N possibilities in about the square root of N steps. Against a symmetric key, that halves the key length in bits: AES-128 would offer about 64 bits of work and AES-256 about 128. The remedy is to double the key length, and 256-bit keys are the answer. This site's AES-GCM messages already use a 256-bit key, which is why cipher.ink needs no change.

Shor in miniature

The quantum computer does one job: find the period r of a^x mod N, the smallest r for which a^r = 1. Everything else is arithmetic you can do on paper. To factor N = 15, pick a = 7. The powers of 7 modulo 15 run 7, 4, 13, 1, so r = 4. Then 7² = 49 = 4 modulo 15, and gcd(4 − 1, 15) = 3 and gcd(4 + 1, 15) = 5, which are the factors. For N = 21 and a = 2 the period is 6, 2³ = 8, and gcd(7, 21) = 7 and gcd(9, 21) = 3. Some choices of a fail (an odd period, or a power that comes out as −1), and then you try another. The code below does the whole thing with the period found by brute force, which takes a number of steps comparable to N. That's the step a quantum computer replaces, and it's why the method is hopeless on a classical machine for a 617-digit N and not for a quantum one.

// The classical half of Shor's algorithm. To factor N, pick a number a, find the period r (the smallest r with a^r = 1 mod N), and turn it into factors.
// Finding r is the only slow step, and the only step a quantum computer does faster: here it is brute force, so this works only for tiny N.
function gcd(a, b) { while (b) { var t = a % b; a = b; b = t; } return a; }
function period(a, N) { var r = 1, x = a % N; while (x !== 1) { x = x * a % N; r++; } return r; }
function factorFromPeriod(N, a) {
  if (gcd(a, N) !== 1) return [gcd(a, N), N / gcd(a, N)];       // a lucky guess already shares a factor
  var r = period(a, N);
  if (r % 2) return null;                                       // an odd period does not help: try another a
  var h = Math.pow(a, r / 2) % N;                               // fine for the small numbers used here
  if (h === N - 1) return null;                                 // a^(r/2) = -1 does not help either
  return [gcd(h - 1, N), gcd(h + 1, N), r];
}

Harvest now, decrypt later

An adversary doesn't have to wait for the quantum computer to start. Encrypted traffic can be recorded today and decrypted later, once the machine exists. A key exchange that used Diffie-Hellman or RSA is then exposed retroactively, so for secrets that must stay secret for decades, the transition has to happen before the machine does. That's the motivation for deploying new key exchanges early, in a hybrid with the old ones. Signatures are less urgent. A forged signature has to be made while it still matters, so they need replacing only before such a computer appears.

The new standards

NIST ran a public competition for quantum-resistant algorithms over six years and four rounds. On 5 July 2022 it announced its first selections: CRYSTALS-Kyber for key establishment, and CRYSTALS-Dilithium, FALCON and SPHINCS+ for signatures. On 13 August 2024 it published the first three standards:

FALCON is to be standardized as FIPS 206 (FN-DSA), still in development at the time of writing. In March 2025 NIST also selected a fifth algorithm, HQC, a code-based key-establishment scheme, as a backup that doesn't rest on lattices.

Where the security comes from

Several families of hard problems are believed to resist quantum computers:

• Lattices (ML-KEM, ML-DSA, FALCON): finding a short vector in a high-dimensional grid of points, or solving noisy linear equations (learning with errors). They give small keys and fast operations, which is why they were chosen first.
• Hash functions (SLH-DSA): security rests only on the hash being hard to invert, the most conservative assumption there is, at the cost of larger signatures.
• Error-correcting codes (HQC, Classic McEliece): decoding a random-looking code. McEliece's scheme is decades old and has survived the scrutiny, with very large public keys.
• Isogenies: the SIKE scheme was spectacularly broken in 2022 by an attack on a classical computer (Castryck and Decru), a reminder that "new" and "unbroken" aren't the same as "secure".

What's deployed

The first deployments are hybrids, which run a classical exchange and a post-quantum one side by side and combine the results, so the connection is safe if either one holds. Signal added a Kyber-based exchange, PQXDH, in 2023. Apple announced its PQ3 protocol for iMessage on 21 February 2024. OpenSSH 10.0 (9 April 2025) made the hybrid mlkem768x25519-sha256 its default key exchange, and browsers talking to large content networks can now negotiate X25519MLKEM768 in TLS. Signatures lag behind. Certificates and software signing are still mostly classical, because the new signatures are much larger.

Common questions