Paper 2023/1580
Algorithmic Views of Vectorized Polynomial Multipliers – NTRU Prime
Abstract
In this paper, we explore the cost of vectorization for polynomial multiplication with coefficients in $\mathbb{Z}_q$ for an odd prime $q$. If there is a large power of two dividing $q−1$, we can apply radix-2 Cooley–Tukey fast Fourier transforms to multiply polynomials in $\mathbb{Z}_q[x]$. The radix-2 nature admits efficient vectorization. Conversely, if 2 is the only power of two dividing $q−1$, we can apply Schönhage’s and Nussbaumer’s FFTs to craft radix-2 roots of unity, but these double the number of coefficients. We show how to avoid this doubling while maintaining vectorization friendliness with Good–Thomas, Rader’s, and Bruun’s FFTs. In particular, we exploit the existing Fermat-prime factor of $q − 1$ for Rader’s FFT and the power-of-two factor of $q + 1$ for Bruun’s FFT. We implement these ideas for the NTRU Prime instances ntrulpr761/sntrup761, operating over the coefficient ring $\mathbb{Z}_{4591}$ on a Cortex-A72. sntrup761 is currently used in OpenSSH 9.0 by default. Our polynomial multiplication outperforms the state-of-the-art vector-optimized implementation by 6.1×. For ntrulpr761, our keygen, encap, and decap are 2.98×, 2.79×, and 3.07× faster than the state-of-the-art vector-optimized implementation. For sntrup761, we outperform the reference implementation significantly.
Note: Abstract formatting.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Published elsewhere. ACNS 2024
- Keywords
- Good–Thomas FFTRader’s FFTBruun’s FFTNTRU PrimeVectorization
- Contact author(s)
-
vincentvbh7 @ gmail com
gting906 @ gmail com
by @ crypto tw - History
- 2023-10-13: revised
- 2023-10-12: received
- See all versions
- Short URL
- https://ia.cr/2023/1580
- License
-
CC0
BibTeX
@misc{cryptoeprint:2023/1580, author = {Vincent Hwang and Chi-Ting Liu and Bo-Yin Yang}, title = {Algorithmic Views of Vectorized Polynomial Multipliers – {NTRU} Prime}, howpublished = {Cryptology {ePrint} Archive, Paper 2023/1580}, year = {2023}, url = {https://eprint.iacr.org/2023/1580} }