Avaliação de requisitos de processamento e memória do algoritmo de criptografia pós-quântica SABER em plataforma ARM Cortex-M0+
Resumo
O SABER é um esquema de encapsulamento de chaves CCA-seguro pós-quântico baseado em reticulados e finalista na terceira rodada padronização de algoritmos de criptografia pós-quântica do NIST. Neste trabalho, avaliamos sua execução em um microcontrolador ARM Cortex-M0+ e aplicamos otimizações sugeridas na literatura, adaptando-as para execução no SABER, no LightSABER, versão mais rápida, mas com menor segurança, e no FireSABER, versão mais lenta e mais segura. Essas otimizações diminuem o uso de memória, em troca de um número maior de ciclos de CPU, tornando a execução dos algoritmos viável em ambientes restritos.Referências
Shor, P. (1997), “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer”, SIAM Journal on Computing.
Proos, J., Zalka, C. (2003), “Shor’s discrete logarithm quantum algorithm for elliptic curves”, eprint arXiv:quant-ph/0301141.
National Institute of Standard and Technology – NIST (2016), “Request for Comments on Post-Quantum Cryptography Requirements and Evaluation Criteria”, Notice 81 FR 50686, p. 50686-50687. https://csrc.nist.gov/projects/post-quantum-cryptography
Bernstein, D., Chou, T., et. al (2017), “Classic McEliece: conservative code-based cryptography, ‘Supporting Documentation’”. https://classic.mceliece.org/nist.html.
Bos, J., Ducas, L., Kiltz, et. al (2018), “CRYSTALS – Kyber: a CCA-secure module-lattice-based KEM”, 2018 IEEE European Symposium on Security and Privacy, EuroS&P.
Hoffstein, J., Pipher, J. & Silverman, J. (1996), “NTRU: A new high-speed public key cryptosystem”, Manuscript circulated at CRYPTO 1996 rump session.
D’Anvers, JP., Karmakar, A., et. al (2018), “Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM”.
Joux A., Nitaj A., Rachidi T. (eds) Progress in Cryptology - AFRICACRYPT 2018 - 10th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 7-9, 2018, Proceedings. Lecture Notes in Computer Science 10831, Springer 2018, ISBN 978-3-319-89338-9. https://doi.org/10.1007/978-3-319-89339-6_16
Kannwischer, M. et. al (2019), “PQM4: Post-quantum crypto library for the ARM Cortex-M4”, https://github.com/mupq/pqm4. Último acesso em: 27-06-2022.
Conway, J., Sloane, N. (1999), “Sphere Packings, Lattices and Groups”, Grundlehren der Mathematischen Wissenschaften, 290 (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-98585-5, MR0920369.
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.
Banerjee, A., Peikert, C. & Rosen, A. (2012), “Pseudorandom Functions and Lattices”, in: Pointcheval, D., Johansson, T. (eds) Advances in Cryptology EUROCRYPT 2012. EUROCRYPT 2012. Lecture Notes in Computer Science, vol 7237. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29011-4_42
Langlois, A., Stehlé, D. (2015), “Worst-case to average-case reductions for module lattices”, Designs, Codes and Cryptography, 75(3):565–599
Bogdanov, D. (2005), “IND-CCA2 secure cryptosystems”, University of Tartu.
Hofhein, D., Hövelmanns, K. & Kiltz, E. (2017), “A Modular Analysis of the Fujisaki-Okamoto Transformation”, Karlsruhe Institute of Technology.
Tolhuizen, L., et. al (2017), “Improved key-reconciliation method”, IACR Cryptol.
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.
Crandall, R., Pomerance, C. (2005), “Prime Numbers – A Computational Perspective”, Second Edition, Springer, Section 9.5.1: Karatsuba and Toom–Cook methods, p.473.
Karatsuba, A., Ofman, Y. (1963), “Multiplication of multidigit numbers on automata”, Sov Phys Dokl 7:595–596.
Karmakar, A., et. al (2018), “Saber on ARM. CCA-secure module lattice-based key encapsulation on ARM”, In Transactions in Cryptographic Hardware and Embedded Systems.
Mera, J., Karmakar, A. & Verbauwhede, I. (2020), “Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice based cryptography”, In Transactions in Cryptographic Hardware and Embedded Systems.
Proos, J., Zalka, C. (2003), “Shor’s discrete logarithm quantum algorithm for elliptic curves”, eprint arXiv:quant-ph/0301141.
National Institute of Standard and Technology – NIST (2016), “Request for Comments on Post-Quantum Cryptography Requirements and Evaluation Criteria”, Notice 81 FR 50686, p. 50686-50687. https://csrc.nist.gov/projects/post-quantum-cryptography
Bernstein, D., Chou, T., et. al (2017), “Classic McEliece: conservative code-based cryptography, ‘Supporting Documentation’”. https://classic.mceliece.org/nist.html.
Bos, J., Ducas, L., Kiltz, et. al (2018), “CRYSTALS – Kyber: a CCA-secure module-lattice-based KEM”, 2018 IEEE European Symposium on Security and Privacy, EuroS&P.
Hoffstein, J., Pipher, J. & Silverman, J. (1996), “NTRU: A new high-speed public key cryptosystem”, Manuscript circulated at CRYPTO 1996 rump session.
D’Anvers, JP., Karmakar, A., et. al (2018), “Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM”.
Joux A., Nitaj A., Rachidi T. (eds) Progress in Cryptology - AFRICACRYPT 2018 - 10th International Conference on Cryptology in Africa, Marrakesh, Morocco, May 7-9, 2018, Proceedings. Lecture Notes in Computer Science 10831, Springer 2018, ISBN 978-3-319-89338-9. https://doi.org/10.1007/978-3-319-89339-6_16
Kannwischer, M. et. al (2019), “PQM4: Post-quantum crypto library for the ARM Cortex-M4”, https://github.com/mupq/pqm4. Último acesso em: 27-06-2022.
Conway, J., Sloane, N. (1999), “Sphere Packings, Lattices and Groups”, Grundlehren der Mathematischen Wissenschaften, 290 (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-98585-5, MR0920369.
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.
Banerjee, A., Peikert, C. & Rosen, A. (2012), “Pseudorandom Functions and Lattices”, in: Pointcheval, D., Johansson, T. (eds) Advances in Cryptology EUROCRYPT 2012. EUROCRYPT 2012. Lecture Notes in Computer Science, vol 7237. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29011-4_42
Langlois, A., Stehlé, D. (2015), “Worst-case to average-case reductions for module lattices”, Designs, Codes and Cryptography, 75(3):565–599
Bogdanov, D. (2005), “IND-CCA2 secure cryptosystems”, University of Tartu.
Hofhein, D., Hövelmanns, K. & Kiltz, E. (2017), “A Modular Analysis of the Fujisaki-Okamoto Transformation”, Karlsruhe Institute of Technology.
Tolhuizen, L., et. al (2017), “Improved key-reconciliation method”, IACR Cryptol.
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.
Crandall, R., Pomerance, C. (2005), “Prime Numbers – A Computational Perspective”, Second Edition, Springer, Section 9.5.1: Karatsuba and Toom–Cook methods, p.473.
Karatsuba, A., Ofman, Y. (1963), “Multiplication of multidigit numbers on automata”, Sov Phys Dokl 7:595–596.
Karmakar, A., et. al (2018), “Saber on ARM. CCA-secure module lattice-based key encapsulation on ARM”, In Transactions in Cryptographic Hardware and Embedded Systems.
Mera, J., Karmakar, A. & Verbauwhede, I. (2020), “Time-memory trade-off in Toom-Cook multiplication: an application to module-lattice based cryptography”, In Transactions in Cryptographic Hardware and Embedded Systems.
Publicado
12/09/2022
Como Citar
GIGILAS JUNIOR, George; HENRIQUES, Marco A. A..
Avaliação de requisitos de processamento e memória do algoritmo de criptografia pós-quântica SABER em plataforma ARM Cortex-M0+. In: WORKSHOP DE TRABALHOS DE INICIAÇÃO CIENTÍFICA E DE GRADUAÇÃO - SIMPÓSIO BRASILEIRO DE SEGURANÇA DA INFORMAÇÃO E DE SISTEMAS COMPUTACIONAIS (SBSEG), 22. , 2022, Santa Maria.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 212-225.
DOI: https://doi.org/10.5753/sbseg_estendido.2022.224574.
