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, reducing exponential-class problems to O(n³) in qubit-circuit depth.

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: transition timeline — deprecate quantum-vulnerable algorithms by 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.

Hardware Implementation

PQC accelerators for SoCs, FPGAs, and ASICs.

Python: Simplified ML-KEM Core

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

# Precompute twiddle factors: ζ^(BitRev₇(i)) for NTT layers
def precompute_zetas():
    zetas = [0] * 128
    for i in range(128):
        br = int(f'{i:07b}'[::-1], 2)        # 7-bit bit-reversal
        zetas[i] = pow(ZETA, br, Q)
    return zetas

ZETAS = precompute_zetas()

def ntt(f):
    """Number Theoretic Transform: O(n log n) polynomial → NTT domain."""
    a = list(f)
    k, length = 0, 128
    while length >= 1:
        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

def pointwise_mul(f_hat, g_hat):
    """Pointwise multiplication in NTT domain (128 degree-1 polynomials)."""
    h = [0] * N
    for i in range(0, N, 2):
        z = ZETAS[64 + i // 2]
        h[i]   = (f_hat[i]*g_hat[i] + f_hat[i+1]*g_hat[i+1]*z) % Q
        h[i+1] = (f_hat[i]*g_hat[i+1] + f_hat[i+1]*g_hat[i]) % Q
    return h
  

Python: Key Generation Sketch

import os, hashlib

def cbd(eta, seed, nonce):
    """Centered Binomial Distribution — sample small polynomial."""
    # In production: expand seed with SHAKE-256, extract 64·eta bytes
    # Here simplified for illustration
    coeffs = [0] * N
    data = hashlib.shake_256(seed + bytes([nonce])).digest(64 * eta)
    for i in range(N):
        a = sum((data[2*eta*i + j] >> b) & 1
                for j in range(eta) for b in range(8)) 
        # ... (simplified — real CBD sums bit-pairs from byte stream)
        coeffs[i] = (a % (2*eta + 1)) - eta
    return [c % Q for c in coeffs]

def ml_kem_keygen(k=3, eta1=2):
    """ML-KEM-768 key generation (simplified sketch)."""
    rho = os.urandom(32)            # public seed for matrix A
    sigma = os.urandom(32)          # private seed for s, e
    
    # Generate A ∈ R_q^{k×k} from rho (deterministic via SHAKE-128)
    A_hat = [[sample_ntt(rho, i, j) for j in range(k)] for i in range(k)]
    
    # Sample secret s and error e from CBD(eta1)
    s = [ntt(cbd(eta1, sigma, n)) for n in range(k)]
    e = [ntt(cbd(eta1, sigma, n + k)) for n in range(k)]
    
    # t = A·s + e  (all in NTT domain)
    t_hat = [
        [(A_hat[i][j] @ s[j]) for j in range(k)]  # pseudocode
        for i in range(k)
    ]
    # ... sum columns, add e ...
    
    pk = encode(t_hat, rho)         # 1184 bytes for k=3
    sk = encode(s, pk, H(pk), z)    # 2400 bytes for k=3
    return pk, sk
  

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.