Este es un trabajo para LLL: dale a él (o a sus hermanos) una base de una red multidimensional y escupirá una mejor. Este proceso se conoce como reducción de base reticular.
¿Qué tiene todo esto que ver con la criptografía? Resulta que la tarea de romper un sistema criptográfico puede, en algunos casos, reformularse como otro problema: encontrar un vector relativamente corto en una red. Y, a veces, ese vector se puede extraer de la base reducida generada por un algoritmo de estilo LLL. Esta estrategia ha ayudado a los investigadores a derribar sistemas que, en la superficie, parecen tener poco que ver con las celosías.
En un sentido teórico, el algoritmo LLL original se ejecuta rápidamente: el tiempo que lleva ejecutarse no escala exponencialmente con el tamaño de la entrada, es decir, la dimensión de la red y el tamaño (en bits) de los números en el vectores de base. Pero sí aumenta como función polinómica, y “si realmente quieres hacerlo, el tiempo polinómico no siempre es tan factible”, dijo Léo Ducas, criptógrafo del instituto nacional de investigación CWI en los Países Bajos.
En la práctica, esto significa que el algoritmo LLL original no puede manejar entradas demasiado grandes. “Los matemáticos y criptógrafos querían tener la capacidad de hacer más”, dijo Keegan Ryan, estudiante de doctorado de la Universidad de California en San Diego. Los investigadores trabajaron para optimizar los algoritmos de estilo LLL para acomodar entradas más grandes, logrando a menudo un buen rendimiento. Aún así, algunas tareas han permanecido obstinadamente fuera de nuestro alcance.
El nuevo artículo, escrito por Ryan y su asesora, Nadia Heninger, combina múltiples estrategias para mejorar la eficiencia de su algoritmo estilo LLL. Por un lado, la técnica utiliza una estructura recursiva que divide la tarea en partes más pequeñas. Por otro lado, el algoritmo gestiona cuidadosamente la precisión de los números involucrados, encontrando un equilibrio entre velocidad y un resultado correcto. El nuevo trabajo permite a los investigadores reducir las bases de celosías de miles de dimensiones.
Trabajos anteriores han seguido un enfoque similar: un artículo de 2021 también combina la recursividad y la gestión de precisión para agilizar el trabajo con redes grandes, pero funcionó solo para tipos específicos de redes, y no para todas las que son importantes en criptografía. El nuevo algoritmo se comporta bien en un rango mucho más amplio. «Estoy muy feliz de que alguien lo haya hecho», dijo Thomas Espitau, investigador de criptografía de la empresa PQShield y autor de la versión 2021. El trabajo de su equipo ofreció una “prueba de concepto”, dijo; El nuevo resultado muestra que «se puede realizar una reducción de red muy rápida y sólida».
La nueva técnica ya ha comenzado a resultar útil. Aurel Page, matemático del instituto nacional de investigación francés Inria, dijo que él y su equipo han puesto en marcha una adaptación del algoritmo en algunas tareas computacionales de teoría de números.
Los algoritmos de estilo LLL también pueden desempeñar un papel en la investigación relacionada con sistemas de criptografía basados en celosías diseñados para permanecer seguros incluso en un futuro con potentes computadoras cuánticas. No representan una amenaza para dichos sistemas, ya que derribarlos requiere encontrar vectores más cortos que los que estos algoritmos pueden lograr. Pero los mejores ataques que los investigadores conocen utilizan un algoritmo de estilo LLL como “elemento básico”, dijo Wessel van Woerden, criptógrafo de la Universidad de Burdeos. En experimentos prácticos para estudiar estos ataques, ese componente básico puede ralentizar todo. Con la nueva herramienta, los investigadores podrán ampliar la gama de experimentos que pueden ejecutar con los algoritmos de ataque, ofreciendo una imagen más clara de su rendimiento.
historia original reimpreso con permiso de Revista Quanta, una publicación editorialmente independiente del Fundación Simons cuya misión es mejorar la comprensión pública de la ciencia cubriendo los desarrollos y tendencias de la investigación en matemáticas y ciencias físicas y biológicas.