La respuesta a una pregunta espinosa podría desbloquear la seguridad de Internet

¿Es más fácil comprobar que la solución a un problema es correcta que resolverlo?

La pregunta, conocida como el problema «NP versus P», es el problema fundamental más profundo de la informática y la criptografía, y se encuentra en el centro de si los datos de Internet pueden ser realmente privados.

En el improbable caso de que P = NP, todos los esquemas de cifrado y métodos para mantener la privacidad de nuestros datos en Internet serían inseguros. Pero incluso si P no es igual a NP, e incluso si alguien logra probar esto, todavía no sabemos cómo obtener un esquema de cifrado que sea verdaderamente seguro.

Rafael Pass, profesor de informática en Cornell Tech y en el Cornell Ann S. Bowers College of Computing and Information Science, y el coautor Yanyi Liu, estudiante de doctorado en el campo de la informática, han ofrecido una solución.

Su trabajo se detalla en «Sobre la posibilidad de basar la criptografía en EXP ≠ BPP», que ganó el premio al mejor artículo en CRYPTO ’21 y se presentará en la conferencia el 17 de agosto.

La pregunta planteada en el título del artículo trata sobre la idea de la aleatoriedad, una cuestión espinosa de las ciencias de la computación y las matemáticas. El problema EXP versus BPP, aunque no es tan famoso como «NP versus P», es otro problema abierto de larga data y causa aún más vergüenza en el campo, según Pass.

«La pregunta esencialmente es, ¿puede la aleatoriedad acelerar exponencialmente los cálculos?» Pass dijo. «Eso claramente se cree que es imposible. No pensaríamos que lanzar algunas monedas al azar nos permitirá acelerar nuestros cálculos de manera exponencial. Eso sería un poco loco, pero la gente aún no ha podido probarlo».

Si los cálculos pueden acelerarse exponencialmente utilizando la aleatoriedad, entonces todos los esquemas de cifrado pueden romperse. Los llamados ataques de «fuerza bruta», en los que se enumeran todas las claves posibles, ahora podrían implementarse de manera eficiente.

Pass y Liu abordan la cuestión de si simplemente asumir que EXP no es igual a BPP —que los cálculos no pueden acelerarse exponencialmente usando la aleatoriedad— es suficiente para obtener esquemas de cifrado irrompibles. Con este fin, Pass y Liu revisan una conexión entre los esquemas de cifrado y la complejidad de Kolmogorov limitada en el tiempo que establecieron el año pasado.

La complejidad de Kolmogorov limitada en el tiempo de una cadena (x) es la longitud del programa más corto que puede generar x en un período de tiempo determinado. Pero el nuevo trabajo considera una noción diferente de la complejidad de Kolmogorov: calcular la «Complejidad de Levin-Kolmogorov» de una cadena (x). El problema: Dado x, encuentre el programa «más eficiente» que imprima x, donde «eficiencia» es la suma de la longitud del programa y el logaritmo del tiempo de ejecución del programa.

Su artículo muestra que los cifrados irrompibles son posibles si y solo si no existe un algoritmo eficiente que pueda calcular la complejidad de Levin-Kolmogorov para la mayoría de las cadenas, sin cometer demasiados errores.

«Entonces, para obtener un cifrado irrompible», dijo Pass, «solo tenemos que demostrar que ningún algoritmo eficiente puede resolver este problema en particular».

Si bien no pueden probar que no exista tal algoritmo, muestran que, asumiendo que EXP no es igual a BPP, no existe un algoritmo eficiente «sin errores» (un algoritmo que produce la respuesta correcta o dice «Yo no saber «) para determinar la complejidad de Levin-Kolmogorov de una gran fracción de cadenas aleatorias.

«No tiene que resolverlo para todos los hilos, a veces puede ceder», dijo Pass. «Pero cuando da una respuesta, siempre debe ser la correcta».

En otras palabras, los algoritmos que pueden errar funcionan muy bien en las pruebas en las que se le recompensa en función de la cantidad de preguntas que acierte, mientras que los algoritmos sin errores también funcionan bien en las pruebas en las que se le penaliza por las preguntas que se equivocan.

Sus resultados concluyen que el problema de la complejidad de Levin-Kolmogorov es fundamental para comprender tanto el problema EXP frente al BPP como el problema de si existen esquemas de cifrado irrompibles.

«Este problema es la clave para algunas de las preguntas más importantes de la informática», dijo Pass. «Este problema específico es fundamental y realmente necesitamos comprender la brecha entre los algoritmos sin errores y los algoritmos que pueden fallar».

Los autores muestran que si se puede cerrar la brecha, un gigantesco «si» en la ciencia de la computación, entonces no solo ha demostrado que existe una criptografía inquebrantable si EXP no es igual a BPP, sino que de hecho también ha demostrado que NP no es igual a pag.