Pese a que apenas haya encontrado menciones en la red, en estos días se está celebrando uno de los eventos informáticos más importantes de los últimos 30 años.
¿La razón? László Babai (Universidad de Chicago), uno de los profesores más reputados del mundo en cuanto a informática teórica se refiere, está dando en estos días una serie de conferencias (EN) (por aquí la grabación de la primera (EN)) en las que asegura poder demostrar una manera más sencilla de solucionar informáticamente el isomorfismo de grafos, uno de los problemas más complejos de afrontar por una máquina.
Y esto, como veremos, podría llegar a poner en jaque la seguridad y privacidad de buena parte de la información que circula por el mundo virtual.
¿Que cómo es posible esto?
Sobre la informática teórica y la “solución” al problema de los isomorfismos de grafos
He tenido que echar la vista atrás para acordarme de aquellas clases de Álgebra Lineal y Geométrico, de Programación Analítica, que en su día cursé en la Ingeniería Superior de Telecomunicaciones.
El isomorfismo de grafos (ES) es un problema que se suele exponer como ejemplo de tipo “extremadamente difícil”, en tanto en cuanto, conforme más elementos tiene un grafo, su dificultad se multiplica exponencialmente.
En la imagen superior podemos ver dos grafos que a priori son distintos. Aplicando alguna metodología de solución del isomorfismo de grafos (la más sencilla y lenta sería asegurarnos si cada elemento del grafo está unido con los mismos elementos que en el otro grafo), vemos que en los dos casos, se cumple que:
- A está unido a B, E y C.
- B está unido a A y D.
- C está unido a D, E y A.
- D está unido a B, E y C.
- E está unido a A, C y D.
Claro que este grafo tiene 5 elementos. Si en vez de 5, tuviera 5 millones (como puede tener tranquilamente una base de datos relacional), la cosa se complica bastante más :).
Pertenecería por tanto a un grupo de problemáticas consideradas NP (ES), que quiere decir que su solución informática escala exponencialmente, con un gasto energético (de recursos) cada vez mayor hasta que acaba por volverse físicamente irresoluble, y que habitualmente, una vez conocida la solución, resulta muy sencillo demostrarla.
Por ejemplo, resolver un puzzle de millones de piezas es un problema de tipo NP, ya que resulta muy complicado saber dónde tiene que ir cada pieza, pero una vez el puzzle está completo, es muy sencillo demostrar que una pieza específica tiene que ocupar ese espacio específico y no otro.
Si al final este nuevo algoritmo de László Babai (que por cierto, destronaría al anterior, publicado en 1983 por el mismo profesor) demuestra ser correcto, el problema pasaría de extremadamente difícil a un nivel por debajo, volviéndose un problema de tipo P (ES), y por tanto, resoluble en cualquier supuesto con los recursos informáticos necesarios.
De hecho, algunos expertos, como el profesor Scott Aaronson, comentaron públicamente que de demostrarse, podría ser “el resultado de la década en la informática teórica”.
Una solución más eficiente a algunas de las problemáticas más habituales que nos encontramos en el mundo digital, como es la gestión de redes de información, la optimización de elementos y/o la identificación y organización de patrones en consultas informáticas.
Y ¿en qué afecta esto a la seguridad de nuestros datos?
La mayoría de cifrados que se utilizan en las comunicaciones informáticas dependen de la factorización (la descomposición de un número en todos sus factores), otro problema cuya mejor implementación se considera NP, semejante al del isomorfismo de grafos.
Precisamente el éxito de este tipo de cifrados radica en la dificultad (extremadamente difícil) de que un tercero pueda resolver la factorización que da sentido al cifrado, para con ella descifrar la información.
Algunas de las características del isomorfismo de grafos son compartidas por este otro problema, por lo que si al final resulta que Babai ha conseguido reducir la dificultad de su algoritmo, abriría un nuevo campo de estudio para simplificar el problema de la factorización.
Y gracias a ello, todos los cifrados basados en factorización serían de la noche a la mañana más sencillos de descifrar.
De hecho, este tenso equilibrio (por un lado, nos interesa volver P todos los problemas NP, para poder resolver problemáticas prácticas en la informática, y por otro, nos interesa que algunos problemas NP sigan siendo NP para mantener la robustez de los algoritmos de cifrado) es el que evita que una agencia de inteligencia (un gobierno, un grupo ciberterrorista,…) les salga más rentable explotar el cifrado por fuerza bruta (puro músculo computacional) que por exploits, 0 days o simples campañas de ingeniería social.
Y aunque al final ese nuevo algoritmo siga siendo NP, si con ello se ha rebajado sustancialmente el gasto en recursos necesario para descifrarlo, estaríamos ante un escenario sustancialmente menos seguro.
De ahí la importancia de la informática teórica, que generalmente nos suena a años luz de los problemas “reales” a los que nos enfrentamos.
Con tan solo un éxito en este campo, se podría poner en jaque todo el paradigma computacional y comunicativo que hemos estado tejiendo durante las últimas décadas. Absolutamente todo cifrado basado en la factorización, que no es poco.
Así que, recemos porque Babai no tenga éxito. O porque lo tenga, y esto nos permita disfrutar de sistemas más eficientes (por ejemplo, podría ser aplicado para hallar la manera más óptima de conectar los transistores en una placa de silicio, o realizar búsquedas en menor tiempo), forzando a la industria a encontrar nuevos cifrados cuya base teórica dependa de algoritmos menos eficientes.
