[en] Multi-Precision Integer (MPI) arithmetic is a performance-critical component of many public-key cryptosystems, including besides classical ones (e.g., RSA, ECC) also isogeny-based post-quantum schemes. In this paper, we analyze and compare two widely-used MPI representations, namely full-radix and reduced-radix, for the efficient implementation of modular arithmetic operations on the 64-bit RISC-V (RV64GC) architecture. We also evaluate how the execution times of both can be further improved with Instruction Set Extensions (ISEs). The ISEs we propose are able to accelerate a CSIDH-512 class group action by a factor of 1.71 compared to a standard software implementation on a 64-bit Rocket core. This speed-up comes at the cost of a hardware overhead of about 10%.
Disciplines :
Computer science
Author, co-author :
CHENG, Hao ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA
FOTIADIS, Georgios ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust > APSIA > Team Peter RYAN
GROSZSCHÄDL, Johann ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
PAGE, Daniel; University of Bristol [GB] > Department of Computer Science
PHAM, Thinh; University of Bristol [GB] > Department of Computer Science
RYAN, Peter Y A ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
External co-authors :
yes
Language :
English
Title :
RISC-V Instruction Set Extensions for Multi-Precision Integer Arithmetic
Publication date :
June 2024
Event name :
61st ACM/IEEE Design Automation Conference
Event place :
San Francisco, United States
Event date :
from 23-06-2024 to 27-06-2024
Audience :
International
Main work title :
61st ACM/IEEE Design Automation Conference, DAC 2024, San Francisco, CA, USA, June 23-27, 2024, Proceedings
E. Alkim, H. Evkan, N. Lahr, et al. 2020. ISA extensions for finite field arithmetic: Accelerating Kyber and NewHope on RISC-V. In CHES 2020. IACR, 219-242.
K. Asanovi, R. Avizienis, J. Bachrach, et al. 2016. The Rocket Chip Generator. Technical Report UCB/EECS-2016-17. University of California, Berkeley.
W. Castryck, T. Lange, C. Martindale, et al. 2018. CSIDH: An efficient postquantum commutative group action. In ASIACRYPT 2018 (LNCS 11274). Springer, 395-427.
H. Cheng, G. Fotiadis, J. Großschädl, et al. 2022. Highly Vectorized SIKE for AVX-512. In CHES 2022. IACR, 41-68.
L. De Feo, D. Jao, and J. Plut. 2014. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies. Journal of Mathematical Cryptology 8, 3 (2014), 209-247.
S.D. Galbraith. 2012. Mathematics of Public Key Cryptography. Cambridge University Press.
D.R. Hankerson, A.J. Menezes, and S.A. Vanstone. 2004. Guide to Elliptic Curve Cryptography. Springer.
C.K. Koc, T. Acar, and B.S. Kaliski Jr. 1996. Analyzing and comparing Montgomery multiplication algorithms. IEEE Micro 16, 3 (1996), 26-33.
H. Li, N. Mentens, and S. Picek. 2022. A scalable SIMD RISC-V based processor with customized vector extensions for CRYSTALS-Kyber. In DAC 2022. ACM, 733-738.
B. Marshall, G.R. Newell, D. Page, et al. 2021. The design of scalar AES instruction set extensions for RISC-V. In CHES 2021. IACR, 109-136.
P. Nannipieri, S. Di Matteo, L. Zulberti, et al. 2021. A RISC-V post quantum cryptography instruction set extension for number theoretic transform to speedup CRYSTALS algorithms. IEEE Access 9 (2021), 150798-150808.
C. Peikert. 2020. He gives C-sieves on the CSIDH. In EUROCRYPT 2020 (LNCS 12106). Springer, 463-492.
A.Waterman and K. Asanovi 2019. The RISC-V Instruction Set Manual. Technical Report Volume I: User-Level ISA (Version 20191213).
