Criptografía basada en celosía

La criptografía basada en retículas es el término genérico para las construcciones de primitivas criptográficas que involucran retículas , ya sea en la construcción misma o en la prueba de seguridad. Las construcciones basadas en retículas respaldan importantes estándares de criptografía poscuántica . ^[1] A diferencia de los esquemas de clave pública más utilizados y conocidos, como RSA , Diffie-Hellman o criptosistemas de curva elíptica , que podrían, teóricamente, ser derrotados utilizando el algoritmo de Shor en una computadora cuántica , algunas construcciones basadas en retículas parecen ser resistentes a los ataques tanto de computadoras clásicas como cuánticas. Además, muchas construcciones basadas en retículas se consideran seguras bajo el supuesto de que ciertos problemas computacionales de retículas bien estudiados no se pueden resolver de manera eficiente.

En 2024, el NIST anunció el estándar de firma digital basado en red modular para la criptografía postcuántica. ^[2]

En 1996, Miklós Ajtai introdujo la primera construcción criptográfica basada en retículas cuya seguridad podía basarse en la dureza de problemas de retículas bien estudiados, ^[3] y Cynthia Dwork demostró que un determinado problema de retícula de caso promedio, conocido como soluciones enteras cortas (SIS), es al menos tan difícil de resolver como un problema de retícula de peor caso . ^[4] Luego mostró una función hash criptográfica cuya seguridad es equivalente a la dureza computacional de SIS.

En 1998, Jeffrey Hoffstein , Jill Pipher y Joseph H. Silverman introdujeron un esquema de cifrado de clave pública basado en red , conocido como NTRU . ^[5] Sin embargo, no se sabe que su esquema sea al menos tan difícil como resolver un problema de red en el peor de los casos.

El primer esquema de cifrado de clave pública basado en retícula cuya seguridad se demostró bajo supuestos de dureza del peor caso fue introducido por Oded Regev en 2005 ^[6] , junto con el problema de aprendizaje con errores (LWE). Desde entonces, gran parte del trabajo de seguimiento se ha centrado en mejorar la prueba de seguridad de Regev ^{[7] [8]} y mejorar la eficiencia del esquema original. ^{[9] [10] [11] [12]} Se ha dedicado mucho más trabajo a construir primitivas criptográficas adicionales basadas en LWE y problemas relacionados. Por ejemplo, en 2009, Craig Gentry introdujo el primer esquema de cifrado completamente homomórfico , que se basaba en un problema de retícula. ^[13]

En álgebra lineal , una red es el conjunto de todas las combinaciones lineales enteras de vectores a partir de una base de . En otras palabras, Por ejemplo, es una red generada por la base estándar para . Fundamentalmente, la base para una red no es única. Por ejemplo, los vectores , , y forman una base alternativa para .${\displaystyle L\subset \mathbb {R} ^{n}}$ ${\displaystyle \{\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\}}$${\displaystyle \mathbb {R} ^{n}}$${\displaystyle L={\Big \{}\suma a_{i}\mathbf {b} _{i}:a_{i}\in \mathbb {Z} {\Big \}}.}$${\displaystyle \mathbb {Z} ^{n}}$${\displaystyle \mathbb {R} ^{n}}$${\estilo de visualización (3,1,4)}$${\estilo de visualización (1,5,9)}$${\displaystyle (2,-1,0)}$${\displaystyle \mathbb {Z} ^{3}}$

El problema computacional basado en retículas más importante es el problema del vector más corto (SVP o, a veces, GapSVP), que nos pide aproximar la longitud euclidiana mínima de un vector de retícula distinto de cero. Se cree que este problema es difícil de resolver de manera eficiente, incluso con factores de aproximación que son polinómicos en , e incluso con una computadora cuántica. Se sabe que muchas construcciones criptográficas basadas en retículas (aunque no todas) son seguras si el SVP es de hecho difícil en este régimen.${\estilo de visualización n}$

En esta sección se presentan esquemas seleccionados basados ​​en celosía, agrupados por primitivo.

Esquemas seleccionados para fines de cifrado:

• Esquema de cifrado GGH , que se basa en el problema del vector más cercano (CVP). En 1999, Nguyen publicó una falla crítica en el diseño del esquema. ^[14]
• NTRUEncrypt .

Esquemas seleccionados para el propósito del cifrado homomórfico :

• El plan original de Gentry. ^[13]
• Brakerski y Vaikuntanathan. ^{[15] [16]}

Esquemas criptográficos basados ​​en celosía seleccionados para fines de hash:

• RÁPIDO .
• Función hash basada en red (LASH). ^{[17] [18]}

Esquemas seleccionados para el intercambio de claves, también llamado establecimiento de claves, encapsulación de claves y mecanismo de encapsulación de claves (KEM):

• CRYSTALS-Kyber , ^[19] que se basa en el aprendizaje de módulos con errores (module-LWE). Kyber fue seleccionado para su estandarización por el NIST en 2023. ^[1] En agosto de 2023, el NIST publicó FIPS 203 (borrador público inicial) y comenzó a referirse a su versión de Kyber como Mecanismo de encapsulación de claves basado en módulos y retículas (ML-KEM). ^[20]
• FrodoKEM, ^{[21] [22]} un esquema basado en el problema de aprendizaje con errores (LWE). FrodoKEM se unió a la convocatoria de estandarización realizada por el Instituto Nacional de Estándares y Tecnología (NIST) [ ^1] y estuvo a la altura de la tercera ronda del proceso. Luego fue descartado por razones de bajo rendimiento. En octubre de 2022, la cuenta de Twitter asociada al criptólogo Daniel J. Bernstein publicó problemas de seguridad en frodokem640. ^[23]
• NewHope se basa en el problema de aprendizaje de anillos con errores (RLWE). ^[24]
• NTRU Prime. ^[25]
• El trabajo de Peikert , que se basa en el problema de aprendizaje de anillos con errores (RLWE). ^[10]
• Saber, ^[26] que se basa en el problema de aprendizaje de módulos con redondeo (módulo-LWR).

En esta sección se enumera una selección de esquemas basados ​​en celosía para el propósito de firmas digitales.

• CRISTALES-Dilithium, ^{[27] [28]} que se basa en el aprendizaje de módulos con errores (módulo-LWE) y la solución de enteros cortos de módulos (módulo-SIS). Dilithium fue seleccionado para la estandarización por el NIST. ^[1] Según un mensaje de Ray Perlner, que escribe en nombre del equipo PQC del NIST, el estándar de firma de módulo-LWE del NIST se basará en la versión 3.1 de la especificación Dilithium.

• Falcon , que se basa en una solución de enteros cortos (SIS) sobre NTRU, fue seleccionado por el NIST para su estandarización. ^{[29] [1]}
• Esquema de firma GGH .
• El trabajo de Güneysu, Lyubashevsky y Pöppelmann, que se basa en el aprendizaje de anillos con errores (RLWE). ^[30]

• MITAKA, una variante de Falcon. ^[31]
• Signo NTRUSign .
• qTESLA, que se basa en el aprendizaje en anillo con errores (RLWE). El esquema qTESLA se unió a la convocatoria de estandarización realizada por el Instituto Nacional de Estándares y Tecnología (NIST) . ^{[32] [1]}

CRYSTALS-Dilithium o simplemente Dilithium ^{[27] [28]} se basa en el módulo LWE y el módulo SIS. El NIST seleccionó Dilithium como base para un estándar de firma digital. ^[1] Según un mensaje de Ray Perlner, que escribe en nombre del equipo PQC del NIST, el estándar de firma del módulo LWE del NIST se basará en la versión 3.1 de la especificación Dilithium. Los cambios del NIST en Dilithium 3.1 tienen como objetivo admitir una aleatoriedad adicional en la firma (firma protegida) y otras mejoras. ^[33]

El dilitio fue uno de los dos esquemas de firma digital elegidos inicialmente por el NIST en su proceso de criptografía postcuántica; el otro es SPHINCS⁺, que no se basa en redes sino en hashes.

En agosto de 2023, el NIST publicó FIPS 204 (borrador público inicial) y comenzó a llamar a Dilithium algoritmo de firma digital basado en módulos y redes (ML-DSA). ^[34]

A partir de octubre de 2023, ML-DSA se estaba implementando como parte de Libgcrypt , según Falco Strenzke. ^[35]

Las construcciones criptográficas basadas en retículas son muy prometedoras para la criptografía postcuántica de clave pública . ^[36] De hecho, las principales formas alternativas de criptografía de clave pública son los esquemas basados ​​en la dificultad de la factorización y problemas relacionados y los esquemas basados ​​en la dificultad del logaritmo discreto y problemas relacionados . Sin embargo, se sabe que tanto la factorización como el problema del logaritmo discreto se pueden resolver en tiempo polinomial en una computadora cuántica . ^[37] Además, los algoritmos para la factorización tienden a producir algoritmos para el logaritmo discreto y viceversa. Esto motiva aún más el estudio de construcciones basadas en supuestos alternativos, como la dificultad de los problemas de retícula.

Se sabe que muchos esquemas criptográficos basados ​​en retículas son seguros asumiendo la peor dificultad de ciertos problemas de retícula. ^{[3] [6] [7]} Es decir, si existe un algoritmo que puede romper eficientemente el esquema criptográfico con una probabilidad no despreciable, entonces existe un algoritmo eficiente que resuelve un cierto problema de retícula en cualquier entrada. Sin embargo, para las construcciones prácticas basadas en retículas (como esquemas basados ​​en NTRU e incluso esquemas basados ​​en LWE con parámetros eficientes), no se conocen garantías significativas de seguridad basadas en reducción.

Las evaluaciones de los niveles de seguridad proporcionados por los argumentos de reducción de problemas difíciles (basados ​​en tamaños de parámetros recomendados, estimaciones estándar de la complejidad computacional de los problemas difíciles y un examen detallado de los pasos en las reducciones) se denominan seguridad concreta y, a veces , seguridad demostrable orientada a la práctica . ^[38] Los autores que han investigado la seguridad concreta para criptosistemas basados ​​en celosías han descubierto que los resultados de seguridad demostrable para tales sistemas no proporcionan ninguna seguridad concreta significativa para los valores prácticos de los parámetros. ^{[39] [40]}

En el caso de muchos primitivos criptográficos, las únicas construcciones conocidas se basan en retículas u objetos estrechamente relacionados. Estos primitivos incluyen el cifrado totalmente homomórfico , ^[13] la ofuscación de indistinguibilidad , ^[41] los mapas multilineales criptográficos y el cifrado funcional . ^[41]

• Problemas de celosía
• Aprendiendo con errores
• Cifrado homomórfico
• Criptografía post-cuántica
• Aprendizaje de anillos con errores
• Aprendizaje de anillos con intercambio de claves de errores

• Oded Goldreich, Shafi Goldwasser y Shai Halevi. "Sistemas criptográficos de clave pública a partir de problemas de reducción de red". En Crypto '97: Actas de la 17.ª Conferencia Anual Internacional de Criptología sobre Avances en Criptología , páginas 112-131, Londres, Reino Unido, 1997. Springer-Verlag.
• Oded Regev. Criptografía basada en retículas. En Advances in cryptology (CRYPTO) , páginas 131–141, 2006.