Evaluation of modular multiplication techniques for Supersingular Isogeny Schemes on ARMv8 cores

• Vitor Satoru Machi Matsumine UNICAMP
• Félix Carvalho Rodrigues UNICAMP https://orcid.org/0000-0002-2776-5105
• Décio Gazzoni Filho UNICAMP https://orcid.org/0000-0002-6001-2172
• Caio Teixeira UNICAMP https://orcid.org/0000-0002-9902-0866
• Julio López UNICAMP
• Ricardo Dahab UNICAMP https://orcid.org/0000-0002-7002-875X

DOI: https://doi.org/10.5753/sbseg.2022.224951

Resumo

This paper focuses on the evaluation of different modular multiplication implementation techniques on 64-bit ARMv8 systems for the third-round NIST alternate candidate SIKE. The benchmarks were performed on four devices: an Orange Pi WinPlus featuring the Cortex-A53 processor, an NVIDIA Jetson Nano with a Cortex-A57, a Raspberry Pi 4 with a Cortex-A72 and a Macbook Air based on an Apple M1 chip. Throughout these platforms we observed that the two-level Karatsuba Comba method performs better on most Cortex-A processors but the Operand Scanning method presented a performance improvement ranging from 10% to 43% for the multiplication procedure and a 7% to 25% improvement for the modular reduction on the Apple M1 for all SIKE security levels, resulting in an overall improvement ranging from 8% to 28% for the SIKE KEM operations on this architecture.

Palavras-chave: Supersingular isogeny-based cryptography, SIKE, ARM processors, Prime fields, Extension fields, Efficient computation, Post-quantum cryptography

Referências

Castryck, W. and Decru, T. (2022). An efficient key recovery attack on sidh (preliminary version). Cryptology ePrint Archive.

Costello, C., Longa, P., and Naehrig, M. (2016). Efficient algorithms for supersingular isogeny Diffie-Hellman. In Annual International Cryptology Conference, pages 572– 601. Springer.

Couveignes, J.-M. (2006). Hard homogeneous spaces. Cryptology ePrint Archive. De Feo, L., Jao, D., and Plut, J. (2014). Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Journal of Mathematical Cryptology, 8(3):209–247.

Faz-Hernandez, A., López, J., Ochoa-Jiménez, E., and Rodríguez-Henríquez, F. (2017). A faster software implementation of the supersingular isogeny Diffie-Hellman key exchange protocol. IEEE Transactions on Computers, 67(11):1622–1636.

Hofheinz, D., Hovelmanns, K., and Kiltz, E. (2017). A modular analysis of the Fujisaki-Okamoto transformation. In Theory of Cryptography Conference, pages 341–371. Springer.

Jalali, A., Azarderakhsh, R., Kermani, M. M., Campagna, M., and Jao, D. (2019). ARMv8 SIKE: Optimized supersingular isogeny key encapsulation on ARMv8 processors. IEEE Transactions on Circuits and Systems I: Regular Papers, 66(11):4209–4218.

Jalali, A., Azarderakhsh, R., Kermani, M. M., and Jao, D. (2017). Supersingular isogeny Diffie-Hellman key exchange on 64-bit ARM. IEEE Transactions on Dependable and Secure Computing, 16(5):902–912.

Koziel, B., Jalali, A., Azarderakhsh, R., Jao, D., and Mozaffari-Kermani, M. (2016). NEON-SIDH: Efficient implementation of supersingular isogeny Diffie-Hellman key exchange protocol on ARM. In International Conference on Cryptology and Network Security, pages 88–103. Springer.

NIST, N. (2017). Post-Quantum Cryptography. [link].

Rostovtsev, A. and Stolbunov, A. (2006). Public-key cryptosystem based on isogenies. Cryptology ePrint Archive.

Seo, H., Sanal, P., Jalali, A., and Azarderakhsh, R. (2020). Optimized implementation of SIKE round 2 on 64-bit ARM Cortex-A processors. IEEE Transactions on Circuits and Systems I: Regular Papers, 67(8):2659–2671.

Shor, P. W. (1999). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332.