Paper 2022/930

Multi-Parameter Support with NTTs for NTRU and NTRU Prime on Cortex-M4

Erdem Alkim, Dokuz Eylul University
Vincent Hwang, National Taiwan University, Academia Sinica
Bo-Yin Yang, Academia Sinica
Abstract

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.

Note: Corrections.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
A minor revision of an IACR publication in TCHES 2022
Keywords
NTT NTRU NTRU Prime Cortex-M4 NISTPQC Vector-Radix FFT Good–Thomas FFT
Contact author(s)
erdemalkim @ gmail com
vincentvbh7 @ gmail com
by @ crypto tw
History
2022-09-30: revised
2022-07-17: received
See all versions
Short URL
https://ia.cr/2022/930
License
No rights reserved
CC0

BibTeX

@misc{cryptoeprint:2022/930,
      author = {Erdem Alkim and Vincent Hwang and Bo-Yin Yang},
      title = {Multi-Parameter Support with {NTTs} for {NTRU} and {NTRU} Prime on Cortex-M4},
      howpublished = {Cryptology {ePrint} Archive, Paper 2022/930},
      year = {2022},
      url = {https://eprint.iacr.org/2022/930}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.