Efficient Implementation of CNTR/CTRU Key Encapsulation Mechanism Based on Cortex-M4

The rapid advancement of quantum computing technology poses an imminent and formidable threat to the foundations of our existing public key cryptography systems. As researchers grapple with the urgent need to safeguard our digital infrastructure against the imminent threat of quantum attacks, the concept of Post-Quantum Cryptography(PQC) has emerged as a dynamic and thriving field of study. By exploring innovative cryptographic techniques and mathematical constructs, researchers in the field of PQC strive to ensure the long-term security and resilience of our digital communication systems in the face of the impending quantum revolution. At present, the security issues of the Internet of Things (IoT) have attracted much attention. ARM Cortex-M4, as a low-power embedded processor, is widely used in IoT devices, thus deploying post-quantum cryptography algorithms on it will provide more reliable guarantees for the security of IoT devices. CNTR and CTRU are NTRU lattice-based Key Encapsulation Mechanisms (KEM) proposed by Chinese scholars. These schemes offer comprehensive advantages in terms of security and performance compared to lattice-based KEMs based on the Learning With Errors (LWE) technical route. They have received funding from the Cryptography Standardization Technical Committee (CSTC) in China. The primary focus of this research paper is to efficaciously and succinctly implement the CNTR and CTRU schemes on the ARM Cortex-M4 platform. Leveraging the power of Single Instruction Multiple Data (SIMD) instructions, strategically adjusting the operation structure, and optimizing the instruction arrangement, we have succeeded in significantly augmenting the speed and optimizing the stack usage of these algorithms. The main contributions of this paper include: Firstly, this paper introduces the implementation of the time-consuming module polynomial Central Binomial Distribution (CBD) sampling on ARM Cortex-M4 for the first time. This implementation accelerates the sampling process by an impressive 32. 49%. Additionally, mixed-radix Number Theoretic Transform (NTT) is employed to expedite NTT-unfriendly polynomial multiplication. By fully utilizing the Floating-Point Unit (FPU) registers and employing layer merging in NTT to minimize time-consuming operations like load and store, the speed of NTT and inverse NTT experiences substantial improvements of 84. 24% and 81. 15% respectively. Moreover, this research employs coefficient range analysis during the NTT process to delay reduction, thereby reducing the number of reductions required. Furthermore, it utilizes improved Barrett reduction and Montgomery reduction techniques to minimize the number of assembly instructions involved. Polynomial inversion is achieved through loop unrolling, optimizing the time-consuming process and resulting in a speed optimization rate of 68. 85%. To accelerate the decryption process, which involves NTT-unfriendly prime modulus polynomial ring multiplication, a combination of multi-moduli NTT and the Chinese Remainder Theorem (CRT) is employed, providing a remarkable speed improvement of 96.26%. Additionally, space multiplexing is utilized to optimize stack usage, resulting in stack usage reductions of 29. 86% and 28. 17% for CNTR and CTRU respectively. Experimental results demonstrate that the proposed optimization techniques significantly enhance algorithm efficiency. Compared to the C reference implementation, CNTR and CTRU exhibit overall speed optimization rates of 85. 54% and 85. 56% respectively. Furthermore, in a comparative analysis with the state-of-the-art implementation of other lattice-based key encapsulation mechanisms on the ARM Cortex-M4 platform, the optimized implementation presented in this paper clearly demonstrates comprehensive advantages across multiple dimensions, including speed, efficient utilization of space, and robust security measures. © 2024 Science Press. All rights reserved.