Lattice Reduction
Lattice reduction finds short, nearly orthogonal basis vectors in an n-dimensional lattice, used to break weak RSA and cryptosystems such as NTRU.
Purpose
To find short vectors in lattices, used in cryptanalysis and optimization.
Mechanism
A lattice is a discrete subset of Z^n under a linear transform. Reduction finds a short basis whose vector lengths approach the continuous shortest vector (the Minkowski bound). The LLL algorithm performs approximate reduction; exact SVP/CVP is NP-hard.
Use cases
- Cryptanalysis
- CVP/SVP solving
- Signal processing