Multi-Parameter Support with NTTs for NTRU and NTRU Prime on Cortex-M4
DOI:
https://doi.org/10.46586/tches.v2022.i4.349-371Keywords:
NTT, NTRU, NTRU Prime, Cortex-M4, NISTPQC, Vector-Radix FFT, Good–Thomas FFTAbstract
We propose NTT implementations with each supporting at least one parameter of NTRU and one parameter of NTRU Prime. Our implementations are based on size-1440, size-1536, and size-1728 convolutions without algebraic assumptions on the target polynomial rings. We also propose several improvements for the NTT computation. Firstly, we introduce dedicated radix-(2, 3) butterflies combining Good–Thomas FFT and vector-radix FFT. In general, there are six dedicated radix-(2, 3) butterflies and they together support implicit permutations. Secondly, for odd prime radices, we show that the multiplications for one output can be replaced with additions/subtractions. We demonstrate the idea for radix-3 and show how to extend it to any odd prime. Our improvement also applies to radix-(2, 3) butterflies. Thirdly, we implement an incomplete version of Good–Thomas FFT for addressing potential code size issues. For NTRU, our polynomial multiplications outperform the state-of-the-art by 2.8%−10.3%. For NTRU Prime, our polynomial multiplications are slower than the state-of-the-art. However, the SotA exploits the specific structure of coefficient rings or polynomial moduli, while our NTT-based multiplications exploit neither and apply across different schemes. This reduces the engineering effort, including testing and verification.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2022 Erdem Alkim, Vincent Hwang, Bo-Yin Yang
This work is licensed under a Creative Commons Attribution 4.0 International License.