Towards Practical Microcontroller Implementation of the Signature Scheme Falcon

Tobias Oder, Julian Speith, Kira Höltgen, Tim Güneysu

The Tenth International Conference on Post-Quantum Cryptography, Chongqing University, Chongqing, May 8-10, 2019, to appear


The majority of submissions to NIST's recent call for Post-Quantum Cryptography are encryption schemes or key encapsulation mechanisms. Signature schemes constitute a much smaller group of submissions with only 21 proposals. In this work, we analyze the practicability of one of the latter category - the signature scheme Falcon with respect to its suitability for embedded microcontroller platforms. Falcon has a security proof in the QROM in combination with smallest public key and signature sizes among all lattice-based signature scheme submissions with decent performance on common x86 computing architectures. One of the specific downsides of the scheme is, however, that according to its specification it is "non-trivial to understand and delicate to implement".This work aims to provide some new insights on the realization of Falcon by presenting an optimized implementation for the ARM Cortex-M4F platform. This includes a revision of its memory layout as this is the limiting factor on such constrained platforms. We managed to reduce the dynamic memory consumption of Falcon by 43% in comparison to the reference implementation. Summarizing, our implementation requires 812 ms for key generation, 573 ms for signing, and only 3.5 ms for verification for the n = 512 parameter set.