Cryptology ePrint Archive: Report 2022/439

Efficient Multiplication of Somewhat Small Integers using Number-Theoretic Transforms

Hanno Becker and Vincent Hwang and Matthias J. Kannwischer and Lorenz Panny and Bo-Yin Yang

Abstract: Conventional wisdom purports that FFT-based integer multiplication methods (such as the Schönhage-Strassen algorithm) begin to compete with Karatsuba and Toom-Cook only for integers of several tens of thousands of bits. In this work, we challenge this belief: Leveraging recent advances in the implementation of Number-Theoretic Transforms (NTT) stimulated by their use in Post-Quantum Cryptography, we report on implementations of NTT-based integer arithmetic on two Arm Cortex-M CPUs on opposite ends of the performance spectrum: Cortex-M3 and Cortex-M55. Our results indicate that NTT-based multiplication is capable of outperforming the big-number arithmetic implementations of popular embedded cryptography libraries for integers as small as 2048 bits. To provide a realistic case study, we benchmark implementations of the RSA encryption and decryption operations. Our cycle counts on Cortex-M55 are about $10\times$ lower than on Cortex-M3.

Category / Keywords: implementation / FFT-based multiplication, NTT, Arm processors, RSA

Date: received 6 Apr 2022, last revised 15 Apr 2022

Contact author: hanno becker at arm com, vincentvbh7 at gmail com, matthias at kannwischer eu, lorenz at yx7 cc, by at crypto tw

Available format(s): PDF | BibTeX Citation

Version: 20220415:083139 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]