Resuelven el problema del vector más corto en tiempo 2^{0.6039n} con la hessiana en el punto medio

Solving the Shortest Vector Problem in $2^{0.6039n}$ Time via Mid-Point Hessian

Presentamos algoritmos aleatorizados para el problema del vector más corto (SVP). Para una red n-dimensional L, nuestros algoritmos resuelven SVP en tiempo 2^{0.6039n+o(n)} clásico y 2^{0.5411n+o(n)} cuántico, con espacio 2^{0.5n+o(n)}, mejorando el mejor algoritmo anterior de Aggarwal, Dadush, Regev y Stephens-Davidowitz [STOC'15] que requería tiempo y espacio 2^{n+o(n)}. Nuestros algoritmos aprovechan la propiedad de la hessiana de la función gaussiana periódica en el punto medio del vector más corto: para un vector más corto v∈L, la hessiana en v/2 tiene un eigenvector cercano a v, que se puede usar para recuperar v mediante el algoritmo de decodificación por distancia acotada (con preprocesamiento). Dada la periodicidad módulo L, los puntos medios candidatos se indexan por las clases de paridad en L/2L. Nuestro algoritmo busca la clase de un vector más corto estimando las hessianas correspondientes usando muestras gaussianas discretas. Optimizamos el algoritmo usando subredes aleatorias y diversas técnicas de muestreo, logrando la complejidad final. Las técnicas de optimización pueden ser de interés independiente.