Polinomios contra ordenadores cuánticos

Gobiernos y multinacionales están invirtiendo grandes cantidades de dinero en la construcción del ordenador cuántico; a día de hoy IBM y Google son los más avanzados en esta dirección. Estos ordenadores podrán realizar simulación cuántica para modelar complejas reacciones químicas, o diseñar nuevos medicamentos, operaciones que están fuera del alcance de los más potentes ordenadores binarios. Pero este avance también tiene sus inconvenientes, por ejemplo, dejarán de ser seguros los sistemas criptográficos empleados hoy en día para garantizar el comercio electrónico y las comunicaciones en la red, ya que un ordenador cuántico podrá factorizar rápidamente los grandes números en los que se basa la seguridad de algoritmos de cifrado de clave pública o firma digital más empleados, como el RSA y DSA, empleando el algoritmo de Shor.

Frente a esta situación, en 2015 la Agencia Nacional de Seguridad (NSA) de EE UU anunció que los estándares actuales de criptografía de clave pública no son seguros a largo plazo y pidió que se iniciara cuanto antes la búsqueda de algoritmos de cifrado de clave pública seguros contra ordenadores cuánticos, también llamados postcuánticos. Motivado por este anuncio, el Instituto Nacional de Estándares y Tecnología (NIST) de EE UU lanzó en 2016 un concurso público para identificar, elegir y estandarizar algoritmos postcuánticos. Se buscaban sistemas de dos tipos: de cifrado e intercambio de claves, y de firma digital. Se han presentado 83 propuestas de 17 países, de los cuáles 56 mantienen su resistencia a los ataque con ordenadores clásicos y a los algoritmos cuánticos conocidos por el momento.

Todos los sistemas multivariables propuestos al NIST utilizan polinomios cuadráticos (de grado dos) en un numero alto N de variables (por ejemplo N=512) salvo el sistema llamado DME que hemos desarrollado y patentado en la Universidad Complutense y el ICMAT, que usa polinomios en seis variables de grado muy alto (hasta 2^48) sobre cuerpos finitos. Este sistema, implementado en colaboración con la Universidad de Zaragoza, es muy rápido (al igual que los sistemas cuadráticos) y tiene la ventaja sobre estos que las claves son mucho más pequeñas. De momento se cree que estos sistemas son seguros contra ordenadores cuánticos y ahora se evalúa su resistencia a ataques con ordenadores “clásicos”. Por ahora el DME se mantiene en el concurso, como candidato a ser uno de los varios “ganadores” esperados del mismo (al menos, habrá uno por cada tecnología en concurso). Según los planes del NIST, el proceso de estandarización se completará a partir de 2025 y se comenzará una migración a los nuevos sistemas criptográficos, preparados para la revolución cuántica. Aunque no se sabe cuándo llegarán los ordenadores cuánticos, todos los datos confidenciales y el tráfico de Internet deberían de estar protegidos a partir de esa fecha, preparados para resistir al futuro cuántico.