Problema de celosía
En informática , los problemas de celosías son una clase de problemas de optimización relacionados con objetos matemáticos llamados celosías . La intratabilidad conjeturada de tales problemas es fundamental para la construcción de criptosistemas seguros basados en celosías : Los problemas de celosías son un ejemplo de problemas NP-difíciles que han demostrado ser casos difíciles promedio., proporcionando un caso de prueba para la seguridad de los algoritmos criptográficos. Además, algunos problemas de celosía que son difíciles en el peor de los casos pueden usarse como base para esquemas criptográficos extremadamente seguros. El uso de la dureza del peor de los casos en tales esquemas los convierte en uno de los pocos esquemas que muy probablemente son seguros incluso contra las computadoras cuánticas . Para aplicaciones en tales criptosistemas , generalmente se consideran redes sobre espacio vectorial (a menudo ) o módulos libres (a menudo ).
Para todos los problemas a continuación, suponga que tenemos (además de otras entradas más específicas) una base para el espacio vectorial V y una norma N . La norma generalmente considerada es la norma euclidiana L 2 . Sin embargo, también se consideran otras normas (como L p ) y aparecen en una variedad de resultados. [1] Sea la longitud del vector distinto de cero más corto en la red L , es decir,
En el SVP, se dan una base de un espacio vectorial V y una norma N (a menudo L 2 ) para una red L y uno debe encontrar el vector distinto de cero más corto en V , medido por N , en L . En otras palabras, el algoritmo debe generar un vector v distinto de cero tal que .
En la versión de aproximación γ SVP γ , uno debe encontrar un vector de red de longitud distinto de cero como máximo para dado .
Para resolver la versión exacta del SVP bajo la norma euclidiana, se conocen varios enfoques diferentes, que se pueden dividir en dos clases: algoritmos que requieren tiempo superexponencial ( ) y memoria, y algoritmos que requieren tiempo y espacio exponencial ( ) en la dimensión de red . La primera clase de algoritmos incluye más notablemente la enumeración de celosía [5] [6] [7] y la reducción de muestreo aleatorio, [8] [9] mientras que la última incluye el tamizado de celosía, [10] [11] [12] calculando la celda de Voronoi de la red, [13] [14] y muestreo gaussiano discreto. [15]Un problema abierto es si existen algoritmos para resolver SVP exactos que se ejecuten en tiempo exponencial único ( ) y requieran un escalado de memoria polinomial en la dimensión reticular. [dieciséis]
