Post-Quantum Cryptography

Why post-quantum cryptography matters

Nearly every secure connection you make today — HTTPS, SSH, a signed software update, an encrypted messenger — bootstraps its security from a public-key handshake. That handshake rests on one of two hard problems: factoring a large integer (RSA) or computing a discrete logarithm (Diffie-Hellman and elliptic-curve cryptography). Both are hard for classical computers: the best factoring algorithm, the general number field sieve, runs in sub-exponential time, so a 3072-bit RSA modulus or a 256-bit elliptic curve is comfortably out of reach.

In 1994 Peter Shor showed those defenses evaporate on a quantum computer. Shor's algorithm factors an n-bit integer using roughly O(n³) quantum gates and solves discrete logarithms with the same period-finding trick. That is polynomial time. The moment a machine with enough logical qubits and low enough error rates exists — a "cryptographically relevant quantum computer," or CRQC — RSA, DH, and ECC are all simultaneously dead. Not weakened: broken.

Post-quantum cryptography is the answer that keeps everything else the same. It runs on the classical CPUs we already own; it needs no quantum hardware; it slots into TLS, SSH, and X.509 certificates. What changes is the math underneath: the hard problem is no longer factoring but finding short vectors in a high-dimensional lattice, inverting a hash, or decoding a random linear code.

The clock already started: harvest-now, decrypt-later

A common objection is "no quantum computer can break RSA yet, so why rush?" The answer is harvest-now, decrypt-later (also called store-now, decrypt-later). An adversary records your encrypted traffic today and archives the ciphertext. It does nothing with it. Years later, when a CRQC arrives, it retroactively decrypts the entire archive.

This turns confidentiality into a race against the shelf life of your secrets. If a document must stay secret for 25 years and a quantum computer is plausibly 10–15 years out, the data transmitted today is already exposed. Diplomatic cables, health records, genomic data, and long-lived intellectual property all fall into this bucket. That is why standards bodies and governments — the U.S. via CNSA 2.0, for instance — set migration deadlines well before any quantum computer is expected: the deadline is set by the value-lifetime of data, not by the arrival of the attacker.

How lattice cryptography works: Learning With Errors

The workhorse of modern PQC is the Learning With Errors (LWE) problem, introduced by Oded Regev in 2005. Fix a dimension n and a modulus q. Pick a secret vector s in ℤ_qⁿ. An attacker sees many equations of the form:

bi = ⟨ai, s⟩ + ei (mod q)

where each a_i is public and random, and each e_i is a small random error drawn from a narrow distribution. Without the errors this is just linear algebra — Gaussian elimination recovers s instantly. Add the small noise and the system becomes, as far as anyone knows, exponentially hard to solve. Recovering s is equivalent to finding a short vector in a related lattice.

Two properties make LWE special. First, Regev's worst-case to average-case reduction: solving a random LWE instance is at least as hard as solving lattice problems (like the approximate Shortest Vector Problem) in the worst case. Most cryptography assumes an average random instance is hard and hopes so; LWE reduces to a worst-case guarantee. Second, no known quantum speedup applies — Shor's period-finding needs hidden periodic structure, and a noisy lattice has none. The best attacks, lattice basis reduction (the BKZ algorithm) and sieving, are exponential on both classical and quantum hardware.

Kyber and Dilithium use a structured variant, Module-LWE, where scalars are replaced by polynomials in the ring ℤ_q[x]/(x²⁵⁶+1). This adds algebraic structure that shrinks keys and lets you multiply via the Number-Theoretic Transform (an FFT over a finite field) in O(n log n), while — the community believes — not weakening security in a way any known attack exploits.

The three post-quantum families

NIST deliberately hedged across independent hard problems, so a mathematical break in one family does not collapse the others.

Family	Hard problem	Examples	Key / signature size	Best for
Lattice-based	Module-LWE / Module-SIS	ML-KEM (Kyber), ML-DSA (Dilithium)	Small (~1–2 KB)	General purpose: TLS, VPN, signatures
Hash-based	Second-preimage of a hash	SPHINCS+ (SLH-DSA), LMS, XMSS	Large sig (~8–50 KB)	Firmware / code signing; ultra-conservative
Code-based	Decoding random linear codes	Classic McEliece, HQC	Very large key (100 KB–1 MB+)	Static long-term keys
Isogeny-based	Supersingular isogeny walks	SIKE (broken 2022), SQIsign	Tiny keys	Research; SIDH broken by Castryck–Decru

Hash-based signatures are the most conservative: their only assumption is that a hash function resists (second-)preimage attacks. If SHA-3 is secure, SPHINCS+ is secure — no number theory required. The cost is signature size (SPHINCS+ signatures run roughly 8–50 KB) and, for the stateful variants LMS/XMSS, the operational hazard that reusing a one-time key catastrophically leaks the private key. That statefulness is why Merkle trees are central: a single long-term public key authenticates many one-time keys via a hash tree.

Code-based cryptography, epitomized by Classic McEliece, dates to 1978 and has survived 45+ years of cryptanalysis unbroken. Its Achilles heel is the public-key size — hundreds of kilobytes to over a megabyte — which rules it out of a normal TLS handshake but makes it attractive where a key is installed once and used for years.

Isogeny-based cryptography is the cautionary tale. SIKE reached NIST's fourth round with the smallest keys of any candidate, then was broken in 2022 by Castryck and Decru in hours on a laptop using a clever theorem of Kani. It is the reason the field diversifies rather than betting everything on one elegant idea.

The 2024 NIST standards

After an eight-year competition begun in 2016, NIST published three finished standards on 13 August 2024:

• FIPS 203 — ML-KEM (derived from CRYSTALS-Kyber): a key-encapsulation mechanism. It is the quantum-safe replacement for ECDH. Two parties end up with a shared symmetric key that then feeds AES. Parameter sets ML-KEM-512 / 768 / 1024 target NIST security levels 1 / 3 / 5.
• FIPS 204 — ML-DSA (from CRYSTALS-Dilithium): a lattice signature scheme, the default replacement for ECDSA and RSA signatures.
• FIPS 205 — SLH-DSA (from SPHINCS+): a stateless hash-based signature, the conservative fallback if lattices ever fall.

A fourth, FN-DSA (Falcon, a compact lattice signature using floating-point Fourier sampling), is still being drafted because its constant-time implementation is delicate — a real concern given how easily side-channel attacks exploit timing leaks.

Hybrid mode: why we belt-and-suspenders the transition

Because these lattice assumptions are newer than factoring, most deployments run hybrid key exchange: they combine a classical ECDH (say X25519) with ML-KEM and derive the session key from both. Concatenate the two shared secrets and feed them to an HKDF. An attacker must break both to recover the key. If lattices turn out weaker than believed, X25519 still protects you today; if a quantum computer arrives, ML-KEM still protects you. Cloudflare, Google Chrome, and OpenSSH ship exactly this — the X25519MLKEM768 group is already live in TLS 1.3 handshakes across a large share of the web.

Worked example: an ML-KEM-style key exchange

The heart of Kyber is Module-LWE encryption used as a KEM. The following pseudocode strips the scheme to its skeleton — the real thing operates on 256-degree polynomials, uses centered-binomial noise, and applies the Fujisaki-Okamoto transform to reach CCA security, but the shape is faithful.

# Simplified Module-LWE KEM (illustrative — NOT the real FIPS 203 spec).
# All arithmetic is over the polynomial ring R_q = Z_q[x]/(x^256 + 1),
# with entries reduced mod q = 3329. Vectors/matrices are over R_q.

def keygen():
    A = sample_uniform_matrix(k, k)      # public, k x k over R_q  (k=3 for ML-KEM-768)
    s = sample_small_noise_vector(k)     # secret, short coefficients
    e = sample_small_noise_vector(k)     # error, short coefficients
    t = A @ s + e                        # public key component (LWE samples)
    return public_key=(A, t), secret_key=s

def encapsulate(public_key):
    A, t = public_key
    r  = sample_small_noise_vector(k)    # ephemeral randomness
    e1 = sample_small_noise_vector(k)
    e2 = sample_small_noise()            # scalar-ish error in R_q
    m  = random_message_bits()           # 256-bit shared-key seed
    u  = A.transpose() @ r + e1          # ciphertext part 1
    v  = t.dot(r) + e2 + encode(m)       # ciphertext part 2, hides m
    shared_key = kdf(m)                  # symmetric key both sides derive
    return ciphertext=(u, v), shared_key

def decapsulate(secret_key, ciphertext):
    s = secret_key
    u, v = ciphertext
    # v - s.u  =  (t.r + e2 + encode(m)) - s.(A^T r + e1)
    #          =  encode(m) + [small error terms]   -> rounds back to m
    m_recovered = decode(v - s.dot(u))
    return kdf(m_recovered)              # equals the sender's shared_key

The correctness rests on error size: every term of the "small error" noise stays below q/4 in magnitude, so rounding recovers each message bit. Security rests on the fact that t = A·s + e and the ciphertext are indistinguishable from uniform random under the Module-LWE assumption — an eavesdropper learns nothing about m. Notice there is no factoring and no discrete log anywhere, so Shor's algorithm has no handle to grab.

Post-quantum vs classical public-key crypto

	RSA-3072	ECC (X25519)	ML-KEM-768 (Kyber)	ML-DSA-65 (Dilithium)
Hard problem	Factoring	Elliptic-curve DLP	Module-LWE	Module-LWE / SIS
Broken by Shor?	Yes	Yes	No (believed)	No (believed)
Role	KEM + signature	Key exchange	Key encapsulation	Signature
Public key size	~384 B	32 B	1184 B	1952 B
Ciphertext / signature	~384 B	32 B	1088 B (ct)	3309 B (sig)
Classical security	128-bit	128-bit	Level 3 (~AES-192)	Level 3

The trade-off is plain: post-quantum keys and ciphertexts are an order of magnitude larger than elliptic-curve ones, which pressures bandwidth-tight protocols (a TLS ClientHello grows, DNSSEC packets fragment). But the compute cost is often lower — Kyber's NTT-based math beats an RSA modular exponentiation handily.

Common misconceptions and pitfalls

• "PQC is quantum cryptography." No. Post-quantum cryptography is classical software run on classical CPUs. Quantum key distribution (QKD) is a different thing that needs photonic hardware and dedicated fiber; PQC needs neither.
• "We must replace AES and SHA-256." No. AES and SHA-256 face only Grover's quadratic speedup. AES-256 keeps ~128-bit post-quantum strength; double the key, keep the cipher. Only public-key primitives need replacing.
• "Lattice crypto is proven unbreakable." No. There is a worst-case reduction, not a proof of hardness. Concrete parameters are set from the best-known attack cost, which cryptanalysts keep sharpening. This is precisely why hybrid deployment and family diversification exist.
• "No quantum computer exists, so there's no urgency." Harvest-now, decrypt-later means long-lived secrets are already at risk. Migration timelines are driven by data lifetime, not by attacker readiness.
• Stateful hash signatures are dangerous if mishandled. LMS/XMSS keys must never sign twice with the same one-time key; a duplicate leaks the private key. Prefer stateless SLH-DSA unless you can rigorously guarantee state.
• Constant-time is non-negotiable. Lattice samplers and rejection loops leak secrets through timing if implemented naively. See constant-time cryptography — Falcon's floating-point sampler is the hardest case.

A short history

1978 — McEliece proposes code-based cryptography; still unbroken. 1994 — Shor publishes his factoring/DLP algorithm, making the quantum threat concrete. 1996 — Grover's algorithm shows a quadratic (not exponential) speedup on unstructured search, sparing symmetric crypto. 2005 — Regev introduces LWE with its worst-case reduction. 2016 — NIST opens the PQC standardization competition; 69 submissions arrive. 2022 — Kyber, Dilithium, Falcon, and SPHINCS+ are selected; weeks later SIKE is spectacularly broken, validating the diversification strategy. August 2024 — FIPS 203, 204, and 205 are finalized, giving the world its first standardized quantum-safe algorithms.