Implementing Lattice-Based PQC on Resource-Constrained Processors:

This paper studies the implementation of the lattice-based PQC on the 32-bit constrained processors that only have constrained multiplication instructions. A typical example of such constrained processors is the ARM Cortex-M0/M0+, which features a tiny silicon area, low power, and low cost. This paper focuses on implementing polynomial multiplication, the most challenging part in many resource-constrained processors. To achieve an efficient implementation compatible with the target platforms, we first investigate the features of different modular reduction algorithms (e.g., Montgomery reduction, Barrett reduction, and k-reduction) for ARM Cortex-M0/M0+. The investigation suggests a hybrid method combining k-reduction and Montgomery reduction, which is the most efficient with constrained multiplication instructions. Then, we combine two recent techniques, namely Number Theoretic Transform (NTT) multiplication for NTT-unfriendly rings and multi-moduli NTTs, to enable the calculation of NTT for Kyber and Saber in the absence of long multiplication instructions (i.e., the product is larger than \(2^{32}\) ). The above combination finally contributes to the fine-grained ARM Cortex-M0/M0+ implementations that significantly outperform state-of-the-art ones. Notably, we increase the running speed of Saber by a factor of \(\approx \) 2.9 on Cortex-M0 and save up to \(80\%\) memory requirement for Kyber.