Post-Quantum Cryptography
Why quantum computers threaten RSA/ECC, NIST PQC standards, and migration planning
Skills taught: crypto.post-quantum
The Quantum Threat to Cryptography
Shor's algorithm, running on a large enough quantum computer, can break RSA, ECDSA, ECDH, and Diffie-Hellman in polynomial time. This threatens all current public-key cryptography. While large quantum computers don't exist yet, the threat is real: adversaries may be recording encrypted traffic today to decrypt it later ('harvest now, decrypt later').
- RSA-2048: broken by Shor's algorithm (requires ~4000 logical qubits)
- ECDSA P-256: broken by Shor's algorithm
- ECDH / Diffie-Hellman: broken by Shor's algorithm
- AES-256: weakened but NOT broken by Grover's (retains ~128-bit quantum security)
- SHA-256: weakened but NOT broken (use SHA-384 for long-term secrets)
Classical Algorithms vs Quantum Safety
- Quantum-Vulnerable Algorithms: Broken by Shor's algorithm on a large quantum computer
- Quantum-Safe Algorithms: Secure against both classical and quantum attacks
NIST Post-Quantum Standards (2024)
NIST Post-Quantum Cryptography Standards (August 2024)
=== Key Encapsulation (replaces ECDH/DH for key exchange) ===
ML-KEM (CRYSTALS-Kyber) — FIPS 203
Basis: Module Learning With Errors (MLWE) — lattice problem
Key sizes: ML-KEM-512 (128-bit), ML-KEM-768 (192-bit), ML-KEM-1024 (256-bit)
Public key: 1184 bytes (ML-KEM-768) vs 32 bytes (X25519)
=== Digital Signatures (replaces RSA/ECDSA) ===
ML-DSA (CRYSTALS-Dilithium) — FIPS 204
Basis: MLWE + Module SIS — lattice problem
Signature sizes: 2420-4595 bytes vs 64 bytes (Ed25519)
SLH-DSA (SPHINCS+) — FIPS 205
Basis: Hash functions only — no new math assumptions
Stateless hash-based signatures; conservative security
Large signatures: 7856-49856 bytes
=== Still Secure (no quantum algorithm breaks them efficiently) ===
AES-256 — 128-bit quantum security (Grover halves to 128 bits from 256)
SHA-384 — 192-bit quantum security
AES-128 — 64-bit quantum security (too low for long-term use)
SHA-256 — 128-bit quantum security (acceptable until large QC exist)
Using ML-KEM in Python (liboqs)
# pip install liboqs-python (wraps liboqs C library)
import oqs
# --- ML-KEM-768 Key Encapsulation ---
alg = "ML-KEM-768" # NIST FIPS 203 — 192-bit security
with oqs.KeyEncapsulation(alg) as kem:
# Recipient generates key pair
public_key = kem.generate_keypair() # 1184 bytes
print("Public key size:", len(public_key), "bytes")
# Sender encapsulates a shared secret using recipient's public key
ciphertext, shared_secret_sender = kem.encap_secret(public_key)
print("Ciphertext size:", len(ciphertext), "bytes")
print("Shared secret:", shared_secret_sender.hex())
# Recipient decapsulates using their private key
shared_secret_recipient = kem.decap_secret(ciphertext)
# Both have the same shared secret — use it to derive AES key with HKDF
assert shared_secret_sender == shared_secret_recipient
print("Shared secrets match!")
# --- Hybrid Key Exchange: X25519 + ML-KEM-768 ---
# TLS 1.3 uses X25519MLKEM768 (hybrid) in Chrome/Firefox
# Neither classical nor quantum alone can break it
Migration Planning
POST-QUANTUM MIGRATION PRIORITY MATRIX
PRIORITY 1 (Start now — data with 10+ year secrecy requirement)
- Long-lived TLS certificates (switch to hybrid ECDH+ML-KEM)
- Government/defence communications
- Financial data encrypted for long-term storage
PRIORITY 2 (Plan for 2025-2027 migration)
- All public TLS certificates: add ML-DSA signatures
- API key exchange: hybrid X25519+ML-KEM
- Code signing certificates
PRIORITY 3 (Already safe — verify parameters)
- AES-256 encrypted data at rest: SAFE (use AES-256 not AES-128)
- SHA-256 / SHA-384 hashing: SAFE
- Argon2 password hashing: SAFE
STEPS FOR MIGRATION:
1. Inventory all cryptographic dependencies
2. Identify algorithms (RSA, ECDSA, ECDH, DH)
3. Assess data lifetime (1yr vs 10yr+ confidentiality need)
4. Test hybrid key exchange (X25519+ML-KEM-768) in non-prod
5. Enable hybrid TLS in production
6. Migrate signatures (RSA certs → ML-DSA or hybrid ECDSA+ML-DSA)
Hybrid key exchange is the recommended transition approach: combine classical ECDH (X25519) with post-quantum ML-KEM. The combined shared secret requires breaking both algorithms. This protects against: a quantum computer breaking ML-KEM (would need ECDH too), and a classical attack on ML-KEM (would still need X25519).
Chrome and Firefox already support X25519MLKEM768 (hybrid post-quantum TLS). Cloudflare has deployed it for all connections. TLS 1.3 supports it via the RFC 8446 key_share extension.
Warning: 'Harvest now, decrypt later': Nation-state adversaries may be storing encrypted TLS traffic recorded today, planning to decrypt it once quantum computers exist. If your data must remain confidential for 10+ years, you need post-quantum key exchange NOW — not when large quantum computers exist.
Tip: AES-256 and SHA-384 are quantum-safe today. No action needed for symmetric encryption — just ensure you are using AES-256 (not AES-128) and SHA-384 for long-term commitments.
Frequently Asked Questions
Should I migrate to post-quantum cryptography today?
Begin inventory and planning now. For TLS and APIs serving ordinary web traffic, hybrid key exchange is a low-risk addition you can enable today. For long-lived secrets or high-value targets (government, finance, defence), migrate urgently. For data encrypted for <5 years, you have more time.
What is ML-KEM and how does it differ from ECDH?
ML-KEM (CRYSTALS-Kyber, NIST FIPS 203) is a key encapsulation mechanism based on the hardness of the Module Learning With Errors problem — believed to be hard for quantum computers. ECDH is based on the elliptic curve discrete logarithm, which Shor's algorithm breaks.
Are the NIST post-quantum algorithms safe from classical attacks?
Yes — NIST ran a 7-year competition with global cryptanalysis. The selected algorithms have no known classical weaknesses. The main concern is that they are newer and have less deployment history than RSA/ECC, which is why hybrid schemes are recommended during the transition.