Cryptology ePrint Archive: Report 2021/995

Multi-moduli NTTs for Saber on Cortex-M3 and Cortex-M4

Amin Abdulrahman and Jiun-Peng Chen and Yu-Jia Chen and Vincent Hwang and Matthias J. Kannwischer and Bo-Yin Yang

Abstract: 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.

Category / Keywords: public-key cryptography / NTT, Saber, Cortex-M4, Cortex-M3, NISTPQC

Original Publication (with major differences): IACR-CHES-2022

Date: received 25 Jul 2021, last revised 8 Dec 2021

Contact author: amin abdulrahman at rub de, jpchen at citi sinica edu tw, yujia at email ikv-tech com tw, vincentvbh7 at gmail com, matthias at kannwischer eu, by at crypto tw

Available format(s): PDF | BibTeX Citation

Note: Appendices are added.

Version: 20211208:221852 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]