¿Existe un código irrompible?
La pregunta ha sido fundamental para la criptografía durante miles de años y se encuentra en el centro de los esfuerzos para proteger la información privada en Internet. En un nuevo artículo, los investigadores de Cornell Tech identificaron un problema que contiene la clave para determinar si todo el cifrado puede serroto, así como una conexión sorprendente con un concepto matemático que tiene como objetivo definir y medir la aleatoriedad.
"Nuestro resultado no solo muestra que la criptografía tiene un problema 'madre' natural, sino que también muestra una conexión profunda entre dos áreas bastante separadas de las matemáticas y la informática: la criptografía y la teoría de la información algorítmica", dijo Rafael Pass, profesor de informática.ciencia en Cornell Tech.
Pass es coautor de "On One-Way Functions and Kolmogorov Complexity", que se presentará en el Simposio IEEE sobre Fundamentos de la informática, que se celebrará del 16 al 19 de noviembre en Durham, Carolina del Norte.
"El resultado", dijo, "es que un problema computacional natural introducido en la década de 1960 en la Unión Soviética caracteriza la viabilidad de la criptografía básica: cifrado de clave privada, firmas digitales y autenticación, por ejemplo".
Durante milenios, la criptografía se consideró un ciclo: alguien inventó un código, el código fue efectivo hasta que alguien finalmente lo rompió y el código se volvió ineficaz. En la década de 1970, los investigadores que buscaban una mejor teoría de la criptografía introdujeron el concepto de uno-función de manera: una tarea o problema fácil en una dirección que es imposible en la otra.
Por ejemplo, es fácil encender una cerilla, pero es imposible devolver una cerilla encendida a su estado apagado sin reorganizar sus átomos, una tarea inmensamente difícil.
"La idea era, si tenemos una función unidireccional, tal vez sea un buen punto de partida para comprender la criptografía", dijo Pass. "Encriptar el mensaje es muy fácil. Y si tienes la clave, también puedesdescifrarla. Pero alguien que no conozca la clave debería tener que hacer lo mismo que restaurar una cerilla encendida ".
Pero los investigadores no han podido probar la existencia de una función unidireccional. El candidato más conocido, que también es la base de los esquemas de cifrado más utilizados en Internet, se basa en la factorización de enteros.fácil de multiplicar dos números primos aleatorios, por ejemplo, 23 y 47, pero significativamente más difícil de encontrar esos dos factores si solo se le da su producto, 1,081.
Se cree que no existe un algoritmo de factorización eficiente para grandes números, dijo Pass, aunque es posible que los investigadores aún no hayan encontrado los algoritmos correctos.
"La pregunta central que estamos abordando es: ¿Existe? ¿Existe algún problema natural que caracterice la existencia de funciones unidireccionales?", Dijo. "Si es así, esa es la madre de todos los problemas, y siSi tiene una forma de resolver ese problema, puede romper todas las funciones unidireccionales supuestas. Y si no sabe cómo resolver ese problema, puede obtener una criptografía segura ".
Mientras tanto, los matemáticos de la década de 1960 identificaron lo que se conoce como Complejidad de Kolmogorov, que se refiere a cuantificar la cantidad de aleatoriedad o patrón de una cadena de números. La Complejidad de Kolmogorov de una cadena de números se define como la longitud del programa informático más corto quepuede generar la cadena; para algunas cadenas, como 121212121212121212121212121212, hay un programa corto que la genera: 1 y 2 alternativos. Pero para cadenas de números más complicadas y aparentemente aleatorias, como 37539017332840393452954329, es posible que no exista un programa quees más corta que la longitud de la propia cuerda.
El problema ha interesado durante mucho tiempo a los matemáticos e informáticos, incluido Juris Hartmanis, profesor emérito de informática e ingeniería. Debido a que el programa informático que intenta generar el número podría tardar millones o incluso miles de millones de años, los investigadores de la Unión Soviética en la década de 1960, así como Hartmanis y otros en la década de 1980, desarrollaron la Complejidad de Kolmogorov limitada en el tiempo: la longitud del programa más corto que puede generar una cadena de números en un cierto período de tiempo.
En el artículo, Pass y la estudiante de doctorado Yanyi Liu demostraron que si calcular la complejidad de Kolmogorov limitada en el tiempo es difícil, entonces existen funciones unidireccionales.
Aunque su hallazgo es teórico, tiene implicaciones potenciales en la criptografía, incluida la seguridad de Internet.
"Si puede idear un algoritmo para resolver el problema de complejidad de Kolmogorov limitado en el tiempo, entonces puede romper todas las criptomonedas, todos los esquemas de cifrado, todas las firmas digitales", dijo Pass. "Sin embargo, si no existe un algoritmo eficiente para resolvereste problema, puede obtener una función unidireccional y, por lo tanto, puede obtener cifrado seguro y firmas digitales, etc. "
La investigación fue financiada en parte por la National Science Foundation y la Oficina de Investigación Científica de la Fuerza Aérea, y se basó en una investigación financiada por la Actividad de Proyectos de Investigación Avanzada de Inteligencia en la Oficina del Director de Inteligencia Nacional.
Fuente de la historia :
Materiales proporcionado por Universidad de Cornell . Original escrito por Melanie Lefkowitz. Nota: el contenido se puede editar por estilo y longitud.
cite esta página :