Abstract
This work presents a versatile and flexible generator of various large integer polynomial multipliers to be used in hardware cryptocores. Flexibility is offered by allowing circuit designers to choose an appropriate multiplication method from a list that includes Schoolbook, Booth, Karatsuba, and Toom-Cook. Moreover, the generator supports traditional and digitized polynomial multiplication solutions, where inputs are broken in smaller parts for efficiency. A parameterized digit serial multiplier wrapper provides the digitized solution for multiplying polynomial coefficients. To explore power-performance-area (PPA) trade-offs, pipelining for the non-digitized multiplication methods is also introduced. Our generator automatically creates the multiplier’s logic in Verilog HDL that is compliant with field-programmable gate array (FPGA) and application specific integrated circuits (ASIC) synthesis. Moreover, it also generates configurable and parameterizable scripts for commercial ASIC synthesis tools. For our experimental results, we have evaluated PPA for multipliers that are sized according to NIST-defined prime and binary fields. Results are presented for two ASIC technologies (65 nm and 15 nm technology) and for the Artix-7 FPGA family. Our generator is also versatile since it creates several architectures simultaneously, thus allowing a designer to easily explore the complex optimization search space of polynomial multiplication in cryptography.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Notes
We clarify that this FPGA is designed in 28 nm.
The Xilinx Virtex-II Pro devices are built on a 90nm technology.
References
Abd-Elkader AA, Rashdan M, Hasaneen ESA, Hamed HF (2020) Advanced implementation of montgomery modular multiplier. Microelectron J 106
Imran M, Abideen ZU, Pagliarini S (2020) An experimental study of building blocks of lattice-based nist post-quantum cryptographic algorithms. Electronics 9(11):1953. https://doi.org/10.3390/electronics9111953
Morales-Sandoval M, Feregrino-Uribe C, Kitsos P, Cumplido R (2013) Area/performance trade-off analysis of an fpga digit-serial gf(2m) montgomery multiplier based on lfsr. Comput Electr Eng 39(2):542–549. https://doi.org/10.1016/j.compeleceng.2012.08.010
Rafferty C, O’Neill M, Hanley N (2017) Evaluation of large integer multiplication methods on hardware. IEEE Trans Comput 66(8):1369–1382. https://doi.org/10.1109/TC.2017.2677426
Rashidi B (2020) Throughput/area efficient implementation of scalable polynomial basis multiplication. Journal of Hardware and Systems Security 4(2):120–135. https://doi.org/10.1007/s41635-019-00087-5
Eberle H, Gura N, Shantz S, Gupta V, Rarick L, Sundaram S (2004) A public-key cryptographic processor for rsa and ecc. In: Proceedings. 15th IEEE International Conference on Application-Specific Systems, Architectures and Processors, 2004., pp. 98–110. IEEE. https://doi.org/10.1109/ASAP.2004.1342462
NIST (2020) Computer security resource centre: Pqc standardization process, third round candidate announcement. URL https://csrc.nist.gov/news/2020/pqc-third-round-candidate-announcement
López-Alt A, Tromer E, Vaikuntanathan V (2012) On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, p. 1219-1234. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/2213977.2214086
NIST (2020) Computer security resource centre: post-quantum cryptography, round 2 submissions. URL https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions
Azarderakhsh R, Järvinen KU, Mozaffari-Kermani M (2014) Efficient algorithm and architecture for elliptic curve cryptography for extremely constrained secure applications. IEEE Trans Circuits Syst I Regul Pap 61(4):1144–1155. https://doi.org/10.1109/TCSI.2013.2283691
Doröz Y, Öztürk E, Sunar B (2014) Accelerating fully homomorphic encryption in hardware. IEEE Trans Comput 64(6), 1509–1521. https://doi.org/10.1109/TC.2014.2345388
Mert AC, Öztürk E, Savaş E (2020) FPGA implementation of a run-time configurable ntt-based polynomial multiplication hardware. Microprocess Microsyst 78. https://doi.org/10.1016/j.micpro.2020.103219
Mrabet A, El-Mrabet N, Lashermes R, Rigaud JB, Bouallegue B, Mesnager S, Machhout M (2017) A scalable and systolic architectures of montgomery modular multiplication for public key cryptosystems based on dsps. Journal of Hardware and Systems Security 1(3):219–236. https://doi.org/10.1007/s41635-017-0018-x
Pan J, Song P, Yang C (2018) Efficient digit-serial modular multiplication algorithm on fpga. IET Circuits Devices Syst 12(5):662–668. https://doi.org/10.1049/iet-cds.2017.0300
Xie J, He JJ, Meher PK (2013) Low latency systolic montgomery multiplier for finite field \(gf(2^{m})\) based on pentanomials. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 21(2), 385–389. https://doi.org/10.1109/TVLSI.2012.2185257
Xie J, Meher PK, Zhou X, Lee C (2018) Low register-complexity systolic digit-serial multiplier over \(gf(2^m)\) based on trinomials. IEEE Transactions on Multi-Scale Computing Systems 4(4):773–783. https://doi.org/10.1109/TMSCS.2018.2878437
Imran M, Abideen ZU, Pagliarini S (2020) TTech-LIB: center for hardware security. URL https://github.com/Centre-for-Hardware-Security/TTech-LIB
Imran M, Abideen ZU, Pagliarini S (2021) An open-source library of large integer polynomial multipliers. In: 2021 24th International Symposium on Design and Diagnostics of Electronic Circuits Systems (DDECS), pp. 145–150. https://doi.org/10.1109/DDECS52668.2021.9417065
NIST (1999) Recommended elliptic curves for federal government use. https://csrc.nist.gov/csrc/media/publications/fips/186/2/archive/2000-01-27/documents/fips186-2.pdf
Machhout M, Guitouni Z, Torki K, Khriji L, Tourki R (2010) Coupled fpga/asic implementation of elliptic curve crypto-processor. International Journal of Network Security & Its Applications 2(2):100–112. https://doi.org/10.5121/ijnsa.2010.2208
Somayajulu PK, Ramesh S (2020) Area and power efficient 64-bit booth multiplier. In: 2020 6th International Conference on Advanced Computing and Communication Systems (ICACCS), pp. 721–724. https://doi.org/10.1109/ICACCS48705.2020.9074305
Sutter GD, Deschamps JP, Imana JL (2013) Efficient elliptic curve point multiplication using digit-serial binary field operations. IEEE Trans Ind Electron 60(1):217–225. https://doi.org/10.1109/TIE.2012.2186104
Venkatachalam S, Lee HJ, Ko SB (2018) Power efficient approximate booth multiplier. In: 2018 IEEE International Symposium on Circuits and Systems (ISCAS), pp. 1–4. https://doi.org/10.1109/ISCAS.2018.8351708
Rezai A, Keshavarzi P (2015) High-throughput modular multiplication and exponentiation algorithms using multibit-scan-multibit-shift technique. IEEE Transactions on Very Large Scale Integration (VLSI) Systems 23(9), 1710–1719. https://doi.org/10.1109/TVLSI.2014.2355854
Azarderakhsh R, Reyhani-Masoleh A (2013) Low-complexity multiplier architectures for single and hybrid-double multiplications in gaussian normal bases. IEEE Trans Comput 62(4):744–757. https://doi.org/10.1109/TC.2012.22
Venkatachalam S, Adams E, Lee HJ, Ko SB (2019) Design and analysis of area and power efficient approximate booth multipliers. IEEE Trans Comput 68(11):1697–1703. https://doi.org/10.1109/TC.2019.2926275
Martins M, Matos JM, Ribas RP, Reis A, Schlinker G, Rech L, Michelsen J (2015) Open cell library in 15nm freepdk technology. In: Proceedings of the 2015 Symposium on International Symposium on Physical Design, ISPD ’15, p. 171-178. Association for Computing Machinery, New York, NY, USA. https://doi.org/10.1145/2717764.2717783
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Funding
This work was partially supported by the EC through the European Social Fund in the context of the project “ICT programme”. It was also partially supported by the Estonian Research Council grant MOBERC35.
Conflict of Interest
The authors declare that they have no conflict of interest.
Data Availability
The datasets generated during and/or analysed during the current study are available in the TTech-LIB repository: TTech-LIB
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Imran, M., Abideen, Z.U. & Pagliarini, S. A Versatile and Flexible Multiplier Generator for Large Integer Polynomials. J Hardw Syst Secur 7, 55–71 (2023). https://doi.org/10.1007/s41635-023-00134-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s41635-023-00134-2