La criptografía postcuántica ( PQC ), a veces denominada a prueba de cuánticos , segura para cuánticos o resistente a cuánticos , es el desarrollo de algoritmos criptográficos (normalmente algoritmos de clave pública ) que actualmente se consideran seguros contra un ataque criptoanalítico por parte de un ordenador cuántico . La mayoría de los algoritmos de clave pública más utilizados se basan en la dificultad de uno de tres problemas matemáticos: el problema de factorización de números enteros , el problema del logaritmo discreto o el problema del logaritmo discreto de curva elíptica . Todos estos problemas podrían resolverse fácilmente en un ordenador cuántico suficientemente potente que ejecute el algoritmo de Shor [1] [2] o incluso alternativas más rápidas y menos exigentes (en términos de la cantidad de cúbits necesarios). [3]
Si bien, a partir de 2023, las computadoras cuánticas carecen del poder de procesamiento para descifrar algoritmos criptográficos ampliamente utilizados, [4] los criptógrafos están diseñando nuevos algoritmos para prepararse para Y2Q o Q-Day , el día en que los algoritmos actuales serán vulnerables a los ataques de computación cuántica. Su trabajo ha ganado la atención de académicos e industria a través de la serie de conferencias PQCrypto organizada desde 2006, varios talleres sobre criptografía cuántica segura organizados por el Instituto Europeo de Normas de Telecomunicaciones (ETSI) y el Instituto de Computación Cuántica . [5] [6] [7] La existencia rumoreada de programas generalizados de recolección ahora y descifrado más tarde también se ha visto como una motivación para la introducción temprana de algoritmos poscuánticos, ya que los datos registrados ahora pueden seguir siendo sensibles muchos años en el futuro. [8] [9] [10]
A diferencia de la amenaza que la computación cuántica representa para los algoritmos de clave pública actuales, la mayoría de los algoritmos criptográficos simétricos y las funciones hash actuales se consideran relativamente seguros contra los ataques de las computadoras cuánticas. [2] [11] Si bien el algoritmo cuántico de Grover acelera los ataques contra cifrados simétricos, duplicar el tamaño de la clave puede bloquearlos de manera efectiva. [12] Por lo tanto, la criptografía simétrica poscuántica no necesita diferir significativamente de la criptografía simétrica actual.
El 13 de agosto de 2024, el Instituto Nacional de Estándares y Tecnología de EE. UU. (NIST) publicó las versiones finales de sus primeros tres estándares de criptografía postcuántica. [13]
La investigación en criptografía post-cuántica se centra principalmente en seis enfoques diferentes: [2] [6]
Este enfoque incluye sistemas criptográficos como el aprendizaje con errores , el aprendizaje en anillo con errores ( ring-LWE ), [14] [15] [16] el intercambio de claves de aprendizaje en anillo con errores y la firma de aprendizaje en anillo con errores , los esquemas de cifrado más antiguos NTRU o GGH , y las firmas NTRU y BLISS más nuevas . [17] Algunos de estos esquemas, como el cifrado NTRU, se han estudiado durante muchos años sin que nadie haya encontrado un ataque factible. Otros, como los algoritmos ring-LWE, tienen pruebas de que su seguridad se reduce a un problema del peor de los casos. [18] El Grupo de Estudio de Criptografía Post Cuántica patrocinado por la Comisión Europea sugirió que se estudiara la variante Stehle–Steinfeld de NTRU para su estandarización en lugar del algoritmo NTRU. [19] [20] En ese momento, NTRU todavía estaba patentado. Los estudios han indicado que NTRU puede tener propiedades más seguras que otros algoritmos basados en celosía. [21]
Esto incluye sistemas criptográficos como el esquema Rainbow ( Unbalanced Oil and Vinegar ), que se basa en la dificultad de resolver sistemas de ecuaciones multivariadas. Varios intentos de construir esquemas de cifrado de ecuaciones multivariadas seguros han fracasado. Sin embargo, los esquemas de firma multivariada como Rainbow podrían proporcionar la base para una firma digital segura cuántica. [22] El esquema de firma Rainbow está patentado.
Esto incluye sistemas criptográficos como las firmas de Lamport , el esquema de firmas de Merkle , el XMSS, [23] el SPHINCS, [24] y los esquemas WOTS. Las firmas digitales basadas en hash fueron inventadas a fines de la década de 1970 por Ralph Merkle y se han estudiado desde entonces como una alternativa interesante a las firmas digitales basadas en la teoría de números como RSA y DSA. Su principal inconveniente es que para cualquier clave pública basada en hash, existe un límite en el número de firmas que se pueden firmar utilizando el conjunto correspondiente de claves privadas. Este hecho redujo el interés en estas firmas hasta que el interés se reavivó debido al deseo de criptografía que fuera resistente al ataque de las computadoras cuánticas. Parece que no hay patentes sobre el esquema de firmas de Merkle [ cita requerida ] y existen muchas funciones hash no patentadas que podrían usarse con estos esquemas. El esquema de firma basado en hash con estado XMSS desarrollado por un equipo de investigadores bajo la dirección de Johannes Buchmann se describe en RFC 8391. [25]
Tenga en cuenta que todos los esquemas anteriores son firmas de un solo uso o de tiempo limitado; Moni Naor y Moti Yung inventaron el hash UOWHF en 1989 y diseñaron una firma basada en hash (el esquema Naor-Yung) [26] que puede usarse por tiempo ilimitado (la primera firma de este tipo que no requiere propiedades de trampilla).
Esto incluye sistemas criptográficos que se basan en códigos de corrección de errores , como los algoritmos de cifrado McEliece y Niederreiter y el esquema de firma relacionado Courtois, Finiasz y Sendrier . La firma original de McEliece que utiliza códigos aleatorios Goppa ha resistido el escrutinio durante más de 40 años. Sin embargo, muchas variantes del esquema McEliece, que buscan introducir más estructura en el código utilizado para reducir el tamaño de las claves, han demostrado ser inseguras. [27] El Grupo de Estudio de Criptografía Post Cuántica patrocinado por la Comisión Europea ha recomendado el sistema de cifrado de clave pública McEliece como candidato para la protección a largo plazo contra ataques de computadoras cuánticas. [19]
Estos sistemas criptográficos se basan en las propiedades de los grafos de isogenia de curvas elípticas (y variedades abelianas de dimensión superior ) sobre campos finitos, en particular grafos de isogenia supersingulares , para crear sistemas criptográficos. Entre los representantes más conocidos de este campo se encuentran el intercambio de claves tipo Diffie-Hellman CSIDH , que puede servir como un reemplazo sencillo y resistente a los cuánticos para los métodos de intercambio de claves Diffie-Hellman y Diffie-Hellman de curva elíptica que se utilizan ampliamente en la actualidad, [28] y el esquema de firma SQISign que se basa en la equivalencia categórica entre curvas elípticas supersingulares y órdenes máximos en tipos particulares de álgebras de cuaterniones. [29] Otra construcción ampliamente notada, SIDH/SIKE , fue espectacularmente descifrada en 2022. [30] Sin embargo, el ataque es específico de la familia de esquemas SIDH/SIKE y no se generaliza a otras construcciones basadas en isogenia. [31]
Si se utilizan tamaños de clave suficientemente grandes, los sistemas criptográficos de clave simétrica como AES y SNOW 3G ya son resistentes a los ataques de un ordenador cuántico. [32] Además, los sistemas y protocolos de gestión de claves que utilizan criptografía de clave simétrica en lugar de criptografía de clave pública, como Kerberos y la Estructura de Autenticación de Redes Móviles 3GPP , también son inherentemente seguros contra los ataques de un ordenador cuántico. Dado que ya se ha extendido su uso en el mundo, algunos investigadores recomiendan el uso ampliado de la gestión de claves simétricas similar a Kerberos como una forma eficiente de lograr la criptografía postcuántica en la actualidad. [33]
En la investigación criptográfica, es deseable demostrar la equivalencia de un algoritmo criptográfico y un problema matemático complejo conocido. Estas pruebas se denominan a menudo "reducciones de seguridad" y se utilizan para demostrar la dificultad de descifrar el algoritmo de cifrado. En otras palabras, la seguridad de un algoritmo criptográfico determinado se reduce a la seguridad de un problema complejo conocido. Los investigadores están buscando activamente reducciones de seguridad en las perspectivas de la criptografía postcuántica. Los resultados actuales se muestran a continuación:
En algunas versiones de Ring-LWE hay una reducción de seguridad al problema del vector más corto (SVP) en una red como límite inferior de la seguridad. Se sabe que el SVP es NP-duro . [34] Los sistemas ring-LWE específicos que tienen reducciones de seguridad demostrables incluyen una variante de las firmas ring-LWE de Lyubashevsky definidas en un artículo de Güneysu, Lyubashevsky y Pöppelmann. [15] El esquema de firma GLYPH es una variante de la firma Güneysu, Lyubashevsky y Pöppelmann (GLP) que tiene en cuenta los resultados de investigación que han surgido después de la publicación de la firma GLP en 2012. Otra firma Ring-LWE es Ring-TESLA. [35] También existe una "variante desaleatorizada" de LWE, llamada Learning with Rounding (LWR), que produce "una aceleración mejorada (al eliminar pequeños errores de muestreo de una distribución similar a Gauss con errores deterministas) y ancho de banda". [36] Mientras que LWE utiliza la adición de un pequeño error para ocultar los bits inferiores, LWR utiliza el redondeo para el mismo propósito.
Se cree que la seguridad del esquema de cifrado NTRU y la firma BLISS [17] están relacionadas con el problema del vector más cercano (CVP) en una red, pero no se puede demostrar que se puedan reducir a él. Se sabe que el CVP es NP-hard . El Grupo de Estudio de Criptografía Post Cuántica patrocinado por la Comisión Europea sugirió que se estudie la variante Stehle–Steinfeld de NTRU, que sí tiene una reducción de seguridad, para su uso a largo plazo en lugar del algoritmo NTRU original. [19]
Los esquemas de firma de aceite y vinagre no balanceados son primitivos criptográficos asimétricos basados en polinomios multivariados sobre un campo finito . Bulygin , Petzoldt y Buchmann han demostrado una reducción de sistemas UOV cuadráticos multivariados genéricos al problema de resolución de ecuaciones cuadráticas multivariadas NP-Hard. [37]
En 2005, Luis García demostró que existía una reducción de seguridad de las firmas del árbol hash de Merkle en relación con la seguridad de la función hash subyacente. García demostró en su artículo que si existen funciones hash computacionalmente unidireccionales, entonces la firma del árbol hash de Merkle es demostrablemente segura. [38]
Por lo tanto, si uno utilizara una función hash con una reducción de seguridad demostrable para un problema difícil conocido, tendría una reducción de seguridad demostrable de la firma del árbol de Merkle para ese problema difícil conocido. [39]
El Grupo de Estudio de Criptografía Post Cuántica patrocinado por la Comisión Europea ha recomendado el uso del esquema de firma Merkle para la protección de seguridad a largo plazo contra las computadoras cuánticas. [19]
El sistema de cifrado McEliece tiene una reducción de seguridad para el problema de decodificación del síndrome (SDP). Se sabe que el SDP es NP-hard . [40] El grupo de estudio de criptografía post-cuántica patrocinado por la Comisión Europea ha recomendado el uso de esta criptografía para la protección a largo plazo contra ataques de computadoras cuánticas. [19]
En 2016, Wang propuso un esquema de cifrado de código lineal aleatorio RLCE [41] que se basa en esquemas McEliece. El esquema RLCE se puede construir utilizando cualquier código lineal, como el código Reed-Solomon, insertando columnas aleatorias en la matriz generadora de código lineal subyacente.
La seguridad está relacionada con el problema de construir una isogenia entre dos curvas supersingulares con el mismo número de puntos. La investigación más reciente sobre la dificultad de este problema es la de Delfs y Galbraith, que indica que este problema es tan difícil como sugieren los inventores del intercambio de claves. [42] No existe ninguna reducción de seguridad para un problema NP-hard conocido.
Una característica común de muchos algoritmos de criptografía poscuántica es que requieren tamaños de clave más grandes que los algoritmos de clave pública "precuánticos" comúnmente utilizados. A menudo es necesario hacer concesiones en cuanto al tamaño de la clave, la eficiencia computacional y el tamaño del texto cifrado o la firma. La tabla enumera algunos valores para diferentes esquemas a un nivel de seguridad poscuántico de 128 bits.
Una consideración práctica a la hora de elegir entre algoritmos criptográficos postcuánticos es el esfuerzo que se requiere para enviar claves públicas a través de Internet. Desde este punto de vista, los algoritmos Ring-LWE, NTRU y SIDH proporcionan tamaños de clave convenientemente inferiores a 1 kB, las claves públicas de firma hash tienen un tamaño inferior a 5 kB y McEliece, basado en MDPC, ocupa aproximadamente 1 kB. Por otro lado, los esquemas Rainbow requieren alrededor de 125 kB y McEliece, basado en Goppa, requiere una clave de casi 1 MB.
La idea fundamental de utilizar LWE y Ring LWE para el intercambio de claves fue propuesta y presentada en la Universidad de Cincinnati en 2011 por Jintai Ding. La idea básica proviene de la asociatividad de las multiplicaciones de matrices, y los errores se utilizan para proporcionar seguridad. El artículo [52] apareció en 2012 después de que se presentara una solicitud de patente provisional en 2012.
En 2014, Peikert [53] presentó un esquema de transporte de claves que seguía la misma idea básica de Ding, donde también se utiliza la nueva idea de enviar una señal de 1 bit adicional para el redondeo en la construcción de Ding. Para algo más de 128 bits de seguridad , Singh presenta un conjunto de parámetros que tienen claves públicas de 6956 bits para el esquema de Peikert. [54] La clave privada correspondiente sería de aproximadamente 14.000 bits.
En 2015, en Eurocrypt 2015 se presentó un intercambio de claves autenticadas con seguridad demostrable hacia adelante que seguía la misma idea básica de Ding, [55] que es una extensión de la construcción HMQV [56] en Crypto2005. Los parámetros para diferentes niveles de seguridad de 80 bits a 350 bits, junto con los tamaños de clave correspondientes, se proporcionan en el documento. [55]
Para 128 bits de seguridad en NTRU, Hirschhorn, Hoffstein, Howgrave-Graham y Whyte recomiendan utilizar una clave pública representada como un polinomio de grado 613 con coeficientes . Esto da como resultado una clave pública de 6130 bits. La clave privada correspondiente sería de 6743 bits. [43]
Para lograr 128 bits de seguridad y el tamaño de firma más pequeño en un esquema de firma de ecuación cuadrática multivariada Rainbow, Petzoldt, Bulygin y Buchmann recomiendan usar ecuaciones con un tamaño de clave pública de poco más de 991.000 bits, una clave privada de poco más de 740.000 bits y firmas digitales con una longitud de 424 bits. [44]
Para obtener 128 bits de seguridad para firmas basadas en hash para firmar 1 millón de mensajes utilizando el método del árbol fractal de Merkle de Naor Shenhav y Wool, los tamaños de clave pública y privada tienen una longitud de aproximadamente 36.000 bits. [57]
Para 128 bits de seguridad en un esquema McEliece, el grupo de estudio de criptografía postcuántica de la Comisión Europea recomienda utilizar un código binario Goppa de longitud al menos y dimensión al menos , y capaz de corregir errores. Con estos parámetros la clave pública para el sistema McEliece será una matriz generadora sistemática cuya parte no identidad ocupa bits. La clave privada correspondiente, que consiste en el soporte de código con elementos de y un polinomio generador de con coeficientes de , tendrá una longitud de 92.027 bits [19]
El grupo también está investigando el uso de códigos MDPC cuasicíclicos de longitud al menos y dimensión al menos , y capaces de corregir errores. Con estos parámetros, la clave pública para el sistema McEliece será la primera fila de una matriz generadora sistemática cuya parte no identidad toma bits. La clave privada, una matriz de verificación de paridad cuasicíclica con entradas distintas de cero en una columna (o el doble en una fila), no toma más que bits cuando se representa como las coordenadas de las entradas distintas de cero en la primera fila.
Barreto et al. recomiendan utilizar un código binario Goppa de longitud al menos y dimensión al menos , y capaz de corregir errores. Con estos parámetros la clave pública para el sistema McEliece será una matriz generadora sistemática cuya parte no identidad toma bits. [58] La clave privada correspondiente, que consiste en el soporte del código con elementos de y un polinomio generador de con coeficientes de , tendrá una longitud de 40.476 bits.
Para 128 bits de seguridad en el método de isogenia supersingular Diffie-Hellman (SIDH), De Feo, Jao y Plut recomiendan utilizar una curva supersingular módulo un primo de 768 bits. Si se utiliza la compresión de puntos de curva elíptica, la clave pública no deberá tener más de 8x768 o 6144 bits de longitud. [59] Un artículo de marzo de 2016 de los autores Azarderakhsh, Jao, Kalach, Koziel y Leonardi mostró cómo reducir a la mitad la cantidad de bits transmitidos, lo que fue mejorado aún más por los autores Costello, Jao, Longa, Naehrig, Renes y Urbanik, lo que resultó en una versión de clave comprimida del protocolo SIDH con claves públicas de solo 2640 bits de tamaño. [51] Esto hace que la cantidad de bits transmitidos sea aproximadamente equivalente a la RSA y Diffie-Hellman seguras no cuánticas con el mismo nivel de seguridad clásico. [60]
Como regla general, para 128 bits de seguridad en un sistema basado en claves simétricas, se pueden utilizar con seguridad tamaños de clave de 256 bits. El mejor ataque cuántico contra sistemas arbitrarios de claves simétricas es una aplicación del algoritmo de Grover , que requiere un trabajo proporcional a la raíz cuadrada del tamaño del espacio de claves. Para transmitir una clave cifrada a un dispositivo que posee la clave simétrica necesaria para descifrarla también se requieren aproximadamente 256 bits. Está claro que los sistemas de claves simétricas ofrecen los tamaños de clave más pequeños para la criptografía poscuántica. [ cita requerida ]
Un sistema de clave pública demuestra una propiedad conocida como secreto directo perfecto cuando genera claves públicas aleatorias por sesión para fines de acuerdo de claves. Esto significa que el compromiso de un mensaje no puede llevar al compromiso de otros, y también que no hay un solo valor secreto que pueda llevar al compromiso de múltiples mensajes. Los expertos en seguridad recomiendan usar algoritmos criptográficos que admitan secreto directo en lugar de aquellos que no lo hagan. [61] La razón de esto es que el secreto directo puede proteger contra el compromiso de claves privadas de largo plazo asociadas con pares de claves pública/privada. Esto se considera como un medio para prevenir la vigilancia masiva por parte de agencias de inteligencia.
Tanto el intercambio de claves Ring-LWE como el intercambio de claves Diffie-Hellman (SIDH) de isogenia supersingular pueden admitir el secreto hacia adelante en un intercambio con la otra parte. Tanto Ring-LWE como SIDH también se pueden utilizar sin secreto hacia adelante mediante la creación de una variante de la variante clásica de cifrado ElGamal de Diffie-Hellman.
Los otros algoritmos de este artículo, como NTRU, no admiten el secreto hacia adelante tal como está.
Cualquier sistema de cifrado de clave pública autenticado se puede utilizar para crear un intercambio de claves con secreto hacia adelante. [62]
El proyecto Open Quantum Safe ( OQS ) se inició a fines de 2016 y tiene el objetivo de desarrollar y crear prototipos de criptografía resistente a la cuántica. [63] [64] Su objetivo es integrar los esquemas postcuánticos actuales en una biblioteca: liboqs . [65] liboqs es una biblioteca C de código abierto para algoritmos criptográficos resistentes a la cuántica. Inicialmente se centra en algoritmos de intercambio de claves, pero ahora incluye varios esquemas de firma. Proporciona una API común adecuada para algoritmos de intercambio de claves postcuánticos y recopilará varias implementaciones. liboqs también incluirá un arnés de prueba y rutinas de evaluación comparativa para comparar el rendimiento de las implementaciones postcuánticas. Además, OQS también proporciona la integración de liboqs en OpenSSL . [66]
A partir de marzo de 2023, se admiten los siguientes algoritmos de intercambio de claves: [63]
A partir de agosto de 2024, el NIST ha publicado los 3 algoritmos siguientes como estándares FIPS y se espera que el cuarto esté disponible cerca de fin de año: [67]
Las versiones compatibles más antiguas que se han eliminado debido al avance del Proyecto de estandarización de criptografía post-cuántica del NIST son:
Se considera que uno de los principales desafíos de la criptografía postcuántica es la implementación de algoritmos potencialmente seguros desde el punto de vista cuántico en los sistemas existentes. Existen pruebas realizadas, por ejemplo, por Microsoft Research, que implementa PICNIC en una PKI utilizando módulos de seguridad de hardware . [85] Los proveedores de HSM también han realizado implementaciones de prueba para el algoritmo NewHope de Google . En agosto de 2023, Google lanzó una implementación de clave de seguridad FIDO2 de un esquema de firma híbrido ECC /Dilithium que se realizó en asociación con ETH Zürich . [86]
El protocolo de señal utiliza el Diffie-Hellman extendido postcuántico (PQXDH). [87]
El 21 de febrero de 2024, Apple anunció que iba a actualizar su protocolo iMessage con un nuevo protocolo PQC llamado "PQ3", que utilizará claves continuas. [87] [88] [89] Apple afirmó que, aunque las computadoras cuánticas aún no existen, querían mitigar los riesgos de las computadoras cuánticas futuras, así como los escenarios de ataque denominados " Cosechar ahora, descifrar después ". Apple afirmó que cree que su implementación de PQ3 proporciona protecciones que "superan las de todas las demás aplicaciones de mensajería ampliamente implementadas", porque utiliza claves continuas. Apple tiene la intención de reemplazar completamente el protocolo iMessage existente dentro de todas las conversaciones compatibles con PQ3 para fines de 2024. Apple también definió una escala para facilitar la comparación de las propiedades de seguridad de las aplicaciones de mensajería, con una escala representada por niveles que van de 0 a 3: 0 para ningún extremo a extremo de forma predeterminada, 1 para extremo a extremo precuántico de forma predeterminada, 2 solo para establecimiento de clave PQC (por ejemplo, PQXDH) y 3 para establecimiento de clave PQC y re-clave continua (PQ3). [87]
Otras implementaciones notables incluyen:
Google ha mantenido el uso de "cifrado híbrido" en su uso de criptografía post-cuántica: siempre que se utiliza un esquema post-cuántico relativamente nuevo, se combina con un esquema no PQ más probado. Esto es para asegurar que los datos no se vean comprometidos incluso si el algoritmo PQ relativamente nuevo resulta ser vulnerable a ataques no cuánticos antes del Y2Q. Este tipo de esquema se utiliza en sus pruebas de 2016 y 2019 para TLS post-cuántico, [92] y en su clave FIDO2 de 2023. [86] De hecho, uno de los algoritmos utilizados en la prueba de 2019, SIKE, se rompió en 2022, pero la capa no PQ X25519 (ya utilizada ampliamente en TLS) todavía protegía los datos. [92] El PQ3 de Apple y el PQXDH de Signal también son híbridos. [87]
La NSA y el GCHQ se oponen al cifrado híbrido, alegando que añade complejidad a la implementación y la transición. Daniel J. Bernstein , que respalda el cifrado híbrido, sostiene que estas afirmaciones son falsas. [92]
{{cite web}}
: CS1 maint: bot: estado de URL original desconocido ( enlace ){{cite web}}
: CS1 maint: bot: estado de URL original desconocido ( enlace ){{cite web}}
: CS1 maint: bot: estado de URL original desconocido ( enlace ){{cite web}}
: CS1 maint: bot: estado de URL original desconocido ( enlace ){{cite web}}
: CS1 maint: bot: estado de URL original desconocido ( enlace )Con un cifrado resistente a las vulneraciones y amplias defensas contra ataques cuánticos incluso muy sofisticados, PQ3 es el primer protocolo de mensajería que alcanza lo que llamamos seguridad de nivel 3, lo que proporciona protecciones de protocolo que superan las de todas las demás aplicaciones de mensajería ampliamente implementadas.