Post-quantum cryptography: maths that resists quantum computers

Which ciphers do quantum computers break, and which can they not? Meet NIST’s 2024 standards and the “learning with errors” problem behind them through a small toy cipher.

What is at risk?

Shor’s algorithm breaks RSA and elliptic curve cryptography (ECC), which are used on the internet to share keys and make digital signatures. These methods are everywhere, from banking apps to the padlock icon of websites.

Symmetric ciphers such as AES are much more robust. Grover search speeds up key search only quadratically; that is like halving the key length. So doubling the key is enough: AES-256 is considered safe against quantum computers.

New standards

At the end of a competition started in 2016, NIST, the US standards body, published the first three post-quantum standards in August 2024: ML-KEM (formerly Kyber) for key exchange, and ML-DSA (Dilithium) and SLH-DSA (SPHINCS+) for signatures. In March 2025 HQC was also selected as a backup key-exchange method.

These methods run on ordinary computers and can be adopted with a software update. Browsers and messaging apps have already started using ML-KEM against the “harvest now, decrypt later” threat.

Learning with errors (LWE)

ML-KEM and ML-DSA rest on lattice problems, in particular the learning with errors (LWE) problem. For a secret vector s, b = A·s + e is computed, where e is small random errors. Without the errors, s could be found with school maths (by solving a system of equations). The small errors make this hopelessly hard in high dimensions, both for classical and for known quantum algorithms.

The toy example below builds Regev’s 2005 LWE encryption with small numbers and encrypts and decrypts bits. Real systems use hundreds of dimensions and far more carefully chosen parameters; do not use this code for real encryption.

import numpy as np

rng = np.random.default_rng(1)
q, n, m = 97, 8, 20
s = rng.integers(0, q, n)                  # secret key
A = rng.integers(0, q, (m, n))
e = rng.integers(-1, 2, m)                 # small errors: -1, 0 or 1
b = (A @ s + e) % q                        # public key: (A, b)

def encrypt(bit):
    r = rng.integers(0, 2, m)              # add up random rows
    return (r @ A) % q, (r @ b + bit * (q // 2)) % q

def decrypt(u, v):
    d = (v - u @ s) % q                    # what remains is a small error + bit · q/2
    return int(q // 4 < d < 3 * q // 4)

print([decrypt(*encrypt(bit)) for bit in [0, 1, 1, 0]])   # [0, 1, 1, 0]

Try it yourself

Grover found the right key among four options in a single step. For a cipher with 2¹²⁸ keys that means about 2⁶⁴ steps; raise the key to 256 bits and Grover’s work goes back up to 2¹²⁸ steps. Remove the X gates in the oracle to change the key being searched for.

Open the circuit in your browser

The circuit playground is in Turkish. Button guide: “1000 kez ölç” = measure 1000 times, “Durum vektörünü göster” = show the state vector, “Bu devrenin Qiskit kodu” = this circuit’s Qiskit code, “Geri al” = undo, “Temizle” = clear. Click a gate in the circuit to remove it.

Key points

Shor’s algorithm breaks RSA and elliptic curve cryptography; for symmetric ciphers such as AES a longer key is enough.
In 2024 NIST published the post-quantum standards ML-KEM, ML-DSA and SLH-DSA.
ML-KEM and ML-DSA rest on the hardness of lattice problems such as learning with errors (LWE).
Post-quantum cryptography runs on ordinary computers and the transition has already begun.

Test yourself

What is enough to protect symmetric ciphers such as AES against quantum computers?

Doubling the key length
Giving up encryption entirely
Using only QKD

Show the answer

Doubling the key length. Grover gives only a quadratic speed-up; AES-256 is considered safe against quantum computers too.

← BB84: quantum key distribution that detects eavesdropping · Noise and quantum error correction course →