Paper 2022/439
Efficient Multiplication of Somewhat Small Integers using Number-Theoretic Transforms
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× lower than on Cortex-M3.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. IWSEC 2022
- Keywords
- FFT-based multiplication NTT Arm processors RSA
- Contact author(s)
-
hanno becker @ arm com
vincentvbh7 @ gmail com
matthias @ kannwischer eu
lorenz @ yx7 cc
by @ crypto tw - History
- 2022-10-22: last of 2 revisions
- 2022-04-12: received
- See all versions
- Short URL
- https://ia.cr/2022/439
- License
-
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}
}
