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

This paper, presented by a multi-institutional team of researchers, explores how to squeeze maximum performance out of NTRU Prime, a leading candidate in the race for Post-Quantum Cryptography (PQC) standards, specifically on the ubiquitous ARM Cortex-M4 microcontroller.

TL;DR

Researchers successfully applied Number Theoretic Transform (NTT) techniques to NTRU Prime—a cryptographic scheme specifically designed not to be NTT-friendly. By utilizing "Good’s trick" and mixed-radix NTTs, they achieved up to a 32% speedup in polynomial multiplication and a 39% reduction in memory usage compared to the previous state-of-the-art.

What Problem Does This Paper Address?

As quantum computers loom on the horizon, current encryption (like RSA and ECC) faces obsolescence. The cryptographic community is transitioning to Post-Quantum Cryptography, with lattice-based schemes like NTRU Prime being top contenders.

However, NTRU Prime presents a unique engineering challenge. Most lattice-based schemes use "NTT-friendly" math (like power-of-two cyclotomic rings) to make polynomial multiplication—the most computationally expensive part—extremely fast. NTRU Prime intentionally uses a "messier" ring ($x^p - x - 1$) to avoid potential structural vulnerabilities. The trade-off is that it usually relies on slower multiplication algorithms like Toom-Cook. The authors set out to prove that even this "messy" math can be accelerated using NTT-based methods on resource-constrained embedded hardware.

Methods

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

  1. Good’s Trick (The Speed Demon): This technique maps a large, one-dimensional NTT into a multi-dimensional NTT of smaller, coprime sizes. The authors used this to perform multiplication in a larger, NTT-friendly ring and then reduced the result back to the NTRU Prime ring. This approach is fast and flexible but requires 32-bit multipliers.
  2. Mixed-Radix NTT (The Memory Miser): This approach uses Rader’s Trick to handle NTTs where the size is a prime number. It allows for smaller multipliers and uses significantly less memory, making it ideal for the most constrained microcontrollers or FPGAs.

Hardware-Specific Optimizations: To make these work on the ARM Cortex-M4, the authors employed several "hacks":

  • Floating-Point Register Abuse: They used the 32 single-precision floating-point registers as extra storage to alleviate "register pressure," effectively avoiding slow memory access without actually performing floating-point math.
  • Custom Assembly: They wrote hand-optimized assembly for Barrett and Montgomery reductions to ensure constant-time execution (protecting against timing attacks).

Datasets

The algorithms were evaluated using the standard parameter sets submitted to the NIST PQC standardization process:

  • Streamlined NTRU Prime: sntrup653, sntrup761, sntrup857.
  • NTRU LPRime: ntrulpr653, ntrulpr761, ntrulpr857. The primary benchmark for comparison was the pqm4 library, the community standard for PQC on Cortex-M4.

Key Insights and Ideas

  • The "Unfriendly" is Friendly Enough: The biggest takeaway is that the performance gap between "NTT-friendly" and "NTT-unfriendly" rings is narrower than previously thought. With enough mathematical cleverness, NTTs can outperform Toom-Cook even in rings designed to avoid them.
  • Register Management is King: On embedded chips with only 14 general-purpose registers, the bottleneck is often moving data, not the math itself. Using the FPU registers as a "fast cache" was a critical design choice.
  • Flexibility vs. Efficiency: Good’s trick is easier to adapt to different parameter sets (engineering efficiency), while Mixed-Radix NTT is more efficient in terms of hardware resources (silicon efficiency).

Key Results

Comparing their work against the previous best (Toom-Cook based) implementation on the Cortex-M4:

  • Multiplication Speed: Polynomial multiplication was 17% to 32% faster.
  • Total Operation Speed: For the ntrulpr761 parameter set, total KEM operations (Keygen + Encapsulation + Decapsulation) were 9% to 16% faster.
  • Memory Usage: Their implementations required 15% to 39% less stack memory, a massive win for embedded systems where RAM is scarce.

Limitations and Future Work

  • Multipliers: The Good’s trick implementation relies on 32-bit constant-time multipliers. Some smaller chips (like the Cortex-M3) lack these, meaning the mixed-radix approach would be the only viable NTT option there.
  • Parameter Specificity: The mixed-radix NTT is highly tailored to specific prime factors. If the NIST parameters change, significant re-engineering of the assembly code would be required.
  • Hybrid Approaches: The authors suggest that future work could combine Good’s trick and mixed-radix NTTs to find an even better "sweet spot" between speed and memory.

Summary updated

Abstract

This paper proposes two different methods to perform NTT-based polynomial multiplication in polynomial rings that do not naturally support such a multiplication. We demonstrate these methods on the NTRU Prime key-encapsulation mechanism (KEM) proposed by Bernstein, Chuengsatiansup, Lange, and Vredendaal, which uses a polynomial ring that is, by design, not amenable to use with NTT. One of our approaches is using Good’s trick and focuses on speed and supporting more than one parameter set with a single implementation. The other approach is using a mixed radix NTT and focuses on the use of smaller multipliers and less memory. On a ARM Cortex-M4 microcontroller, we show that our three NTT-based implementations, one based on Good’s trick and two mixed radix NTTs, provide between 32% and 17% faster polynomial multiplication. For the parameter-set ntrulpr761, this results in between 16% and 9% faster total operations (sum of key generation, encapsulation, and decapsulation) and requires between 15% and 39% less memory than the current state-of-the-art NTRU Prime implementation on this platform, which is using Toom-Cook-based polynomial multiplication.
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},
}

Loading related content...

Figure