Lattice Reduction
La reducción de retículos encuentra vectores base cortos y casi ortogonales en un retículo de n dimensiones, usada para romper RSA débil y criptosistemas como NTRU.
Propósito
Encontrar vectores cortos en retículos, usada en criptoanálisis y optimización.
Mecanismo
Un retículo es un subconjunto discreto de Z^n bajo una transformación lineal. La reducción halla una base corta cuyas longitudes se acercan al vector continuo más corto (cota de Minkowski). El algoritmo LLL realiza reducción aproximada; el SVP/CVP exacto es NP-duro.
Casos de uso
- Criptoanálisis
- Resolución de CVP/SVP
- Procesamiento de señales