Lattice-Based Cryptography: Development and Analysis of a New Variant of the Crystals-Kyber Algorithm
DOI:
https://doi.org/10.26439/interfases2024.n020.7383Palavras-chave:
post-quantum, lattice-based, quantum computing, Kyber, quantum cryptanalysisResumo
The imminent arrival of quantum computing has accelerated the need for cryptographic systems resistant to quantum attacks. Such attacks exploit the vulnerability in private and public key encryption systems, where the public key is derived from the private key, which could be refactored from the public key. To address this issue, the National Institute of Standards and Technology (NIST) launched a global competition in 2016 to create quantum-resistant algorithms. CRYSTALS-Kyber, a lattice-based algorithm focused on the learning with errors (LWE) problem, was selected for standardization. This work introduces RKyber, a variant that instead targets the learning with rounding (LWR) problem, simplifying computations by using deterministic errors rather than random noise. Both algorithms were executed 1000 times, showing that RKyber offers improved speed at the cost of some security.
Downloads
Referências
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
Downloads
Publicado
Edição
Seção
Licença
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
