Memory-efficient high-speed implementation of Kyber on Cortex-M4. (English) Zbl 1454.94051

Buchmann, Johannes (ed.) et al., Progress in cryptology – AFRICACRYPT 2019. 11th international conference on cryptology in Africa, Rabat, Morocco, July 9–11, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11627, 209-228 (2019).
Summary: This paper presents an optimized software implementation of the module-lattice-based key-encapsulation mechanism Kyber for the ARM Cortex-M4 microcontroller. Kyber is one of the round-2 candidates in the NIST post-quantum project. In the center of our work are novel optimization techniques for the number-theoretic transform (NTT) inside Kyber, which make very efficient use of the computational power offered by the “vector” DSP instructions of the target architecture. We also present results for the recently updated parameter sets of Kyber which equally benefit from our optimizations.
As a result of our efforts we present software that is 18% faster than an earlier implementation of Kyber optimized for the Cortex-M4 by the Kyber submitters. Our NTT is more than twice as fast as the NTT in that software. Our software runs at about the same speed as the latest speed-optimized implementation of the other module-lattice based round-2 NIST PQC candidate Saber. However, for our Kyber software, this performance is achieved with a much smaller RAM footprint. Kyber needs less than half of the RAM of what the considerably slower RAM-optimized version of Saber uses. Our software does not make use of any secret-dependent branches or memory access and thus offers state-of-the-art protection against timing attacks.
For the entire collection see [Zbl 1428.94007].


94A60 Cryptography


XKCP; NTRUEncrypt; Kyber; PQM4
Full Text: DOI