08 — Post-Quantum Cryptography (PQC)

Algorithms resistant to quantum computers. Shor (1994) breaks IFP, DLP, ECDLP — destroys RSA, DH, ECC. Grover (1996) gives a quadratic speedup in search — implying symmetric keys/hashes need to double.

PQC uses problems that are (presumably) hard even with quantum: lattices, hash-based, code-based, multivariate, isogenies (one broken).

1. Quantum threat

Shor (1994)

On a quantum computer with \(\sim 4000\) stable qubits and enough gates, factors a 2048-bit \(N\) in hours. Current state (2026):

  • IBM Condor (2023) — 1121 noisy physical qubits.
  • IBM Heron (2024) — 156 qubits with partial error correction.
  • Google Willow (2024) — 105 qubits, first demo of error correction below threshold.
  • Quantinuum H2 — 56 trapped-ion qubits, high fidelity.

Gap to cryptanalysis-relevant: needs logical qubits (not physical). Estimates: 20M physical qubits to factor RSA-2048 (Gidney + Ekerå 2019). Possibly 2030–2040; maybe never; you cannot bet on it.

Grover (1996)

Search over a base of size \(N\) in \(O(\sqrt{N})\) queries. Implies:

  • AES-128 → 64-bit quantum security → insufficient.
  • AES-256 → 128-bit quantum security → OK.
  • SHA-256 collision → ~\(2^{85}\) (BHT) → still OK; some debate.
  • SHA-256 preimage → \(2^{128}\) Grover → OK.

Recommendation: AES-256 and SHA-384/SHA-3-384 minimum for the post-quantum scenario. SHA-256 considered borderline.

"Harvest Now, Decrypt Later" (HNDL)

Attackers can collect encrypted traffic today (TLS, VPN, encrypted backups) and store it until quantum is available. Everything encrypted with RSAECDHECC today is under retrospective threat.

Hence the urgency: sensitive data with long-term value (state secrets, IP, medical data) needs PQC now.

2. The NIST PQC Process problem

Round Year Submissions
Round 1 2017 69
Round 2 2019 26
Round 3 2020 7 finalists + 8 alternates
Selection Jul/2022 4 algorithms for standardization
Round 4 2022–2024 KEM backups (BIKE, HQC, Classic McEliece, SIKE)
HQC selected Mar/2025 KEM backup confirmed
Round Signatures 2023–ongoing extra competition for signatures

Finalized NIST standards (Aug/2024)

Standard Algorithm Type Round 3 Variant
FIPS 203 ML-KEM KEM CRYSTALS-Kyber
FIPS 204 ML-DSA Signature CRYSTALS-Dilithium
FIPS 205 SLH-DSA Signature SPHINCS+
FIPS 206 (draft) FN-DSA Signature FALCON

New acronyms

NIST renamed:

  • CRYSTALS-Kyber → ML-KEM (Module-Lattice-based KEM).
  • CRYSTALS-Dilithium → ML-DSA (Module-Lattice-based DSA).
  • SPHINCS+ → SLH-DSA (Stateless Hash-based DSA).
  • FALCON → FN-DSA (Fast-Fourier-over-NTRU DSA).

3. Lattice-based — mathematical foundation

Lattice

\(\Lambda = \{ \sum b_i \mathbf{v}_i : b_i \in \mathbb{Z} \}\) — integer combination of basis vectors \(\mathbf{v}_i\).

Hard problems

  • SVP (Shortest Vector Problem): find the shortest non-zero vector.
  • CVP (Closest Vector Problem): given a point, find the nearest lattice point.
  • LWE (Learning With Errors) — Regev 2005: given \((A, A\mathbf{s} + \mathbf{e})\) where \(\mathbf{e}\) is small noise, find \(\mathbf{s}\).
  • Module-LWE — structured variant used in Kyber/Dilithium.
  • Ring-LWE — extra structure.
  • NTRU — Hoffstein-Pipher-Silverman 1996, polynomial ring problem.

Why hard?

LWE reduces to worst-case lattice problems (SIVP, GapSVP) — Regev's reduction. It means: an average LWE solver → worst-case lattice solver. There is no known quantum algorithm for SVP beyond a small polynomial speedup.

4. ML-KEM (Kyber) — FIPS 203

CRYSTALS-Kyber: Bos, Ducas, Kiltz, Lepoint, Lyubashevsky, Schanck, Schwabe, Seiler, Stehlé. 2017–2022.

KEM (Key Encapsulation Mechanism) — does not encrypt a message; generates a shared secret + ciphertext that the recipient decapsulates with the private key.

Variants

Variant Security Public Key Ciphertext Shared Secret
ML-KEM-512 NIST L1 (~AES-128) 800 B 768 B 32 B
ML-KEM-768 NIST L3 (~AES-192) 1184 B 1088 B 32 B
ML-KEM-1024 NIST L5 (~AES-256) 1568 B 1568 B 32 B

Performance (3GHz CPU)

  • Keygen: ~50 µs
  • Encap: ~70 µs
  • Decap: ~80 µs

Faster than ECDH on a CPU without ECC accel. Larger sizes than ECC (32 B → 1.5 KB).

Adoption

  • TLS 1.3 hybrid X25519MLKEM768 — Cloudflare (Sep2024), Google Chrome (May2024), Firefox (Oct/2024).
  • OpenSSH — sntrup761x25519 still dominant; ML-KEM coming.
  • Apple iMessage PQ3 — Curve25519 + Kyber-1024.
  • Signal PQXDH — X25519 + ML-KEM-1024 (Sep/2023).
  • AWS KMS, Google Cloud KMS — pilots in 2024.

Hybrid mode

Combine classical KEM + PQC. The attacker has to break both:

shared = KDF(X25519_shared \\\| ML_KEM_shared \\\| context)

Standard during migration; hybrid is dropped once confidence in PQC is consolidated.

5. ML-DSA (Dilithium) — FIPS 204

CRYSTALS-Dilithium: Bai, Ducas, Kiltz, Lepoint, Lyubashevsky, Schwabe, Seiler, Stehlé.

Lattice-based signature (Fiat-Shamir + Aborts paradigm).

Variants

Variant Security Public Key Signature
ML-DSA-44 NIST L2 1312 B 2420 B
ML-DSA-65 NIST L3 1952 B 3293 B
ML-DSA-87 NIST L5 2592 B 4595 B

Performance

  • Keygen: ~70 µs
  • Sign: ~250 µs (variable due to rejection sampling)
  • Verify: ~80 µs

Trade-off: signature ~3 KB vs Ed25519 64 B. Pubkey ~2 KB vs Ed25519 32 B. Significant cost for X.509 certificates (impacts TLS cert chain size).

Adoption

  • Apple iMessage PQ3 contains Dilithium in addition to Kyber for signing.
  • IETF draft tls-mldsa-signature in progress.
  • X.509 — id-ml-dsa-44/65/87 in RFC 9810/draft.
  • WebAuthn passkeys: PQC roadmap in progress.

6. SLH-DSA (SPHINCS+) — FIPS 205

Hash-based signatures. Bernstein, Hülsing, Andreeva, Andersen, Aumasson, Buchmann, Castelnovi, Cid, Fluhrer, Gazdag, Hülsing, Kampanakis, Kölbl, Lange, Lauridsen, Mendel, Niederhagen, Reijnders, Rijneveld, Schwabe.

Stateless (no need to track a signature counter, unlike XMSS, LMS).

How it works

  • Built on Merkle trees + WOTS+ (Winternitz One-Time Signature) + FORS (Forest of Random Subsets).
  • Does not use lattices — security based solely on hash properties. Conservatively secure even if lattices are broken.
  • Slowness is the trade-off.

Variants (FIPS 205)

Param set Hash Sig size
SLH-DSA-SHA2-128s SHA-256 7856 B
SLH-DSA-SHA2-128f SHA-256 17088 B
SLH-DSA-SHA2-192s SHA-384 16224 B
SLH-DSA-SHA2-192f SHA-384 35664 B
SLH-DSA-SHA2-256s SHA-512 29792 B
SLH-DSA-SHA2-256f SHA-512 49856 B
SLH-DSA-SHAKE-128s/f SHAKE similar

s = small (smaller signature, slower), f = fast (larger signature, faster).

Performance (-128f)

  • Keygen: ~5 ms
  • Sign: ~150 ms (!!!)
  • Verify: ~5 ms

Sign is 1000× slower than Ed25519. Hence usage restricted to:

  • Code signing (rare, high value).
  • Firmware updates.
  • Root certificates (sign little).
  • Long-term archival signatures.

Hash-based (stateful variants)

  • XMSS (RFC 8391) — stateful, efficient, but CRITICAL: state reuse = compromised key.
  • LMS (RFC 8554) — similar.
  • HSS — multi-tree LMS.
  • NIST SP 800-208 (2020) — used for restricted firmware signatures.

7. FN-DSA (FALCON) — FIPS 206 draft

Fast-Fourier-based NTRU signatures. Fouque, Hoffstein, Kirchner, Lyubashevsky, Pornin, Prest, Ricosset, Seiler, Whyte, Zhang.

Lattice-based, NTRU-based. Harder to implement (floating-point arithmetic), but signatures much smaller than ML-DSA.

Variants

Variant Security Public Key Signature
FN-DSA-512 NIST L1 897 B ~666 B
FN-DSA-1024 NIST L5 1793 B ~1280 B

Performance

  • Sign: ~3 ms (slower than ML-DSA)
  • Verify: ~50 µs (faster than ML-DSA)

Trade-off vs ML-DSA

  • FN-DSA: smaller signature, harder impl (FP), constant-time challenging.
  • ML-DSA: larger signature, simpler impl, integer-only.

ML-DSA is the "default" for almost everything; FN-DSA when size is critical (e.g., bandwidth-constrained channels).

8. HQC — selected Mar/2025

Hamming Quasi-Cyclic — Aguilar Melchor, Aragon, Bettaieb, Bidoux, Blazy, Deneuville, Gaborit, Persichetti, Zémor.

Code-based KEM — security based on decoding random linear codes (a classic problem, McEliece-style).

NIST chose HQC as a backup for ML-KEM in case lattices are broken. Mainly because code-based has been studied for 50 years (McEliece 1978).

Variants

Variant Security Public Key Ciphertext
HQC-128 NIST L1 2249 B 4481 B
HQC-192 NIST L3 4522 B 9026 B
HQC-256 NIST L5 7245 B 14469 B

Larger than Kyber. Adoption will be niche.

9. Code-based: Classic McEliece

McEliece 1978 — the oldest PQC. Goppa codes. Robust, enormous historical confidence.

Problem: gigantic public key.

Variant Public Key
mceliece348864 261 KB
mceliece6960119 1 MB
mceliece8192128 1.4 MB

Unfeasible for a web TLS handshake. Used only in specific situations (storage one-time keys, B2B with pre-distributed keys).

NIST did not standardize it (Round 4); the algorithm is available in liboqs.

10. Multivariate (notable losers)

Based on the MQ problem (Multivariate Quadratic): solving a non-linear polynomial system over \(\mathbb{F}_q\).

HFEv-, Rainbow, GeMSS — all broken or weakened during the NIST process.

  • Rainbow — Round 3 finalist — broken by Beullens (2022) on a laptop in ~50 hours. Eliminated dramatically late.

Multivariate is still a research area; no NIST standard.

11. Isogeny-based — drama

SIDH / SIKE (catastrophic loser)

Supersingular Isogeny Diffie-Hellman. Jao + de Feo 2011. Attractive: very small keys (~330 B).

SIKE an alternate in NIST Round 4 (2022).

Broken in Jul/2022 by Wouter Castryck + Thomas Decru (KU Leuven). Polynomial algorithm on a laptop in ~1 hour. Uses glue-and-split attacking the torsion. A shock to the community — the area went stone dead.

CSIDH

A different variant — was not broken. But adoption is minimal.

Lesson: PQC is new, based on little-studied problems; redundancy (lattice + hash + code) is critical.

12. Practical migration

CNSA 2.0 (NSA, 2022)

NSA Cybersecurity Advisory: requires PQC transition for classified systems.

Category Algorithm Use
Asymmetric KEM ML-KEM-1024 Replace ECDH/RSA
Signature ML-DSA-87 Replace ECDSA/RSA
Long-term signature LMS / XMSS Stateful firmware
Symmetric AES-256 Continues
Hash SHA-384 or SHA-512 Continues

NSA Timeline:

  • 2025: new systems must support PQC.
  • 2030: conforming software required.
  • 2033: conforming hardware required.

Generic approach

  1. Inventory RSA, DH, ECC usage.
  2. Prioritize by long-term value of the data (HNDL risk).
  3. Hybrid first — add PQC without removing classical (the attacker needs both).
  4. Test in a pilot — TLS termination edge first.
  5. Migrate the PKI — root CAs with SLH-DSA or ML-DSA; intermediates can be hybrid.
  6. Rotate firmware signing keys to LMS/XMSS for boot validation.
  7. Monitor for breaks in PQC algorithms; prepare a re-revisited migration.

Available implementations

  • liboqs (Open Quantum Safe) — C library with all finalists.
  • OpenSSL 3.5+ — ML-KEM, ML-DSA via provider.
  • BoringSSL — Kyber in Cloudflare/Google production.
  • bouncycastle (Java) — full PQC suite.
  • wolfSSL — embedded-targeted PQC.
  • ML-KEM-Reference (NIST), liboqs-go, liboqs-rust bindings.
  • kyber-py — pure Python reference.

IETF standards

  • draft-ietf-pquip-* — PQC use guidance.
  • draft-ietf-tls-hybrid-design — hybrid TLS 1.3.
  • draft-ietf-tls-mldsa — TLS auth with ML-DSA.
  • draft-ietf-cose-dilithium — JOSE/COSE with Dilithium.
  • RFC 8391 XMSS, RFC 8554 LMS — already standardized.

13. PQC beyond NIST

China

CSTC (Chinese Standardization Technical Committee) 260 published its own PQC process. Aigis-Sig, LAC, SM9-PQ. Not NIST-aligned.

Korea

KpqC (Korea PQ Crypto): NTRU+, SMAUG, REDOG. Pilot in 2024–2026.

Europe

ENISA follows NIST but has a more cautious profile. Adoption via eIDAS 2.0.

NIST extra signatures (2023–ongoing)

Additional competition to diversify signatures:

  • 50 initial submissions.
  • Round 1 included: SQIsign (isogeny — the only one post-SIKE), Mayo (multivariate), HAWK (lattice), MIRATH (rank metric), SDitH (zero-knowledge), MAYO, etc.
  • Round 2 (2024–) — narrowing.

14. Real comparative performance (cycles, M2/Ryzen)

Operation RSA-3072 Ed25519 ML-KEM-768 ML-DSA-65 SLH-DSA-128f X25519+MLKEM768 (hybrid)
Keygen ~30 ms 50 µs 45 µs 70 µs 5 ms 100 µs
Encap/Sign 3 ms 25 µs 70 µs 250 µs 150 ms 120 µs
Decap/Verify 100 µs 50 µs 80 µs 80 µs 5 ms 130 µs
Pubkey size 384 B 32 B 1184 B 1952 B 32 B 1216 B
Sig/CT size 384 B 64 B 1088 B 3293 B 17088 B 1120 B

PQC adds ~1 KB extra to the TLS handshake but is faster than RSA. For signatures the overhead is larger in size.

15. Fully Homomorphic Encryption (FHE)

Non-NIST PQC but related. Crypto that computes over encrypted data without decrypting.

Schemes

  • BFV (Brakerski-Fan-Vercauteren) — integer arithmetic.
  • BGV (Brakerski-Gentry-Vaikuntanathan) — leveled.
  • CKKS (Cheon-Kim-Kim-Song) — approximate (floating-point).
  • TFHE (Chillotti-Gama-Georgieva-Izabachène) — boolean gates, fast bootstrap.
  • FHEW — boolean.

Performance

  • ~10⁵–10⁶ times slower than plaintext computation.
  • Bootstrap (refresh noise) is expensive: ~50 ms per gate in modern TFHE.

Libraries

  • OpenFHE (DARPA) — BGVBFVCKKSTFHEFHEW.
  • Microsoft SEAL — BFV/CKKS.
  • Concrete / TFHE-rs (Zama) — TFHE.
  • HElib (IBM) — BGV.

Real applications

  • ML inference on encrypted data (Microsoft Edge ML pilots).
  • Private set intersection.
  • Encrypted database queries (limited).

16. MPC — Multi-Party Computation

Compute a function over private inputs without revealing them. Not FHE — uses secret sharing + interactive protocols.

Frameworks

  • MP-SPDZ (Bristol).
  • EMP-toolkit (Wang et al.) — semi-honest and malicious.
  • MOTION (TU Darmstadt).
  • ABY3 — three-party for ML.

Applications

  • Threshold signatures (Bitcoin custodial).
  • Private auctions.
  • Federated learning with secure aggregation.
  • Genomic data analysis.
  • Boston Women's Workforce Council salary parity study (2017) — first publicized production MPC use case.

17. Zero-Knowledge Proofs (ZKP)

Goldwasser-Micali-Rackoff 1985. Prove a statement without revealing the witness.

Categories

  • Interactive: Σ-protocols, Schnorr.
  • Non-interactive (NIZK): Fiat-Shamir transform.
  • zk-SNARKs: Succinct, Non-interactive, Argument of Knowledge. Small (~200 bytes), constant-time verify. Trusted setup (with ceremony).
  • zk-STARKs: Scalable, Transparent (no trusted setup), larger (~50 KB).
  • Bulletproofs: range proofs without trusted setup, \(O(\log n)\).
  • PLONK, Halo, Halo2, Nova: modern SNARKs with universal trusted setup.

Applications

  • Zcash (zk-SNARKs Sapling, Halo2).
  • Ethereum L2 rollups (StarkNet, Polygon zkEVM, zkSync, Scroll, Linea).
  • Private credentials (anonymous proof of age/citizenship).
  • Hardware attestation with privacy.

See 10-cryptocurrency.md for blockchain usage.

18. Consolidated recommendation (2026)

For any new system:

Need Use
Symmetric encryption AES-256 or ChaCha20-Poly1305
Hash SHA-384 or SHA-3-384 (PQ-conservative)
Key exchange X25519MLKEM768 hybrid
Server signing Ed25519 today; plan ML-DSA-65 migration
Code signing SLH-DSA-128f (long-term) or Ed25519 + dual sig
Firmware updates LMS or XMSS (with state management)
Long-term archival sig SLH-DSA
Bandwidth-critical FN-DSA (FALCON) when stable
Privacy compute TFHE-rs or Concrete; OpenFHE
Threshold FROST (Schnorr) or Lindell-style ECDSA

Anti-patterns 2026

❌ New systems without a PQC plan (HNDL). ❌ Pure PQC without hybrid in production (no track record yet). ❌ XMSS/LMS without rigorous state management (bug = total compromise). ❌ Ignoring signature size in protocols with tight bandwidth. ❌ SIKE/SIDH anywhere (broken).

19. Bibliography

  • Bernstein, Buchmann, Dahmen (eds.), Post-Quantum Cryptography, Springer 2009.
  • NIST PQC pages: csrc.nist.gov/Projects/post-quantum-cryptography.
  • Open Quantum Safe: openquantumsafe.org.
  • Cloudflare PQC blog: blog.cloudflare.com/pq-2024/.
  • PQ-Crystals website: pq-crystals.org.
  • SPHINCS+ website: sphincs.org.
  • Real World Crypto 2023, 2024, 2025 — PQC sessions.

20. Cross-reference

  • Classical algorithms being replaced: 05-asymmetric.md (RSA, DH, ECC).
  • TLS hybrid integration: 07-protocols.md.
  • Quantum hardware projection: see §1 and the external Quantum Roadmap.
  • Confidential Computing as a complement: 09-confidential-computing.md.