Paper 2026/1410

A Memory-Efficient and Assembly-Optimized Implementation of NTRU+

Abstract

This paper presents a memory-efficient and high-speed implementation of NTRU+, one of the key encapsulation mechanisms (KEMs) selected by Korea’s post-quantum cryptography project (KpqC), on the ARM Cortex-M4. NTRU+ is small enough to run on its own on a Cortex-M4 class microcontroller, yet in real embedded environments, the peak stack occupied by polynomial buffers and the running time dominated by the NTT become key constraints. To address this, in the proposed technique, we reduce memory by analyzing when each polynomial buffer is actually live and restructuring the algorithm so that only a single buffer is resident during computation, and we significantly improve speed by rewriting the NTT for the mixed-radix structure of NTRU+ in Cortex-M4 assembly. By doing so, the assembly NTT acceleration compensates for the recomputation overhead introduced by the memory optimization, so that the combined implementation is both smaller and faster than the reference. Experimental results show that, relative to the KpqClean_ver2[1] reference implementation, the proposed technique reduces the peak stack by 83–84% while improving the speed of all three operations by up to 1.8×.