Cryptology ePrint Archive: Report 2018/1116

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

Joppe W. Bos and Simon Friedberger and Marco Martinoli and 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%.

Category / Keywords: implementation / LWE, Frodo, ARM Cortex-M4, SIMD, PRNG

Date: received 16 Nov 2018

Contact author: marco martinoli at bristol ac uk

Available format(s): PDF | BibTeX Citation

Version: 20181120:031936 (All versions of this report)

Short URL: ia.cr/2018/1116


[ Cryptology ePrint archive ]