Lattice-Based Cryptography: Development and Analysis of a New Variant of the Crystals-Kyber Algorithm
DOI:
https://doi.org/10.26439/interfases2024.n020.7383Keywords:
post-quantum, lattice-based, quantum computing, Kyber, quantum cryptanalysisAbstract
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
References
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
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under an Attribution 4.0 International (CC BY 4.0) License. that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Last updated 03/05/21
