Criptografía basada en retículas: desarrollo y análisis de una nueva variante del algoritmo Crystals-Kyber
Resumen
La inminente llegada de la computación cuántica ha hecho necesario el desarrollo de sistemas criptográficos resistentes a los ataques cuánticos. Los ataques cuánticos explotan la debilidad de la encriptación de llave pública y privada, la cual radica en que la llave pública es derivada desde la llave privada y esta última podría ser factorizada a partir de la llave pública. En respuesta, el NIST inició un concurso mundial en 2016 para crear algoritmos resistentes a la computación cuántica. CRYSTALS-Kyber, un algoritmo basado en celosía que aborda el problema de Aprendizaje con Errores fue seleccionado para su estandarización. Este trabajo introduce una variante, RKyber, que en su lugar aborda el problema de Aprendizaje con Redondeo, simplificando los cálculos mediante el uso de errores deterministas en lugar de ruido aleatorio. Ambos algoritmos se ejecutaron 1000 veces, demostrando que RKyber es más rápido, aunque sacrifica algo de seguridad.
Descargas
Citas
Aaronson, S., & Chen, L. (2017). Complexity-theoretic foundations of quantum supremacy experiments. Proceedings of the 32nd Computational Complexity Conference (CCC’17), Dagstuhl, Germany, Article 22, 1–67. https://doi.org/10.48550/arXiv.1612.05903
Alwen, J., Krenn, S., Pietrzak, K., & Wichs, D. (2013). Learning with rounding, revisited. In R. Canetti, & J. A. Garay (Eds.), Lecture Notes in Computer Science: Vol. 8042. Advances in Cryptology – CRYPTO 2013 (pp. 57–74). Springer. https://doi.org/10.1007/978-3-642-40041-4_4
Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehlé, D. (2021). CRYSTALS-Kyber: Algorithm specifications and supporting documentation (version 3.01). https://pq-crystals.org/kyber/data/kyber-specification-round3-20210131.pdf
Benioff, P. (1980). The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics, 22, 563–591. https://doi.org/10.1007/bf01011339
Bernstein, D. J. (2024, June 28). KyberSlash: division timings depending on secrets in Kyber software. FAQ. https://kyberslash.cr.yp.to/faq.html
Gonzalez, R. (2021, September 14). Kyber - How does it work? Approachable Cryptography. https://cryptopedia.dev/posts/kyber/
Grover, L.K. (1996). A fast quantum mechanical algorithm for database search. Bell Labs. https://doi.org/10.1145/237814.237866
Lyubashevsky, V., Peikert, C., & Regev, O. (2010). On ideal lattices and learning with errors over rings. In H. Gilbert (Ed.), Lecture Notes in Computer Science: Vol. 6110. Advances in Cryptology – EUROCRYPT 2010 (pp. 1–23). Springer. https://doi.org/10.1007/978-3-642-13190-5_1
Micciancio, D., & Goldwasser, S. (2002). Complexity of lattice problems: A cryptographic perspective. Springer. https://ci.nii.ac.jp/ncid/BB14507293
Mor, T., & Renner, R. (2014). Preface. Natural Computing, 13(4), 447–452. https://doi.org/10.1007/s11047-014-9464-3
NTT DATA Perú. (2024, April 17). Algoritmos post-cuánticos: criptografía y ciberseguridad en la era cuántica. NTT DATA Perú. https://pe.nttdata.com/documents/paper_crystals_kyber_ntt_data.pdf
Peikert, C. (2016). A decade of lattice cryptography. Foundations and Trends in Theoretical Computer Science, 10 (4), 283–424. https://doi.org/10.1561/0400000074
Regev, O. (2005). On lattices, learning with errors, random linear codes, and cryptography. Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (STOC ‘05), New York, NY, USA, 84–93. https://doi.org/10.1145/1060590.1060603
Shor, P. W. (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing, 26(5), 1484–1509. https://doi.org/10.1137/s0097539795293172
Wei, Y., Bi, L., Lu, X., & Wang, K. (2023). Security estimation of LWE via BKW algorithms. Cybersecurity, 6, Article 24. https://doi.org/10.1186/s42400-023-00158-9
Esta obra está bajo licencia internacional Creative Commons Reconocimiento 4.0.
Los autores/as que publiquen en esta revista aceptan las siguientes condiciones:
Los autores/as conservan los derechos de autor y ceden a la revista el derecho de la primera publicación, con el trabajo registrado con la licencia de atribución de Creative Commons, que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
Los autores/as pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
Se permite y recomienda a los autores/as a publicar su trabajo en Internet (por ejemplo en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado (vea The Effect of Open Access).
Última actualización: 03/05/21