Un grupo de investigadores ha presentado nuevos algoritmos aleatorios que mejoran de forma significativa la resolución del problema del vector más corto (SVP) en retículos de dimensión n. Frente al récord anterior, fijado en un tiempo y espacio de 2^{n+o(n)} por Aggarwal, Dadush, Regev y Stephens-Davidowitz en STOC 2015, las nuevas propuestas resuelven el problema en 2^{0,6039n+o(n)} con un ordenador clásico y en 2^{0,5411n+o(n)} con uno cuántico, manteniendo un espacio de 2^{0,5n+o(n)}.
La clave del avance está en explotar una 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 de un retículo, la Hessiana en v/2 posee un autovector próximo a v, lo que permite recuperarlo mediante un algoritmo de decodificación a distancia acotada. Los candidatos al punto medio se indexan a través de las clases de paridad en el retículo módulo 2L, y el algoritmo identifica la clase del vector más corto estimando las Hessianas correspondientes con muestras gaussianas discretas. La optimización final recurre a coclases aleatorias de subretículos y a diversas técnicas de muestreo.
El SVP es uno de los problemas centrales de la criptoanálisis basada en retículos y de la complejidad computacional, y cualquier mejora algorítmica tiene implicaciones directas para la seguridad de varios esquemas criptográficos poscuánticos. El artículo, firmado por Minki Hhan, se publicó el 3 de agosto de 2026 en arXiv y cuenta con una revisión al día siguiente.