Lattice Reduction
La réduction de réseaux trouve des vecteurs de base courts et presque orthogonaux dans un réseau de dimension n, utilisée pour casser des RSA faibles et des cryptosystèmes comme NTRU.
Objectif
Trouver des vecteurs courts dans les réseaux, utilisée en cryptanalyse et optimisation.
Mécanisme
Un réseau est un sous-ensemble discret de Z^n sous une transformation linéaire. La réduction trouve une base courte dont les longueurs approchent le plus court vecteur continu (borne de Minkowski). L'algorithme LLL fait une réduction approchée ; le SVP/CVP exact est NP-difficile.
Cas d’usage
- Cryptanalyse
- Résolution de CVP/SVP
- Traitement du signal