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:
- 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.
- 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 thepqm4library, 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
ntrulpr761parameter 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