Optimization studies of the CRYSTALS-KYBER post-quantum cryptography algorithm
Abstract
The development of quantum computers is getting closer to reality, and as a result the public key cryptographic algorithms used in industry are threatened. In recent years the National Institute of Standards and Technology (NIST) has been carrying out a research over promising quantum-safe cryptographic schemes. All of them demand high computational capability and large key sizes. This paper describes a study about possible optimizations on NIST third round candidate CRYSTALS-KYBER in order to reduce memory consumption and processing time in Intel i5 and ARM Cortex M0+ platforms.
Keywords:
cryptography, post-quantum algorithms, information security, IoT
References
Shor, P. (1997), “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM Journal on Computing.
Micciancio, D., Regev, O. (2008), “Lattice-based cryptography”, CSE Department, University of California, San Diego.
Goldreich, O., Goldwasser, S. & Halevi, S. (1997), “Public-key cryptosystems from lattice reduction problems”, Lecture Notes in Computer Science, vol. 1294.
Regev, O. (2005), “The Learning with Errors Problem”, Courant Institute of Mathematical Sciences, New York University.
Moody, D. (2021), “NIST Status Update on the 3rd Round”, Cryptography Technology Group, National Institute of Standards and Technology.
Bogdanov, D. (2005), “IND-CCA2 secure cryptosystems”, University of Tartu.
Albrecht, M., Deo, M. (2017), “Large Modulus Ring-LWE = Module-LWE”, Information Security Group, Royal Holloway, University of London.
Hofhein, D., Hövelmanns, K. & Kiltz, E. (2017), “A Modular Analysis of the Fujisaki-Okamoto Transformation”, Karlsruhe Institute of Technology.
May, W. (2015), “SHA-3 Standard: Permutation-Based and Extendable-Output Functions”, Federal Information Processing Standards Publication, National Institute of Standards and Technology.
Hedge, S., Nagapadma, R. (2019), “Number Theoretic Transform for Fast Digital Computation”, Department of Electronic and Communication Engineering, NIE Institute of Technology.
Avanzi, R. et al. (2021), “CRYSTALS-Kyber - Submission to round 3 of the NIST post-quantum project”, https://pq-crystals.org/kyber/resources.shtml, January.
Bertoni, G et al. (2011), “The Keccak reference”, Submission to the NIST SHA-3 Competition, https://keccak.team/files/Keccak-reference-3.0.pdf, January.
Langley, A. (2017), “Maybe Skip SHA-3”, Blog post on ImperialViolet https://www.imperialviolet.org/2017/05/31/skipsha3.html, May.
Bertoni, G. et al. (2017), “Is SHA-3 slow?”, Blog post on KeccakTeam, https://keccak.team/2017/is_sha3_slow.html, June.
Kannwischer, M. et al. (2019), “pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4”, Radboud University, Netherlands.
Micciancio, D., Regev, O. (2008), “Lattice-based cryptography”, CSE Department, University of California, San Diego.
Goldreich, O., Goldwasser, S. & Halevi, S. (1997), “Public-key cryptosystems from lattice reduction problems”, Lecture Notes in Computer Science, vol. 1294.
Regev, O. (2005), “The Learning with Errors Problem”, Courant Institute of Mathematical Sciences, New York University.
Moody, D. (2021), “NIST Status Update on the 3rd Round”, Cryptography Technology Group, National Institute of Standards and Technology.
Bogdanov, D. (2005), “IND-CCA2 secure cryptosystems”, University of Tartu.
Albrecht, M., Deo, M. (2017), “Large Modulus Ring-LWE = Module-LWE”, Information Security Group, Royal Holloway, University of London.
Hofhein, D., Hövelmanns, K. & Kiltz, E. (2017), “A Modular Analysis of the Fujisaki-Okamoto Transformation”, Karlsruhe Institute of Technology.
May, W. (2015), “SHA-3 Standard: Permutation-Based and Extendable-Output Functions”, Federal Information Processing Standards Publication, National Institute of Standards and Technology.
Hedge, S., Nagapadma, R. (2019), “Number Theoretic Transform for Fast Digital Computation”, Department of Electronic and Communication Engineering, NIE Institute of Technology.
Avanzi, R. et al. (2021), “CRYSTALS-Kyber - Submission to round 3 of the NIST post-quantum project”, https://pq-crystals.org/kyber/resources.shtml, January.
Bertoni, G et al. (2011), “The Keccak reference”, Submission to the NIST SHA-3 Competition, https://keccak.team/files/Keccak-reference-3.0.pdf, January.
Langley, A. (2017), “Maybe Skip SHA-3”, Blog post on ImperialViolet https://www.imperialviolet.org/2017/05/31/skipsha3.html, May.
Bertoni, G. et al. (2017), “Is SHA-3 slow?”, Blog post on KeccakTeam, https://keccak.team/2017/is_sha3_slow.html, June.
Kannwischer, M. et al. (2019), “pqm4: Testing and Benchmarking NIST PQC on ARM Cortex-M4”, Radboud University, Netherlands.
Published
2021-10-04
How to Cite
FERRO, Luiz F. C.; RAMPAZZO, Felipe J. A.; HENRIQUES, Marco A. A..
Optimization studies of the CRYSTALS-KYBER post-quantum cryptography algorithm. In: WORKSHOP ON SCIENTIFIC INITIATION AND UNDERGRADUATE WORKS - BRAZILIAN SYMPOSIUM ON CYBERSECURITY (SBSEG), 21. , 2021, Evento Online.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2021
.
p. 205-218.
DOI: https://doi.org/10.5753/sbseg_estendido.2021.17353.
