Inapprossimabilità dello Shortest Vector Problem per mezzo di codici Reed-Solomon

Lo Shortest Vector Problem (SVP) è il problema di individuare l'elemento più corto di un reticolo. La sua complessità è alla base della sicurezza di numerosi sistemi di criptazione moderni. In questo lavoro dimostriamo che la variante decisionale e approssimata dello SVP è NP-difficile per riduzioni randomizzate utilizzano reticoli localmente densi costruiti attraverso codici Reed-Solomon.