Post-Quantum Cryptography
Post-Quantum Cryptography
Quantum computers running Shor's algorithm can break RSA, ECC, and DH in polynomial time. Post-quantum cryptography (PQC) builds on problems believed hard even for quantum computers — lattices, hash-based signatures, and error-correcting codes.
Definition
Shor's algorithm: a quantum computer finds prime factors of \(n\) in \(O((\log n)^3)\) operations using quantum Fourier transform. This breaks RSA-2048 in hours on a sufficiently large fault-tolerant quantum computer.
Key Result
NIST PQC standardization (2022): selected CRYSTALS-Kyber (lattice-based KEM) and CRYSTALS-Dilithium, FALCON, SPHINCS+ (signature schemes). Kyber's security rests on the Module Learning With Errors (MLWE) problem.
Example 1
Learning With Errors (LWE): given many pairs \((\mathbf{a}_i, b_i = \mathbf{a}_i\cdot\mathbf{s} + e_i\bmod q)\) with small noise \(e_i\), recover secret \(\mathbf{s}\). Best algorithms run in \(2^{O(n)}\) — believed quantum-hard.
Example 2
Hash-based signatures (SPHINCS+): construct a stateless signature scheme from a one-time Winternitz scheme combined with a hypertree of Merkle trees. Security reduces to properties of the hash function alone — minimal assumptions.
Loading lattice-crypto-viz...
Practice
- What is Grover's algorithm and how does it affect symmetric key sizes?
- Compare LWE-based cryptography with lattice-based cryptography more broadly.
- Why must key encapsulation mechanisms (KEMs) replace raw DH in TLS?
- What is a hybrid classical-post-quantum scheme and why is it recommended now?
Show Answer Key
1. Grover's algorithm: quantum search of $N$ items in $O(\sqrt{N})$ queries. For symmetric key search (AES-$k$): brute force $2^k$ keys → Grover finds the key in $O(2^{k/2})$ quantum operations. AES-128 → 64-bit quantum security (insufficient). AES-256 → 128-bit quantum security (adequate). Recommendation: double symmetric key sizes (use AES-256) to maintain 128-bit security against quantum adversaries.
2. LWE (Learning With Errors): solve $\mathbf{b} = A\mathbf{s}+\mathbf{e}\pmod{q}$ for secret $\mathbf{s}$, given noisy samples. Hardness related to worst-case lattice problems (GapSVP, SIVP). Lattice-based crypto more broadly includes: NTRU (lattice-based but predates LWE), ring-LWE (structured lattices, more efficient), module-LWE (ML-KEM/Kyber, NIST standard). All rely on hardness of lattice problems, but differ in structure, efficiency, and security assumptions.
3. Raw DH produces a shared secret, but in TLS, we need a key encapsulation mechanism (KEM) that outputs a fixed-length symmetric key with a formal security proof. KEMs have cleaner security definitions (IND-CCA2), handle edge cases (e.g., malformed messages), and compose better with symmetric encryption. Post-quantum schemes (Kyber/ML-KEM) are natively KEMs, not DH-like protocols. TLS 1.3 already uses HKDF to derive keys from DH outputs, and KEMs formalize this.
4. Hybrid scheme: combine a classical algorithm (e.g., X25519) with a post-quantum algorithm (e.g., ML-KEM-768) in the same handshake. The combined key is secure if either algorithm is secure. Rationale: post-quantum algorithms are newer and less battle-tested; if a PQ scheme is broken, classical security remains. Recommended now (NIST, IETF) as a transition strategy. Example: TLS 1.3 with X25519Kyber768Draft00.