Paper 2023/1580

Algorithmic Views of Vectorized Polynomial Multipliers – NTRU Prime

Vincent Hwang, Max Planck Institute for Security and Privacy, Academia Sinica
Chi-Ting Liu, National Taiwan University
Bo-Yin Yang, Academia Sinica

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.

Available format(s)
Publication info
Published elsewhere. ACNS 2024
Good–Thomas FFTRader’s FFTBruun’s FFTNTRU PrimeVectorization
Contact author(s)
vincentvbh7 @ gmail com
gting906 @ gmail com
by @ crypto tw
2023-10-13: revised
2023-10-12: received
See all versions
Short URL
No rights reserved


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.