Paper 2018/1116

Fly, you fool! Faster Frodo for the ARM Cortex-M4

Joppe W. Bos, Simon Friedberger, Marco Martinoli, Elisabeth Oswald, and Martijn Stam

Abstract

We present an efficient implementation of FrodoKEM-640 on an ARM Cortex-M4 core. We leverage the single instruction, multiple data paradigm, available in the instruction set of the ARM Cortex-M4, together with a careful analysis of the memory layout of matrices to considerably speed up matrix multiplications. Our implementations take up to 79.4% less cycles than the reference. Moreover, we challenge the usage of a cryptographically secure pseudorandom number generator for the generation of the large public matrix involved. We argue that statistically good pseudorandomness is enough to achieve the same security goal. Therefore, we propose to use xoshiro128** as a PRNG instead: its structure can be easily integrated in FrodoKEM-640, it passes all known statistical tests and greatly outperforms previous choices. By using xoshiro128** we improve the generation of the large public matrix, which is a considerable bottleneck for embedded devices, by up to 96%.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. Minor revision.
Keywords
LWEFrodoARM Cortex-M4SIMDPRNG
Contact author(s)
marco martinoli @ bristol ac uk
History
2018-11-20: received
Short URL
https://ia.cr/2018/1116
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1116,
      author = {Joppe W.  Bos and Simon Friedberger and Marco Martinoli and Elisabeth Oswald and Martijn Stam},
      title = {Fly, you fool! Faster Frodo for the ARM Cortex-M4},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1116},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1116}},
      url = {https://eprint.iacr.org/2018/1116}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.