Post-Quantum Cryptography

Why Post-Quantum?

Every public-key cryptosystem in wide deployment today — RSA, Diffie-Hellman, ECDSA, ECDH, EdDSA — derives security from one of two problems: integer factorisation or the discrete logarithm problem.

Shor's algorithm (1994) solves both in polynomial time on a quantum computer, turning attacks that are sub-exponential classically into polynomial ones (roughly O(n³) gates for an n-bit modulus).

Grover's algorithm gives only a quadratic speedup against symmetric ciphers — doubling key length neutralises the threat.

The Quantum Threat Timeline

PQC Algorithm Families

Post-quantum schemes derive hardness from problems believed resistant to both classical and quantum algorithms.

Lattice Fundamentals

A lattice ℒ(B) is the set of all integer linear combinations of basis vectors B = {b₁, b₂, …, bₙ} ⊂ ℝⁿ:

Learning With Errors (LWE)

Introduced by Oded Regev (2005, Gödel Prize 2018). LWE is the computational foundation for ML-KEM and ML-DSA.

Interactive: LWE in Action

This demonstrates why noise makes LWE hard. Without error, the system is trivially solvable.

NIST PQC Standards (Aug 2024)

NIST IR 8547 (initial public draft, Nov 2024): quantum-vulnerable algorithms deprecated after 2030 and disallowed after 2035, with high-risk systems transitioning much earlier.

ML-KEM (FIPS 203) — Deep Dive

Module-Lattice-Based Key-Encapsulation Mechanism, derived from CRYSTALS-Kyber.

ML-KEM Protocol Flow

Number Theoretic Transform (NTT)

The NTT is the workhorse of lattice cryptography — it converts polynomial multiplication from O(n²) to O(n log n).

ML-DSA (FIPS 204) — Digital Signatures

Module-Lattice-Based Digital Signature Algorithm, derived from CRYSTALS-Dilithium.

SLH-DSA (FIPS 205) — Hash-Based Signatures

Stateless Hash-Based Digital Signature Algorithm, derived from SPHINCS+. The conservative choice — security rests solely on hash function properties.

Interactive: Key & Signature Sizes

Compare PQC algorithms against classical schemes. Select a metric to visualise:

Performance Benchmarks

PQC algorithms are competitive with — and often faster than — classical schemes in software.

One x86-64 core. Classical columns: openssl speed (OpenSSL 3.0); PQC columns: indicative portable-C figures (AVX2 code is 2–4× faster). Treat all as orders of magnitude.

Hardware Implementation

PQC accelerators for SoCs, FPGAs, and ASICs.

Python: Simplified ML-KEM Core (1/2)

A pedagogical implementation of the core NTT and polynomial arithmetic in ℤ₃₃₂₉.

Q = 3329          # ML-KEM modulus
N = 256           # polynomial degree
ZETA = 17         # primitive 256th root of unity mod Q (17^128 = -1)

def bitrev7(i):
    return int(f'{i:07b}'[::-1], 2)

# Twiddle factors ζ^BitRev7(i), as in FIPS 203
ZETAS = [pow(ZETA, bitrev7(i), Q) for i in range(128)]

def ntt(f):
    """FIPS 203 Alg. 9: 7 layers, 128 -> 2; output = 128 degree-1 residues."""
    a = list(f)
    k, length = 1, 128
    while length >= 2:
        for start in range(0, N, 2 * length):
            zeta = ZETAS[k]; k += 1
            for j in range(start, start + length):
                t = (zeta * a[j + length]) % Q
                a[j + length] = (a[j] - t) % Q
                a[j]          = (a[j] + t) % Q
        length //= 2
    return a

Python: Simplified ML-KEM Core (2/2)

def intt(a):
    """FIPS 203 Alg. 10: Gentleman-Sande butterflies, then multiply by 128^-1."""
    a = list(a)
    k, length = 127, 2
    while length <= 128:
        for start in range(0, N, 2 * length):
            zeta = ZETAS[k]; k -= 1
            for j in range(start, start + length):
                t = a[j]
                a[j] = (t + a[j + length]) % Q
                a[j + length] = (zeta * (a[j + length] - t)) % Q
        length *= 2
    return [(x * 3303) % Q for x in a]          # 3303 = 128^-1 mod 3329

def multiply_ntts(f_hat, g_hat):
    """FIPS 203 Alg. 11: 128 products of degree-1 polys mod (X^2 - γ_i)."""
    h = [0] * N
    for i in range(128):
        g = pow(ZETA, 2 * bitrev7(i) + 1, Q)     # γ_i = ζ^(2·BitRev7(i)+1)
        a0, a1, b0, b1 = f_hat[2*i], f_hat[2*i+1], g_hat[2*i], g_hat[2*i+1]
        h[2*i]   = (a0 * b0 + a1 * b1 * g) % Q
        h[2*i+1] = (a0 * b1 + a1 * b0) % Q
    return h
  

Python: K-PKE Key Generation (FIPS 203) (1/2)

import os, hashlib

def cbd(eta, seed, nonce):
    """Centred binomial sample (FIPS 203 Alg. 8): coefficient = x - y."""
    data = hashlib.shake_256(seed + bytes([nonce])).digest(64 * eta)  # PRF
    bits = [(byte >> b) & 1 for byte in data for b in range(8)]
    return [(sum(bits[2*eta*i : 2*eta*i + eta])
             - sum(bits[2*eta*i + eta : 2*eta*(i + 1)])) % Q for i in range(N)]

def sample_ntt(rho, j, i):
    """FIPS 203 Alg. 7: uniform NTT-domain poly by rejection from SHAKE-128."""
    xof = hashlib.shake_128(rho + bytes([j, i])).digest(840)  # ample bytes
    a, p = [], 0
    while len(a) < N:
        d1 = xof[p] | (xof[p+1] & 15) << 8
        d2 = xof[p+1] >> 4 | xof[p+2] << 4
        a += [d for d in (d1, d2) if d < Q]; p += 3
    return a[:N]

def encode12(f):                     # ByteEncode_12: 256 x 12 bits = 384 B
    return b''.join((f[i] | f[i+1] << 12).to_bytes(3, 'little')
                    for i in range(0, N, 2))

Python: K-PKE Key Generation (FIPS 203) (2/2)

def k_pke_keygen(d, k=3, eta1=2):
    """FIPS 203 Alg. 13 (ML-KEM-768 when k=3)."""
    g = hashlib.sha3_512(d + bytes([k])).digest()
    rho, sigma = g[:32], g[32:]      # public seed for A, private seed for s, e
    A_hat = [[sample_ntt(rho, j, i) for j in range(k)] for i in range(k)]
    s_hat = [ntt(cbd(eta1, sigma, n)) for n in range(k)]
    e_hat = [ntt(cbd(eta1, sigma, n + k)) for n in range(k)]
    t_hat = []                       # t = A·s + e, all in the NTT domain
    for i in range(k):
        acc = e_hat[i]
        for j in range(k):
            prod = multiply_ntts(A_hat[i][j], s_hat[j])
            acc = [(x + y) % Q for x, y in zip(acc, prod)]
        t_hat.append(acc)
    ek = b''.join(map(encode12, t_hat)) + rho      # 1152 + 32 = 1184 B
    dk_pke = b''.join(map(encode12, s_hat))        # 1152 B
    return ek, dk_pke     # ML-KEM dk = dk_pke ‖ ek ‖ H(ek) ‖ z = 2400 B
  

Uses ntt and multiply_ntts from the "Simplified ML-KEM Core" slides; for a fixed seed d the output matches the ML-KEM-768 keys of the kyber-py reference byte for byte. Production implementations: use liboqs, pqcrypto (Rust), or OpenSSL 3.5+ with ML-KEM support.

Hybrid Schemes & Migration

The transition strategy: combine classical + PQC for defence-in-depth.

Algorithm Decision Matrix

Recommendation: Use ML-KEM-768 for key exchange and ML-DSA-65 for general signing. Add SLH-DSA where conservative hash-only assumptions are required. Deploy hybrid initially.