International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Cortex-M4 optimizations for {R,M} LWE schemes

Authors:
Erdem Alkim , Department of Computer Engineering, Ondokuz Mayıs University, Samsun, Turkey; Fraunhofer SIT, Darmstadt, Germany
Yusuf Alper Bilgin , Aselsan Inc., Ankara, Turkey; Institute of Applied Mathematics, Middle East Technical University, Ankara, Turkey
Murat Cenk , Institute of Applied Mathematics, Middle East Technical University, Ankara, Turkey
François Gérard , Université libre de Bruxelles, Brussels, Belgium
Download:
DOI: 10.13154/tches.v2020.i3.336-357
URL: https://tches.iacr.org/index.php/TCHES/article/view/8593
Search ePrint
Search Google
Presentation: Slides
Abstract: This paper proposes various optimizations for lattice-based key encapsulation mechanisms (KEM) using the Number Theoretic Transform (NTT) on the popular ARM Cortex-M4 microcontroller. Improvements come in the form of a faster code using more efficient modular reductions, optimized small-degree polynomial multiplications, and more aggressive layer merging in the NTT, but also in the form of reduced stack usage. We test our optimizations in software implementations of Kyber and NewHope, both round 2 candidates in the NIST post-quantum project, and also NewHope-Compact, a recently proposed variant of NewHope with smaller parameters. Our software is the first implementation of NewHope-Compact on the Cortex-M4 and shows speed improvements over previous high-speed implementations of Kyber and NewHope. Moreover, it gives a common framework to compare those schemes with the same level of optimization. Our results show that NewHope- Compact is the fastest scheme, followed by Kyber, and finally NewHope, which seems to suffer from its large modulus and error distribution for small dimensions.
Video from TCHES 2020
BibTeX
@article{tches-2020-30394,
  title={Cortex-M4 optimizations for {R,M} LWE schemes},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 3},
  pages={336-357},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8593},
  doi={10.13154/tches.v2020.i3.336-357},
  author={Erdem Alkim and Yusuf Alper Bilgin and Murat Cenk and François Gérard},
  year=2020
}