Code-Based and Alternative PQC Approaches
Learning Objectives
Describe code-based cryptography and its 45-year track record
Explain why multivariate and isogeny approaches have struggled
Analyze why NIST selected lattice/hash over alternatives
Assess the role of Classic McEliece as a conservative option
Understand the lessons from SIKE/SIDH's failure
Classic McEliece Overview:
Foundation:
├── Proposed by Robert McEliece in 1978
├── Based on error-correcting codes
├── Predates RSA (1977) and ECC (1985)
└── 45+ years without fundamental break
How It Works:
├── Secret key: Efficiently decodable code (Goppa code)
├── Public key: Disguised version of code
├── Encryption: Encode message + add errors
├── Decryption: Use secret structure to correct errors
└── Security: Decoding random code is NP-hard
Key Characteristics:
├── Very large public keys (~1 MB for 256-bit security)
├── Small ciphertexts (~100-200 bytes)
├── Fast encryption/decryption
├── No known quantum speedup
└── Most conservative assumption besides hash-based
Code-Based Limitations:
For Key Encapsulation (Encryption):
├── Works well
├── Large public key is main drawback
├── NIST finalist (Classic McEliece)
└── Used for very high assurance applications
For Signatures:
├── No efficient code-based signature scheme
├── Attempts exist but impractical
├── Size and performance poor
└── Not competitive with lattice or hash-based
For XRPL:
├── Classic McEliece is for encryption, not signatures
├── XRPL needs signatures (transaction authorization)
├── Code-based signatures not mature
└── Not applicable to XRPL's needs
Alternative Code-Based KEMs:
BIKE (Bit Flipping Key Encapsulation):
├── Based on QC-MDPC codes
├── Smaller keys than McEliece
├── Under consideration in NIST Round 4
└── Still larger than ML-KEM
HQC (Hamming Quasi-Cyclic):
├── Based on quasi-cyclic codes
├── Similar trade-offs to BIKE
├── Also in NIST Round 4
└── Potential future standard
Status:
├── Both in "additional signature" NIST track
├── May become standards eventually
├── Still not for signatures (KEM only)
└── Not directly relevant to XRPL
Multivariate Polynomial Systems:
Foundation:
├── Security based on solving systems of polynomial equations
├── MQ problem (solving multivariate quadratic equations)
├── NP-hard in general case
└── Proposed since 1980s
Schemes:
├── Rainbow (NIST finalist — BROKEN)
├── GeMSS
├── MQDSS
└── Various others
Characteristics:
├── Very small signatures (some variants)
├── Fast operations
├── BUT: Difficult to get parameters right
└── Several schemes broken over time
Rainbow Failure (2022):
Timeline:
├── Rainbow was NIST Round 3 finalist
├── Expected to be standardized
├── February 2022: Ward Beullens publishes attack
├── Attack breaks Rainbow in weekend on laptop
└── Complete cryptographic failure
The Attack:
├── Exploited algebraic structure
├── Reduced to simpler linear algebra problem
├── 53 hours on laptop for 128-bit security parameters
└── Completely practical, not just theoretical
Impact:
├── Rainbow removed from NIST consideration
├── Entire multivariate family under suspicion
├── Other multivariate schemes likely vulnerable
└── Lesson: "Clever" constructions can hide weaknesses
Takeaway:
├── Long standardization ≠ guaranteed security
├── New attacks can emerge suddenly
├── Conservative assumptions (hash, lattice) are safer
└── Multivariate cryptography mostly abandoned
Isogeny Cryptography:
Foundation:
├── Based on maps between elliptic curves (isogenies)
├── Finding isogenies between random curves is hard
├── Proposed as compact PQC option
└── SIDH/SIKE was NIST Round 3 finalist
Appeal:
├── Very small keys (~200-500 bytes)
├── Smallest of any PQC scheme
├── Similar to classical ECC in key sizes
└── Seemed ideal for constrained environments
SIKE (Supersingular Isogeny Key Encapsulation):
├── Round 3 finalist
├── Expected to be alternative to Kyber
├── Compact keys made it attractive
└── Then disaster struck...
SIKE Failure (July 2022):
The Attack:
├── Wouter Castryck and Thomas Decru
├── Published attack using "torsion point information"
├── Breaks SIKE in hours on single laptop
├── Completely practical attack
└── Uses classical mathematics (not quantum!)
Key Point:
├── SIKE broken by CLASSICAL computer
├── Didn't even need quantum computer
├── Mathematical structure was fatally flawed
├── 6 years of analysis missed this weakness
Impact:
├── SIKE immediately withdrawn from NIST
├── Entire isogeny-based family questioned
├── Research into "safe" isogeny variants continues
└── But trust is severely damaged
Lessons:
├── Novel mathematics carries novel risks
├── Small key sizes came from exploitable structure
├── Conservative choices (lattice, hash) validated
└── "Compact PQC" may be too good to be true
Current Isogeny Research:
CSIDH:
├── Different isogeny construction
├── Group action based
├── Not broken by SIKE attack
├── But: Very slow, uncertain security
SQISign:
├── New signature scheme
├── Very compact signatures (~200 bytes)
├── Based on different isogeny mathematics
├── Under active analysis, too new to trust
Status:
├── Isogeny cryptography continues as research area
├── But NOT for near-term deployment
├── Needs many more years of analysis
└── Not considered for XRPL planning
NIST's Decision Framework:
Security Confidence:
├── Lattice: 15+ years analysis, no breaks
├── Hash-based: 45+ years (Merkle signatures)
├── Code-based: 45+ years (McEliece)
├── Multivariate: Repeated breaks
├── Isogeny: Novel, then catastrophically broken
└── Winner: Lattice + Hash
Practical Performance:
├── Lattice: Good balance of size/speed
├── Hash-based: Large signatures, slow
├── Code-based: Huge public keys
├── Multivariate: Small but broken
├── Isogeny: Small but broken
└── Winner: Lattice
Versatility:
├── Need both KEM and signatures
├── Lattice: Excellent for both (ML-KEM, ML-DSA)
├── Others: Partial solutions only
└── Winner: Lattice
Final Selection:
├── Primary: Lattice-based (ML-KEM, ML-DSA)
├── Backup: Hash-based (SLH-DSA)
├── Conservative KEM: Code-based (Classic McEliece)
└── Signature alternatives: Still being evaluated
What NIST Process Teaches Us:
1. Conservative Wins Long-Term:
1. Maturity Matters:
1. Flexibility Important:
1. Size vs. Security Trade-off:
---
NIST Additional Signatures Track:
Status (2024-2025):
├── Looking for additional signature schemes
├── Different trade-offs than ML-DSA
├── May standardize 1-2 more options
└── Timeline: 2025-2027
Candidates Under Review:
├── MAYO (multivariate, but new design)
├── UOV variants
├── Hash-based compact schemes
├── Isogeny-based (cautiously)
└── Others
Potential Outcomes:
├── Compact signature alternative to ML-DSA
├── Different security assumptions
├── Diversity in case of lattice concerns
└── May affect future XRPL options
Emerging PQC Research:
Lattice Improvements:
├── More efficient parameters
├── Smaller signature sizes
├── Hardware acceleration
└── Timeline: Ongoing, incremental
New Primitives:
├── Group actions (CSIDH-like)
├── Multiparty computation adaptations
├── Zero-knowledge PQC proofs
└── Timeline: 5-10 years for standards
Hybrid Approaches:
├── Combining multiple PQC families
├── Combining classical + PQC
├── Threshold signatures
└── Timeline: Being deployed now
Proven: Code-based (McEliece) has 45-year track record; multivariate and isogeny schemes have been broken.
Uncertain: Whether remaining isogeny research will yield secure schemes; whether new multivariate designs will survive.
Risky: Adopting novel "compact" PQC schemes; assuming small keys are achievable securely; ignoring lessons of Rainbow/SIKE.
Assignment: Deep-dive into a broken PQC scheme.
Part 1: Choose Rainbow or SIKE and explain the pre-break security argument (20%)
Part 2: Describe the attack that broke the scheme (25%)
Part 3: Analyze what the failure teaches about PQC design (25%)
Part 4: Assess whether similar attacks could threaten ML-DSA (20%)
Part 5: Recommend lessons for XRPL's PQC adoption strategy (10%)
Time Investment: 2-3 hours
1. Classic McEliece has been analyzed for: Answer: 45+ years (since 1978)
2. Rainbow was broken by: Answer: Classical algebraic attack in 2022
3. SIKE's appeal was: Answer: Very small key sizes
4. What broke SIKE? Answer: Classical attack (not quantum)
5. The lesson of Rainbow/SIKE for XRPL: Answer: Stick with proven conservative algorithms
End of Lesson 11
Key Takeaways
Code-based cryptography has longest track record
but impractical signatures and huge keys
Rainbow (multivariate) broken in 2022
— algebraic attacks devastated the approach
SIKE (isogeny) broken in 2022
— by classical computer, not even quantum
NIST chose lattice + hash for good reasons
— balance of security confidence and practicality
Novel "compact" schemes carry hidden risks
— XRPL should stick with proven algorithms ---