Number Theory
Post-Quantum Cryptography
Harvest-now-decrypt-later: intelligence agencies are already recording encrypted internet traffic today, waiting for quantum computers powerful enough to decrypt it. State secrets, medical records, and financial transactions encrypted now could be compromised in 10 to 15 years. That is why NIST launched the PQC competition in 2016 and standardized Kyber in 2022. The migration is already underway: Chrome, Firefox, and Cloudflare all support post-quantum TLS today.
- **Google Chrome 116+ (2023):** X25519Kyber768 enabled by default in TLS 1.3; protects against harvest-now attacks
- **Cloudflare:** deployed Kyber768 in production in 2023; handles ~20% of global internet traffic
- **NIST FIPS 203/204/205 (2024):** ML-KEM (Kyber), ML-DSA (Dilithium), SLH-DSA (SPHINCS+)-official US standards
Предварительные знания
Shor's Algorithm: The End of RSA and DH
In 1994 Peter Shor showed that a quantum computer can factor n = p·q in polynomial time. That breaks RSA, DH, and ECDH simultaneously - not in some hand-wavy '50 years', but the moment a sufficiently powerful quantum computer exists.
**Shor's algorithm:** Factors n in O(log³ n) quantum operations using the Quantum Fourier Transform to find the period of f(x) = aˣ mod n. **What it breaks:** - RSA: factors n = p·q → computes d - DH in ℤₚ*: solves DLP in O(log³ p) - ECDH/ECDSA: solves ECDLP in O(log³ p) **What it does NOT break:** - AES-256: Grover's algorithm reduces strength from 2²⁵⁶ to 2¹²⁸-still safe - SHA-256/SHA-3: Grover halves the effective bit security-doubling key sizes suffices - Lattice cryptography: no significant quantum speedup for LWE/SVP **Current state:** IBM Condor (2023)-1121 qubits; breaking RSA-2048 requires ~4000 error-corrected logical qubits.
Harvest-now-decrypt-later attack: adversaries are already storing encrypted traffic today, waiting for quantum computers powerful enough to decrypt it later. Data with long confidentiality requirements-state secrets, medical records, long-term financial records-needs post-quantum protection now.
Grover's algorithm reduces brute-force search from O(2ⁿ) to O(2^(n/2)). What does this mean for AES-128?
Lattice Problems: SVP and LWE
A lattice is a discrete subgroup of ℝⁿ. Finding the shortest nonzero vector in a lattice is hard, both classically and quantumly. That hardness is the foundation of post-quantum cryptography.
**Lattice in ℝⁿ:** L = {Σ aᵢ·bᵢ : aᵢ ∈ ℤ}-integer linear combinations of basis vectors b₁,...,bₙ. **SVP (Shortest Vector Problem):** find the shortest nonzero vector in L. - Complexity: NP-hard in general - Best classical: LLL/BKZ in ≈ 2^(0.292·β) time - Quantum speedup: at most square root-not catastrophic **LWE (Learning With Errors):** given A ∈ ℤqⁿˣᵐ and b = As + e (s secret, e small noise), find s. - Hardness: as hard as SVP in the worst case (Regev's theorem) - Ring-LWE: same problem in R_q = ℤq[x]/(xⁿ+1) **Module-LWE:** intermediate form-used in Kyber.
Regev's theorem (2005): LWE is as hard as worst-case SVP. So if anyone breaks LWE, they have also broken SVP. Since SVP is believed to be genuinely hard, classically and quantumly, LWE-based cryptosystems rest on strong theoretical foundations.
What is the fundamental difference between LWE and ordinary linear system solving?
CRYSTALS-Kyber and CRYSTALS-Dilithium
In 2022 NIST concluded its post-quantum standardization competition (launched 2016). Winners: CRYSTALS-Kyber for key encapsulation and CRYSTALS-Dilithium for digital signatures. Both rely on Module-LWE in the ring ℤq[x]/(xⁿ+1).
**CRYSTALS-Kyber (FIPS 203, renamed ML-KEM):** - Type: KEM (Key Encapsulation Mechanism) - Problem: Module-LWE in R_q = ℤ_3329[x]/(x^256+1) - Levels: Kyber-512 (128-bit), Kyber-768 (192-bit), Kyber-1024 (256-bit) - Public key: ~800 bytes (Kyber-512); ciphertext: ~768 bytes **CRYSTALS-Dilithium (FIPS 204, renamed ML-DSA):** - Type: digital signature - Problem: Module-LWE + Module-SIS - Signature size: ~2420 bytes (Dilithium2) **Hybrid deployment:** - TLS 1.3: X25519Kyber768 = ECDH + Kyber768 combined - Already in Chrome 116+ (2023), Firefox 119+
| Scheme | Type | Hard Problem | Quantum-safe? | Key/Sig size |
|---|---|---|---|---|
| RSA-2048 | Encryption | Factorization | No (Shor) | 256 bytes |
| ECDH P-256 | KEM | ECDLP | No (Shor) | 64 bytes |
| Kyber-768 | KEM | Module-LWE | Yes (~178-bit) | 1184 bytes |
| Dilithium3 | Signature | Module-LWE+SIS | Yes (~128-bit) | 1952 bytes |
| SPHINCS+ | Signature | Hash functions | Yes (conservative) | ~8 KB |
Why does TLS 1.3 use X25519Kyber768 (a hybrid) rather than Kyber768 alone?
Key Ideas
- **Shor's algorithm:** factors n in O(log³ n) quantum operations; breaks RSA, DH, and every discrete-log scheme
- **SVP/LWE:** hard lattice problems; quantum speedup is at most square-root, not catastrophic; the foundation of PQC
- **Kyber (FIPS 203):** Module-LWE KEM; about 1 KB keys; already deployed in Chrome and Firefox
- **Migration:** harvest-now-decrypt-later forces action today; X25519+Kyber hybrid is the recommended transition strategy
Related Topics
Post-quantum cryptography is built on algebraic number theory and lattice mathematics:
- Algebraic Number Theory — Kyber operates in ℤq[x]/(xⁿ+1), the ring of integers of a cyclotomic number field
- Number Theory in Cryptography — RSA and DH are the classical schemes that post-quantum algorithms replace
- Number Theory in Computer Science — NTT (Number Theoretic Transform) is the key polynomial multiplication optimization inside Kyber
Вопросы для размышления
- Shor's algorithm needs ~4000 error-corrected logical qubits to break RSA-2048. At current error rates (~0.1% per gate), how many physical qubits does that require with surface code error correction?
- LWE with e=0 is directly solvable. How exactly does adding small noise transform the problem from polynomial-time solvable to (believed) exponential-time hard?
- Hybrid TLS: X25519+Kyber768. How are the two shared secrets combined into one key? Why is the combined scheme secure even if one of the two underlying schemes is broken?