Paper 2022/439

Efficient Multiplication of Somewhat Small Integers using Number-Theoretic Transforms

Hanno Becker, Vincent Hwang, Matthias J. Kannwischer, 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
FFT-based multiplicationNTTArm processorsRSA
Contact author(s)
hanno becker @ arm com
vincentvbh7 @ gmail com
matthias @ kannwischer eu
lorenz @ yx7 cc
by @ crypto tw
History
2022-04-15: revised
2022-04-12: received
See all versions
Short URL
https://ia.cr/2022/439
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/439,
      author = {Hanno Becker and Vincent Hwang and Matthias J.  Kannwischer and Lorenz Panny and Bo-Yin Yang},
      title = {Efficient Multiplication of Somewhat Small Integers using Number-Theoretic Transforms},
      howpublished = {Cryptology ePrint Archive, Paper 2022/439},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/439}},
      url = {https://eprint.iacr.org/2022/439}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.