La criptografía poscuántica ( PQC ), a veces denominada a prueba de cuántica , segura cuántica o resistente a cuántica , es el desarrollo de algoritmos criptográficos (generalmente algoritmos de clave pública ) que se cree que son seguros contra un ataque criptoanalítico por parte de un computadora cuántica . El problema con los algoritmos populares utilizados actualmente en el mercado es que su seguridad se basa en uno de tres problemas matemáticos difíciles: el problema de factorización de números enteros , el problema de logaritmos discretos o el problema de logaritmos discretos de curva elíptica . Todos estos problemas podrían resolverse fácilmente con una computadora cuántica suficientemente potente que ejecute el algoritmo de Shor [1] [2] o incluso con alternativas más rápidas y menos exigentes (en términos de número de qubits necesarios). [3]
Si bien a partir de 2023 las computadoras cuánticas carecen de la capacidad de procesamiento para descifrar los algoritmos criptográficos ampliamente utilizados, [4] los criptógrafos están diseñando nuevos algoritmos para prepararse para el Q-Day , el día en que los algoritmos actuales serán vulnerables a los ataques de la computación cuántica. Su trabajo ha atraído la atención de los académicos y la industria a través de la serie de conferencias PQCrypto organizadas 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] Los rumores sobre la existencia de programas generalizados de recolección ahora y descifrado posteriores también se han visto como una motivación para la introducción temprana de algoritmos poscuánticos, ya que los datos registrados ahora pueden seguir siendo confidenciales muchos años después. . [8] [9] [10]
En contraste con 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 funciones hash actuales se consideran relativamente seguros contra ataques de 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 bloquear eficazmente estos ataques. [12] Por lo tanto, la criptografía simétrica poscuántica no necesita diferir significativamente de la criptografía simétrica actual.
La investigación sobre criptografía poscuá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 ), [13] [14] [15] el aprendizaje en anillo con intercambio de claves con errores y el aprendizaje en anillo con firma de errores , los más antiguos NTRU o GGH. esquemas de cifrado y las firmas NTRU y BLISS más nuevas . [16] 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 al peor de los casos. [17] 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 estandarización en lugar del algoritmo NTRU. [18] [19] 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ías. [20]
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 crear esquemas seguros de cifrado de ecuaciones multivariadas han fracasado. Sin embargo, los esquemas de firma multivariante como Rainbow podrían proporcionar la base para una firma digital cuántica segura. [21] El esquema Rainbow Signature está patentado.
Esto incluye sistemas criptográficos como las firmas Lamport , el esquema de firma Merkle , el XMSS, [22] el SPHINCS, [23] y los esquemas WOTS. Las firmas digitales basadas en hash fueron inventadas a finales de la década de 1970 por Ralph Merkle y desde entonces se han estudiado 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 la cantidad de firmas que se pueden firmar utilizando el conjunto correspondiente de claves privadas. Este hecho había reducido el interés por estas firmas hasta que el interés se revivió debido al deseo de una criptografía resistente al ataque de los ordenadores cuánticos. Parece que no hay patentes sobre el esquema de firma Merkle [ cita necesaria ] 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. [24]
Tenga en cuenta que todos los esquemas anteriores son firmas de una sola vez 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) [25] que puede ser de tiempo ilimitado en uso (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 relacionado de firmas de Courtois, Finiasz y Sendrier . La firma original de McEliece que utiliza códigos Goppa aleatorios ha resistido el escrutinio durante más de 40 años. Sin embargo, se ha demostrado que muchas variantes del esquema McEliece, que buscan introducir más estructura en el código utilizado para reducir el tamaño de las claves, son inseguras. [26] 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. [18]
Estos sistemas criptográficos se basan en las propiedades de los gráficos de isogenia de curvas elípticas (y variedades abelianas de dimensiones superiores ) sobre campos finitos, en particular los gráficos de isogenia supersingulares , para crear sistemas criptográficos. Entre los representantes más conocidos de este campo se encuentra el CSIDH de intercambio de claves tipo Diffie-Hellman , que puede servir como un reemplazo sencillo y resistente a los cuánticos de los métodos de intercambio de claves Diffie-Hellman y de curva elíptica Diffie-Hellman que están muy extendidos. uso actual, [27] 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. [28] Otra construcción ampliamente notada, SIDH/SIKE , se rompió espectacularmente en 2022. [29] Sin embargo, el ataque es específico de la familia de esquemas SIDH/SIKE y no se generaliza a otras construcciones basadas en isogenia. [30]
Siempre que se utilicen tamaños de clave suficientemente grandes, los sistemas criptográficos de clave simétrica como AES y SNOW 3G ya son resistentes al ataque de una computadora cuántica. [31] 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 red móvil 3GPP también son inherentemente seguros contra ataques de una computadora cuántica. Dado su despliegue generalizado en el mundo, algunos investigadores recomiendan un uso ampliado de la gestión de claves simétricas similar a Kerberos como una forma eficiente de obtener criptografía poscuántica en la actualidad. [32]
En la investigación de criptografía, es deseable demostrar la equivalencia de un algoritmo criptográfico y un problema matemático difícil conocido. Estas pruebas suelen denominarse "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 difícil conocido. Los investigadores buscan activamente reducciones de seguridad en las perspectivas de la criptografía poscuántica. Los resultados actuales se dan aquí:
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 . [33] 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. [14] 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 la investigación que se produjeron después de la publicación de la firma GLP en 2012. Otra firma Ring-LWE es Ring-TESLA. . [34] También existe una "variante desaleatorizada" de LWE, llamada Aprendizaje con redondeo (LWR), que produce "aceleración mejorada (al eliminar pequeños errores de muestreo de una distribución similar a Gauss con errores deterministas) y ancho de banda". [35] 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 [16] está relacionada, pero no es demostrablemente reducible, al problema del vector más cercano (CVP) en una red. Se sabe que el CVP es NP-duro . El Grupo de Estudio de Criptografía Post Cuántica patrocinado por la Comisión Europea sugirió que la variante Stehle-Steinfeld de NTRU, que tiene una reducción de seguridad, se estudie para uso a largo plazo en lugar del algoritmo NTRU original. [18]
Los esquemas de firma desequilibrados de petróleo y vinagre son primitivas criptográficas asimétricas basadas en polinomios multivariados sobre un campo finito . Bulygin, Petzoldt y Buchmann han demostrado una reducción de los sistemas UOV cuadráticos multivariados genéricos al problema de resolución de ecuaciones cuadráticas multivariadas NP-Hard. [36]
En 2005, Luis García demostró que había una reducción de la seguridad de las firmas de Merkle Hash Tree con respecto a 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 Merkle Hash Tree es demostrablemente segura. [37]
Por lo tanto, si se utilizara una función hash con una reducción de seguridad demostrable para un problema difícil conocido, se tendría una reducción de seguridad demostrable de la firma del árbol Merkle para ese problema difícil conocido. [38]
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 computadoras cuánticas. [18]
El sistema de cifrado McEliece tiene una reducción de seguridad para el síndrome de problema de decodificación (SDP). Se sabe que el SDP es NP-duro . [39] 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 una computadora cuántica. [18]
En 2016, Wang propuso un esquema de cifrado de código lineal aleatorio RLCE [40] 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 realizada por Delfs y Galbraith, indica que este problema es tan difícil como sugieren los inventores del intercambio de claves. [41] 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 hay que hacer concesiones en el tamaño de la clave, la eficiencia computacional y el tamaño del texto cifrado o de la firma. La tabla enumera algunos valores para diferentes esquemas en un nivel de seguridad poscuántico de 128 bits.
Una consideración práctica a la hora de elegir entre algoritmos criptográficos poscuánticos es el esfuerzo necesario 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 menos de 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 [51] apareció en 2012 después de que se presentara una solicitud de patente provisional en 2012.
En 2014, Peikert [52] presentó un esquema de transporte clave siguiendo la misma idea básica de Ding, donde también se utiliza la nueva idea de enviar una señal adicional de 1 bit para 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. [53] La clave privada correspondiente sería de aproximadamente 14.000 bits.
En 2015, en Eurocrypt 2015 se presentó un intercambio de claves autenticado con seguridad directa demostrable siguiendo la misma idea básica de Ding, [54] que es una extensión de la construcción HMQV [55] en Crypto2005. Los parámetros para diferentes niveles de seguridad, desde 80 bits hasta 350 bits, junto con los tamaños de clave correspondientes, se proporcionan en el documento. [54]
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. [42]
Para obtener 128 bits de seguridad y el tamaño de firma más pequeño en un esquema de firma de ecuación cuadrática multivariante 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 una clave digital de poco más de 740.000 bits. firmas que tienen 424 bits de longitud. [43]
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 Merkle de Naor Shenhav y Wool, los tamaños de clave pública y privada tienen aproximadamente 36.000 bits de longitud. [56]
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 al menos una longitud y una dimensión de al menos , y capaz de corregir errores. Con estos parámetros la clave pública del sistema McEliece será una matriz generadora sistemática cuya parte no identitaria ocupa bits. La clave privada correspondiente, que consta del soporte de código con elementos de y un polinomio generador de con coeficientes de , tendrá una longitud de 92.027 bits [18]
El grupo también está investigando el uso de códigos MDPC cuasicíclicos de al menos longitud y dimensión de al menos , y capaces de corregir errores. Con estos parámetros la clave pública del sistema McEliece será la primera fila de una matriz generadora sistemática cuya parte no identificativa 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 ocupa más que bits cuando se representa como las coordenadas de las entradas distintas de cero en la primera fila.
Barreto et al. Recomendamos utilizar un código Goppa binario de al menos una longitud y una dimensión de al menos , y capaz de corregir errores. Con estos parámetros la clave pública del sistema McEliece será una matriz generadora sistemática cuya parte no identitaria ocupa bits. [57] La clave privada correspondiente, que consta del soporte de 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 primo de 768 bits. Si se utiliza compresión de puntos de curva elíptica, la clave pública no deberá tener más de 8x768 o 6144 bits de longitud. [58] Un artículo de marzo de 2016 de los autores Azarderakhsh, Jao, Kalach, Koziel y Leonardi mostró cómo reducir a la mitad el número 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. [50] Esto hace que el número de bits transmitidos sea aproximadamente equivalente al RSA seguro no cuántico y Diffie-Hellman con el mismo nivel de seguridad clásico. [59]
Como regla general, para 128 bits de seguridad en un sistema basado en claves simétricas, se pueden usar con seguridad tamaños de claves de 256 bits. El mejor ataque cuántico contra sistemas genéricos de clave simétrica es una aplicación del algoritmo de Grover , que requiere un trabajo proporcional a la raíz cuadrada del tamaño del espacio clave. Para transmitir una clave cifrada a un dispositivo que posee la clave simétrica necesaria para descifrar esa clave 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 necesaria ]
Un sistema de clave pública demuestra una propiedad denominada secreto directo perfecto cuando genera claves públicas aleatorias por sesión a los efectos del acuerdo de claves. Esto significa que el compromiso de un mensaje no puede llevar al compromiso de otros, y también que no existe un único valor secreto que pueda llevar al compromiso de múltiples mensajes. Los expertos en seguridad recomiendan utilizar algoritmos criptográficos que admitan el secreto directo en lugar de aquellos que no lo hacen. [60] La razón de esto es que el secreto directo puede proteger contra el compromiso de claves privadas a largo plazo asociadas con pares de claves públicas/privadas. Esto se considera un medio para impedir la vigilancia masiva por parte de las agencias de inteligencia.
Tanto el intercambio de claves Ring-LWE como el intercambio de claves de isogenia supersingular Diffie-Hellman (SIDH) pueden respaldar el secreto directo en un intercambio con la otra parte. Tanto Ring-LWE como SIDH también se pueden utilizar sin secreto directo creando una variante de la variante de cifrado ElGamal clásica de Diffie-Hellman.
Los otros algoritmos de este artículo, como NTRU, no admiten el secreto directo tal como están.
Se puede utilizar cualquier sistema de cifrado de clave pública autenticado para crear un intercambio de claves con secreto directo. [61]
El proyecto Open Quantum Safe ( OQS ) se inició a finales de 2016 y tiene como objetivo desarrollar y crear prototipos de criptografía resistente a los cuánticos. [62] [63] Su objetivo es integrar los esquemas poscuánticos actuales en una biblioteca: liboqs . [64] liboqs es una biblioteca C de código abierto para algoritmos criptográficos resistentes a los cuánticos. 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 poscuá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 poscuánticas. Además, OQS también proporciona integración de liboqs en OpenSSL . [sesenta y cinco]
A partir de marzo de 2023, se admiten los siguientes algoritmos de intercambio de claves: [62]
Las versiones anteriores compatibles que se han eliminado debido a la progresión del Proyecto de estandarización de criptografía poscuántica del NIST son:
Se considera que uno de los principales desafíos de la criptografía poscuántica es la implementación de algoritmos potencialmente cuánticos seguros en los sistemas existentes. Hay pruebas realizadas, por ejemplo, por parte de Microsoft Research implementando PICNIC en una PKI utilizando módulos de seguridad de Hardware . [79] 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 . [80]
El 21 de febrero de 2024, Apple anunció que iban a actualizar su protocolo iMessage con un nuevo protocolo PQC llamado "PQ3", que utilizará codificación continua. [81] [82] [83] Apple declaró que, aunque las computadoras cuánticas aún no existen, querían mitigar los riesgos de las futuras computadoras cuánticas, así como los escenarios de ataque llamados " Cosechar ahora, descifrar después ". Apple declaró que cree que su implementación de PQ3 brinda protecciones que "superan a las de todas las demás aplicaciones de mensajería ampliamente implementadas, porque utiliza codificación continua. Apple tiene la intención de reemplazar completamente el protocolo iMessage existente en todas las conversaciones admitidas 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 del 0 al 3. [81]
Otras implementaciones notables incluyen:
{{cite web}}: CS1 maint: bot: original URL status unknown (link){{cite web}}: CS1 maint: bot: original URL status unknown (link){{cite web}}: CS1 maint: bot: original URL status unknown (link){{cite web}}: CS1 maint: bot: original URL status unknown (link){{cite web}}: CS1 maint: bot: original URL status unknown (link)Con cifrado resistente a compromisos y amplias defensas incluso contra ataques cuánticos altamente sofisticados, PQ3 es el primer protocolo de mensajería que alcanza lo que llamamos seguridad de Nivel 3, proporcionando protecciones de protocolo que superan a las de todas las demás aplicaciones de mensajería ampliamente implementadas.