Preparing for the Quantum Computing Era
Based on integer factorization
Broken by Shor's algorithmBased on elliptic curve discrete log
Broken by Shor's algorithmBased on discrete logarithm
Broken by Shor's algorithmLattice-based key encapsulation
NIST Standard 2024Lattice-based digital signatures
NIST Standard 2024Hash-based signatures
NIST Standard 2024Finding the shortest vector in high-dimensional lattices is hard even for quantum computers
Find the shortest non-zero vector in the lattice. Computationally hard in high dimensions.
Find the lattice point closest to a given target point. No known quantum speedup.
Recover secret from noisy linear equations. Basis for Kyber and Dilithium.
Lattice problems have been studied for centuries and remain hard even for quantum computers. Unlike factoring (which Shor's algorithm solves efficiently), no quantum algorithm provides significant speedup for lattice problems.
Key advantages: Fast operations, reasonable key sizes, well-understood security reductions.
Trade-off: Larger keys than ECC (but smaller than RSA at equivalent security).