6 min read
On this page

Post-Quantum Cryptography

Motivation

Shor's algorithm breaks RSA, ECC (ECDSA, ECDH), and all discrete-log/factoring-based schemes in polynomial time on a sufficiently large quantum computer. Grover's algorithm provides quadratic speedup against symmetric primitives (effectively halving key lengths). Post-quantum cryptography (PQC) develops classical algorithms believed secure against quantum adversaries.

Timeline urgency: "Harvest now, decrypt later" -- adversaries can store encrypted data today and decrypt when quantum computers arrive. Long-lived secrets (government, medical, financial) require migration now.

Lattice-Based Cryptography

The dominant paradigm in PQC. Security based on the hardness of lattice problems.

Learning With Errors (LWE)

Problem: Given (A, b = As + e mod q) where A is random in Z_q^{m x n}, s is secret in Z_q^n, and e is a small error vector, find s (search-LWE) or distinguish (A, b) from uniform (decision-LWE).

Hardness: Worst-case to average-case reduction from GapSVP (approximate shortest vector problem) on lattices (Regev 2005). Believed hard for quantum computers.

Ring-LWE (RLWE): Replace Z_q^n with the polynomial ring R_q = Z_q[x]/(x^n + 1). Operations become polynomial multiplications (O(n log n) via NTT). Dramatically more efficient while maintaining security.

Module-LWE (MLWE): Intermediate between LWE and RLWE. Work over R_q^k for small k. Provides a tunable security/efficiency tradeoff. Basis for Kyber/ML-KEM and Dilithium/ML-DSA.

NTRU

One of the oldest lattice-based schemes (Hoffstein-Pipher-Silverman 1996).

Key generation: Choose small polynomials f, g in R. Public key h = g/f mod q. Security based on the NTRU problem (finding short vectors in NTRU lattices).

Encryption: c = h*r + m mod q for random small r. Decryption uses f to recover m.

Advantages: Very fast, compact keys. Status: NTRU was a NIST PQC round 3 finalist but was not selected (Kyber preferred). NTRUPrime (Bernstein et al.) uses a different ring structure to avoid potential algebraic attacks on cyclotomic rings.

Kyber / ML-KEM

NIST's selected post-quantum key encapsulation mechanism (KEM), now standardized as ML-KEM (Module-Lattice Key Encapsulation Mechanism) in FIPS 203.

Construction: CPA-secure public-key encryption (based on Module-LWE) transformed to CCA-secure KEM via Fujisaki-Okamoto transform.

Parameters (ML-KEM-768, targeting ~192-bit security):

  • Module rank k = 3, polynomial degree n = 256, modulus q = 3329
  • Public key: 1184 bytes, ciphertext: 1088 bytes, shared secret: 32 bytes
  • Key generation: ~0.1 ms, encapsulation: ~0.1 ms, decapsulation: ~0.1 ms

Performance: Comparable to or faster than ECDH for computation, but larger keys and ciphertexts (RSA-2048 public key: 256 bytes; ML-KEM-768 public key: 1184 bytes).

Dilithium / ML-DSA

NIST's selected post-quantum digital signature, standardized as ML-DSA (Module-Lattice Digital Signature Algorithm) in FIPS 204.

Construction: Fiat-Shamir with aborts (Lyubashevsky). The "abort" technique ensures signatures do not leak information about the secret key -- the signer rejects and restarts if the signature would reveal too much.

Parameters (ML-DSA-65, targeting ~192-bit security):

  • Public key: 1952 bytes, signature: 3309 bytes
  • Signing: ~0.3 ms, verification: ~0.1 ms

Comparison with classical: ECDSA-256 signature is 64 bytes; ML-DSA-65 is 3309 bytes. The size increase is significant for constrained applications but manageable for most use cases.

Hash-Based Signatures

Security relies solely on the collision resistance and preimage resistance of hash functions -- the most conservative PQC assumption.

SPHINCS+

Stateless hash-based signature scheme, standardized as SLH-DSA (FIPS 205).

Structure: Hypertree of many-time Merkle trees, each leaf a WOTS+ (Winternitz One-Time Signature) instance. A FORS (Forest of Random Subsets) few-time signature scheme handles the bottom layer.

Key properties:

  • Stateless: No state tracking needed between signatures (unlike XMSS/LMS which are stateful and risk catastrophic failure if state is reused)
  • Conservative security: Based only on hash function properties
  • Trade-offs: Multiple parameter sets balancing signature size, signing time, and security level

Parameters (SPHINCS+-SHA2-192f, fast variant):

  • Public key: 48 bytes, signature: ~35 KB
  • Signing: ~5 ms, verification: ~1 ms

Large signatures are the main drawback. Stateful alternatives (XMSS, LMS) achieve ~2.5 KB signatures but require careful state management.

Code-Based Cryptography

McEliece

Oldest PQC proposal (1978). Based on the hardness of decoding random linear codes.

Construction: Secret key is a structured code (binary Goppa code) with efficient decoding. Public key is a random-looking generator matrix obtained by applying secret permutation and scrambling matrices.

Encryption: Encode message with public generator matrix, add random errors (within decoding capacity). Decryption uses the structured private key for efficient error correction.

Key sizes: The primary drawback. Classic McEliece at 256-bit security: public key ~1 MB, ciphertext ~200 bytes. NIST round 4 candidate; selected for standardization despite large keys due to exceptionally long-standing security confidence.

Variants: BIKE (Bit Flipping Key Encapsulation) and HQC (Hamming Quasi-Cyclic) use structured codes for smaller keys (~few KB) at the cost of newer, less-studied security assumptions.

NIST PQC Standardization

Timeline

  • 2016: Call for proposals (82 submissions)
  • 2017-2019: Round 1 evaluation (69 -> 26 candidates)
  • 2020-2022: Rounds 2-3 (26 -> 7 finalists + 8 alternates)
  • 2024: Standards published:
    • FIPS 203 (ML-KEM): Kyber-based KEM
    • FIPS 204 (ML-DSA): Dilithium-based signature
    • FIPS 205 (SLH-DSA): SPHINCS+-based signature
  • Round 4 ongoing: Additional KEM candidates (BIKE, HQC, Classic McEliece) and signature candidates

Additional Signature Candidates

NIST launched a separate call for additional signature schemes (2023) seeking diversity and shorter signatures:

  • FALCON: Lattice-based (NTRU lattices + fast Fourier sampling). Very compact signatures (~666 bytes at 128-bit security) but complex implementation (requires floating-point sampling, side-channel concerns). Standardized as FN-DSA.
  • Multivariate-based: UOV (Unbalanced Oil and Vinegar), MAYO, short signatures but large public keys
  • Isogeny-based: SQISign (very compact but slow; post-SIDH analysis ongoing)

Hybrid Schemes

Combine classical and post-quantum algorithms for defense-in-depth during the transition period.

Hybrid KEM: Combine ECDH and ML-KEM. Shared secret = KDF(ECDH_shared || ML-KEM_shared). Security holds if either component is secure.

Hybrid signatures: Include both ECDSA and ML-DSA signatures. Verification requires both to be valid. Increases message size but provides security guarantee from either assumption.

Composite keys: IETF draft standards for composite public keys and signatures (draft-ounsworth-pq-composite-keys). X.509 certificates with both classical and PQ algorithms.

TLS hybrid key exchange: Already deployed in Chrome (X25519Kyber768) and other browsers. Adds ~1 KB to the TLS handshake.

Migration Challenges

Protocol Impact

  • TLS: Larger handshake messages may cause fragmentation, additional round trips. Post-quantum TLS 1.3 handshakes add ~2 KB for hybrid KEM.
  • SSH: Larger key exchange messages. Post-quantum SSH drafts exist.
  • X.509/PKI: Certificate sizes increase significantly (ML-DSA public key + signature adds ~5 KB per certificate in the chain).
  • Code signing: Larger signatures but generally acceptable.
  • IoT/embedded: Constrained devices may lack resources for some PQC algorithms. Careful parameter selection and hardware acceleration needed.

Cryptographic Agility

Systems should be designed for algorithm substitutability:

  • Protocol negotiation mechanisms (cipher suites, algorithm identifiers)
  • Modular cryptographic backends
  • Avoid hardcoding specific algorithms or key sizes
  • Plan for multiple migration cycles as PQC algorithms mature

Inventory and Prioritization

Migration strategy:

  1. Inventory: Catalog all cryptographic uses (libraries, protocols, certificates, stored data)
  2. Prioritize: Address long-lived secrets first (stored data, CA root keys)
  3. Test: Validate PQC algorithm performance and compatibility
  4. Deploy: Hybrid first, then full PQC as confidence grows
  5. Monitor: Track cryptanalytic developments and update as needed