\n<\/p>\n
Este es un trabajo para LLL: dale a \u00e9l (o a sus hermanos) una base de una red multidimensional y escupir\u00e1 una mejor. Este proceso se conoce como reducci\u00f3n de base reticular.<\/p>\n
\u00bfQu\u00e9 tiene todo esto que ver con la criptograf\u00eda? Resulta que la tarea de romper un sistema criptogr\u00e1fico 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\u00edas.<\/p>\n
En un sentido te\u00f3rico, el algoritmo LLL original se ejecuta r\u00e1pidamente: el tiempo que lleva ejecutarse no escala exponencialmente con el tama\u00f1o de la entrada, es decir, la dimensi\u00f3n de la red y el tama\u00f1o (en bits) de los n\u00fameros en el vectores de base. Pero s\u00ed aumenta como funci\u00f3n polin\u00f3mica, y \u201csi realmente quieres hacerlo, el tiempo polin\u00f3mico no siempre es tan factible\u201d, dijo L\u00e9o Ducas, cript\u00f3grafo del instituto nacional de investigaci\u00f3n CWI en los Pa\u00edses Bajos.<\/p>\n
En la pr\u00e1ctica, esto significa que el algoritmo LLL original no puede manejar entradas demasiado grandes. \u201cLos matem\u00e1ticos y cript\u00f3grafos quer\u00edan tener la capacidad de hacer m\u00e1s\u201d, 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\u00e1s grandes, logrando a menudo un buen rendimiento. A\u00fan as\u00ed, algunas tareas han permanecido obstinadamente fuera de nuestro alcance.<\/p>\n
El nuevo art\u00edculo, escrito por Ryan y su asesora, Nadia Heninger, combina m\u00faltiples estrategias para mejorar la eficiencia de su algoritmo estilo LLL. Por un lado, la t\u00e9cnica utiliza una estructura recursiva que divide la tarea en partes m\u00e1s peque\u00f1as. Por otro lado, el algoritmo gestiona cuidadosamente la precisi\u00f3n de los n\u00fameros involucrados, encontrando un equilibrio entre velocidad y un resultado correcto. El nuevo trabajo permite a los investigadores reducir las bases de celos\u00edas de miles de dimensiones.<\/p>\n
Trabajos anteriores han seguido un enfoque similar: un art\u00edculo de 2021 tambi\u00e9n combina la recursividad y la gesti\u00f3n de precisi\u00f3n para agilizar el trabajo con redes grandes, pero funcion\u00f3 solo para tipos espec\u00edficos de redes, y no para todas las que son importantes en criptograf\u00eda. El nuevo algoritmo se comporta bien en un rango mucho m\u00e1s amplio. \u00abEstoy muy feliz de que alguien lo haya hecho\u00bb, dijo Thomas Espitau, investigador de criptograf\u00eda de la empresa PQShield y autor de la versi\u00f3n 2021. El trabajo de su equipo ofreci\u00f3 una \u201cprueba de concepto\u201d, dijo; El nuevo resultado muestra que \u00abse puede realizar una reducci\u00f3n de red muy r\u00e1pida y s\u00f3lida\u00bb.<\/p>\n
La nueva t\u00e9cnica ya ha comenzado a resultar \u00fatil. Aurel Page, matem\u00e1tico del instituto nacional de investigaci\u00f3n franc\u00e9s Inria, dijo que \u00e9l y su equipo han puesto en marcha una adaptaci\u00f3n del algoritmo en algunas tareas computacionales de teor\u00eda de n\u00fameros.<\/p>\n
Los algoritmos de estilo LLL tambi\u00e9n pueden desempe\u00f1ar un papel en la investigaci\u00f3n relacionada con sistemas de criptograf\u00eda basados \u200b\u200ben celos\u00edas dise\u00f1ados para permanecer seguros incluso en un futuro con potentes computadoras cu\u00e1nticas. No representan una amenaza para dichos sistemas, ya que derribarlos requiere encontrar vectores m\u00e1s cortos que los que estos algoritmos pueden lograr. Pero los mejores ataques que los investigadores conocen utilizan un algoritmo de estilo LLL como \u201celemento b\u00e1sico\u201d, dijo Wessel van Woerden, cript\u00f3grafo de la Universidad de Burdeos. En experimentos pr\u00e1cticos para estudiar estos ataques, ese componente b\u00e1sico puede ralentizar todo. Con la nueva herramienta, los investigadores podr\u00e1n ampliar la gama de experimentos que pueden ejecutar con los algoritmos de ataque, ofreciendo una imagen m\u00e1s clara de su rendimiento.<\/p>\n
historia original<\/em> reimpreso con permiso de<\/em> Revista Quanta, una publicaci\u00f3n editorialmente independiente del<\/em> Fundaci\u00f3n Simons<\/em> cuya misi\u00f3n es mejorar la comprensi\u00f3n p\u00fablica de la ciencia cubriendo los desarrollos y tendencias de la investigaci\u00f3n en matem\u00e1ticas y ciencias f\u00edsicas y biol\u00f3gicas.<\/em><\/p>\n<\/div>\n