Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms

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

doi:10.1007/978-3-031-15255-9_1

Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

1 Scopus citations

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.

Original language	English
Title of host publication	Advances in Information and Computer Security - 17th International Workshop on Security, IWSEC 2022, Proceedings
Editors	Chen-Mou Cheng, Mitsuaki Akiyama
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	3-23
Number of pages	21
ISBN (Print)	9783031152542
DOIs	https://doi.org/10.1007/978-3-031-15255-9_1
State	Published - 2022
Externally published	Yes
Event	17th International Workshop on Security, IWSEC 2022 - Tokyo, Japan Duration: 31 Aug 2022 → 2 Sep 2022

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13504 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	17th International Workshop on Security, IWSEC 2022
Country/Territory	Japan
City	Tokyo
Period	31/08/22 → 2/09/22

Keywords

Arm processors
FFT-based multiplication
NTT
RSA

Access to Document

10.1007/978-3-031-15255-9_1

Cite this

Becker, H., Hwang, V., Kannwischer, M. J., Panny, L., & Yang, B. Y. (2022). Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms. In C.-M. Cheng, & M. Akiyama (Eds.), Advances in Information and Computer Security - 17th International Workshop on Security, IWSEC 2022, Proceedings (pp. 3-23). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13504 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-031-15255-9_1

Becker, Hanno ; Hwang, Vincent ; Kannwischer, Matthias J. et al. / Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms. Advances in Information and Computer Security - 17th International Workshop on Security, IWSEC 2022, Proceedings. editor / Chen-Mou Cheng ; Mitsuaki Akiyama. Springer Science and Business Media Deutschland GmbH, 2022. pp. 3-23 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ab4c272f5af2486ca64f014d5a37dbd9,

title = "Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms",

abstract = "Conventional wisdom purports that FFT-based integer multiplication methods (such as the Sch{\"o}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.",

keywords = "Arm processors, FFT-based multiplication, NTT, RSA",

author = "Hanno Becker and Vincent Hwang and Kannwischer, {Matthias J.} and Lorenz Panny and Yang, {Bo Yin}",

note = "Publisher Copyright: {\textcopyright} 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.; 17th International Workshop on Security, IWSEC 2022 ; Conference date: 31-08-2022 Through 02-09-2022",

year = "2022",

doi = "10.1007/978-3-031-15255-9_1",

language = "English",

isbn = "9783031152542",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "3--23",

editor = "Chen-Mou Cheng and Mitsuaki Akiyama",

booktitle = "Advances in Information and Computer Security - 17th International Workshop on Security, IWSEC 2022, Proceedings",

}

Becker, H, Hwang, V, Kannwischer, MJ, Panny, L & Yang, BY 2022, Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms. in C-M Cheng & M Akiyama (eds), Advances in Information and Computer Security - 17th International Workshop on Security, IWSEC 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13504 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 3-23, 17th International Workshop on Security, IWSEC 2022, Tokyo, Japan, 31/08/22. https://doi.org/10.1007/978-3-031-15255-9_1

Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms. / Becker, Hanno; Hwang, Vincent; Kannwischer, Matthias J. et al.
Advances in Information and Computer Security - 17th International Workshop on Security, IWSEC 2022, Proceedings. ed. / Chen-Mou Cheng; Mitsuaki Akiyama. Springer Science and Business Media Deutschland GmbH, 2022. p. 3-23 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13504 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms

AU - Becker, Hanno

AU - Hwang, Vincent

AU - Kannwischer, Matthias J.

AU - Panny, Lorenz

AU - Yang, Bo Yin

PY - 2022

Y1 - 2022

N2 - 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.

AB - 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.

KW - Arm processors

KW - FFT-based multiplication

KW - NTT

KW - RSA

UR - http://www.scopus.com/inward/record.url?scp=85136934437&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-15255-9_1

DO - 10.1007/978-3-031-15255-9_1

M3 - Conference contribution

AN - SCOPUS:85136934437

SN - 9783031152542

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 3

EP - 23

BT - Advances in Information and Computer Security - 17th International Workshop on Security, IWSEC 2022, Proceedings

A2 - Cheng, Chen-Mou

A2 - Akiyama, Mitsuaki

PB - Springer Science and Business Media Deutschland GmbH

T2 - 17th International Workshop on Security, IWSEC 2022

Y2 - 31 August 2022 through 2 September 2022

ER -

Becker H, Hwang V, Kannwischer MJ, Panny L, Yang BY. Efficient Multiplication of Somewhat Small Integers Using Number-Theoretic Transforms. In Cheng CM, Akiyama M, editors, Advances in Information and Computer Security - 17th International Workshop on Security, IWSEC 2022, Proceedings. Springer Science and Business Media Deutschland GmbH. 2022. p. 3-23. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-15255-9_1