Cortex-M4 Optimizations for \{R,M\}LWE Schemes

Erdem Alkim; Yusuf Alper Bilgin; Murat Cenk; François Gérard

Paper 2020/012

Cortex-M4 Optimizations for \{R,M\}LWE Schemes

Erdem Alkim, Yusuf Alper Bilgin, Murat Cenk, and François Gérard

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, small polynomial multiplications and more aggressive layer merging in the NTT but also reduced stack usage. We test those 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 derivative of NewHope with smaller parameters. Our software is the first implementation of NewHope-Compact on Cortex-M4 and shows speed improvements over previous high-speed implementations on the same platform for Kyber and NewHope . Moreover, it gives a common framework to compare those algorithms with the same level of optimization. Our results show that NewHope-Compact is the faster algorithm, followed by Kyber and finally NewHope that seems to suffer from its large modulus and error distribution for small dimensions.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in TCHES 2020
DOI: 10.13154/tches.v2020.i3.336-357
Contact author(s): fragerar @ ulb ac be
erdemalkim @ gmail com
y alperbilgin @ gmail com
mcenk @ metu edu tr
History: 2020-12-23: revised; 2020-01-06: received; See all versions
Short URL: https://ia.cr/2020/012
License: CC BY

BibTeX

@misc{cryptoeprint:2020/012,
      author = {Erdem Alkim and Yusuf Alper Bilgin and Murat Cenk and François Gérard},
      title = {Cortex-M4 Optimizations for \{R,M\}{LWE} Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/012},
      year = {2020},
      doi = {10.13154/tches.v2020.i3.336-357},
      url = {https://eprint.iacr.org/2020/012}
}