Lattice Reduction
Gitterreduktion findet kurze, nahezu orthogonale Basisvektoren in einem n-dimensionalen Gitter; genutzt, um schwaches RSA und Kryptosysteme wie NTRU zu brechen.
Zweck
Kurze Vektoren in Gittern finden, genutzt in Kryptoanalyse und Optimierung.
Mechanismus
Ein Gitter ist eine diskrete Teilmenge von Z^n unter einer linearen Abbildung. Die Reduktion findet eine kurze Basis, deren Vektorlängen sich dem kontinuierlichen kürzesten Vektor (Minkowski-Schranke) nähern. Der LLL-Algorithmus leistet approximative Reduktion; exaktes SVP/CVP ist NP-schwer.
Anwendungsfälle
- Kryptoanalyse
- CVP/SVP-Lösung
- Signalverarbeitung