Criptografía basada en celosía

Construcciones de primitivas criptográficas que involucran redes

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]

Historia

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]

Antecedentes matemáticos

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 \{}\sum a_{i}\mathbf {b} _{i}:a_{i}\in \mathbb {Z} {\Big \}}.}$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle (3,1,4)}$ ${\displaystyle (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. ${\displaystyle n}$

Esquemas seleccionados basados ​​en celosía

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

Encriptación

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 .

Cifrado homomórfico

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

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

Funciones hash

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

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

Intercambio de claves

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).

Firma

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]}

CRISTALES-Dilitio

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]

Seguridad

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]}

Funcionalidad

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]

Véase también

• 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

Referencias

1. CSRC, Instituto Nacional de Estándares y Tecnología. Criptografía postcuántica. 2019. Disponible en Internet en <https://csrc.nist.gov/Projects/Post-Quantum-Cryptography/>, consultado el 2 de noviembre de 2022.
2. "Estándar de firma digital basado en red modular" (PDF) . NIST.gov . Agosto de 2024.
3. Ajtai, Miklós (1996). "Generación de instancias duras de problemas de red". Actas del vigésimo octavo simposio anual de la ACM sobre teoría de la computación . págs. 99–108. CiteSeerX 10.1.1.40.2489 . doi :10.1145/237814.237838. ISBN .  978-0-89791-785-8.S2CID6864824  .​
4. Criptosistema de clave pública con equivalencia de caso peor/caso promedio.
5. Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (1998). "NTRU: Un criptosistema de clave pública basado en anillos". Teoría algorítmica de números . Apuntes de clase en informática. Vol. 1423. págs. 267–288. CiteSeerX 10.1.1.25.8422 . doi :10.1007/bfb0054868. ISBN .  978-3-540-64657-0.
6. Regev, Oded (1 de enero de 2005). "Sobre redes, aprendizaje con errores, códigos lineales aleatorios y criptografía". Actas del trigésimo séptimo simposio anual de la ACM sobre teoría de la computación – STOC '05 . ACM. pp. 84–93. CiteSeerX 10.1.1.110.4776 . doi :10.1145/1060590.1060603. ISBN .  978-1581139600.S2CID53223958  .​
7. Peikert, Chris (1 de enero de 2009). "Sistemas criptográficos de clave pública a partir del problema del vector más corto en el peor de los casos". Actas del 41.º simposio anual de la ACM sobre teoría de la computación – STOC '09 . ACM. págs. 333–342. CiteSeerX 10.1.1.168.270 . doi :10.1145/1536414.1536461. ISBN .  9781605585062.S2CID 1864880  .
8. Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien (1 de enero de 2013). "Dificultad clásica del aprendizaje con errores". Actas del 45.º simposio anual de la ACM sobre Simposio sobre teoría de la computación – STOC '13 . ACM. págs. 575–584. arXiv : 1306.0281 . doi :10.1145/2488608.2488680. ISBN . 9781450320290.S2CID6005009  .​
9. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (30 de mayo de 2010). "Sobre redes ideales y aprendizaje con errores sobre anillos". Avances en criptología – EUROCRYPT 2010. Apuntes de clase en informática. Vol. 6110. págs. 1–23. CiteSeerX 10.1.1.352.8218 . doi :10.1007/978-3-642-13190-5_1. ISBN .  978-3-642-13189-9.
10. Peikert, Chris (16 de julio de 2014). "Criptografía en red para Internet" (PDF) . IACR . Consultado el 11 de enero de 2017 .
11. Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (1 de enero de 2015). «Intercambio de claves postcuántico: una nueva esperanza». Archivo de ePrints de criptología .
12. Bos, Joppe; Costello, Craig; Ducas, Leo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (1 de enero de 2016). "Frodo: ¡Quítate el anillo! Intercambio de claves práctico y seguro desde el punto de vista cuántico de LWE". Archivo ePrint de criptología .
13. Gentry, Craig (1 de enero de 2009). Un esquema de cifrado completamente homomórfico (tesis). Stanford, CA, EE. UU.: Stanford University.
14. NGUYEN, Phon. Criptoanálisis del criptosistema Goldreich-Goldwasser-Halevi de crypto '97. En Crypto '99: Actas de la 19.ª Conferencia Anual Internacional de Criptología sobre Avances en Criptología , páginas 288-304, Londres, Reino Unido, 1999. Springer-Verlag.
15. Brakerski, Zvika; Vaikuntanathan, Vinod (2011). "Cifrado homomórfico completo y eficiente a partir de LWE (estándar)". Archivo de ePrints de criptología .
16. Brakerski, Zvika; Vaikuntanathan, Vinod (2013). "FHE basado en celosía tan seguro como PKE". Archivo ePrint de criptología .
17. "LASH: una función hash basada en retícula". Archivado desde el original el 16 de octubre de 2008. Consultado el 31 de julio de 2008 .
18. Contini, Scott; Matusiewicz, Krystian; Pieprzyk, Josef; Steinfeld, Ron; Guo, Jian; Ling, San; Wang, Huaxiong (2008). "Criptoanálisis de LASH" (PDF) . Cifrado rápido de software . Apuntes de clase en informática. Vol. 5086. págs. 207–223. doi :10.1007/978-3-540-71039-4_13. ISBN . 978-3-540-71038-7. Número de identificación del sujeto  6207514.
19. AVANZI, R. et al. Especificaciones del algoritmo CRYSTALS-KYBER y documentación complementaria. Equipo CRYSTALS, 2021. Disponible en Internet en <https://www.pq-crystals.org/>, consultado el 4 de noviembre de 2022.
20. Raimondo, Gina M. y Locascio, Laurie E., FIPS 203 (borrador) Publicación de estándares federales de procesamiento de información: estándar de mecanismo de encapsulación de claves basado en red modular. 24 de agosto de 2023. Laboratorio de tecnología de la información, Instituto Nacional de Estándares y Tecnología. Gaithersburg, MD, Estados Unidos de América. DOI 10.6028/NIST.FIPS.203.ipd. Disponible en Internet en <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.203.ipd.pdf>, consultado el 30 de octubre de 2023.
21. Equipo FrodoKEM. FrodoKEM. 2022. Disponible en Internet en <https://frodokem.org/>, consultado el 2 de noviembre de 2022.
22. ALKIM, E. et al. Especificaciones del algoritmo de encapsulación de claves de aprendizaje con errores de FrodoKEM y documentación complementaria. 2020. Disponible en Internet en <https://frodokem.org/files/FrodoKEM-specification-20200930.pdf>, consultado el 1 de noviembre de 2022
23. Bernstein, Daniel J. La documentación de FrodoKEM afirma que "los conjuntos de parámetros de FrodoKEM coinciden cómodamente con sus niveles de seguridad objetivo con un amplio margen". Advertencia: eso no es cierto. Envíe 2^40 textos cifrados a una clave pública frodokem640; uno de ellos será descifrado por un ataque a gran escala factible hoy. 2022. Disponible en Internet en <https://twitter.com/hashbreaker/status/1587184970258255872>, consultado el 2 de noviembre de 2022.
24. SCHWABE, Peter et al. Sitio web de NewHope. 2022. Disponible en Internet en <https://newhopecrypto.org/>, consultado el 6 de diciembre de 2022.
25. Bernstein, Daniel J. et al., NTRU Prime: ronda 3. 2020. Disponible en Internet en <https://ntruprime.cr.yp.to/>, consultado el 8 de noviembre de 2022.
26. D'ANVERS, Jan-Pieter, KARMAKAR, Angshuman, ROY, Sujoy Sinha y VERCAUTEREN, Frederik. Saber: intercambio de claves basado en módulo-LWR, cifrado seguro CPA y KEM seguro CCA. 2018. Disponible en Internet en <https://eprint.iacr.org/2018/230>, consultado el 5 de noviembre de 2022.
27. BAI, S. et al. Especificaciones del algoritmo CRYSTALS-Dilithium y documentación complementaria (versión 3.1). Equipo CRYSTALS, 2021. Disponible en Internet en <https://www.pq-crystals.org/>, consultado el 2 de noviembre de 2021.
28. SEILER, Gregor et al. pq-crystals/dilithium (Dilithium en GitHub), 2022. Disponible en Internet en <https://github.com/pq-crystals/dilithium>, consultado el 29 de diciembre de 2022.
29. FOUQUE, Pierre-Alain et al. Falcon: Fast-Fourier Lattice-based Compact Signatures over NTRU. 2020. Disponible en Internet en <https://falcon-sign.info/>, consultado el 8 de noviembre de 2020.
30. Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Criptografía práctica basada en retículas: un esquema de firma para sistemas integrados" (PDF) . Hardware criptográfico y sistemas integrados – CHES 2012. Apuntes de clase en informática. Vol. 7428. IACR. págs. 530–547. doi :10.1007/978-3-642-33027-8_31. ISBN . 978-3-642-33026-1. Recuperado el 11 de enero de 2017 .
31. ESPITAU, Thomas y col. MITAKA: una variante de Falcon más simple, paralelizable y enmascarable. 2021.
32. ALKIM, E. et al. The Lattice-Based Digital Signature Scheme qTESLA. IACR, 2019. Archivo de ePrints de criptología, Informe 2019/085. Disponible en Internet en <https://eprint.iacr.org/2019/085>, consultado el 1 de NOVIEMBRE de 2022.
33. Perlner, Ray A.. Cambios planificados en la especificación de Dilithium. 20 de abril de 2023. Grupos de Google. Disponible en Internet en <https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/3pBJsYjfRw4/m/GjJ2icQkAQAJ>, consultado el 14 de junio de 2023.
34. Raimondo, Gina M. y Locascio, Laurie E., FIPS 204 (borrador) Publicación de estándares federales de procesamiento de información: estándar de firma digital basado en módulos y retículas. 24 de agosto de 2023. Laboratorio de tecnología de la información, Instituto Nacional de Estándares y Tecnología. Gaithersburg, MD, Estados Unidos de América. DOI 10.6028/NIST.FIPS.204.ipd. Disponible en Internet en <https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.204.ipd.pdf>, consultado el 2 de septiembre de 2023.
35. Lista de correo Gcrypt-devel. Implementación de Dilithium en Libgcrypt. 24 de octubre de 2023. Disponible en Internet en <https://lists.gnupg.org/pipermail/gcrypt-devel/2023-October/005572.html>, consultado el 24 de octubre de 2023.
36. Micciancio, Daniele; Regev, Oded (22 de julio de 2008). "Criptografía basada en retícula" (PDF) . Nyu.edu . Consultado el 11 de enero de 2017 .
37. Shor, Peter W. (1997-10-01). "Algoritmos de tiempo polinomial para factorización prima y logaritmos discretos en una computadora cuántica". Revista SIAM de Computación . 26 (5): 1484–1509. arXiv : quant-ph/9508027 . doi :10.1137/S0097539795293172. ISSN  0097-5397. S2CID  2337707.
38. Bellare, Mihir (1998), Seguridad demostrable orientada a la práctica , Lecture Notes in Computer Science, vol. 1396, Springer-Verlag, págs. 221-231, doi :10.1007/BFb0030423
39. Koblitz, Neal; Samajder, Subhabrata; Sarkar, Palash; Singha, Subhadip (2022). "Análisis concreto de la reducción aproximada de SIVP ideal a LWE de anillo de decisión". Avances en las matemáticas de las comunicaciones . doi : 10.3934/amc.2022082 .
40. Gärtner, Joel (2023), Seguridad concreta desde el peor de los casos hasta las reducciones de red del caso promedio, Lecture Notes in Computer Science, vol. 14064, Springer-Verlag, págs. 344–369, ISBN 978-3-031-37678-8
41. Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (1 de enero de 2013). "Ofuscación de indistinguibilidad de candidatos y cifrado funcional para todos los circuitos". Archivo de ePrints de criptología . CiteSeerX 10.1.1.400.6501 . 

Bibliografía

• 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.