Why PQC
Post-quantum cryptography (PQC) means ordinary algorithms, running on ordinary computers, built on problems believed hard for both classical and quantum computers. It protects against Shor’s algorithm without special hardware, and it fixes the same targets that QKD does not: digital signatures, authentication and key exchange at internet scale.
Families of PQC
| Family | Hard problem | Examples | Trade-offs |
|---|---|---|---|
| Lattice | Learning with errors (LWE/M-LWE), NTRU, short vectors | ML-KEM, ML-DSA, FN-DSA | Fast and compact keys; relatively young assumptions |
| Hash-based | Hash preimage / collision resistance | SLH-DSA (SPHINCS+), LMS, XMSS | Very conservative; large signatures; stateful variants need care |
| Code-based | Decoding random linear codes | HQC, Classic McEliece, BIKE | Old assumptions; large keys or ciphertexts |
| Multivariate | Solving multivariate quadratic systems | UOV, Rainbow (broken 2022) | Small signatures; mixed track record |
| Isogeny | Isogenies between elliptic curves | SIKE (broken 2022); newer signature candidates | Small keys; SIKE’s collapse is a cautionary tale |
NIST standards and status
| Standard | Algorithm (origin) | Purpose | Status |
|---|---|---|---|
| FIPS 203 | ML-KEM (CRYSTALS-Kyber) | Key encapsulation | Final, 13 Aug 2024 |
| FIPS 204 | ML-DSA (CRYSTALS-Dilithium) | Digital signatures | Final, 13 Aug 2024 |
| FIPS 205 | SLH-DSA (SPHINCS+) | Hash-based signatures (backup) | Final, 13 Aug 2024 |
| FIPS 206 (planned) | FN-DSA (Falcon) | Compact lattice signatures | Draft pending in sources reviewed |
| HQC | Hamming Quasi-Cyclic | Backup KEM (code-based) | Selected March 2025; standard pending |
| NIST IR 8547 | Transition roadmap | Deprecate / disallow RSA, ECC | Reported finalised 27 Oct 2026 |
Migration dates. NIST IR 8547 proposes that quantum-vulnerable public-key algorithms be deprecated after 2030 and disallowed after 2035 (112-bit-strength RSA/ECC first; all sizes by 2035). Reports in late October 2026 describe the document as final; please check csrc.nist.gov for the current text. NSA’s CNSA 2.0 sets earlier dates for US national-security systems, and the UK NCSC and EU have published similar multi-year roadmaps (planning around 2028–2031, completion around 2035).
ML-KEM (FIPS 203)
A key-encapsulation mechanism based on Module-LWE. Alice publishes $(A,\,t=As+e)$ with small secrets; Bob uses it to encapsulate a random 32-byte secret. Parameter sets: ML-KEM-512 / 768 / 1024 with public keys 800 / 1184 / 1568 bytes and ciphertexts 768 / 1088 / 1568 bytes. It replaces RSA key transport and (EC)DH key exchange; ML-KEM-768 is the common default.
ML-DSA-44 in detail (FIPS 204)
ML-DSA (Module-Lattice-based Digital Signature Algorithm) works in the ring
where $X^{256}=-1$, so multiplication is “negacyclic” and can use the number-theoretic transform. A public matrix $A\in R_q^{k\times\ell}$ is expanded from a seed $\rho$ with SHAKE. For ML-DSA-44, $(k,\ell)=(4,4)$ and the secret coefficients are small (bound $\eta=2$).
| Parameter set | NIST category | $(k,\ell)$ | Public key | Private key | Signature |
|---|---|---|---|---|---|
| ML-DSA-44 | 2 | (4, 4) | 1312 B | 2560 B | 2420 B |
| ML-DSA-65 | 3 | (6, 5) | 1952 B | 4032 B | 3309 B |
| ML-DSA-87 | 5 | (8, 7) | 2592 B | 4896 B | 4627 B |
Key generation
- Sample random seed; expand with SHAKE into seeds $\rho,\rho',K$.
- Generate $A$ from $\rho$; sample short $s_1\in R_q^\ell$, $s_2\in R_q^k$.
- Compute $t=As_1+s_2$ and split into high bits $t_1$ and low bits $t_0$.
- Public key $=(\rho,t_1)$; private key includes $(\rho,K,s_1,s_2,t_0)$.
Signing (Fiat–Shamir with aborts)
- Hash the message with the public-key hash to get $\mu$.
- Sample a masking vector $y$ with coefficients in a range $\pm\gamma_1$; compute $w=Ay$ and its high bits $w_1$.
- Challenge $\tilde c=H(\mu\,\|\,w_1)$, expanded to a sparse polynomial $c$ with $\tau=39$ coefficients $\pm1$ (ML-DSA-44).
- Response $z=y+cs_1$. Rejection sampling: if $z$ or low bits exceed bounds, restart; this hides $s_1$ in the distribution of $z$.
- Output signature $(\tilde c,z,h)$ where $h$ is a hint that lets the verifier recover $w_1$.
Verification
Check $\|z\|_\infty$ is below the bound, recompute $c$, compute $w'=Az-ct_1\cdot2^d$, use $h$ to recover $w_1$, hash and compare the challenge. It works because
and $cs_2$ is small. Security rests on module-LWE and Module-SIS hardness; it is not “broken” by Shor’s algorithm because no hidden subgroup structure is known. Signatures are thousands of bytes versus 64 bytes for Ed25519, an important deployment cost.
SLH-DSA, FN-DSA, HQC
- SLH-DSA (FIPS 205). Stateless hash-based signatures (SPHINCS+). Only assumes hash-function security. Signatures about 8–50 KB; slower signing. Chosen as a conservative backup to lattices.
- FN-DSA (Falcon). NTRU-lattice signatures over fast Fourier sampling: much smaller signatures (about 0.7–1.3 KB) but delicate floating-point implementation; standard in preparation.
- HQC. Code-based KEM selected in 2025 as diversity against lattice breakthroughs.
Hybrids and deployment
Common practice is a hybrid: combine a classical and a PQC algorithm so security holds if either survives. Examples: TLS 1.3 groups combining X25519 with ML-KEM-768, OpenSSH hybrid KEX, Signal’s PQXDH and Apple iMessage PQ3, and dual-signature or composite certificates under development. Checklist: inventory cryptography; prioritise key exchange for long-lived confidentiality (harvest-now-decrypt-later); plan PKI and signature migration (larger certificates); design for crypto-agility; test performance and middlebox issues; track standards.
PQC vs QKD vs hybrid
| Aspect | PQC | QKD |
|---|---|---|
| Security basis | Computational hardness (believed quantum-hard) | Laws of physics (information-theoretic) |
| Hardware | Software on existing devices | Dedicated optics, detectors, fibre or satellite links |
| Authentication / signatures | Provides them (ML-DSA etc.) | Needs pre-shared key or PQC signature for authentication |
| Range and scaling | Global, internet-scale | Limited by loss; trusted relays for networks |
| Main risks | New maths could be broken; implementation bugs | Side channels, device flaws, relay trust, cost |
| Certification | NIST FIPS, CMVP | Emerging (ETSI, ISO/IEC 23837, CC profiles) |
| Typical role | Default quantum-safe baseline | Niche, high-assurance links, defence-in-depth |
Official positions. NSA states that it does not recommend QKD for national-security systems and prefers PQC; a 2024 joint paper by BSI (Germany), ANSSI (France), NLNCSA (Netherlands) and Sweden’s authorities similarly recommends PQC as the primary measure, seeing QKD only as a possible complement in specific high-security contexts. Others (EuroQCI, China, parts of Asia) invest heavily in QKD infrastructure. Most experts therefore frame them as complementary layers rather than competitors.