Multi-moduli NTTs for Saber on Cortex-M3 and Cortex-M4
The U.S. National Institute of Standards and Technology (NIST) has designated ARM microcontrollers as an important benchmarking platform for its Post-Quantum Cryptography standardization process (NISTPQC). In view of this, we explore the design space of the NISTPQC finalist Saber on the Cortex-M4 a...
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | article |
| Lenguaje: | EN |
| Publicado: |
Ruhr-Universität Bochum
2021
|
| Materias: | |
| Acceso en línea: | https://doaj.org/article/f694151dc838418b80fb71eaddb83137 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| id |
oai:doaj.org-article:f694151dc838418b80fb71eaddb83137 |
|---|---|
| record_format |
dspace |
| spelling |
oai:doaj.org-article:f694151dc838418b80fb71eaddb831372021-11-19T14:36:13ZMulti-moduli NTTs for Saber on Cortex-M3 and Cortex-M410.46586/tches.v2022.i1.127-1512569-2925https://doaj.org/article/f694151dc838418b80fb71eaddb831372021-11-01T00:00:00Zhttps://tches.iacr.org/index.php/TCHES/article/view/9292https://doaj.org/toc/2569-2925 The U.S. National Institute of Standards and Technology (NIST) has designated ARM microcontrollers as an important benchmarking platform for its Post-Quantum Cryptography standardization process (NISTPQC). In view of this, we explore the design space of the NISTPQC finalist Saber on the Cortex-M4 and its close relation, the Cortex-M3. In the process, we investigate various optimization strategies and memory-time tradeoffs for number-theoretic transforms (NTTs). Recent work by [Chung et al., TCHES 2021 (2)] has shown that NTT multiplication is superior compared to Toom–Cook multiplication for unprotected Saber implementations on the Cortex-M4 in terms of speed. However, it remains unclear if NTT multiplication can outperform Toom–Cook in masked implementations of Saber. Additionally, it is an open question if Saber with NTTs can outperform Toom–Cook in terms of stack usage. We answer both questions in the affirmative. Additionally, we present a Cortex-M3 implementation of Saber using NTTs outperforming an existing Toom–Cook implementation. Our stack-optimized unprotected M4 implementation uses around the same amount of stack as the most stack-optimized Toom–Cook implementation while being 33%-41% faster. Our speed-optimized masked M4 implementation is 16% faster than the fastest masked implementation using Toom–Cook. For the Cortex-M3, we outperform existing implementations by 29%-35% in speed. We conclude that for both stack- and speed-optimization purposes, one should base polynomial multiplications in Saber on the NTT rather than Toom–Cook for the Cortex-M4 and Cortex-M3. In particular, in many cases, multi-moduli NTTs perform best. Amin AbdulrahmanJiun-Peng ChenYu-Jia ChenVincent HwangMatthias J. KannwischerBo-Yin YangRuhr-Universität BochumarticleNTTSaberCortex-M4Cortex-M3NISTPQCComputer engineering. Computer hardwareTK7885-7895Information technologyT58.5-58.64ENTransactions on Cryptographic Hardware and Embedded Systems, Vol 2022, Iss 1 (2021) |
| institution |
DOAJ |
| collection |
DOAJ |
| language |
EN |
| topic |
NTT Saber Cortex-M4 Cortex-M3 NISTPQC Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64 |
| spellingShingle |
NTT Saber Cortex-M4 Cortex-M3 NISTPQC Computer engineering. Computer hardware TK7885-7895 Information technology T58.5-58.64 Amin Abdulrahman Jiun-Peng Chen Yu-Jia Chen Vincent Hwang Matthias J. Kannwischer Bo-Yin Yang Multi-moduli NTTs for Saber on Cortex-M3 and Cortex-M4 |
| description |
The U.S. National Institute of Standards and Technology (NIST) has designated ARM microcontrollers as an important benchmarking platform for its Post-Quantum Cryptography standardization process (NISTPQC). In view of this, we explore the design space of the NISTPQC finalist Saber on the Cortex-M4 and its close relation, the Cortex-M3. In the process, we investigate various optimization strategies and memory-time tradeoffs for number-theoretic transforms (NTTs).
Recent work by [Chung et al., TCHES 2021 (2)] has shown that NTT multiplication is superior compared to Toom–Cook multiplication for unprotected Saber implementations on the Cortex-M4 in terms of speed. However, it remains unclear if NTT multiplication can outperform Toom–Cook in masked implementations of Saber. Additionally, it is an open question if Saber with NTTs can outperform Toom–Cook in terms of stack usage. We answer both questions in the affirmative. Additionally, we present a Cortex-M3 implementation of Saber using NTTs outperforming an existing Toom–Cook implementation. Our stack-optimized unprotected M4 implementation uses around the same amount of stack as the most stack-optimized Toom–Cook implementation while being 33%-41% faster. Our speed-optimized masked M4 implementation is 16% faster than the fastest masked implementation using Toom–Cook. For the Cortex-M3, we outperform existing implementations by 29%-35% in speed. We conclude that for both stack- and speed-optimization purposes, one should base polynomial multiplications in Saber on the NTT rather than Toom–Cook for the Cortex-M4 and Cortex-M3. In particular, in many cases, multi-moduli NTTs perform best.
|
| format |
article |
| author |
Amin Abdulrahman Jiun-Peng Chen Yu-Jia Chen Vincent Hwang Matthias J. Kannwischer Bo-Yin Yang |
| author_facet |
Amin Abdulrahman Jiun-Peng Chen Yu-Jia Chen Vincent Hwang Matthias J. Kannwischer Bo-Yin Yang |
| author_sort |
Amin Abdulrahman |
| title |
Multi-moduli NTTs for Saber on Cortex-M3 and Cortex-M4 |
| title_short |
Multi-moduli NTTs for Saber on Cortex-M3 and Cortex-M4 |
| title_full |
Multi-moduli NTTs for Saber on Cortex-M3 and Cortex-M4 |
| title_fullStr |
Multi-moduli NTTs for Saber on Cortex-M3 and Cortex-M4 |
| title_full_unstemmed |
Multi-moduli NTTs for Saber on Cortex-M3 and Cortex-M4 |
| title_sort |
multi-moduli ntts for saber on cortex-m3 and cortex-m4 |
| publisher |
Ruhr-Universität Bochum |
| publishDate |
2021 |
| url |
https://doaj.org/article/f694151dc838418b80fb71eaddb83137 |
| work_keys_str_mv |
AT aminabdulrahman multimodulinttsforsaberoncortexm3andcortexm4 AT jiunpengchen multimodulinttsforsaberoncortexm3andcortexm4 AT yujiachen multimodulinttsforsaberoncortexm3andcortexm4 AT vincenthwang multimodulinttsforsaberoncortexm3andcortexm4 AT matthiasjkannwischer multimodulinttsforsaberoncortexm3andcortexm4 AT boyinyang multimodulinttsforsaberoncortexm3andcortexm4 |
| _version_ |
1718420108401967104 |