Introduction to Post-Quantum Cryptography
Learning Objectives
Define post-quantum cryptography and its design principles
Identify the major families of PQC algorithms
Explain why these algorithms resist quantum attacks
Describe the NIST PQC standardization process and outcomes
Compare PQC algorithm families on key metrics (security, performance, size)
Post-Quantum Cryptography Requirements:
Must Resist:
├── Classical attacks (brute force, mathematical)
├── Shor's algorithm (exponential quantum speedup)
├── Grover's algorithm (quadratic quantum speedup)
└── Any known quantum algorithm
Design Strategy:
├── DON'T rely on factoring difficulty (Shor's breaks this)
├── DON'T rely on discrete log difficulty (Shor's breaks this)
├── DO rely on problems with no known quantum speedup
└── DO maintain classical security against non-quantum attacks
Problems Believed Quantum-Resistant:
1. Lattice Problems:
1. Hash-Based Security:
1. Coding Theory Problems:
1. Multivariate Polynomials:
1. Isogeny Problems:
NIST PQC Security Levels:
Level 1: Equivalent to AES-128
├── 2^128 quantum security
├── Breaks with ~2^64 Grover's oracle calls
└── Minimum acceptable for most applications
Level 2: Equivalent to SHA-256 collision resistance
├── 2^128 quantum collision security
└── Higher than Level 1 for some applications
Level 3: Equivalent to AES-192
├── 2^192 quantum security
└── Higher security margin
Level 4: Equivalent to SHA-384 collision resistance
├── 2^192 quantum collision security
└── Very high security
Level 5: Equivalent to AES-256
├── 2^256 quantum security
├── Highest standardized level
└── For highest-security applications
Lattice-Based Algorithms:
Foundation:
├── Lattices are regular grids in n-dimensional space
├── Hard problems: Finding shortest vector, closest vector
├── Learning With Errors (LWE): Solving noisy linear equations
└── No known quantum algorithm provides significant speedup
Standardized Algorithms:
├── ML-KEM (Kyber): Key encapsulation mechanism
│ └── For key exchange, encryption
├── ML-DSA (Dilithium): Digital signatures
│ └── Primary NIST signature standard
└── NTRU: Alternative lattice scheme (in some standards)
Characteristics:
├── Moderate key sizes (1-2 KB public keys)
├── Good performance (fast signing/verification)
├── Well-studied security foundations
├── Best balance of properties
└── MOST LIKELY for XRPL adoption
Hash-Based Signatures:
Foundation:
├── Security relies ONLY on hash function security
├── One-time signature schemes combined with Merkle trees
├── Extremely conservative assumption
└── Grover's only halves effective security (still secure)
Standardized Algorithms:
├── SLH-DSA (SPHINCS+): Stateless hash-based signatures
│ └── NIST backup standard
├── XMSS: Stateful hash-based signatures (RFC 8391)
└── LMS: Lightweight stateful signatures (RFC 8554)
Characteristics:
├── Largest signatures (tens of KB)
├── Very slow signing
├── Highly confident security (minimal assumptions)
├── Stateful variants require careful key management
└── Best for highest-assurance applications
Code-Based Algorithms:
Foundation:
├── Error-correcting codes (since 1978 - McEliece)
├── Decoding random linear codes is hard
├── 40+ years of cryptanalysis without break
└── No known quantum speedup
Standardized Algorithms:
├── Classic McEliece: Key encapsulation
│ └── Very large public keys (~1 MB)
│ └── Very small ciphertexts
└── BIKE, HQC: Alternative code-based KEMs (under consideration)
Characteristics:
├── Extremely large public keys
├── Fast encapsulation/decapsulation
├── Longest track record of security
├── Size impractical for many applications
└── Not likely for XRPL signatures
PQC Algorithm Family Comparison:
Family | Signatures | Key Size | Sig Size | Speed | Confidence
------------|------------|-----------|-----------|---------|------------
Lattice | ML-DSA | ~2 KB | ~3 KB | Fast | High
Hash-Based | SLH-DSA | ~64 B | ~8-50 KB | Slow | Very High
Code-Based | N/A* | ~1 MB | N/A | Fast | Very High
Multivariate| Broken** | - | - | - | Deprecated
- Code-based signatures exist but less developed
For XRPL Signatures:
├── ML-DSA: Most practical (best size/performance balance)
├── SLH-DSA: Backup option (larger but more conservative)
└── Code-based: Unlikely (no mature signature scheme)
NIST PQC Competition Timeline:
2016: Call for proposals
├── 82 submissions received
└── Goal: Standardize quantum-resistant algorithms
2017-2019: Round 1-2
├── Analysis and elimination
├── 69 → 26 → 7 finalists
└── Public cryptanalysis
2020-2022: Round 3
├── Intensive analysis of finalists
├── Some schemes broken (SIKE, Rainbow)
└── Selection of winners
2024: Final Standards Published
├── FIPS 203: ML-KEM (Kyber)
├── FIPS 204: ML-DSA (Dilithium)
├── FIPS 205: SLH-DSA (SPHINCS+)
└── Full federal standard
2024+: Ongoing
├── Additional signature schemes under review
├── Hybrid deployment guidance
└── Migration timeline mandates
NIST PQC Standards (Final):
FIPS 203 - ML-KEM (Module-Lattice Key Encapsulation):
├── Purpose: Key exchange, encryption
├── Based on: Kyber (CRYSTALS family)
├── Variants: ML-KEM-512 (Level 1), ML-KEM-768 (Level 3), ML-KEM-1024 (Level 5)
└── Status: Final standard
FIPS 204 - ML-DSA (Module-Lattice Digital Signature):
├── Purpose: Digital signatures
├── Based on: Dilithium (CRYSTALS family)
├── Variants: ML-DSA-44 (Level 2), ML-DSA-65 (Level 3), ML-DSA-87 (Level 5)
├── Sizes: Public key ~1.3-2.6 KB, Signature ~2.4-4.6 KB
└── Status: Final standard — PRIMARY XRPL CANDIDATE
FIPS 205 - SLH-DSA (Stateless Hash-Based Digital Signature):
├── Purpose: Digital signatures (backup/conservative)
├── Based on: SPHINCS+
├── Variants: Multiple security levels and speed/size tradeoffs
├── Sizes: Much larger signatures (17-50 KB)
└── Status: Final standard — XRPL BACKUP OPTION
Why These Algorithms Won:
ML-KEM (Kyber):
├── Best balance of security and efficiency
├── Small keys and ciphertexts
├── Fast operations
├── Well-analyzed lattice construction
└── Clear winner in practical metrics
ML-DSA (Dilithium):
├── Moderate signature size (vs. hash-based)
├── Fast signing and verification
├── Proven lattice security
├── Same mathematical foundation as ML-KEM
└── Most practical signature option
SLH-DSA (SPHINCS+):
├── Minimal security assumptions (hash functions only)
├── Backup if lattice cryptanalysis advances
├── Stateless (no key state management)
├── Trade-off: Much larger signatures
└── Conservative option for high-assurance
Blockchain Signature Needs:
1. Size Constraints:
1. Verification Speed:
1. Security Requirements:
1. Statelessness:
ML-DSA-65 (Likely XRPL Choice):
Parameters:
├── Security Level: 3 (128-bit quantum security)
├── Public Key: 1,952 bytes
├── Signature: 3,293 bytes
└── Verification: ~5 μs
Comparison to Current:
├── secp256k1 Public Key: 33 bytes (59× smaller)
├── ECDSA Signature: ~71 bytes (46× smaller)
└── ECDSA Verification: ~0.1 μs (50× faster)
Impact on XRPL:
├── Transaction size: ~3.3 KB overhead per signature
├── Verification time: Acceptable (~5 μs)
├── Storage: 59× more per public key
└── Fees: May need adjustment for larger transactions
Blockchain PQ Migration Challenges:
1. Backward Compatibility:
1. Address Format:
1. Multi-Signature:
1. Hardware Wallet Support:
---
Proven: Lattice and hash-based cryptography have strong security foundations; NIST standardization is complete.
Uncertain: Long-term security of lattice schemes (new cryptanalysis possible); practical deployment challenges.
Risky: Assuming any single algorithm is "forever secure"; delaying deployment waiting for "perfect" algorithms.
Assignment: Deep-dive into one NIST-standardized algorithm.
Part 1: Select ML-KEM, ML-DSA, or SLH-DSA and describe its mathematical foundation (25%)
Part 2: Analyze key/signature sizes across security levels (20%)
Part 3: Compare verification performance to ECDSA/EdDSA (20%)
Part 4: Assess suitability for XRPL specifically (20%)
Part 5: Identify potential weaknesses and mitigation strategies (15%)
Time Investment: 3-4 hours
1. Why don't PQC algorithms rely on factoring difficulty? Answer: Shor's algorithm breaks factoring efficiently
2. ML-DSA signature size for Level 3 security is approximately: Answer: ~3.3 KB
3. Which PQC family has the most conservative security assumptions? Answer: Hash-based (SLH-DSA)
4. The NIST PQC standardization finalized in: Answer: 2024
5. Lattice-based security relies on: Answer: Learning With Errors (LWE) / shortest vector problems
End of Lesson 8
Key Takeaways
PQC algorithms resist quantum attacks
by relying on mathematical problems without known quantum speedup
Lattice-based algorithms (ML-DSA)
offer the best balance of security and performance for signatures
NIST finalized three standards in 2024:
ML-KEM, ML-DSA, SLH-DSA
ML-DSA is the most likely XRPL candidate
— acceptable size/performance trade-offs
PQC signatures are 30-50× larger
than ECDSA — blockchain-specific challenges ---