El futuro de la criptografía de clave pública en la era de la computación cuántica

(Para Mario Raso)
27/07/20

En los últimos años, el mundo académico, industrial y gubernamental ha invertido energías y recursos en el campo de la computación cuántica, en computadoras que explotan los fenómenos de la mecánica cuántica para resolver problemas matemáticos difíciles o poco prácticos para las computadoras convencionales.

Si alguna vez comienza la producción a gran escala de computadoras cuánticas, podrán destruir muchos de los sistemas de criptografía de clave pública (o asimétricos) actualmente en uso. Esto comprometería seriamente la confidencialidad e integridad de las comunicaciones digitales en Internet y en otros lugares.

En este contexto, el objetivo de la criptografía post-cuántico (o seguro cuántico) es desarrollar cifras seguras, tanto de los ataques de criptoanálisis realizados con computadoras cuánticas como de los clásicos, y que pueden interactuar al mismo tiempo con los protocolos y redes de comunicación existentes.

Si bien la criptografía de clave pública y de doble clave para descifrado / descifrado podría estar en grave peligro por el advenimiento de las computadoras cuánticas, la criptografía simétrica (o privada) y las funciones hash se basan en algoritmos cuánticos. Entre estos, la mayor amenaza para los cifrados simétricos está representada porAlgoritmo de Grover (concebido por Lov Grover en 1996 en i Bell Labs1) Este algoritmo que se ejecuta en una computadora cuántica le permite buscar un elemento dentro de una lista desordenada de longitud N, en un tiempo proporcional a la raíz cuadrada de N. Por el contrario, en una computadora clásica el tiempo sería proporcional a N Esto significa que para obtener el mismo nivel de seguridad, la longitud de la clave debe duplicarse.

Entre los algoritmos de clave simétrica, elAdvanced Encryption Standard (AES), el Blowfish, la Twofish o Serpiente, con una longitud de clave mayor o igual a 256 bits y en condiciones adecuadas, pueden demostrar su valía seguro cuántico.

Sin embargo, en el frente de la criptografía asimétrica, la perspectiva es menos tranquilizadora. Los criptosistemas de clave pública se utilizan principalmente para realizar dos tareas fundamentales, el intercambio seguro de claves, para su posterior uso con cifrados simétricos, y la firma digital.

Los cifrados de clave pública más conocidos y actualmente en uso incluyen:

  • RSA, basado en el problema de factorización de números enteros;
  • criptografía de curva elíptica, que basa su seguridad en la dificultad de realizar ciertas operaciones en los puntos de este tipo de curva;
  • Diffie-Hellman, se centró en la dificultad de calcular el logaritmo discreto en algunos grupos cíclicos.

Para cada uno de ellos es posible realizar fácilmente un ataque de criptoanálisis, descifrando la información sin usar la clave, mediante elAlgoritmo de Shor (concebido por Peter Shor en 19942) ejecutándose en una computadora cuántica. La razón por la cual el algoritmo de Shor es capaz de "romper" los sistemas criptográficos de clave pública es la consecuencia del hecho de que se basan en problemas con la complejidad computacional no polinómica, que una computadora cuántica puede resolver en un tiempo polinómico. Específicamente, dado un número entero N, el algoritmo Shor lo factoriza en un tiempo polinómico en registro (N), mientras que en una computadora clásica el tiempo es exponencial en N.

Motivado por estas consideraciones, el estadounidense Instituto Nacional de Estándares y Tecnología (NIST) ha emprendido la selección de algoritmos criptográficos de clave pública seguro cuántico Al final de una llamada pública, anunciada durante la conferencia PQCrypto 2016 y lanzada en diciembre del mismo año.
La invitación reunió 82 algoritmos candidatos que, a través de procesos de revisión por pares y rondas de selección, redujeron el campo para llegar al final, presumiblemente para 2024, con el lanzamiento de un estándar.

Los nuevos cifrados serán adoptados por los Estados Unidos en analogía con iniciativas anteriores para la introducción de Estándar de cifrado de datos (DES) y AES.

Entre clases de algoritmos post-cuántico Los algoritmos basados ​​en la "criptografía basada en código" que, introducida en 1978 por el estadounidense Robert McEliece, están demostrando ser los más prometedores.3 para la criptografía de clave pública, no tuvieron mucha suerte debido al tamaño excesivo de la clave. Los mismos, hoy en día, tienen variantes capaces de ofrecer tamaños de clave significativamente reducidos y competitivos. Estos algoritmos se basan en la dificultad de buscar dentro de un gran conjunto de números desordenados. También se ha demostrado teóricamente que pertenecen a la clase de los llamados problemas NP (polinomio no determinista) que podrían resistir el cálculo cuántico.

Una segunda clase, Criptografía multivariante4, se basa en la dificultad de resolver sistemas de ecuaciones algebraicas cuadráticas en muchas variables (NP-dureza).

Una tercera clase es la que se basa en el concepto algebraico de "celosía" (Criptografía basada en látex), incluidas las variantes basadas en el problema del "aprendizaje con errores", que consiste en la reconstrucción de una función a partir de algunas de sus evaluaciones inexactas5. Esta formulación permitió definir algunos algoritmos innovadores para la criptografía asimétrica, acompañados de severas demostraciones de seguridad.

La implementación de nuevos cifrados de clave pública seguro cuántico hoy representa un esfuerzo inevitable. La omnipresencia del uso de los algoritmos de clave pública actuales afecta la vida cotidiana de todos, desde la navegación segura por Internet hasta los sistemas de seguridad bancaria, desde las firmas digitales hasta las criptomonedas.

Una carrera contra el tiempo para algunos, mientras que para otros todavía tomará tiempo para que la potencia computacional de una computadora cuántica alcance el nivel necesario para que los estándares actuales sean obsoletos.

Mientras tanto, en el sector privado, gigantes como Google e IBM realizan experimentos destinados a adquirir la llamada "supremacía cuántica", desafiándose mutuamente en el logro de nuevos y cada vez más ambiciosos registros computacionales. Además, con el mismo propósito, en el ámbito internacional, las superpotencias como los Estados Unidos y China, así como la Unión Europea, están haciendo inversiones cada vez mayores para el desarrollo de planes de investigación en el campo de computación cuántica. China, por ejemplo, anunció recientemente su intención de construir un laboratorio nacional de ciencias de la información cuántica en Hefei para 2020, al que se asignará un presupuesto multianual de diez mil millones de dólares.6.

Al mismo tiempo, en el contexto europeo, la nueva presidenta de la Comisión Europea, Ursula von der Leyen, se ha pronunciado sobre el tema afirmando que el computación cuántica Es una de las prioridades de la Unión y expresar la voluntad de apoyar las iniciativas de desarrollo en este ámbito, además de poner los recursos informáticos europeos a disposición de la academia y la investigación, a través del nube. Con este fin, la Unión ha puesto a disposición mil millones de dólares para ser utilizados en los próximos diez años.7, para el desarrollo de ciertos proyectos ya identificados.

En este contexto, la razón detrás de la espasmódica "raza" de actores estatales y privados, dirigida a lograr la supremacía antes mencionada en el campo de computación cuántica, se encuentra en las palabras que Mike McCaul8, Político norteamericano y miembro del American Enterprise Institute, pronunciado en 2018 sobre la competencia en el campo de computación cuántica de los Estados Unidos con oponentes globales como China, Rusia, Corea del Norte e Irán: "Creo que cualquier superpotencia que alcance este hito antes que las demás tendría la primera bomba nuclear digital".

1 Grover, "Un algoritmo mecánico cuántico rápido para la búsqueda en bases de datos", Actas, 28º Simposio anual de ACM sobre la teoría de la informática, p. 212, 1996.

2 Shor, "Algoritmos para la computación cuántica: registro discreto y factorización", en Actas del 35º Simposio anual sobre los fundamentos de la informática, Santa Fe, IEEE Computer Society Press, pp. 124-134, 1994.

3 McEliece, "Sistema de clave pública basado en la teoría de codificación algebraica", DSN Progress Report 44, pp. 114-116, 1978.

4 Matsumoto, Imai, "Una clase de criptosistemas asimétricos basados ​​en polinomios sobre anillos finitos", IEEE International Symposium on InformationTheory, Abstract of Papers, pp. 131-132, 1983.

5 Goldreich, Goldwasser, Halevi, "Criptosistema de clave pública del problema de reducciones de red", en Proc. Of Crypto '97, volumen 1294 de LNCS pp. 112-131, IACR, Springer-Verlag, 1997.

6https://itbrief.com.au/story/apac-jumps-on-quantum-computing-bandwagon

7https://www.ilsole24ore.com/art/la-cina-l-occidente-e-sfida-globale-big-...

8https://fedmanager.com/news/congressman-quantum-computing-equivalent-to-...

Foto: IBM