Abstract
In this paper we propose a HDL generator for finite-field multipliers on FPGAs. The generated multipliers are based on the CIOS variant of Montgomery multiplication. They are designed to exploit finely the DSPs available on most FPGAs, interleaving independent computations to maximize throughput and DSP’s workload. Beside their throughput-efficiency, these operators can dynamically adapt to different finite-fields by changing both operand width and precomputed elements.
From this flexible and efficient operator base, our HDL generator allows the exploration of a wide range of configurations. This is a valuable asset for specialized circuit designers who wish to tune state-of-the-art IPs and explore design space for their applications.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
When fully loaded with instructions, \(\sigma \) operations are outputed every \(s^2 \sigma \) cycles.
- 2.
Speedup = \(\frac{f_\# \left( \frac{p}{4^2} + \frac{1-p}{8^2}\right) }{\frac{f}{8^2}}\).
References
Bossuet, L., Gogniat, G., Philippe, J.L.: Exploration de l’espace de conception des architectures reconfigurables. 25(7), 921–946. https://doi.org/10.3166/tsi.25.921-946
Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference on ITCS 2012. ACM Press (2012). https://doi.org/10.1145/2090236.2090262
Cathébras, J., Chotin, R.: Finely Pipelined Modular Multiplier (FPMM). https://gitlab.lip6.fr/roselyne/fpmm/. Accessed 12 Aug 2020
Deschamps, J.P., Sutter, G.D., Cantó, E.: Guide to FPGA Implementation of Arithmetic Functions. Springer, Netherlands (2012). https://doi.org/10.1007/978-94-007-2987-2
Gallin, G., Tisserand, A.: Generation of finely-pipelined GF(P) multipliers for flexible curve based cryptography on FPGAs, pp. 1–12. https://doi.org/10.1109/TC.2019.2920352
Gallin, G., Tisserand, A.: Hyper-Threaded Modular Multipliers (HTMM). https://sourcesup.renater.fr/www/htmm/. Accessed 25 Feb 2020
Gallin, G., Tisserand, A.: Hyper-threaded multiplier for HECC. In: 2017 51st Asilomar Conference on Signals, Systems, and Computers. IEEE (2017). https://doi.org/10.1109/acssc.2017.8335378
Koc, C.K., Acar, T., Kaliski, B.: Analyzing and comparing montgomery multiplication algorithms. IEEE Micro 16(3), 26–33 (1996). https://doi.org/10.1109/40.502403
Ma, Y., Liu, Z., Pan, W., Jing, J.: A high-speed elliptic curve cryptographic processor for generic curves over GF\((p)\). In: Lange, T., Lauter, K., Lisoněk, P. (eds.) SAC 2013. LNCS, vol. 8282, pp. 421–437. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43414-7_21
Montgomery, P.L.: Modular multiplication without trial division. Math. Comput. 44(170), 519 (1985). https://doi.org/10.1090/s0025-5718-1985-0777282-x
Morales-Sandoval, M., Diaz-Perez, A.: Scalable GF(P) montgomery multiplier based on a digit-digit computation approach. IET Comput. Digit. Tech. 10(3), 102–109 (2016). https://doi.org/10.1049/iet-cdt.2015.0055
Mrabet, A., et al.: A scalable and systolic architectures of montgomery modular multiplication for public key cryptosystems based on DSPs. J. Hardw. Syst. Secur. 1(3), 219–236 (2017). https://doi.org/10.1007/s41635-017-0018-x
Pimentel, A.D.: Exploring exploration: a tutorial introduction to embedded systems design space exploration. IEEE Des. Test 34(1), 77–90 (2016). https://doi.org/10.1109/mdat.2016.2626445
Walter, C.: Montgomery exponentiation needs no final subtractions. Electron. Lett. 35(21), 1831 (1999). https://doi.org/10.1049/el:19991230
Ackowledgments
We would like to thank Arnaud Tisserand for our interesting exchanges and his encouragement to publish these results; as well as the anonymous reviewers for their pertinent and welcome remarks and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Cathébras, J., Chotin, R. (2021). A HDL Generator for Flexible and Efficient Finite-Field Multipliers on FPGAs. In: Bajard, J.C., Topuzoğlu, A. (eds) Arithmetic of Finite Fields. WAIFI 2020. Lecture Notes in Computer Science(), vol 12542. Springer, Cham. https://doi.org/10.1007/978-3-030-68869-1_4
Download citation
DOI: https://doi.org/10.1007/978-3-030-68869-1_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-68868-4
Online ISBN: 978-3-030-68869-1
eBook Packages: Computer ScienceComputer Science (R0)