Compact Dilithium Implementations on Cortex-M3 and Cortex-M4

Denisa O. C. Greconici; Matthias J. Kannwischer; Amber Sprenkels

Paper 2020/1278

Compact Dilithium Implementations on Cortex-M3 and Cortex-M4

Denisa O. C. Greconici, Radboud University Nijmegen

Matthias J. Kannwischer

, Max Planck Institute for Security and Privacy

Amber Sprenkels

, Radboud University Nijmegen

Abstract

We present implementations of the lattice-based digital signature scheme Dilithium for ARM Cortex-M3 and ARM Cortex-M4. Dilithium is one of the three signature finalists of the NIST post-quantum cryptography competition. As our Cortex-M4 target, we use the popular STM32F407-DISCOVERY development board. Compared to the previous speed records on the Cortex-M4 by Ravi, Gupta, Chattopadhyay, and Bhasin we speed up the key operations and by 20% which together with other optimizations results in speedups of 7%, 15%, and 9% for Dilithium3 key generation, signing, and verification respectively. We also present the first constant-time Dilithium implementation on the Cortex-M3 and use the Arduino Due for benchmarks. For Dilithium3, we achieve on average 2 562 kilocycles for key generation, 10 667 kilocycles for signing, and 2 321 kilocycles for verification. Additionally, we present stack consumption optimizations applying to both our CortexM3 and Cortex-M4 implementation. Due to the iterative nature of the Dilithium signing algorithm, there is no optimal way to achieve the best speed and lowest stack consumption at the same time. We present three different strategies for the signing procedure which allow trading more stack and flash memory for faster speed or vice-versa. Our implementation of Dilithium3 with the smallest memory footprint uses less than 12kB. As an additional output of this work, we present the first Cortex-M3 implementations of the key-encapsulation schemes NewHope and Kyber.

Note: Updated Cortex-M4 'KeyGen (1)' results, which were listed incorrectly in the original version

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Published by the IACR in TCHES 2021
DOI: 10.46586/tches.v2021.i1.1-24
Keywords: Dilithium ARM Cortex-M4 ARM Cortex-M3 number theoric transform lattice-based cryptography
Contact author(s): denisa greconici @ gmail com
matthias @ kannwischer eu
amber @ electricdusk com
History: 2022-10-26: last of 2 revisions; 2020-10-14: received; See all versions
Short URL: https://ia.cr/2020/1278
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1278,
      author = {Denisa O. C. Greconici and Matthias J. Kannwischer and Amber Sprenkels},
      title = {Compact Dilithium Implementations on Cortex-M3 and Cortex-M4},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1278},
      year = {2020},
      doi = {10.46586/tches.v2021.i1.1-24},
      url = {https://eprint.iacr.org/2020/1278}
}