Polynomial Multiplication in NTRU Prime: Comparison of Optimization Strategies on Cortex-M4

Erdem Alkim, Dean Yun-Li Cheng, Chi-Ming Marvin Chung, Hülya Evkan, Leo Wei-Lun Huang, Vincent Hwang, Ching-Lin Trista Li, Ruben Niederhagen, Cheng-Jhih Shih, Julian Wälde, Bo-Yin Yang

Abstract

NTRU Prime is a leading candidate for Post-Quantum Cryptography (PQC) standards, designed with a "non-NTT-friendly" ring to enhance security. This paper explores optimization strategies for polynomial multiplication in NTRU Prime on the ARM Cortex-M4 microcontroller. By implementing Number Theoretic Transform (NTT) techniques such as "Good’s trick" and mixed-radix NTTs, the researchers achieved significant performance gains, including up to a 32% speedup in polynomial multiplication and a 39% reduction in stack memory usage compared to previous state-of-the-art implementations.

Introduction

As quantum computing advances, traditional cryptographic systems like RSA and ECC are becoming vulnerable. Lattice-based cryptography, particularly NTRU Prime, offers a robust alternative. However, NTRU Prime's unique ring structure ($x^p - x - 1$) is intentionally designed to avoid the structural properties that typically make polynomial multiplication fast via the Number Theoretic Transform (NTT). This study demonstrates that with advanced mathematical techniques and hardware-specific optimizations, NTT-based methods can still provide superior performance on resource-constrained embedded devices like the ARM Cortex-M4.

The Challenge of "NTT-Unfriendly" Rings

Most lattice-based schemes utilize power-of-two cyclotomic rings, which are highly compatible with standard NTT algorithms. NTRU Prime avoids these to mitigate potential vulnerabilities, traditionally necessitating slower multiplication algorithms like Toom-Cook. The core challenge addressed here is whether these "messy" rings can be accelerated using NTT variants without compromising the security or efficiency of the implementation on microcontrollers.

Methodology: NTT-Based Strategies

The researchers implemented two primary NTT-based strategies to overcome the limitations of the NTRU Prime ring:

  1. Good’s Trick: This method maps a large, one-dimensional NTT into a multi-dimensional NTT of smaller, coprime sizes. This allows for multiplication in a larger, NTT-friendly ring before reducing the result back to the target NTRU Prime ring.
  2. Mixed-Radix NTT: Utilizing Rader’s Trick, this approach handles NTTs where the size is a prime number. It is particularly effective for memory-constrained environments as it allows for smaller multipliers.
Butterfly diagram illustrating the data flow in a mixed-radix NTT structure.

To optimize these for the Cortex-M4, the team employed "floating-point register abuse," using the 32 single-precision FPU registers as a high-speed cache to reduce register pressure and memory access. Additionally, hand-optimized assembly for Barrett and Montgomery reductions ensured constant-time execution, protecting against timing-based side-channel attacks.

Parameter Sets and Evaluation

The implementation was evaluated against the standard parameter sets submitted to the NIST PQC standardization process, specifically the Streamlined NTRU Prime (sntrup) and NTRU LPRime (ntrulpr) variants.

Parameter sets for the ntrulpr scheme, including security levels and ring constants.

Benchmarks were conducted using the pqm4 library, the industry standard for evaluating PQC on the Cortex-M4 platform.

Key Results

The NTT-based implementations showed marked improvements over the previous best Toom-Cook-based versions:

  • Multiplication Performance: Speed increased by 17% to 32%.
  • KEM Operations: For the ntrulpr761 set, total Keygen, Encapsulation, and Decapsulation operations were 9% to 16% faster.
  • Memory Efficiency: Stack memory usage was reduced by 15% to 39%, a critical improvement for embedded systems with limited RAM.

Conclusion

This research proves that the performance gap between "NTT-friendly" and "NTT-unfriendly" rings is smaller than previously assumed. By leveraging mathematical cleverness and hardware-specific register management, NTRU Prime can be highly efficient on embedded hardware. Future work may explore hybrid approaches combining Good’s trick and mixed-radix NTTs to further optimize the balance between execution speed and silicon area.

Summary updated

BibTeX
@article{alkim2021polynomial,
  author = {Erdem Alkim and Dean Yun-Li Cheng and Chi-Ming Marvin Chung and Hülya Evkan and Leo Wei-Lun Huang and Vincent Hwang and Ching-Lin Trista Li and Ruben Niederhagen and Cheng-Jhih Shih and Julian Wälde and Bo-Yin Yang},
  title = {{Polynomial Multiplication in NTRU Prime: Comparison of Optimization Strategies on Cortex-M4}},
  journal = {IACR Trans. Cryptogr. Hardw. Embed. Syst.},
  year = {2021},
  url = {https://openreview.net/forum?id=vaaA20kXG6},
}
Figure