El célebre algoritmo de criptografía se actualiza | Revista Quanta

En nuestras vidas cada vez más digitales, la seguridad depende de la criptografía. Envíe un mensaje privado o pague una factura en línea y dependerá de algoritmos diseñados para mantener sus datos en secreto. Naturalmente, algunas personas quieren descubrir esos secretos, por lo que los investigadores trabajan para probar la solidez de estos sistemas y asegurarse de que no se desmoronen a manos de un atacante inteligente.

Una herramienta importante en este trabajo es el algoritmo LLL, que lleva el nombre de los investigadores que lo publicó en 1982: Arjen Lenstra, Hendrik Lenstra hijo y László Lovász. LLL, junto con sus numerosos descendientes, puede romper esquemas criptográficos en algunos casos; estudiar cómo se comportan ayuda a los investigadores a diseñar sistemas que sean menos vulnerables a los ataques. Y los talentos del algoritmo van más allá de la criptografía: también es una herramienta útil en campos matemáticos avanzados como la teoría computacional de números.

A lo largo de los años, los investigadores han perfeccionado variantes de LLL para hacer que el enfoque sea más práctico, pero sólo hasta cierto punto. Ahora, un par de criptógrafos han creado un nuevo algoritmo estilo LLL con un aumento significativo en la eficiencia. La nueva técnica, que ganó el Premio al mejor artículo en el Conferencia Internacional de Criptología 2023, amplía la gama de escenarios en los que los informáticos y matemáticos pueden utilizar enfoques similares a LLL.

"Fue realmente emocionante", dijo Chris Peikert, un criptógrafo de la Universidad de Michigan que no participó en el artículo. La herramienta ha sido objeto de estudio durante décadas, afirmó. "Siempre es agradable cuando un objetivo en el que se ha trabajado durante tanto tiempo... demuestra que todavía hay sorpresas por encontrar".

Los algoritmos de tipo LLL operan en el mundo de las redes: colecciones infinitas de puntos espaciados regularmente. Como una forma de visualizar esto, imagina que estás poniendo baldosas en el suelo. Podrías cubrirlo con mosaicos cuadrados y las esquinas de esos mosaicos formarían una celosía. Alternativamente, puedes elegir una forma de mosaico diferente (por ejemplo, un paralelogramo largo) para crear una red diferente.

Una red se puede describir utilizando su "base". Este es un conjunto de vectores (esencialmente, listas de números) que puedes combinar de diferentes maneras para obtener cada punto de la red. Imaginemos una red con una base formada por dos vectores: [3, 2] y [1, 4]. La red son solo todos los puntos a los que puedes llegar sumando y restando copias de esos vectores.

Ese par de vectores no es la única base de la red. Toda red con al menos dos dimensiones tiene infinitas bases posibles. Pero no todas las bases son iguales. Una base cuyos vectores son más cortos y más cercanos a ángulos rectos entre sí suele ser más fácil de trabajar y más útil para resolver algunos problemas computacionales, por lo que los investigadores llaman a esas bases "buenas". Un ejemplo de esto es el par de vectores azules en la siguiente figura. Las bases que consisten en vectores más largos y menos ortogonales, como los vectores rojos, pueden considerarse "malas".

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 Leo Ducas, criptógrafo del instituto nacional de investigación CWI de 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 en la Universidad de California, 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 asesor, 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: A papel 2021 También combina recursividad y gestión de precisión para agilizar el trabajo con redes grandes, pero funcionó sólo 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 Tomás 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. Página de Aurel, 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 seguro incluso en un futuro con potentes ordenadores cuánticos. 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.

¿Cuánto está realizando una serie de encuestas para servir mejor a nuestra audiencia. Toma nuestro encuesta a lectores de informática y entrarás para ganar gratis ¿Cuánto mercancía.